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

Question

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

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

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

Answer 1

Как описано Джоном Скитом в этом ответе 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-метода.

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

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

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

Обновление:

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

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

и ваш второй:

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

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

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

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

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

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

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

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

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

Answer 3

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

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

Answer 4

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