Использование GetHashCode для проверки равенства в переопределении Equals - PullRequest
Новая
       3

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

9 голосов
/ 22 ноября 2010

Можно ли вызывать 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;
  }
}

Ответы [ 8 ]

14 голосов
/ 23 ноября 2010

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

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

7 голосов
/ 22 ноября 2010

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

equality <=> hashcode equality.

Это просто

equality => hashcode equality.

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

hashcode inequality => inequality.

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

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

2 голосов
/ 22 ноября 2010

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

1 голос
/ 22 ноября 2010

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

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

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

1 голос
/ 22 ноября 2010

Вы можете вызвать 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.
  }
1 голос
/ 22 ноября 2010

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

0 голосов
/ 15 декабря 2013

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

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

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

    в методе Equals , только если вы уверены, что последующая реализация 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);
0 голосов
/ 29 ноября 2010

В одном случае использование хеш-кодов в качестве ярлыка для сравнений на равенство имеет смысл.

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

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

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

Повторная вставка элементов для изменения размера будет зависеть от хэш-кодов. Из-за этого, хотя редко имеет смысл запоминать GetHashCode() в объекте (он просто не вызывается достаточно часто для большинства объектов), безусловно, имеет смысл запоминать его в самой хеш-таблице (или, возможно, запоминать производимый результат, например, если вы повторно хэшировали с помощью хэша Ванга / Дженкинса, чтобы уменьшить ущерб, вызванный неправильными реализациями 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-нормализованные сравнения на равенство (поэтому он не может даже сокращать длину), тогда экономия вполне может стоить.

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

...