Магический номер в boost :: hash_combine

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

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

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

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

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

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

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

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

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

  • Вычислить наибольший прямоугольник во вращающемся прямоугольнике
  • Наименьшее общее число для 3 или более номеров
  • Как проверить, пересекает ли сегмент линии прямоугольник?
  • Худший случай для QuickSort - когда это может произойти?
  • в чем разница между set и unordered_set в C ++?
  • Словарь в Swift с Mutable Array как значение работает очень медленно? Как оптимизировать или построить правильно?
  • Объясните этот fragment, который находит максимум два целых числа без использования if-else или любого другого оператора сравнения?
  • Проверьте, является ли одно целое число целым числом другого
  • Алгоритм раздувания / дефляции (смещения, буферизации) полигонов
  • как объединить два отсортированных целочисленных массива на месте с использованием O (n) времени и O (1) пространственной стоимости
  • Самый короткий путь для преобразования одного слова в другое
  • Давайте будем гением компьютера.