Оптимальная производительность словаря с пользовательскими Equals() и GetHashCode()

Question

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

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

Answer 1

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

Answer 2

Словари хранят данные в ведрах, но для каждого хэш-кода нет ни одного ведра. Количество ведер основано на емкости. Значения помещаются в ведра, основанные на модуле хэш-кода и количестве ведер.

Допустим, у вас есть GetHashCode() метод, который производит эти хэш-коды для пяти объектов:

925 
10641 
14316 
17213 
28624 

коды хеширования должны быть распределены. Значит, эти взгляды разбросаны, верно? Если у нас есть 7 ведер, то в конечном итоге расчета модуля каждого, который дает нам:

1 
1 
1 
0 
1 

Таким образом, мы в конечном итоге с ведрами:

0 - 1 item 
1 - 4 items 
2 - 0 items 
3 - 0 items 
4 - 0 items 
5 - 0 items 
6 - 0 items 

Упс, не так хорошо распространено в настоящее время.

Это не составленные данные. Это фактические хэш-коды.

Вот пример того, как генерировать хеш-код из содержащихся данных (не формула, используемая для вышеуказанных хеш-кодов, лучшая).

https://stackoverflow.com/a/263416/118703

Answer 3

Вам должны убедиться, что имеет место следующее:

(GetHashCode(a) != GetHashCode(b)) => !Equals(a, b) 

Реверс Подразумевается идентичен по смыслу:

Equals(a, b) => (GetHashCode(a) == GetHashCode(b)) 

Кроме того, генерировать, как несколько столкновений, как возможное. Столкновение определяется как:

(GetHashCode(a) == GetHashCode(b)) && !Equals(a, b) 

Столкновение не влияет на правильность, но производительность. GetHashCode, всегда возвращающий ноль, будет правильным, например, но медленным.