Magiczna liczba doładowania :: hash_combine

94

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?

Fred Foo
źródło
Biorąc pod uwagę, że na wielu komputerach koszt rotacji liczb całkowitych jest mniej więcej taki sam jak przesunięcie, konwersja wyrażenia na: <code> seed ^ = hash_value (v) + 0x9e3779b9 + rotl (seed, 6) + rotr (seed, 2); </code>
John Yates

Odpowiedzi:

141

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.

Mike Seymour
źródło
14
Fajne! Podoba mi się, gdy teoria liczb nagle się przydaje :)
Fred Foo
8
@larsmans Uwielbiam, jak używasz słowa „nagle” - jest bardzo odpowiednie! Teoria liczb jest w stylu „tak, to miłe ... ale mam dużo pracy, przepraszam” w 99% wszystkich przypadków. A potem, jak mówisz, „nagle”, teoria liczb jest super przydatna. To nie jest jak młotek, w którym jest raczej przydatny do wielu rzeczy. Zamiast tego jest jak skalpel, który jest niezwykle przydatny do niewielkiej liczby rzeczy.
corsiKa
5
@SamKellett Działałby jeszcze lepiej, gdybyś użył prawidłowej liczby nawiasów i uzyskał0x9e3779b97f4a7800
Barry
5
Ponieważ liczba zmiennoprzecinkowa Pythona nie ma wystarczającej precyzji, powyższe 64-bitowe złote proporcje nie są poprawne. Rzeczywisty wynik powinien być 0x9e3779b97f4a7c15.
kennytm
1
@kennytm Nie masz na myśli 0x9e3779b97f4a7c16? Mam na myśli, to tylko 1 zniżki.
bit2shift
25

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.

NPE
źródło