Каков наилучший способ реализовать этот составной GetHashCode()

У меня есть простой класс:

public class TileName {
    int Zoom, X, Y;

    public override bool Equals (object obj)
    {
        var o = obj as TileName;
        return (o != null) && (o.Zoom == Zoom) && (o.X == X) && (o.Y == Y);
    }

    public override int GetHashCode ()
    {
        return (Zoom + X + Y).GetHashCode();
    }
}

Мне было любопытно, если бы я получил лучшее распределение хеш-кодов, если бы я сделал что-то вроде:

    public override int GetHashCode ()
    {
        return Zoom.GetHashCode() + X.GetHashCode() + Y.GetHashCode();
    }

Этот класс будет использоваться в качестве словаря, поэтому я хочу убедиться, что есть достойное распространение.

Ответы

Ответ 1

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

public int GetHashCode()
{
    unchecked
    {
        int hash = 17;
        // Maybe nullity checks, if these are objects not primitives!
        hash = hash * 23 + Zoom.GetHashCode();
        hash = hash * 23 + X.GetHashCode();
        hash = hash * 23 + Y.GetHashCode();
        return hash;
    }
}

Проблемы с хэшами xor:

  • Если X равно Y, тогда ваш хеш будет просто Zoom, потому что тогда X ^ Y = X ^ X = 0 содержит
  • xor является симметричным оператором, он будет производить точные хэши для объектов [Zoom = 3, X = 5, Y = 7], [Zoom = 3, X = 7, Y = 5], [Zoom = 7, X = 5, Y = 3] и т.д.

Эти факты делают xor-метод более вероятным причиной конфликтов.

В дополнение к сообщению Jons рассмотрите использование контекста unchecked для явного игнорирования переполнения. Поскольку MSDN говорит:

Если ни checked, ни unchecked не существует используется постоянное выражение использует проверка переполнения по умолчанию при компиляции время, которое проверяется. В противном случае, если выражение непостоянно, проверка переполнения времени выполнения зависит от другие факторы, такие как параметры компилятора и конфигурации среды.

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

Обновление:

Кстати: someInt.GetHashCode() возвращает someInt. Таким образом, это, конечно, самый быстрый и идеальный хеш-распределение без единого столкновения. Как еще вы могли бы сопоставить int с int-hash?:) Итак, что я хотел сказать: ваш первый подход:

return (Zoom + X + Y).GetHashCode();

и ваш второй:

return Zoom.GetHashCode() + X.GetHashCode() + Y.GetHashCode();

точно такие же. Вам даже не нужно называть GetHashCode, и у обоих, скорее всего, будут столкновения. Может быть, даже хуже, чем метод xor, если вы, скорее всего, имеете небольшие целочисленные значения для всех трех ints.

Обновление 2:

Как я писал в комментарии к сообщению ChaosPandions: Если у вас есть только эти три значения int, а X, Y и Zoom - относительно небольшие числа (меньше 1000 или 10000), это может быть также хороший хэш-генератор:

public int GetHashCode()
{
    return (X << 16) ^ (Y << 8) ^ Zoom;
}

Он просто распределяет биты в хэш-значении (пример в формате big-endian для удобочитаемости):

00000000 00000000 00000011 00110001    X = 817
00000000 00000000 00011011 11111010    Y = 7162
00000000 00000000 00000010 10010110    Zoom = 662

00000011 00110001 00000000 00000000    X << 16
00000000 00011011 11111010 00000000    Y << 8
00000000 00000000 00000010 10010110    Zoom

00000011 00101010 11111000 10010110    (X << 16) ^ (Y << 8) ^ Zoom

Ответ 2

Ни одна из реализаций в вашем вопросе не идеальна. Например, они вернут точно такой же хеш для { Zoom=1, X=2, Y=3 }, { Zoom=2, X=3, Y=1 }, { Zoom=3, X=1, Y=2 } и т.д. И т.д.

Я обычно использую что-то вроде этого:

public override int GetHashCode()
{
    // 269 and 47 are primes
    int hash = 269;
    hash = (hash * 47) + Zoom.GetHashCode();
    hash = (hash * 47) + X.GetHashCode();
    hash = (hash * 47) + Y.GetHashCode();
    return hash;
}

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

Ответ 3

Я действительно нашел, что это действительно эффективно.

public override int GetHashCode ()
{
    return Zoom.GetHashCode() ^ X.GetHashCode() ^ Y.GetHashCode();
}

Ответ 4

public override int GetHashCode ()
{
    return (Zoom.ToString() + "-" + X.ToString() + "-" + Y.ToString()).GetHashCode();
}