Функция boost::hash_combine
шаблона принимает ссылку на хэш (вызываемый seed
) и объект v
. Согласно документам , он сочетается seed
с хешем v
by
seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
Я вижу, что это детерминировано. Я понимаю, почему используется XOR.
Бьюсь об заклад, это добавление помогает отображать похожие значения на значительном расстоянии друг от друга, так что хеш-таблицы не сломаются, но может ли кто-нибудь объяснить, что такое магическая константа?
Ответы:
Предполагается, что магическое число состоит из 32 случайных битов, каждый из которых с равной вероятностью будет 0 или 1, и без простой корреляции между битами. Обычный способ найти строку таких битов - использовать двоичное расширение иррационального числа; в данном случае это число является обратной величиной золотого сечения:
phi = (1 + sqrt(5)) / 2 2^32 / phi = 0x9e3779b9
Таким образом, включение этого числа "случайным образом" изменяет каждый бит начального числа; как вы говорите, это означает, что последовательные значения будут далеко друг от друга. Включение смещенных версий старого начального числа гарантирует, что даже при
hash_value()
довольно небольшом диапазоне значений различия скоро будут распространяться по всем битам.источник
0x9e3779b97f4a7800
0x9e3779b97f4a7c15
.0x9e3779b97f4a7c16
? Я имею в виду, что это всего 1 шт.Взгляните на статью Боба Дженкинса в DDJ 1997 года . Магическая константа («золотое сечение») объясняется следующим образом:
источник