Hashtable

0x9e3779b9

представляет собой целую часть дробной части Золотого сечения 0,61803398875… (sqrt(5)-1)/2, умноженную на 2^32.

Следовательно, если φ = (sqrt(5)+1)/2 = 1,61803398875 — это Золотое сечение, хэш-функция вычисляет дробную часть n * φ, которая имеет хорошие свойства рассеивания. Чтобы убедиться, просто создайте диаграмму рассеивания

(n, n*c-FLOOR(n*c))

в вашей любимой таблице, заменив

c

с φ, e, π и т. д. Некоторые интересные реальные проблемы, возникающие при неправильном выполнении, описаны в https://lkml.org/lkml/2016/4/29/838.Этот метод часто называют «хешированием золотого сечения» или «хешированием Фибоначчи», и он был популяризирован Дональдом Кнутом (Искусство программирования: Том 3: Сортировка и поиск). В терминах теории чисел он в основном сводится к гипотезе Штейнгауза (https://en.wikipedia.org/wiki/Three-gap_theorem) и рекурсивной симметрии дробных частей кратных золотому сечению φ.Иногда вы также можете увидеть

0x9e3779b1

, который является ближайшим к

0x9e3779b9

(и, похоже, это немного похоже на «культ карго», поскольку это не модульный хэш). Аналогично,

0x9e3779b97f4a7c15

и

0x9e3779b97f4a7c55

являются 64-битными эквивалентами этих чисел.
ZeroTierOne-1.14.2\node\Hashtable.hpphttps://softwareengineering.stackexchange.com/questions/402542/where-do-magic-hashing-constants-like-0x9e3779b9-and-0x9e3779b1-come-from
http://troydhanson.github.com/uthash/
erlang-fast_tls
https://github.com/processone/fast_tls/tree/master/c_src
The Paul Hsieh hash functionhttps://www.azillionmonkeys.com/qed/hash.html
https://www.azillionmonkeys.com/qed/hash.c