Почему C# не реализует GetHashCode для коллекций?



Я портирую что-то с Java на C#. В Java hashcode a ArrayList зависит от элементов в нем. В C# я всегда получаю один и тот же хэш-код из List...

Почему это?

Для некоторых моих объектов хэш-код должен быть другим, потому что объекты в их свойстве list делают объекты неравными. Я ожидал бы, что хэш-код всегда уникален для состояния объекта и только равен другому хэш-коду, когда объект равен. Или я ошибаюсь?

171   7  

7 ответов:

Для корректной работы хэш-коды должны быть неизменяемыми – хэш-код объекта должен Никогда не изменяться.

Если хэш-код объекта изменится, все словари, содержащие этот объект, перестанут работать.

Поскольку коллекции не являются неизменяемыми, они не могут реализовать GetHashCode.
Вместо этого они наследуют значение по умолчанию GetHashCode, которое возвращает (надеюсь) уникальное значение для каждого экземпляра объекта. (Обычно на основе адреса памяти)

Да, вы ошибаетесь. Как в Java, так и в C# равенство подразумевает наличие одного и того же хэш-кода, но обратное не обязательно верно.

СмотритеGetHashCode для получения дополнительной информации.

Хэш-коды должны зависеть от используемого определения равенства, так что если A == B, то A.GetHashCode() == B.GetHashCode() (но не обязательно обратное; A.GetHashCode() == B.GetHashCode() не влечет за собой A == B).

По умолчанию определение равенства типа значения основано на его значении, а ссылочного типа-на его идентичности (то есть по умолчанию экземпляр ссылочного типа равен только самому себе), следовательно, хэш-код по умолчанию для типа значения таков, что он зависит от значений полей, которые он содержит* и для него самого. ссылочные типы это зависит от идентичности. Действительно, поскольку мы в идеале хотим, чтобы хэш-коды для неравных объектов отличались, особенно в младших битах (скорее всего, это повлияет на значение повторного хэширования), мы обычно хотим, чтобы два эквивалентных, но неравных объекта имели разные хэши.

Поскольку объект останется равным самому себе, также должно быть ясно, что эта реализация по умолчанию GetHashCode() будет продолжать иметь то же значение, даже когда объект мутирует (идентичность не мутирует даже для изменяемого объекта).

Теперь в некоторых случаях ссылочные типы (или типы значений) переопределяют равенство. Примером этого является string, где, например, "ABC" == "AB" + "C". Хотя сравниваются два разных экземпляра строки, они считаются равными. В этом случае GetHashCode() должно быть переопределено таким образом, чтобы значение относилось к состоянию, в котором определяется равенство (в данном случае последовательность содержащихся символов).

В то время как это чаще всего делают с типы, которые также неизменны, по целому ряду причин, GetHashCode() не зависит от неизменности . Скорее, GetHashCode() должен оставаться последовательным перед лицом изменчивости-изменить значение, которое мы используем при определении хэша, и хэш должен соответственно измениться. Заметьте, однако, что это проблема, если мы используем этот изменяемый объект в качестве ключа в структуру, использующую хэш, поскольку изменение объекта изменяет положение, в котором он должен храниться, не перемещая его в это положение (это также верно для любого другого случая, когда положение объекта в коллекции зависит от его значения - например, если мы сортируем список и затем мутируем один из элементов в списке, список больше не сортируется). Однако это не означает, что мы должны использовать только неизменяемые объекты в словарях и хэш-наборах. Скорее это означает, что мы не должны мутировать объект, который находится в такой структуре, и сделать его неизменным-это ясный способ гарантировать это.

Действительно, их довольно много случаи, когда хранение изменяемых объектов в таких структурах желательно, и до тех пор, пока мы не мутируем их в течение этого времени, это нормально. Поскольку у нас нет гарантии неизменности, мы хотим предоставить ее другим способом (например, провести короткое время в коллекции и получить доступ только из одного потока).

Следовательно, неизменность ключевых значений - это один из тех случаев, когда что-то возможно, но в целом идея. Человеку, определяющему алгоритм хэш-кода хотя, это не для них, чтобы предположить, что любой такой случай всегда будет плохой идеей (они даже не знают, что мутация произошла, когда объект был сохранен в такой структуре); это для них, чтобы реализовать хэш-код, определенный на текущем состоянии объекта, независимо от того, является ли вызов его в данной точке хорошим или нет. Поэтому, например, хэш-код не должен быть записан на изменяемый объект, если только память не будет очищена на каждом мутирующем объекте. (Вообще говоря, это пустая трата времени на запоминание хэшей, поскольку структуры, которые попадание же объектов хэшкода многократно будет иметь свою собственную мемуаризацию о нем).

Теперь в рассматриваемом случае 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

Теперь, это на самом деле хорошая вещь. Почему? Ну, а как вы узнаете из вышесказанного, что мы хотим считать а равным в? Мы могли бы, но есть много веских причин не делать этого и в других случаях.

Более того, гораздо проще переопределить равенство из личность-на основе стоимости, отличных от значения-на основе личных данных. Наконец, существует несколько определений равенства на основе значений для многих объектов (классический случай-различные представления о том, что делает строку равной), поэтому нет даже одного и единственного определения, которое работает. Например:

ArrayList c = new ArrayList();
for(short i = 0; i != 10; ++i)
{
  c.Add(i);
}

Если мы рассматривали a == b выше, должны ли мы рассматривать a == c также? Ответ зависит от того, что именно нас интересует в определении равенства, которое мы используем, поэтому структура не может знайте, что правильный ответ для всех случаев, так как все случаи не согласны.

Теперь, если мы действительно заботимся о равенстве на основе ценности в данном случае, у нас есть два очень простых варианта. Первый-это подкласс и над-ездное равенство:
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;
  }
}

Вкратце:

  1. определение равенства по умолчанию для ссылочного типа является зависимым только на идентичности.
  2. Большую часть времени мы этого хотим. Когда человек, определяющий класс, решает, что это не то, что нужно, он может переопределить это поведение.
  3. когда человек, использующий класс, снова хочет получить другое определение равенства, он может использовать IEqualityComparer<T> и IEqualityComparer, так что их словари, хэш-карты, хэш-наборы и т. д. используйте их концепцию равенства.
  4. катастрофично мутировать объект, пока он является ключом к структуре, основанной на хэше. Неизменность может быть использована для обеспечения того, чтобы этого не произошло, но она не обязательна и не всегда желательна.

В целом, фреймворк дает нам хорошие значения по умолчанию и подробные возможности переопределения.

* существует ошибка в случае десятичной дроби внутри структуры, потому что существует короткий путь, используемый в некоторых случаях со стуктами, когда это безопасно, а не в других случаях, но в то время как структура, содержащая десятичную дробь, является одним случаем, когда короткий путь не безопасен, он неправильно идентифицируется как случай там, где безопасно.

Невозможно, чтобы хэш-код был уникальным во всех вариантах большинства нетривиальных классов. В C# понятие равенства списков не то же самое, что в Java (см. здесь), поэтому реализация хэш - кода также не то же самое-она отражает равенство списков C#.

Основные причины-производительность и человеческая природа - Люди склонны думать о хэшах как о чем-то быстром, но обычно это требует прохождения всех элементов объекта по крайней мере один раз.

Пример: Если вы используете строку в качестве ключа в хэш-таблице, каждый запрос имеет сложность O (|s|) - используйте строки в 2 раза длиннее, и это будет стоить вам как минимум вдвое дороже. Представьте, что это было полноценное дерево (просто список списков) - ой : -)

Если полное, глубокое вычисление хэша было стандартным работая над коллекцией, огромный процент программистов просто использовал бы ее невольно, а затем обвинил бы фреймворк и виртуальную машину в медлительности. для такой дорогостоящей вещи, как полный обход, крайне важно, чтобы программист знал о сложности.Единственный способ добиться этого-убедиться, что вы должны написать свой собственный. Это также хороший сдерживающий фактор: -)

Другая причина-обновление тактики . Вычисление и обновление хэша на лету. выполнение полного расчета каждый раз требует вызова решения в зависимости от конкретного случая в руке.

Immutability - это просто академический полицейский выход - люди делают хэши как способ быстрее обнаружить изменения (например, файловые хэши), а также используют хэши для сложных структур, которые все время меняются. Хэш имеет гораздо больше применений, чем 101 основы. ключ опять же в том, что то, что использовать для хэша сложного объекта должно быть вызовом суждения по каждому случаю основа.

Использование адреса объекта (фактически дескриптора, чтобы он не менялся после GC) в качестве хэша-это тот случай, когда значение хэша остается неизменным для произвольного изменяемого объекта: -) причина, по которой C# делает это, заключается в том, что это дешево и снова подталкивает людей вычислять свои собственные.

Ты ошибаешься лишь отчасти. Вы определенно ошибаетесь, когда думаете, что равные хэшкоды означают равные объекты, но равные объекты должны иметь равные хэшкоды, что означает, что если хэшкоды отличаются, то и объекты тоже.

Почему-это слишком философски. Создайте вспомогательный метод (возможно, метод расширения) и вычислите хэш-код, как вам нравится. Может быть хеш-кодами элементов XOR

    Ничего не найдено.

Добавить ответ:
Отменить.