Как выбрать простые числа для вычисления хеш-кода?

Question

Этот вопрос следует за ответом, данным Джоном Скитом на вопрос: " Каков наилучший алгоритм для переопределенного System.Object.GetHashCode?". Для вычисления хеш-кода используется следующий алгоритм:

public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        // Suitable nullity checks etc, of course :)
        hash = hash * 23 + field1.GetHashCode();
        hash = hash * 23 + field2.GetHashCode();
        hash = hash * 23 + field3.GetHashCode();
        return hash;
    }
}

Я не понимаю, почему выбраны номера 17 и 23. Почему бы нам не выбрать 3 и 5? Это и простые числа. Может кто-нибудь объяснить, какие простые простые числа выбрать и почему?

Answer 1

В комментариях к ответу, на который вы ссылаетесь, кратко постарайтесь объяснить, почему 17 а также 23 здесь не годятся простые числа.

Многие классы.NET, использующие хеш-коды, хранят элементы в контейнерах. Предположим, есть три ведра. Затем все объекты с хэш-кодом 0, 3, 6, 9, ... сохраняются в сегменте 0. Все объекты с хэш-кодом 1, 4, 7, 10, ... сохраняются в сегменте 1. Все объекты с сегментом 2, 5, 8, 11, ... хранятся в ведре 2.

Теперь предположим, что ваш GetHashCode() использования hash = hash * 3 + field3.GetHashCode();, Это будет означать, что если hash достаточно большой, чтобы умножение можно было обернуть, в хэш-наборе с тремя сегментами, в котором сегмент, в котором окажется объект, зависит только от field3,

С неравномерным распределением объектов по ковшам, HashSet<T> не может дать хорошую производительность.

Вы хотите, чтобы фактор был взаимно простым для всего возможного количества сегментов. Само количество блоков будет простым по тем же причинам, поэтому, если ваш фактор является простым, единственный риск состоит в том, что он равен количеству блоков.

.NET использует фиксированный список разрешенных номеров сегментов:

public static readonly int[] primes = {
    3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
    1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
    17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
    187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
    1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};

Ваш фактор должен быть тем, который.NET не использует, и что другие пользовательские реализации также вряд ли будут использовать. Это означает 23 это плохой фактор. 31 может быть хорошо с собственными контейнерами.NET, но может быть одинаково плохо с пользовательскими реализациями.

В то же время он не должен быть таким низким, чтобы он давал много коллизий для общего использования. Это риск с 3 а также 5Предположим, у вас есть обычай Tuple<int, int> реализация с большим количеством маленьких целых чисел. Имейте в виду, что int.GetHashCode() просто возвращает это int сам. Предположим, ваш коэффициент умножения 3, Это означает, что (0, 9), (1, 6), (2, 3) а также (3, 0) все дают одинаковые хэш-коды.

Обе проблемы можно избежать, используя достаточно большие простые числа, как указано в комментарии, который Джон Скит включил в свой ответ:

РЕДАКТИРОВАТЬ: Как отмечено в комментариях, вы можете найти, что лучше выбрать большое простое число для умножения вместо. Видимо 486187739 это хорошо...

Когда-то большие простые числа для умножения могли быть плохими, потому что умножение на большие целые числа было достаточно медленным, чтобы разница в производительности была заметной. Умножение на 31 было бы хорошо в этом случае, потому что это может быть реализовано как x * 31 => x * 32 - x => (x << 5) - x, В настоящее время, однако, умножение гораздо реже вызывает какие-либо проблемы с производительностью, и тогда, вообще говоря, чем больше, тем лучше.