Frage Magische Zahl in boost :: hash_combine


Das boost::hash_combine Template - Funktion nimmt Bezug auf einen Hash (genannt seed) und ein Objekt v. Entsprechend der Dokumente, es kombiniert seed mit dem Hash von v durch

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

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

Ich wette, die Addition hilft bei der Abbildung ähnlicher Werte weit auseinander, so dass Hashtabellen nicht zusammenbrechen, aber kann jemand erklären, was die magische Konstante ist?


76
2018-02-09 18:14


Ursprung


Antworten:


Die magische Zahl soll 32 zufällige Bits sein, wobei jedes gleich wahrscheinlich 0 oder 1 ist, und ohne eine einfache Korrelation zwischen den Bits. Eine übliche Methode, um eine Kette solcher Bits zu finden, ist die binäre Erweiterung einer irrationalen Zahl; In diesem Fall ist diese Zahl der Kehrwert des Goldenen Schnitts:

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

Also ändert diese Zahl "zufällig" jedes Bit des Samens; Wie Sie sagen, bedeutet dies, dass aufeinanderfolgende Werte weit auseinander liegen. Einschließlich der verschobenen Versionen der alten Samen sorgt dafür, dass, wenn auch hash_value() hat einen recht kleinen Bereich von Werten, werden bald Unterschiede über alle Bits verteilt werden.


118
2018-02-09 18:32



Sieh dir das an DDJ Artikel von Bob Jenkins von 1997. Die magische Konstante ("golden ratio") wird wie folgt erklärt:

Das goldene Verhältnis ist wirklich ein willkürlicher Wert. Sein Zweck ist es, zu vermeiden, dass alle Nullen auf alle Nullen abgebildet werden.


20
2018-02-09 18:47