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

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

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

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

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

2 Solutions collect form web for “Магический номер в boost :: hash_combine”

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

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

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

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

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

  • Как конвертировать 16-битный RGB565 в 24-разрядный RGB888?
  • Определите, перекрываются ли два прямоугольника друг с другом?
  • TMP: как обобщить декартово произведение векторов?
  • Как я могу эффективно определить, является ли многоугольник выпуклым, невыпуклым или сложным?
  • Алгоритмы выбора на отсортированной матрице
  • Дифф-алгоритм?
  • Редкие матрицы / массивы в Java
  • Создание генератора случайных чисел из броска монеты
  • Разница между примечаниями Big-O и Little-O
  • Найти наименьшее целое число в списке
  • std :: map, как сортировать по значению, затем по ключу
  • Давайте будем гением компьютера.