Зачем использовать GetHashCode() вместо Equals()?

Для некоторых типов тест Equals может быть относительно дорогим. Обычно он должен сравнивать каждое поле класса. Другими словами, требуется линейное время в зависимости от размера класса. Большие классы дороже сравнивать на равенство.

Что произойдет, если вам нужно сравнить один объект с 1000 других? Звонок Equals 1000 раз может дорого обойтись. Вам нужно сделать N * 2000 обращений к полю, если N - размер класса

GetHashCode вместо этого генерирует «в основном уникальное» целое число на основе содержимого класса. Другими словами, доступ к полям класса осуществляется один раз. И как только вы это сделаете, вы сможете сравнить это целое число с 1000 целыми числами, составляющими хеш-коды других объектов.

Даже в таком наивном варианте использования нам теперь нужно только N * 1000 доступов к полям.

Но что, если мы сохраним хэш-код? Когда мы вставляем объект в набор хэшей, его хеш-код вычисляется один раз. Теперь, в любой раз, когда мы хотим выполнить поиск в хэш-наборе, нам просто нужно вычислить один хэш-код (код внешнего объекта), а затем вы просто получите сравнивать простые целые числа. Таким образом, доступ к полю класса N (для нового объекта, чей хэш-код нам нужно вычислить), плюс ряд целочисленных сравнений, которые варьируются в зависимости от алгоритма, но 1) относительно немногочисленны и 2) дешевы.

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

GetHashCode позволяет вам помещать вещи в ведра — несколько объектов могут иметь один и тот же хэш-код. Затем Equals используется для поиска совпадений в корзине. Это позволяет очень быстро находить вещи в больших коллекциях.

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

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

Например, если поместить в один набор все объекты, где GetHashCode возвращает четное число, а в другой набор все объекты, где GetHashCode возвращает нечетное число, то затем дается объект для поиска, вызов GetHashCode позволит мгновенно исключить из рассмотрения всех объектов в одном из наборов. Если бы вместо двух наборов использовалось двадцать, можно было бы исключить все из девятнадцати наборов. Если 256 наборов, можно удалить 255. Во многих случаях, если настроить количество наборов в зависимости от количества имеющихся у него предметов, можно будет исключить все объекты, кроме горстки, без необходимости смотреть на каждый из них. из них.

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