Магическое число в boost :: hash_combine

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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