Как реализовать метод Equals, совместимый с GetHashCode, если пространство больше 32 бит? - PullRequest
Новая
       39

Как реализовать метод Equals, совместимый с GetHashCode, если пространство больше 32 бит?

1 голос
/ 21 июля 2009

В .NET вам нужно, чтобы Equals (объект) и GetHashCode () были совместимы. Но иногда вы не можете: 

public class GreaterThan32Bits
{
    public int X { get; set; }
    public int Y { get; set; }
}

Поскольку плотность данных превышает 32 бита, а GetHashCode возвращает Int32, у вас будет 3 решения (при условии правильно реализованного GetHashCode):

  1. Избегать дублирования кода отбрасывается как неправильный 

    public override bool Equals(object other)
{
    if(ReferenceEquals(null, other)) return false;
    if(ReferenceEquals(this, other)) return true;
    return this.GetHashCode() == other.GetHashCode();
}

  2. Реализация Equals отдельно от GetHashCode () 

    public override bool Equals(object obj)
{
    if(ReferenceEquals(null, other)) return false;
    if(ReferenceEquals(this, other)) return true;
    var other = obj as GreaterThan32Bits;
    if(this.X == other.X) return this.Y == other.Y;
    return false;
}

  3. Реализация большей точности GetHashCode64, переопределенный GetHashCode (32 бита) вернет (int) GetHashCode64 (), а Equals вернет this.GetHashCode64 () == other.GetHashCode64 ()

Какой из них вы бы реализовали?

Первое решение - неточно неверно, но чище. Второй вариант кажется чистым, но становится очень сложным, когда у класса больше свойств. Третий вариант - это компромисс.

Ответы [ 4 ]

5 голосов
/ 21 июля 2009

Требование следующее: если (a.Equals (b)), то a.GetHashCode () == b.GetHashCode ()

Не наоборот.

Вы никогда не должны реализовывать Equals () в терминах GetHashCode (). Для GetHashCode вполне допустимо иметь коллизии, но Equals () не должен возвращать ложных срабатываний.

Я бы предложил эту реализацию: 

public override int GetHashCode()
{
    return unchecked( this.X * p1 + this.Y * p2 );
}

public override bool Equals(object obj) 
{
    var other = obj as GreaterThan32Bits;
    // you must do the null test after the cast, otherwise the
    // function crashes when obj is not a GreaterThan32Bits instance
    if (ReferenceEquals(other, null)) return false;
    return this.X == other.X && this.Y == other.Y;
}

Где p1 и p2 - большие простые числа. Обычно это приводит к хорошей хеш-функции (несколько коллизий хешей -> Словарь становится эффективным) Если значения X и Y независимы (например, вы не ожидаете много точек на прямой линии, например, X = Y), то даже что-то простое, например X ^ Y, может быть хорошей хеш-функцией.

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

На самом деле, вполне нормально всегда возвращать 0 в GetHashCode () и реализовывать только Equals (). Словарь по-прежнему будет правильно работать с такими объектами, как ключи, он просто будет неэффективным.

4 голосов
/ 21 июля 2009

Ваша первая реализация не правильная. Хеш-код двух объектов может быть одинаковым, даже если сами объекты не равны: Это суть хеш-кода.

Хеш-код объекта может быть полезен для определения, когда два объекта равны не , но чтобы определить, равны ли они , вам придется вызвать .Equals().

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

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

2 голосов
/ 21 июля 2009

Строго говоря, первое решение не работает. Тогда это не решение проблемы.

Идея хеширования совершенно иная. Int32 достаточно для этих целей.

Рекомендуемый GetHashCode () равен 

return X ^ Y;

Просто как есть.

EDIT : методы Equals могут затем использовать GetHashCode (), но только для возврата false, когда хэши различаются В любом случае требуется глубокое сравнение.

1 голос
/ 21 июля 2009

Я думаю, что ключ, который вам не хватает, заключается в том, что GetHashCode () не должен возвращать уникальные значения.

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

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

...