Что лучший способ состоит в том, чтобы реализовать этот составной 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();
}
Этот класс будет используемым в качестве ключа Словаря, таким образом, я действительно хочу удостовериться, что существует достойное распределение.
4 ответа
Как описано Джоном Скитом в этом 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 , сказано:
Если ни
не отмечен, ни, нине отмечен,не используется , постоянное выражение использует проверка переполнения по умолчанию во время компиляции , которая проверяется. В противном случае, если выражение не является константой, проверка переполнения во время выполнения будет зависеть от других факторов, таких как параметры компилятора и конфигурация среды.
Таким образом, хотя обычно переполнение не проверяется, может случиться так, что в какой-то среде или при сборке с использованием какой-либо опции компилятора, это может произойти из-за сбоя. Но в этом случае вы не хотите явно проверять эти переполнения.
Обновление:
Кстати: someInt.GetHashCode () возвращает someInt .Таким образом, это, конечно, максимально быстрое и идеальное распределение хешей без единой коллизии. Как еще вы могли бы сопоставить int с int-хешем? :) Итак, что я хотел сказать: ваш первый подход:
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
Ни одна из реализаций в вашем вопрос идеальный. Например, они вернут точно такой же хеш для {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 для анонимных типов.)
public override int GetHashCode ()
{
return (Zoom.ToString() + "-" + X.ToString() + "-" + Y.ToString()).GetHashCode();
}
Я обнаружил, что это действительно эффективно.
public override int GetHashCode ()
{
return Zoom.GetHashCode() ^ X.GetHashCode() ^ Y.GetHashCode();
}