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

Question

Насколько я понимаю, вы, как правило, должны использовать 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?

Answer 1

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

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

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

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

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

Нет, вышеупомянутое относительно медленно и не очень помогает Некоторые люди используют 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 Метод заключается в том, что если у вас есть тип который имеет два значения, которые часто то же самое, XORing те значения всегда будут одинаковыми результат (0), тогда как выше будет различать между ними, если тебе очень не повезло.

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

Answer 7

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

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;
}