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

У меня есть простой class:

public class TileName { int Zoom, X, Y; public override bool Equals (object obj) { var o = obj as TileName; return (o != null) && (o.Zoom == Zoom) && (oX == X) && (oY == Y); } public override int GetHashCode () { return (Zoom + X + Y).GetHashCode(); } } 

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

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

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

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

 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 hashами:

  • если X равно Y то ваш hash будет просто Zoom, потому что тогда выполняется X ^ Y = X ^ X = 0
  • xor является симметричным оператором, он будет производить точно такие же hashи для объектов [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 , если вы, скорее всего, имеете небольшие целочисленные значения для всех трех int.

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

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

 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 

Ни одна из реализаций в вашем вопросе не является идеальной. Например, они вернут точно такой же hash для { 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.GetHashCode() ^ X.GetHashCode() ^ Y.GetHashCode(); } 
 public override int GetHashCode () { return (Zoom.ToString() + "-" + X.ToString() + "-" + Y.ToString()).GetHashCode(); } 
Interesting Posts

Некоторые указатели пальцев не позволяют системе выйти из экрана загрузки

Как я могу разбирать строку в BigDecimal?

Nerdtree и текущий каталог

maven: Как пропустить тест в некоторых проектах через параметры командной строки?

В чем разница между параллельным программированием и параллельным программированием?

Как заставить ArrayAdapter следовать шаблону ViewHolder?

Как подключить элемент панели управления для запуска?

Загрузка с USB с биографией UEFI для установки Windows 8.1

Внедрение алгоритма сортировки Swift

Работает ли Razor View Engine для Mono?

Получение «Запрос JSON был слишком большим для десериализации»

Проблема при передаче переменной с обозначением знака доллара ($) на aes () в сочетании с facet_grid () или facet_wrap ()

Помогите с пониманием функционального объекта или функтора в Java

Являются ли операторы сдвига (<>) арифметическими или логическими в C?

Как получить путь сборки, в которой находится код?

Давайте будем гением компьютера.