it-swarm-eu.dev

Woher kommen "magische" Hashing-Konstanten wie 0x9e3779b9 und 0x9e3779b1?

Im Code, der sich mit Hash-Tabellen befasst, finde ich oft die Konstante 0x9e3779b9 oder manchmal 0x9e3779b1. Zum Beispiel

hash = n * 0x9e3779b1 >>> 24

Warum wird dieser bestimmte Wert verwendet?

137
bkgs

0x9e3779b9 Ist der integrale Bestandteil des Bruchteils des Goldenen Schnitts 0.61803398875… (sqrt (5) -1)/2, multipliziert mit 2 ^ 32.

Wenn also φ = (sqrt (5) +1)/2 = 1,61803398875 der Goldene Schnitt ist, berechnet die Hash-Funktion den Bruchteil von n * φ, der schöne Streuungseigenschaften aufweist. Um sich selbst zu überzeugen, erstellen Sie einfach ein Streudiagramm von (n, n*c-FLOOR(n*c)) In Ihrer bevorzugten Tabelle und ersetzen Sie c durch φ, e, π usw. Einige interessante Probleme im wirklichen Leben, wenn Sie etwas falsch machen, sind in beschrieben https://lkml.org/lkml/2016/4/29/838 .

Diese Methode wird oft als "Golden Ratio Hashing" oder "Fibonacci Hashing" bezeichnet und wurde von Donald Knuth (Die Kunst der Computerprogrammierung: Band 3: Sortieren und Suchen) populär gemacht. In zahlentheoretischen Begriffen läuft es hauptsächlich auf die Steinhaus-Vermutung ( https://en.wikipedia.org/wiki/Three-gap_theorem ) und die rekursive Symmetrie der Bruchteile der Vielfachen der Goldener Schnitt φ.

Gelegentlich sehen Sie möglicherweise auch 0x9e3779b1, Dies ist die Primzahl, die 0x9e3779b9 Am nächsten kommt (und scheint ein bisschen "Frachtkult" zu sein, da dies kein modularer Hash ist). In ähnlicher Weise sind 0x9e3779b97f4a7c15 Und 0x9e3779b97f4a7c55 Die 64-Bit-Äquivalente dieser Zahlen.

220
32f

Die anderen Antworten erklären die Absicht hinter diesen magischen Zahlen, was Sie wahrscheinlich wissen wollten. Man könnte jedoch sagen, dass "sie kommen" von schlechten Programmierpraktiken herrührt. Magische Zahlen sind schlecht und sollten niemals verwendet werden. Konstanten wie die genannten sollten mit den richtigen beschreibenden Variablennamen versehen werden, und möglicherweise sollten sogar Kommentare hinzugefügt werden, wo sie definiert sind. Dann sollte jedes Auftreten der Werte im Code in Form der benannten Variablen erfolgen. Wo dies in den Codes der Fall ist, in denen Sie diese Werte erfüllt haben, wären Sie von ihrer Absicht überhaupt nicht verwirrt worden.

Beispiel:

Schlechtes Beispiel - verwendet magische Zahlen

hash = n * 0x9e3779b1

Besseres Beispiel - mit Kommentaren und aussagekräftiger Variable

# Golden Ratio constant used for better hash scattering
# See https://softwareengineering.stackexchange.com/a/402543 
GOLDEN_RATIO = 0x9e3779b1
hash = n * GOLDEN_RATIO
30
isilanes
Im Code, der sich mit Hash-Tabellen befasst, finde ich oft die Konstante 0x9e3779b9 oder manchmal 0x9e3779b1

Die andere Antwort erklärte richtig, warum dieser Wert verwendet wird. Wenn Sie diese Konstante jedoch häufig finden, stellen Sie möglicherweise nicht fest, dass Sie häufig Code finden, der für Hash-Flooding-Angriffe anfällig ist.

Es gibt zwei Strategien gegen Hash-Flooding-Angriffe:

  1. Verwenden Sie eine sichere Hash-Funktion mit einem geheimen zufälligen Startwert. Ihre Hash-Funktion hat keinen geheimen zufälligen Startwert. Murmurhash3_32 hat einen geheimen zufälligen Keim, aber aufgrund des kleinen internen Zustands hat es einen samenunabhängigen Multicollisions. Die beste Hash-Funktion mit nahezu kryptografischer Sicherheit und dennoch nahezu akzeptabler Leistung ist wahrscheinlich SipHash. Leider ist es langsam, wenn auch nicht so langsam wie SHA512 usw.

  2. Verwenden Sie eine schnell zu berechnende Hash-Funktion (z. B. die gefundene Hash-Funktion oder Murmurhash3_32) und machen Sie jeden Hash-Bucket zum Stammverzeichnis eines ausgeglichenen binären Suchbaums. Eine gewöhnliche, separat verkettete Hash-Tabelle enthält also jeden Bucket als verknüpfte Liste. Dies ist langsam, wenn viele Werte in denselben Bucket gehasht werden. Indem Sie es zu einem ausgeglichenen binären Suchbaum wie einem AVL-Baum oder einem rot-schwarzen Baum machen, haben Sie immer noch die schlechteste Leistung garantiert.

Meiner Meinung nach ist (2) besser, weil SipHash so langsam ist. Im Kernelspeicher des Betriebssystems ist möglicherweise nicht genügend Entropie vorhanden, um zu Beginn des Startvorgangs einen geheimen zufälligen Startwert zu erstellen. Daher können Sie im Kernelspeicherbereich möglicherweise nicht zu Beginn des Startvorgangs Zufallszahlen erstellen.

Hash-Tabellen werden häufig missbraucht. Es ist einfach, viele Systeme praktisch zum Stillstand zu bringen, indem viele Werte, die Hash sind, an denselben Bucket gesendet werden.

5
juhist