Магическое число в бусте :: hash_combine

94

Функция boost::hash_combineшаблона принимает ссылку на хэш (вызываемый seed) и объект v. Согласно документам , он сочетается seedс хешем vby

seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);

Я вижу, что это детерминировано. Я понимаю, почему используется XOR.

Бьюсь об заклад, это добавление помогает отображать похожие значения на значительном расстоянии друг от друга, так что хеш-таблицы не сломаются, но может ли кто-нибудь объяснить, что такое магическая константа?

c++ algorithm boost hash magic-numbers Фред Фу
источник
Учитывая, что на многих компьютерах стоимость ротации целых чисел примерно такая же, как и сдвиг, можно было бы получить какую-либо пользу от преобразования выражения в: <code> seed ^ = hash_value (v) + 0x9e3779b9 + rotl (seed, 6) + rotr (seed, 2); </code>
Джон Йейтс

Ответы:

141

Предполагается, что магическое число состоит из 32 случайных битов, каждый из которых с равной вероятностью будет 0 или 1, и без простой корреляции между битами. Обычный способ найти строку таких битов - использовать двоичное расширение иррационального числа; в данном случае это число является обратной величиной золотого сечения:

phi = (1 + sqrt(5)) / 2
2^32 / phi = 0x9e3779b9

Таким образом, включение этого числа "случайным образом" изменяет каждый бит начального числа; как вы говорите, это означает, что последовательные значения будут далеко друг от друга. Включение смещенных версий старого начального числа гарантирует, что даже при hash_value()довольно небольшом диапазоне значений различия скоро будут распространяться по всем битам.

Майк Сеймур
источник
14
Круто! Мне нравится, когда теория чисел внезапно становится полезной :)
Фред Фу
8
@larsmans Мне нравится, когда вы используете слово «внезапно» - это очень уместно! Теория чисел похожа на «да, это хорошо ... но у меня есть настоящая работа, извините» в 99% всех случаев. А потом, как вы говорите, «внезапно» теория чисел суперполезна. Это не как молоток , где это весьма полезно для большого количества вещей. Напротив, это как скальпель, чрезвычайно полезный для небольшого числа вещей.
corsiKa
5
@SamKellett Сработал бы еще лучше, если бы вы использовали правильное количество круглых скобок и получили0x9e3779b97f4a7800
Барри,
5
Поскольку число с плавающей запятой в Python не имеет достаточной точности, приведенные выше 64-битные золотые отношения неверны. Фактический результат должен быть 0x9e3779b97f4a7c15.
kennytm
1
@kennytm Вы не имеете в виду 0x9e3779b97f4a7c16? Я имею в виду, что это всего 1 шт.
bit2shift
25

Взгляните на статью Боба Дженкинса в DDJ 1997 года . Магическая константа («золотое сечение») объясняется следующим образом:

Золотое сечение действительно является произвольной величиной. Его цель - избежать отображения всех нулей на все нули.

NPE
источник