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

Question

HashSet<T>.Add сначала сравнивает результаты GetHashCode. Если они равны, он вызывает Equals.

Теперь я понимаю, что для реализации GetHashCode, необходимо что-то сделать с полями объекта. Простой пример реализации можно найти по адресу Каков наилучший алгоритм для переопределенного System.Object.GetHashCode? .

В моем тесте, сравнивающем обе на 1.000.000 пар объектов, заполненных случайными данными, производительность более или менее одинакова между ними. GetHashCode реализован, как в связанном примере, Equals просто вызывает Equals во всех полях. Так почему же нужно использовать GetHashCode сверх Equals?

Answer 1

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

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

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

Даже в таком наивном случае использования нам теперь требуется только N * 1000 полевых обращений.

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

Answer 2

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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