Я переношу что-то с Java на С#. В Java hashcode ArrayList зависит от элементов в нем. В С# я всегда получаю один и тот же хэш-код из List...
Почему это?
Для некоторых моих объектов хэш-код должен быть другим, потому что объекты в свойстве списка делают объекты не равными. Я ожидал бы, что хэш-код всегда уникален для состояния объекта и только равен другому хэш-коду, когда объект равен. Я не прав?
Для правильной работы хэш-коды должны быть неизменными - хеш-код объекта никогда не должен меняться.
Если файл hashcode изменится, любые словари, содержащие объект, перестанут работать.
Так как коллекции не являются неизменяемыми, они не могут реализовать GetHashCode.
Вместо этого они наследуют значение по умолчанию GetHashCode, которое возвращает (надеюсь) уникальное значение для каждого экземпляра объекта. (Как правило, на основе адреса памяти)
Да, вы ошибаетесь. Как в Java, так и в С#, при равном подразумевается наличие одного и того же хеш-кода, но обратное не является (обязательно) истинным.
Подробнее см. GetHashCode.
Хаскоды должны зависеть от определения используемого равенства, так что если A == B, то A.GetHashCode() == B.GetHashCode() (но не обязательно обратное; A.GetHashCode() == B.GetHashCode() не влечет за собой A == B).
По умолчанию определение равенства типа значения основано на его значении, а ссылочного типа - на его идентичности (то есть по умолчанию экземпляр ссылочного типа равен только самому себе), следовательно, default hashcode для типа значения таков, что он зависит от значений полей, которые он содержит *, а для ссылочных типов зависит от личности. Действительно, поскольку мы в идеале хотим, чтобы хэш-коды для неравных объектов были разными, в частности, в младших битах (скорее всего, они влияют на значение повторного хэширования), мы обычно хотим, чтобы два эквивалентных, но не равных объекта имели разные хэши.
Так как объект останется равным самому себе, также должно быть ясно, что эта реализация по умолчанию GetHashCode() будет продолжать иметь такое же значение, даже если объект мутирован (идентификация не мутирует даже для изменяемого объекта).
Теперь в некоторых случаях ссылочные типы (или типы значений) переопределяют равенство. Примером этого является строка, где, например, "ABC" == "AB" + "C". Хотя есть два разных примера сравнения строк, они считаются равными. В этом случае GetHashCode() должен быть переопределен, так что значение относится к состоянию, на котором определено равенство (в этом случае содержится последовательность символов).
Хотя это чаще встречается с типами, которые также неизменяемы, по разным причинам GetHashCode() не зависит от неизменности. Скорее, GetHashCode() должен оставаться постоянным перед лицом изменчивости - измените значение, которое мы используем при определении хеша, и хэш должен измениться соответствующим образом. Обратите внимание, что это проблема, если мы используем этот изменяемый объект как ключ в структуру с использованием хэша, поскольку мутирующий объект меняет положение, в котором он должен быть сохранен, не перемещая его в эту позицию (это также верно для любой другой случай, когда позиция объекта внутри коллекции зависит от его значения - например, если мы сортируем список и затем мутируем один из элементов в списке, список больше не сортируется). Однако это не означает, что мы должны использовать только неизменяемые объекты в словарях и хэш-сетях. Скорее это означает, что мы не должны мутировать объект, который находится в такой структуре, и сделать его неизменным - ясный способ гарантировать это.
Действительно, существует довольно много случаев, когда желательно хранить изменяемые объекты в таких структурах, и пока мы не будем их мутировать в течение этого времени, это нормально. Так как у нас нет гарантийной неизменности, мы тогда хотим предоставить ее другим способом (например, провести короткое время в коллекции и быть доступным только из одного потока).
Следовательно, неизменность ключевых ценностей является одним из тех случаев, когда что-то возможно, но в целом идея. Для человека, определяющего алгоритм hashcode, хотя это не для них предположить, что любой такой случай всегда будет плохой идеей (они даже не знают, что мутация произошла, когда объект хранился в такой структуре); для них для реализации хэш-кода, определенного для текущего состояния объекта, является ли его вызов в данной точке хорошим или нет. Следовательно, например, хэш-код не должен быть замечен на изменчивом объекте, если memoisation не будет очищен для каждого мутанта. (Как правило, это бесполезно для хэшей memoise, так как структуры, которые попадают в одни и те же объекты, hashcode неоднократно будут иметь свои собственные воспоминания об этом).
Теперь, в рассматриваемом случае, ArrayList работает по умолчанию, когда равенство основывается на идентификаторе, например:
ArrayList a = new ArrayList();
ArrayList b = new ArrayList();
for(int i = 0; i != 10; ++i)
{
a.Add(i);
b.Add(i);
}
return a == b;//returns false
Теперь это на самом деле хорошо. Зачем? Ну, как вы знаете выше, что мы хотим считать равным b? Мы могли бы, но есть много веских причин не делать этого и в других случаях.
Что еще, гораздо проще переопределить равенство от основанного на значении к основанию на основе стоимости, чем от основанного на ценности и основанного на идентификации. Наконец, существует множество определений равенства для многих объектов (классический случай - это разные представления о том, что делает строку равным), поэтому не существует даже одно-и единственного определения, которое работает. Например:
ArrayList c = new ArrayList();
for(short i = 0; i != 10; ++i)
{
c.Add(i);
}
Если бы мы рассмотрели A == B выше, рассмотрим ли мы a == c aslo? Ответ зависит только от того, что мы заботимся в определении равенства, которое мы используем, поэтому структура не может знать, какой правильный ответ для всех случаев, поскольку все случаи не согласны.
Теперь, если мы действительно заботимся о равенстве на основе ценности в данном случае, у нас есть два очень простых варианта. Первый заключается в подклассе и превышении равенства:
public class ValueEqualList : ArrayList, IEquatable<ValueEqualList>
{
/*.. most methods left out ..*/
public Equals(ValueEqualList other)//optional but a good idea almost always when we redefine equality
{
if(other == null)
return false;
if(ReferenceEquals(this, other))//identity still entails equality, so this is a good shortcut
return true;
if(Count != other.Count)
return false;
for(int i = 0; i != Count; ++i)
if(this[i] != other[i])
return false;
return true;
}
public override bool Equals(object other)
{
return Equals(other as ValueEqualList);
}
public override int GetHashCode()
{
int res = 0x2D2816FE;
foreach(var item in this)
{
res = res * 31 + (item == null ? 0 : item.GetHashCode());
}
return res;
}
}
Это предполагает, что мы всегда будем рассматривать такие списки таким образом. Мы также можем реализовать IEqualityComparer для данного случая:
public class ArrayListEqComp : IEqualityComparer<ArrayList>
{//we might also implement the non-generic IEqualityComparer, omitted for brevity
public bool Equals(ArrayList x, ArrayList y)
{
if(ReferenceEquals(x, y))
return true;
if(x == null || y == null || x.Count != y.Count)
return false;
for(int i = 0; i != x.Count; ++i)
if(x[i] != y[i])
return false;
return true;
}
public int GetHashCode(ArrayList obj)
{
int res = 0x2D2816FE;
foreach(var item in obj)
{
res = res * 31 + (item == null ? 0 : item.GetHashCode());
}
return res;
}
}
Вкратце:
IEqualityComparer<T> и IEqualityComparer, чтобы их словари, хэшмапы, хэшеты и т.д. использовали свою концепцию равенства.В целом, структура дает нам хорошие настройки по умолчанию и подробные возможности переопределения.
* Существует ошибка в случае десятичного числа в структуре, потому что в некоторых случаях используется короткое сокращение с помощью stucts, когда оно безопасно, а не в другое время, но в то время как структура, содержащая десятичный знак, является одним из случаев, когда короткая вырезка небезопасна, ее неправильно идентифицируют как безопасный случай.
Невозможно, чтобы хэш-код был уникальным для всех вариантов большинства нетривиальных классов. В С# концепция равенства List не такая же, как в Java (см. здесь), поэтому реализация хеш-кода также не является одинаковой - она отражает равенство списка С#.
Вы только отчасти ошибаетесь. Вы определенно ошибаетесь, если считаете, что равные хэш-коды означают равные объекты, но равные объекты должны иметь равные хэш-коды, что означает, что если хэш-коды отличаются, то и объекты.
Основными причинами являются производительность и человеческая природа.. Люди склонны думать о хешах как о чем-то быстро, но обычно требуют пересечения всех элементов объекта хотя бы один раз.
Пример. Если вы используете строку в качестве ключа в хеш-таблице, каждый запрос имеет сложность O (| s |) - используйте 2x более длинные строки, и это будет стоить вам как минимум в два раза больше. Представьте, что это было полномасштабное дерево (только список списков) - oops: -)
Если полный, глубокий хеш-расчет был стандартной операцией в коллекции, огромный процент прогеммеров просто использовал бы это невольно, а затем обвинил бы фреймворк и виртуальную машину в замедлении. Для чего-то столь же дорогостоящего, как и полный обход, крайне важно, чтобы программист должен был знать о сложности. Единственное, что нужно было сделать, это убедиться, что вы должны написать свой собственный. Это хороший сдерживающий фактор: -)
Другая причина - тактика обновления. Вычисление и обновление хэша "на лету" против выполнения полного расчета каждый раз требует решения суда в зависимости от конкретного случая в руке.
Immutabilty - это просто академический полицейский. Люди делают хеши как способ быстрого обнаружения изменения (например, хэши файлов), а также используют хеши для сложных структур, которые постоянно меняются. У Хэша есть еще много вариантов использования 101 основы. Ключ снова состоит в том, что для использования хэша сложного объекта должен быть суждение по каждому случаю.
Использование адреса объекта (на самом деле это дескриптор, поэтому он не изменяется после GC), поскольку хэш на самом деле тот случай, когда значение хэша остается неизменным для любого изменяемого объекта:-) Причина С# заключается в том, что это дешево и снова подталкивает людей к их собственным расчетам.
Почему слишком философски. Создайте вспомогательный метод (может быть методом расширения) и вычислите хэш-код по своему усмотрению. Могут быть хэш-коды XOR-элементов