Проблема GetHashCode() с использованием xor

StackOverflow https://stackoverflow.com/questions/1008633

  •  06-07-2019
  •  | 
  •  

Вопрос

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

class Foo
{
    int m_a;
    int m_b;

    public int A
    {
        get { return m_a; }
        set { m_a = value; }
    }

    public int B
    {
        get { return m_b; }
        set { m_b = value; }
    }

    public Foo(int a, int b)
    {
        m_a = a;
        m_b = b;
    }

    public override int GetHashCode()
    {
        return A ^ B;
    }

    public override bool Equals(object obj)
    {
        return this.GetHashCode() == obj.GetHashCode();
    }
}

Идея в том, что я хочу сравнить один экземпляр Foo с другим на основе значений свойств A и B.Если Foo1.A == Foo2.A и Foo1.B == Foo2.B, то имеем равенство.

Вот проблема:

Foo one = new Foo(1, 2);
Foo two = new Foo(2, 1);

if (one.Equals(two)) { ... }  // This is true!

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

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

Как лучше всего обрабатывать значения свойств, которые можно легко поменять местами при реализации GetHashCode()?

Смотрите также

Каков наилучший алгоритм для переопределенного System.Object.GetHashCode?

Это было полезно?

Решение

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

Контракт для GetHashCode() включает в себя следующее:

  • разные хэш-коды означают, что объекты определенно не равны
  • одинаковые хеш-коды означают объекты мощь быть равными (но, возможно, не может быть)

Эндрю Хэйр предложил мне включить его ответ:

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

Нет, вышеперечисленное относительно медленно и не очень помогает.Некоторые люди используют xor (например, a ^ b ^ c), но я предпочитаю тот тип метода, показанного в «Эффективной Java» Джоша Блоха:

public override int GetHashCode()
{
    int hash = 23;
    hash = hash*37 + craneCounterweightID;
    hash = hash*37 + trailerID;
    hash = hash*37 + craneConfigurationTypeCode.GetHashCode();
    return hash;
}

23 и 37 являются произвольными числами, которые являются совместными.

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

Как упоминалось в приведенном выше фрагменте, вы также можете посмотреть Книга Джошуа Блоха «Эффективная Java». который содержит хорошее рассмотрение этой темы (обсуждение хэш-кода применимо и к .NET).

Другие советы

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

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

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

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

Прочитайте Переопределить GetHashCode для изменяемых объектов? C # и подумайте о реализации IEquatable < T >

Быстрая генерация и хорошее распределение хеша 

public override int GetHashCode()
{
    return A.GetHashCode() ^ B.GetHashCode();         // XOR
}

Из любопытства, поскольку хэш-коды обычно являются плохой идеей для сравнения, не лучше ли будет просто выполнить следующий код или я что-то упустил? 

public override bool Equals(object obj)
{
    bool isEqual = false;
    Foo otherFoo = obj as Foo;
    if (otherFoo != null)
    {
        isEqual = (this.A == otherFoo.A) && (this.B == otherFoo.B);
    }
    return isEqual;
}

Есть несколько лучших реализаций хеша. Хэш FNV , например.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top