[PYTHON] multiplikativer Hash ist nicht perfekt (zertifiziert)

Überblick

Hinweis

Einführung

Auf Mercaris Blog gibt es einen Eintrag [metal_unk 17], der beweist, dass Knuths multiplikativer Hash die am wenigsten vollständige Hash-Funktion ist, und der den Beweis zeigt, dass Knuths multiplikativer Hash die am wenigsten vollständige ist.

Ich habe diesen Eintrag mit großem Interesse gelesen, da praktische Hash-Funktionen normalerweise Indexkollisionen verursachen [Weiss 14]. Bisher habe ich drei Dinge gefunden:

In Bezug auf den ersten Punkt im Hatena-Lesezeichen-Kommentar

Das, was ich mache, ist das gleiche, aber es scheint, dass "prime und max Elemente voneinander sind, so dass es unter der Methode max ein inverses Element von prime gibt. Daher alle Einzelaufnahmen".

[Rauchen186 17]

Es sieht aus wie f (n) = ((n * PRIME) mod MAX) + 1. Da es in mod MAX eine umgekehrte PRIME-Quelle gibt, sind alle Einzelaufnahmen selbstverständlich. Auch wenn die Wiederherstellbarkeit erforderlich ist (denn wenn sich die umgekehrte Quelle nicht im Definitionsbereich befindet, können Sie sie abspielen), muss sie nicht vollständig aufgenommen werden.

Einige Leute, wie [mather314 17], verstehen, dass es selbsterklärend ist. Zuerst konnte ich es nicht allein anhand des Blogeintrags oder dieses Lesezeichen-Kommentars verstehen, daher würde ich es gerne selbst verstehen. Ich habe einen Beweis geschrieben, ohne ihn zu verwenden. Danach konnte ich anhand dieser Kommentare einen präzisen Beweis schreiben. Vielen Dank.

In Bezug auf den zweiten Punkt wird die Definition des multiplikativen Hash grob in zwei Typen unterteilt: Prozeduren, die reelle Zahlenoperationen verwenden (im Folgenden als Multiplikator-Hash (reeller Wert) bezeichnet) und Prozeduren, die ganzzahlige Operationen und Bitverschiebungsoperationen verwenden (im Folgenden Multiplikator-Hash). (Aufgerufen (ganzzahliger Wert)). Beide wurden im Gegensatz zu Mercaris Hash-Funktion durch Computerexperimente bestätigt, um das Ergebnis der Indexkollision zurückzugeben. Siehe jedoch Knuths Originalbuch [Knuth 73]. Da es keine Möglichkeit gab, habe ich den multiplikativen Hash durch Vorlesungsmaterialien verschiedener Autoren ergänzt. Da ich diese Teile in einem Patchwork gelesen habe, kann es aufgrund inkonsistenten Verständnisses zu falschen Erklärungen kommen. Bitte sei vorsichtig mit Sex.

Für den dritten Punkt zeigen wir anhand des implementierten Python-Codes und der Ausführungsergebnisse, dass der multiplikative Hash aus dem konkreten Beispiel einer Kollision nicht perfekt ist. Dies macht Mercaris Hash-Funktion im Wesentlichen zu einem multiplikativen Hash. Sie können sehen, dass es anders ist.

Wenn Sie Fehler in der Beschreibung finden, weisen Sie bitte darauf hin. Vielen Dank.

Mercaris Hash-Funktion

** Definition 1 ** $ p $ ist eine Primzahl größer oder gleich 3, $ m $ ist eine Potenz von 2, die die Tabellengröße der Hash-Funktion darstellt ($ m = 2 ^ r $ unter Verwendung einer positiven ganzen Zahl $ r $). Zu diesem Zeitpunkt wird der Schlüsselwert $ n $ in einen Index umgewandelt. ** Die Hash-Funktion von Mercari ** $ f (n) $ ist wie folgt definiert.

f(n) = (np\mod m) + 1.

Der Wertebereich (Definitionsbereich) des Schlüssels von $ f $ und der Wertebereich (Wertebereich) des Index sind beide "[1, ..., m]".

** Nachtrag 1 ** Sei $ a und m $ positive ganze Zahlen, die zueinander primieren. Für $ 0 \ leq n \ le m-1 $ sei $ g (n) = an \ mod m $. Für eine Menge von $ n, n '$ ($ 0 \ leq n <n' \ leq m-1 $) wird es zu $ g (n) \ neq g (n ') $.

** Satz 1 ** Für zwei willkürlich gegebene unterschiedliche Schlüssel $ n, n '(1 \ leq n, n' \ leq m, n \ neq n ') $, Mercaris Hash-Funktion Es wird $ f (n) \ neq f (n ') $.

** Serie 1 ** In Mercaris Hash-Funktion $ f $ ist $ f $ ein Einzelschuss, solange $ a und m $ zueinander primieren.

Die Mercari-Hash-Funktion $ f (n) $ verfügt über die folgenden Funktionen. ** Satz 2 ** Wenn der Schlüssel $ n $ ungerade ist, ist $ f (n) $ gerade, und wenn $ n $ gerade ist, ist $ f (n) $ ungerade.

Erklären Sie die Bedeutung von Satz 2. Beim Kopieren von einer Gruppe von Indizes in eine Reihe von Schlüsseln trennt die Hashari-Funktion von Mercari die beiden Teilmengen von Indizes in zwei Teilmengen jedes Schlüssels. Der folgende Code gibt den Index der Mercari-Hash-Funktion für $ a = 40507 $, die Tabellengröße $ m = 16 $ und den Index des Multiplikations-Hash (ganzzahliger Wert) unter denselben Vergleichsbedingungen aus.

hashsample.py


import math

def kmh2(n, a, r, w): # Knuth's multiplicative hash
    """
    defined in a handout of lecture 5 Hashing 1
    http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture05.pdf
    """
    return ((a * n) % 2**w) >> (w-r)

def kmh(n, phi, tablesize): # Knuth's multiplicative hash
    """
    defined in a handout on hash functions 
    classes.engineering.wustl.edu/cse241/handouts/hash-functions.pdf
    """
    return int(math.floor(tablesize * (phi * n - math.floor(phi * n))))

def mmh(n, prime, tablesize): # Mercari's multiplicative hash
    return ((n * prime) % tablesize) + 1

def main():
    phis = [0.5*(math.sqrt(5)-1.0)]
    w = 16
    for phi in phis:
        a = 40507 # fixed prime
        # a = 2*int(2**(w-1)*phi)+1
        for v in range(4, 5):
            print "======="
            tablesize = 2**v
            print "tablesize", tablesize
            mmhvals = [mmh(x+1, a, tablesize) for x in range(tablesize)]
            kmh2vals = [kmh2(x, a, v, w) for x in range(tablesize)]
            print "mercali ", mmhvals
            print "multi   ", kmh2vals

main()

Das Ausführungsergebnis ist wie folgt.

hashsample.txt


=======
tablesize 16
mercali  [1, 12, 7, 2, 13, 8, 3, 14, 9, 4, 15, 10, 5, 16, 11, 6]
multi    [0, 9, 3, 13, 7, 1, 11, 5, 15, 9, 2, 12, 6, 0, 10, 4]

Die Ergebnisse dieses Experiments sind in der folgenden Abbildung dargestellt. Die Schlüssel und Indizes sind jedoch nach Gewinnchancen und Gleichungen getrennt angeordnet. Die Schlüssel und Indizes, in denen die Kollision aufgetreten ist, sind mit derselben Farbe (rot, grün) gefüllt. Der Pfeil, der darstellt, wird durch eine dicke Linie dargestellt. Der Index, der von keinem Schlüssel konvertiert wird, ist hellblau gefüllt.

メルカリのハッシュ関数はインデックスの偶奇でキーの偶奇が決まる

Satz 2 zeigt, dass es keinen Schlüsselwert gibt, der die Grenze zwischen ungeraden und geraden Indizes überschreitet. Für den später beschriebenen Multiplikations-Hash (ganzzahliger Wert) gilt Satz 2 nicht und die Schlüssel sind verstreut. Sie können aus der Abbildung sehen.

Darüber hinaus weist die Hash-Funktion von Mercari das gleiche Muster für die ungerade und gerade Entsprechung von Index zu Schlüssel auf. Das Muster aus dem vorherigen Beispiel ist in der folgenden Abbildung dargestellt. Das Paar aus Index und Schlüssel ist mit derselben Farbe gefüllt.

メルカリのハッシュ関数にはパターンがある

Die Hash-Funktion von Mercari erhöht den Indexwert immer um $ 2p $, wenn der Schlüsselwert um 2 erhöht wird, sodass ein solches Muster immer angezeigt wird und der erste Wert des Index vom Index zum Schlüssel in der ungeraden Zahl richtig ausgerichtet wird. Die Entsprechung von kann mit der Entsprechung von gerade abgeglichen werden.

multiplikativer Hash

Multiplikator-Hash (reelle Zahl)

Zunächst wird anhand des Vorlesungsmaterials ein Multiplikator-Hash (Realwert) definiert [Burler 15].

** Definition 2 ** $ m $ ist die Tabellengröße der Hash-Funktion, $ \ phi $ ist eine reelle Zahl zwischen 0 und 1. ** Multipliziere Hash (reelle Zahl) für Schlüssel $ n $ ** $ h_1 (n) ) $ Ist wie folgt definiert.

h(n) = \lfloor m(\phi n - \lfloor \phi n\rfloor)\rfloor.

Der Wert von $ \ phi $ ist Knuths empfohlener goldener Schnitt $ (\ sqrt {5} -1) / 2 $, $ \ sqrt {2} / 2 $, $ \ sqrt {3} -1 $ Oft werden unangemessene Zahlen verwendet [Burler 15].

Der Wertebereich (Definitionsbereich) des Schlüssels von $ h_1 $ und der Wertebereich (Wertebereich) des Index sind beide "[0, ..., m-1]".

Das Berechnungsverfahren für diese Funktion wird auch wie folgt ausgedrückt [FG 00].

s = phi * n
x = fractional part of s
h_1(n) = floor(m*x)

Keiner von beiden enthält $ + 1 $, das in Mercaris Hash-Funktion hinzugefügt wurde, aber im Folgenden betrachten wir es als $ h_1 (n) $, ohne 1 hinzuzufügen.

Die Python-Implementierung des Multiplikator-Hash (reelle Zahl) ist unten dargestellt.

multihash1.py


import math

def kmh(n, phi, tablesize): # Knuth's multiplicative hash
    """
    defined in a handout on hash functions 
    classes.engineering.wustl.edu/cse241/handouts/hash-functions.pdf
    """
    return int(math.floor(tablesize * (phi * n - math.floor(phi * n))))

#def mmh(n, prime, tablesize): # Mercari's multiplicative hash
#    return ((n * prime) % tablesize) + 1

def main():
    phis = [0.5*(math.sqrt(5)-1.0), 0.5*math.sqrt(2), math.sqrt(3)-1.0] # 1st: the golden ratio
    for phi in phis:
        for v in range(2, 6): # tablesize = 4, 8, 16, 32
            print 
            tablesize = 2**v
            kmhvals = [kmh(x, phi, tablesize) for x in range(tablesize)]
            print kmhvals
            if (len(list(set(kmhvals))) != len(kmhvals)):
                print "collision found (phi:", phi, "tablesize:", tablesize, ")"
                #kmhvals.sort()
                kmhset = set(kmhvals)
                print "indices", kmhvals
                missed = sorted(list(set([x for x in range(tablesize)]).difference(kmhset)))
                print "missed indices", missed
            else: print "perfect (phi:", phi, "tablesize:", tablesize, ")"

main()

Ausgabe für jede Kombination der Tabellengröße $ m = 4, 8, 16, 32, \ phi = (\ sqrt {5} -1) / 2, \ sqrt {2} / 2, \ sqrt {3} -1 $ Die Ergebnisse zeigen einige der Indexkonflikte.

multihash1.txt


indices [0, 9, 3, 13, 7, 1, 11, 5, 15, 8, 2, 12, 6, 0, 10, 4]
collision found (phi: 0.61803398875 tablesize: 16 )
missed indices [14]

indices [0, 19, 7, 27, 15, 2, 22, 10, 30, 17, 5, 25, 13, 1, 20, 8, 28, 16, 3, 23, 11, 31, 19, 6, 26, 14, 2, 21, 9, 29, 17, 5]
collision found (phi: 0.61803398875 tablesize: 32 )
missed indices [4, 12, 18, 24]

indices [0, 2, 1, 0]
collision found (phi: 0.707106781187 tablesize: 4 )
missed indices [3]

indices [0, 2, 1, 0]
collision found (phi: 0.732050807569 tablesize: 4 )
missed indices [3]

multihash1.py ist gefundene Kollision (ph i, Tabellengröße), Liste [0, ..., m-1], wenn Indizes mit einer bestimmten Kombination von $ m $ und $ \ phi $ kollidieren. Listet die Indizes für auf und zeigt die Werte an, die aufgrund der Kollision nicht im Index angezeigt wurden.

Das Multiplizieren von Hashes (reelle Werte) verursachte Indexkollisionen. Es ist jedoch wichtig zu beachten, dass Rundungsfehler bei diesen Berechnungen mit reellen Werten zu falschen Ergebnissen führen können. Daher multiplizieren Sie Hashes ohne Rundungsfehler (reelle Werte). Integer-Wert) wird implementiert und verglichen.

Multiplikator-Hash (ganzzahliger Wert)

Basierend auf Seite 6 von [DD 09] definieren wir einen multiplikativen Hash, der nur mit ganzzahligen Werten berechnet wird.

** Definition 3 ** Bei gegebener Tabellengröße $ 2 ^ r = m $, ungerade $ a $ befriedigende Wortbitlänge $ w $, $ 2 ^ {w-1} <a <2 ^ {w} $ ** Der Multiplikator-Hash (ganzzahliger Wert) ** sei $ h_2 (n) = (ein \ mod 2 ^ w) \ gg (w - r) $. $ T \ gg s $ ist jedoch $ Stellt eine Operation dar, die t $ um $ s $ nach rechts verschiebt.

$ a $ entspricht $ \ phi $ im Multiplikator-Hash (reelle Zahl), und eine ungerade Zahl, die weder $ 2 ^ {w - 1} $ noch $ 2 ^ w $ sehr nahe kommt [DD 09] ..

Die Beziehung zwischen dem Multiplikations-Hash (reeller Wert) und dem Multiplikations-Hash (ganzzahliger Wert) wird auf Seite 5 von [Weiss 14] erläutert.

Hier werden der Multiplikations-Hash (reeller Wert) und der Multiplikations-Hash (ganzzahliger Wert) durch ein Computerexperiment verglichen. Indizes unter denselben Bedingungen werden nebeneinander angezeigt und es wird bestätigt, ob ein Fehler im Multiplikations-Hash (reeller Wert) aufgetreten ist. Der Python-Code wird unten gezeigt.

multihash2.py


import math

def kmh2(n, a, r, w): # Knuth's multiplicative hash
    """
    defined in a handout of lecture 5 Hashing 1
    http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture05.pdf
    """
    return ((a * n) % 2**w) >> (w-r)

def kmh(n, phi, tablesize): # Knuth's multiplicative hash
    """
    defined in a handout on hash functions 
    classes.engineering.wustl.edu/cse241/handouts/hash-functions.pdf
    """
    return int(math.floor(tablesize * (phi * n - math.floor(phi * n))))

def mmh(n, prime, tablesize): # Mercari's multiplicative hash
    return ((n * prime) % tablesize) + 1

def main():
    phis = [0.5*(math.sqrt(5)-1.0), 0.5*math.sqrt(2), math.sqrt(3)-1.0] # 1st: the golden ratio
    w = 16
    for phi in phis:
        a = 2*int(2**(w-1)*phi)+1
        for v in range(2, 6):
            print "======="
            tablesize = 2**v
            kmhvals = [kmh(x, phi, tablesize) for x in range(tablesize)]
            kmh2vals = [kmh2(x, a, v, w) for x in range(tablesize)]
            print kmhvals
            print kmh2vals

main()

Das Ergebnis der Ausführung dieses Codes ist unten dargestellt.

multihash2.txt


[0, 2, 0, 3]
[0, 2, 0, 3]
=======
[0, 4, 1, 6, 3, 0, 5, 2]
[0, 4, 1, 6, 3, 0, 5, 2]
=======
[0, 9, 3, 13, 7, 1, 11, 5, 15, 8, 2, 12, 6, 0, 10, 4]
[0, 9, 3, 13, 7, 1, 11, 5, 15, 8, 2, 12, 6, 0, 10, 4]
=======
[0, 19, 7, 27, 15, 2, 22, 10, 30, 17, 5, 25, 13, 1, 20, 8, 28, 16, 3, 23, 11, 31, 19, 6, 26, 14, 2, 21, 9, 29, 17, 5]
[0, 19, 7, 27, 15, 2, 22, 10, 30, 17, 5, 25, 13, 1, 20, 8, 28, 16, 3, 23, 11, 31, 19, 6, 26, 14, 2, 21, 9, 29, 17, 5]
=======
[0, 2, 1, 0]
[0, 2, 1, 0]
=======
[0, 5, 3, 0, 6, 4, 1, 7]
[0, 5, 3, 0, 6, 4, 1, 7]
=======
[0, 11, 6, 1, 13, 8, 3, 15, 10, 5, 1, 12, 7, 3, 14, 9]
[0, 11, 6, 1, 13, 8, 3, 15, 10, 5, 1, 12, 7, 3, 14, 9]
=======
[0, 22, 13, 3, 26, 17, 7, 30, 21, 11, 2, 24, 15, 6, 28, 19, 10, 0, 23, 13, 4, 27, 17, 8, 31, 21, 12, 2, 25, 16, 6, 29]
[0, 22, 13, 3, 26, 17, 7, 30, 21, 11, 2, 24, 15, 6, 28, 19, 10, 0, 23, 13, 4, 27, 17, 8, 31, 21, 12, 2, 25, 16, 6, 29]
=======
[0, 2, 1, 0]
[0, 2, 1, 0]
=======
[0, 5, 3, 1, 7, 5, 3, 0]
[0, 5, 3, 1, 7, 5, 3, 0]
=======
[0, 11, 7, 3, 14, 10, 6, 1, 13, 9, 5, 0, 12, 8, 3, 15]
[0, 11, 7, 3, 14, 10, 6, 1, 13, 9, 5, 0, 12, 8, 3, 15]
=======
[0, 23, 14, 6, 29, 21, 12, 3, 27, 18, 10, 1, 25, 16, 7, 31, 22, 14, 5, 29, 20, 11, 3, 26, 18, 9, 1, 24, 15, 7, 30, 22]
[0, 23, 14, 6, 29, 21, 12, 3, 27, 18, 10, 1, 25, 16, 7, 31, 22, 14, 5, 29, 20, 11, 3, 26, 18, 9, 1, 24, 15, 7, 30, 22]

In den Variableneinstellungen, die ich mit diesem Code versucht habe, haben der Multiplikator-Hash (reeller Wert) und der Multiplikator-Hash (ganzzahliger Wert) denselben Index zurückgegeben und denselben Konflikt verursacht.

** Satz 3 ** multiplikativer Hash ist nicht perfekt.

Wenn man sich die Indexliste "multihash2.txt" ansieht, gibt es außerdem Stellen, an denen Quoten und gerade Zahlen nacheinander erscheinen, und Satz 2 gilt nicht für $ h_1 (n), h_2 (n) $. $ H_1 (n), h_2 (n) $ wird als Opfer der Vollständigkeit wahrgenommen, während die Streuung des Index erhöht wird.

Die Unterschiede zwischen der Mercari-Hash-Funktion $ f (n) $ und dem Multiplikator-Hash (ganzzahliger Wert) $ h_2 (n) $ können in den folgenden zwei Punkten zusammengefasst werden.

Schließlich

Blinddarm

** Beweis von Ergänzung 1 ** Beweisen Sie durch Absurdität. Für einige $ n, n '$ nehmen Sie $ g (n) = g (n') $ an. Dann,

\begin{eqnarray*}
g(n')-g(n)
&=&(an' - an)\mod m\\
&=&a(n'-n)\mod m\\
&=&0
\end{eqnarray*}

Da $ a und m $ Primzahlen zueinander sind, muss $ n'-n $ ein Vielfaches von $ m $ sein, um diesen Unterschied 0 zu machen. Jedoch $ n, n '$ Aus der Definition von $ 0 <n'-n <m $. Daher gibt es kein solches Paar von $ n, n '$. $ \ Box $

** Ein weiterer Beweis von Anhang 1 ** Das inverse Element von $ p $ unter der Methode $ m $ wird als $ p ^ {-1} $ geschrieben. $ N \ neq n '(0 \ leq n, n' \ Für leq m-1) $ wird angenommen, dass $ f (n) = f (n ') $ gilt.

\begin{eqnarray*}
n\mod m
&=&
(p^{-1}np)\mod m\\
&=&
(p^{-1}f(n)\mod m)\\
&=&
(p^{-1}f(n')\mod m)\\
&=&
(p^{-1}n'p)\mod m\\
&=&
n'\mod m
\end{eqnarray*}

Ab $ n = n '$ gilt, was der Wahl von $ n, n' $ widerspricht. Daher ist die Annahme falsch. $ \ Box $

** Beweis von Satz 1 ** Mit der Funktion $ g (n) $ von Anhang 1 können Sie $ f (n) = g (n) + 1 $ schreiben. Da der Definitionsbereich jedoch unterschiedlich ist, ist $ f (m) Sei = g (0) $. $ F $ und $ g $ haben eine Eins-zu-Eins-Entsprechung mit unterschiedlichen $ g (n) $ -Werten für unterschiedliche $ n (0 \ leq n \ leq m-1) $ Für verschiedene $ n (1 \ leq n \ leq m) $ nimmt $ f (n) $ auch unterschiedliche Werte an, wie wir aus Anhang 1 wissen, um zurückzukehren. $ \ Box $

** Nachweis von System 1 ** Aus dem Zustand von Anhang 1 löschen. $ \ Box $

** Beweis von Satz 2 ** Sei $ q $ eine positive ganze Zahl, die $ p = 2q + 1 $ erfüllt.

(1) Wenn $ n $ ungerade ist. $ k $ ist eine ganze Zahl, die $ n = 2k + 1 $ erfüllt ($ 0 \ leq k <m / 2 $). Das Folgende gilt für $ f (2k + 1) $.

\begin{eqnarray*}
f(2k+1) 
&=& ((2k+1)(2q+1)) \mod m + 1\\
&=& (4kq \mod m)+(2(k+q) \mod m) + (1 \mod m) + 1\\
&=& (4kq \mod m)+(2(k+q) \mod m) + 2.
\end{eqnarray*}

Da sowohl $ 4kq $ als auch $ 2 (k + q) $ gerade sind, ist der Rest von $ m $ für sie ebenfalls gerade, und $ f (2k + 1) $, was die Summe von gerade ist, ist gerade.

(2) Wenn $ n $ gerade ist. $ k $ ist eine ganze Zahl, die $ n = 2k $ erfüllt ($ 0 <k \ leq m / 2 $). Das Folgende gilt für $ f (2k) $.

\begin{eqnarray*}
f(2k) 
&=& (2k(2q+1)) \mod m + 1\\
&=&  (4kq \mod m)+(2k \mod m)  + 1.
\end{eqnarray*}

Da $ 4kq und 2k $ beide gerade sind, ist auch der Rest dieser $ m $ gerade, und $ f (2k) $, die Summe aus ihnen und 1, ist ungerade. $ \ Box $

** Beweis von Satz 3 ** Beweisen Sie durch das Gegenbeispiel, das aus dem obigen Computerexperiment erhalten wurde. $ R = 2, m = 4, w = 16, a = 2 \ cdot \ lfloor 2 ^ {w-1} (\ sqrt {5} -1) / 2) \ rfloor + 1 = 40503 $. Zu diesem Zeitpunkt ist $ h_2 (0) = h_2 (2) = 0 $ und die Indizes kollidieren. Außerdem ist $ a $ eine Primzahl. Selbst wenn Sie es durch $ 40507 $ ersetzen, ist $ h_2 (0) = h_2 (2) = 0 $. $ \ Box $

Verweise

Die gesamte Literatur im Internet wurde vom 29. bis 31. August 2017 durchsucht. Außerdem wurde [Knuth 73] nicht durchsucht.

[Buhler 15] Buhler, J. Choosing hash functions, handout of CSE 241 (Algorithms and Data Structures), Dept. Computer Science and Engineering, Washington University in St. Louis, https://classes.engineering.wustl.edu/cse241/handouts/hash-functions.pdf, 2015.

[DD 09] Devadas, S. and Daskalakis, K. Hashing I: Chaining, Hash Functions, Handout of 6.006 (Introduction to Algorithms), Dept Electrical Engineering and Computer Science, Massachusetts Institute of Technology, https://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture05.pdf, 2009.

[FG 00] Fleck, M. and Kuenning, G. Hash Functions, Note for CS 70 (Data Structures and Program Development), Dept. Computer Science, Harvey Mudd College, https://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200101/homework10/hashfuncs.html, 2000.

[Knuth 73] Knuth, D. The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, 1973.

[metal_unk 07] metal_unk, Beweis, dass der multiplikative Knuth-Hash die kleinste vollständige Hash-Funktion ist, Mercari Tech Blog, http://tech.mercari.com/entry/2017/08/29/115047.

[mather314 17] mather314, Hatena Lesezeichen Kommentar, http://b.hatena.ne.jp/mather314/20170829#bookmark-344131614, 2017.

[Rauchen186 17] Rauchen186, Hatena-Lesezeichen-Kommentar, http://b.hatena.ne.jp/smoking186/20170829#bookmark-344131614, 2017.

[Weiss 14] Weiss, S. Chapter 5: Hashing and Hash Tables, Handout of CSci 335 (Software Design and Analysis III), Dept. Computer Science, Hunter College of the City University of New York, http://compsci.hunter.cuny.edu/~sweiss/course_materials/csci335/lecture_notes/chapter05.pdf, 2014.

Recommended Posts

multiplikativer Hash ist nicht perfekt (zertifiziert)
Python-Runde ist nicht streng rund
Ist time.time () nicht sehr genau?
TypeError: Das Objekt 'int' kann nicht tiefgestellt werden
NameError: Name '__ Datei__' ist nicht definiert