Funkcja boost::hash_combine
szablonu przyjmuje odniesienie do skrótu (wywoływanego seed
) i obiektu v
. Według dokumentacji łączy się seed
z hashem pliku v
by
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?
Odpowiedzi:
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.źródło
0x9e3779b97f4a7800
0x9e3779b97f4a7c15
.0x9e3779b97f4a7c16
? Mam na myśli, to tylko 1 zniżki.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:
źródło