Использование GetHashCode для проверки равенства в переопределении равных

Question

Можно ли вызвать GetHashCode как метод для проверки равенства изнутри переопределения Equals?

Например, допустим ли этот код?

public class Class1 
{ 
    public string A 
    { 
    get; 
    set; 
    } 

    public string B 
    { 
    get; 
    set; 
    } 

    public override bool Equals(object obj) 
    { 
    Class1 other = obj as Class1; 
    return other != null && other.GetHashCode() == this.GetHashCode(); 
    } 

    public override int GetHashCode() 
    { 
    int result = 0; 
    result = (result^397)^(A == null ? 0 : A.GetHashCode()); 
    result = (result^397)^(B == null ? 0 : B.GetHashCode()); 
    return result; 
    } 
} 

Answer 1

Другие права; ваша операция равенства нарушена. Для иллюстрации:

public static void Main() 
{ 
    var c1 = new Class1() { A = "apahaa", B = null }; 
    var c2 = new Class1() { A = "abacaz", B = null }; 
    Console.WriteLine(c1.Equals(c2)); 
} 

Я полагаю, вы хотите, чтобы вывод этой программы, чтобы быть «ложным», но с определением равенства является «истинным» на некоторых реализациях CLR.

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

В целом вы можете ожидать, что если есть n возможных хеш-кодов, вероятность получения столкновений резко возрастает, если у вас есть квадратный корень из n элементов в игре. Это так называемый «парадокс дня рождения». Для моей статьи о том, почему вы не должны полагаться на хэш-кодов для равенства, см:

http://blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx

Answer 2

Нет, это не нормально, потому что это не

equality <=> hashcode equality.

Это просто

equality => hashcode equality.

или в другом направлении:

hashcode inequality => inequality.

Цитирование http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx:

Если два объекта сравниваются как равные, метод GetHashCode для каждого объекта должен возвращать то же значение. Однако, если два объекта не сравниваются как равные, методы GetHashCode для двух объектов не должны возвращать разные значения.

Answer 3

Нет, это не приемлемый способ проверить равенство. Очень возможно, чтобы два не равных значения имели один и тот же хэш-код. Это приведет к вашей реализации Equals вернуть true, когда он должен вернуть false

Answer 4

Я бы сказал, если вы не хотите для Equals в основном означает, «имеет тот же хэш-код, как» для вашего типа, то не, потому что два строки могут быть разными, но имеют один и тот же хэш-код. Вероятность может быть малой, но она не равна нулю.

Answer 5

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

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

Например:

public override bool Equals(object obj) 
    { 
    Class1 other = obj as Class1; 
    if (other == null || other.GetHashCode() != this.GetHashCode()) 
     return false; 
    // the hash codes are the same so you have to do a full object compare. 
    } 

Answer 6

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

Единственный раз, когда вы звонили бы GetHashCode внутри Equals, было бы гораздо дешевле вычислить значение хэша для объекта (скажем, потому что вы его кешируете), чем для проверки равенства. В этом случае вы можете сказать if (this.GetHashCode() != other.GetHashCode()) return false;, чтобы вы могли быстро проверить, что объекты не равны.

Итак, когда вы это сделаете?Я написал некоторый код, который периодически выполняет скриншоты и пытается найти, сколько времени прошло с тех пор, как экран изменился. Поскольку мои скриншоты составляют 8 МБ и имеют относительно мало пикселей, которые изменяются в пределах интервала скриншота, довольно дорого искать их список, чтобы найти, какие из них одинаковы. Хэш-значение невелико и только должно быть вычислено один раз за снимок экрана, что упрощает устранение известных неравных. Фактически, в моем приложении я решил, что наличие одинаковых хэшей достаточно близко к тому, чтобы быть равным, что я даже не потрудился реализовать перегрузку Equals, в результате чего компилятор C# предупредил меня, что я перегружал GetHashCode без перегрузки Equals.

Answer 7

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

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

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

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

Повторная установка элементов при изменении размера, очевидно, будет зависеть от хэш-кодов. Из-за этого, хотя редко бывает смысл запоминать GetHashCode() в объекте (он просто не называется достаточно часто на большинстве объектов), он, безусловно, имеет смысл его memoise внутри самой хеш-таблицы (или, возможно, для memoise произведенной результат, например, если вы повторно хешировали хэшем Wang/Jenkins, чтобы уменьшить ущерб, вызванный плохими GetHashCode() реализациями).

Теперь, когда мы приходим, чтобы вставить нашу логику будет что-то вроде:

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

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

private bool IsMatch(KeyType newItem, KeyType storedItem, int newHash, int oldHash) 
{ 
    return ReferenceEquals(newItem, storedItem) // fast, false negatives, no false positives (only applicable to reference types) 
    || 
    (
     newHash == oldHash // fast, false positives, no fast negatives 
     && 
     _cmp.Equals(newItem, storedItem) // slow for some types, but always correct result. 
    ); 
} 

Очевидно, что преимущество этого зависит от сложности _cmp.Equals. Если бы наш ключевой тип был int, тогда это было бы полным отходом. Если наш ключевой тип, в котором используется строка, и мы использовали независимые от Unicode сравнения сравнений с выравниванием по Юникоду (поэтому он не может даже содержать ярлык по длине), то экономия может стоить того.

Как правило, мемориальные хеш-коды не имеют смысла, потому что они недостаточно часто используются для выигрыша производительности, но хранение их в hashset или hashtable может иметь смысл.

Answer 8

1. Это неправильная реализация, так как другие изложили почему.

2. Вы должны закоротить проверить равенство с помощью GetHashCode как:

   if (other.GetHashCode() != this.GetHashCode() 
       return false; 
   

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

3. В этой одной реализации вы показали (что составляет 99% случаев) не только сломан, но и намного медленнее. И причина? Вычисление хэша ваших свойств почти наверняка будет медленнее, чем сравнение их, поэтому вы даже не набираете обороты. Преимущество реализации надлежащего GetHashCode заключается в том, что ваш класс может быть ключевым типом для хэш-таблиц, где хэш вычисляется только один раз (и это значение используется для сравнения). В вашем случае GetHashCode будет вызываться несколько раз, если он находится в коллекции. Несмотря на то, что GetHashCode сам по себе должен быть быстрым, он не в основном быстрее, чем эквивалентEquals.

   Для теста, запустите Equals (надлежащее выполнение, вынимая текущей реализации на основе хэш-функции) и GetHashCode здесь

   var watch = Stopwatch.StartNew(); 
   for (int i = 0; i < 100000; i++) 
   { 
       action(); //Equals and GetHashCode called here to test for performance. 
   } 
   watch.Stop(); 
   Console.WriteLine(watch.Elapsed.TotalMilliseconds);