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

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

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

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

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

Источник

3 ответа

Решение

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

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

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

Источник

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

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

Источник

используя python, чтобы получить этот магический номер:

      from math import sqrt
phi = (1 + sqrt(5)) / 2
hex(int(2**32/phi))
Источник
Другие вопросы по тегам