Magische Zahl in boost :: hash_combine

94

Die boost::hash_combineVorlagenfunktion verweist auf einen Hash (aufgerufen seed) und ein Objekt v. Laut den Dokumenten wird es seedmit dem Hash von vby kombiniert

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

Ich kann sehen, dass dies deterministisch ist. Ich verstehe, warum ein XOR verwendet wird.

Ich wette, der Zusatz hilft bei der Abbildung ähnlicher Werte weit auseinander, damit die Hash-Tabellen nicht zusammenbrechen. Aber kann jemand erklären, was die magische Konstante ist?

c++ algorithm boost hash magic-numbers Fred Foo
quelle
Angesichts der Tatsache, dass auf vielen Computern eine Ganzzahl-Rotation etwa die gleichen Kosten wie eine Verschiebung verursacht, wäre es von Vorteil, den Ausdruck in Folgendes umzuwandeln: <code> seed ^ = hash_value (v) + 0x9e3779b9 + rotl (seed, 6) + rotr (seed, 2); </ code>
John Yates

Antworten:

139

Die magische Zahl soll 32 zufällige Bits sein, wobei jedes gleich wahrscheinlich 0 oder 1 ist und keine einfache Korrelation zwischen den Bits besteht. Ein üblicher Weg, eine Folge solcher Bits zu finden, besteht darin, die binäre Erweiterung einer irrationalen Zahl zu verwenden; In diesem Fall ist diese Zahl der Kehrwert des Goldenen Schnitts:

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

Das Einbeziehen dieser Zahl "zufällig" ändert also jedes Bit des Samens; Wie Sie sagen, bedeutet dies, dass aufeinanderfolgende Werte weit voneinander entfernt sind. Durch das Einbeziehen der verschobenen Versionen des alten Seeds wird sichergestellt, dass sich hash_value()Unterschiede , selbst wenn sie einen relativ kleinen Wertebereich aufweisen, bald auf alle Bits verteilen.

Mike Seymour
quelle
14
Cool! Ich mag es, wenn die Zahlentheorie plötzlich nützlich wird :)
Fred Foo
8
@larsmans Ich liebe deine Verwendung von "plötzlich" - es ist sehr angemessen! Die Zahlentheorie lautet in 99% aller Fälle "Ja, das ist schön ... aber ich habe echte Arbeit zu erledigen, sorry". Und dann, wie Sie sagen, "plötzlich", ist die Zahlentheorie super super nützlich. Es ist nicht wie ein Hammer, bei dem es für eine Vielzahl von Dingen ziemlich nützlich ist. Stattdessen ist es wie ein Skalpell, das für eine kleine Anzahl von Dingen äußerst nützlich ist.
CorsiKa
5
@ SamKellett Würde noch besser funktionieren, wenn Sie die richtige Anzahl von Klammern verwenden und0x9e3779b97f4a7800
Barry
5
Da die Gleitkommazahl von Python nicht genau genug ist, sind die oben genannten 64-Bit-Goldenen Verhältnisse nicht korrekt. Das tatsächliche Ergebnis sollte sein 0x9e3779b97f4a7c15.
Kennytm
1
@ kennytm Meinst du nicht 0x9e3779b97f4a7c16? Ich meine, es ist nur 1 aus.
Bit2shift
25

Schauen Sie sich den DDJ-Artikel von Bob Jenkins aus dem Jahr 1997 an . Die magische Konstante ("goldener Schnitt") wird wie folgt erklärt:

Der goldene Schnitt ist wirklich ein beliebiger Wert. Damit soll vermieden werden, dass alle Nullen allen Nullen zugeordnet werden.

NPE
quelle