Когда Dictionary <TKey, TValue> вызывает TKey.Equals ()?

Question

Просто переопределение Equals в TKey не помогает.

public override bool Equals(object obj)
{ /* ... */  }

... Equals() никогда не будет называться ...

Answer 1

Когда вы выполняете поиск по словарю, происходит следующее:

1. Словарь использует TKey.GetHashCode для вычисления хэша для корзины.
2. Затем он проверяет все хэши, используя это поле, и вызывает Equals для отдельных объектов, чтобы определить совпадение.

Если сегменты никогда не совпадают (поскольку GetHashCode не был перезаписан), вы никогда не вызовете Equals. Это часть того, почему вы должны всегда реализовывать оба, если вы реализуете оба - и вы должны переопределить обе функции (более осмысленно, чем просто вызов base.GetHashCode ()), если вы хотите использовать свой объект в хешированной коллекции.

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

Вы должны также реализовать Equals таким образом, чтобы правильно проверять наличие одинаковых экземпляров.

Реализация по умолчанию для классов (ссылочных типов) просто сравнивает саму ссылку. Два экземпляра с абсолютно одинаковыми значениями по умолчанию возвращают false на Equals (поскольку они имеют разные ссылки). По умолчанию несколько экземпляров всегда будут возвращать другой хэш-код.

Answer 2

Словарь - это хеш-таблица. Он вызывает Equals (object obj), только если два объекта выдают одинаковые значения хеш-функции. Обеспечьте хорошую хэш-функцию для ваших объектов, чтобы избежать вызова Equals ().

Имейте в виду, что часть хеширования имеет сложность O (1), а часть поиска имеет сложность O (n) в худшем случае и O (n / 2) в среднем. Вам следует избегать объектов, которые генерируют одно и то же хеш-значение, в противном случае поиск этих объектов выполняется линейно

Answer 3

Предполагая, что вы определили пользовательский тип ссылки как ключ, вы должны либо:

1. всегда передает один и тот же экземпляр объекта в словарь как ключ, или
2. реализует GetHashCode (), который всегда возвращает одно и то же значение даже для разных экземпляров, а метод Equals () может сравнивать разные экземпляры.

Метод base.GetHashCode () создает хэш на основе идентификатора экземпляра объекта и поэтому не может использоваться при передаче в качестве ключа различных экземпляров типа.

Причина, по которой возвращение 0 для вашего хэша всегда работает, заключается в том, что класс Dictionary сначала использует хеш-код для поиска корзины, к которой принадлежит ваш ключ, и только затем использует метод Equals () для различения экземпляров. Вы не должны возвращать 0 как хеш-код из пользовательского типа, если вы собираетесь использовать его в качестве ключа словаря, потому что это будет эффективно вырождать словарь в список с производительностью поиска O (n) вместо O (1).

Вы также можете рассмотреть возможность реализации IComparable и IEquatable.

Посмотрите на следующий вопрос для получения более подробной информации:

Использование объекта в качестве общего ключа словаря