Magiczna liczba doładowania :: hash_combine

Funkcja boost::hash_combineszablonu przyjmuje odniesienie do skrótu (wywoływanego seed) i obiektu v. Według dokumentacji łączy się seedz hashem pliku vby

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

Widzę, że jest to deterministyczne. Rozumiem, dlaczego używany jest XOR.

Założę się, że dodatek pomaga w odwzorowaniu podobnych wartości w dużej odległości od siebie, więc sondowanie tabel skrótów nie ulegnie awarii, ale czy ktoś może wyjaśnić, czym jest magiczna stała?

Magiczna liczba ma składać się z 32 losowych bitów, z których każdy z równym prawdopodobieństwem będzie równy 0 lub 1 i bez prostej korelacji między bitami. Powszechnym sposobem znalezienia ciągu takich bitów jest użycie binarnego rozwinięcia liczby niewymiernej; w tym przypadku liczba ta jest odwrotnością złotego podziału:

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

Zatem dołączenie tej liczby „losowo” zmienia każdy bit ziarna; jak mówisz, oznacza to, że kolejne wartości będą daleko od siebie. Uwzględnienie przesuniętych wersji starego ziarna zapewnia, że ​​nawet jeśli hash_value()ma dość mały zakres wartości, różnice wkrótce zostaną rozłożone na wszystkie bity.

Spójrz na artykuł DDJ autorstwa Boba Jenkinsa z 1997 roku . Magiczną stałą („złoty współczynnik”) wyjaśniono w następujący sposób:

Złoty podział to naprawdę wartość arbitralna. Jego celem jest uniknięcie odwzorowywania wszystkich zer na wszystkie zera.