le hachage multiplicatif n'est pas parfait (certifié)

Aperçu

Remarque

introduction

Sur le blog de Mercari, il y a une entrée [metal_unk 17] qui prouve que le hachage multiplicatif de Knuth est la fonction de hachage la moins complète, montrant la preuve que le hachage multiplicatif de Knuth est le moins complet.

J'ai lu cette entrée avec beaucoup d'intérêt car les fonctions de hachage pratiques sont généralement décrites comme provoquant des collisions d'index [Weiss 14]. Jusqu'à présent, j'ai trouvé trois choses:

Concernant le premier point, dans le commentaire du signet Hatena,

C'est la même chose que ce que je fais, mais il semble que "prime et max sont des éléments l'un de l'autre, donc il y a un élément inverse de prime sous la méthode max. Par conséquent, tous les plans uniques".

[fumer186 17]

Cela ressemble à f (n) = ((n * PRIME) mod MAX) + 1. Puisqu'il existe une source inversée de PRIME dans le mod MAX, tous les plans uniques sont évidents. De plus, même si la restaurabilité est une exigence (car si l'élément inversé n'est pas dans la plage de définition, vous pouvez le lire), il n'est pas nécessaire qu'il soit plein.

Certaines personnes, comme [mather314 17], comprennent que c'est explicite. Au début, je ne pouvais pas le comprendre à partir de l'entrée de blog ou de ce commentaire de signet seul, alors j'aimerais le comprendre par moi-même. J'ai écrit une preuve sans utiliser, mais après cela, j'ai pu rédiger une preuve concise basée sur ces commentaires.

En ce qui concerne le deuxième point, la définition du hachage multiplicatif est grossièrement divisée en deux types: les procédures qui utilisent des opérations sur les nombres réels (ci-après dénommées hachage de multiplication (valeur réelle)) et les procédures qui utilisent des opérations sur des nombres entiers et des opérations de décalage de bits (ci-après, hachage de multiplication). (Appelé (valeur entière)). Les deux, contrairement à la fonction de hachage de Mercari, ont été confirmés par des expériences informatiques pour renvoyer le résultat de la collision d'index. Cependant, reportez-vous au livre original de Knuth [Knuth 73]. Comme il n'y avait aucun moyen de le faire, j'ai complété le hachage multiplicatif avec des supports de cours de différents auteurs. Comme j'ai lu ces parties dans un patchwork, il peut contenir des explications incorrectes en raison d'une compréhension incohérente. Veuillez faire attention au sexe.

Pour le troisième point, en utilisant le code Python implémenté et les résultats d'exécution, nous montrons que le hachage multiplicatif n'est pas parfait à partir de l'exemple concret de collision, ce qui fait de la fonction de hachage de Mercari essentiellement un hachage multiplicatif. Vous pouvez voir que c'est différent.

Si vous trouvez des erreurs dans la description, veuillez le signaler. Merci.

Fonction de hachage de Mercari

** Définition 1 ** $ p $ est un nombre premier supérieur ou égal à 3, $ m $ est une puissance de 2 représentant la taille de la table de la fonction de hachage ($ m = 2 ^ r $ en utilisant un entier positif $ r $), respectivement. À ce stade, la valeur de clé $ n $ est convertie en un index ** La fonction de hachage de Mercari ** $ f (n) $ est définie comme suit.

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

La plage de valeurs (plage de définition) de la clé de $ f $ et la plage de valeurs (plage de valeurs) de l'index sont toutes deux «[1, ..., m]».

** Addendum 1 ** Soit $ a et m $ des entiers positifs mutuellement premiers. Pour $ 0 \ leq n \ le m-1 $, soit $ g (n) = an \ mod m $. Pour un ensemble de $ n, n '$ ($ 0 \ leq n <n' \ leq m-1 $), cela devient $ g (n) \ neq g (n ') $.

** Proposition 1 ** Pour deux clés différentes arbitrairement données $ n, n '(1 \ leq n, n' \ leq m, n \ neq n ') $, fonction de hachage de Mercari Cela devient $ f (n) \ neq f (n ') $.

** Série 1 ** Dans la fonction de hachage de Mercari $ f $, $ f $ est un seul coup tant que $ a et m $ sont premiers l'un par rapport à l'autre.

Et la fonction de hachage Mercari $ f (n) $ a les caractéristiques suivantes. ** Proposition 2 ** Lorsque la clé $ n $ est impaire, $ f (n) $ est pair, et lorsque $ n $ est pair, $ f (n) $ est impair.

Expliquez la signification de la proposition 2. Lors de la copie d'un ensemble d'index vers un ensemble de clés, la fonction de hachage de Mercari sépare les deux sous-ensembles d'index en deux sous-ensembles de chaque clé. Le code suivant génère l'index de la fonction de hachage de Mercari pour $ a = 40507 $, la taille de la table $ m = 16 $ et l'index du hachage de multiplication (valeur entière) dans les mêmes conditions de comparaison.

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()

Le résultat de l'exécution est le suivant.

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]

Les résultats de cette expérience sont présentés dans la figure suivante. Cependant, les clés et les index sont classés séparément par cotes et égales. Les clés et index dans lesquels la collision s'est produite sont remplis de la même couleur (rouge, vert). La flèche qui représente est représentée par une ligne épaisse. L'index qui n'est converti à partir d'aucune clé est rempli en bleu clair.

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

La proposition 2 montre qu'aucune valeur de clé ne dépasse la limite entre les index pairs et impairs. Pour le hachage de multiplication (valeur entière) décrit plus loin, la proposition 2 ne tient pas et les clés sont dispersées. Vous pouvez le voir sur la figure.

De plus, la fonction de hachage de Mercari a le même modèle pour les correspondances impaires et paires d'index à clé. Le modèle de l'exemple précédent est illustré dans la figure suivante. L'index et la paire de clés sont remplis de la même couleur.

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

La fonction de hachage de Mercari augmente toujours la valeur de l'index de 2p $ lorsque la valeur de la clé augmente de 2, de sorte qu'un tel modèle apparaît toujours, et en alignant correctement la première valeur de l'index, de l'index à la clé dans le nombre impair. La correspondance de peut être mise en correspondance avec la correspondance de pair.

hachage multiplicatif

Hachage multiplicateur (nombre réel)

Tout d'abord, un hachage multiplicateur (valeur réelle) est défini sur la base du matériel didactique [Burler 15].

** Définition 2 ** $ m $ est la taille de la table de la fonction de hachage, $ \ phi $ est un nombre réel entre 0 et 1. ** Multiplier le hachage (nombre réel) pour la clé $ n $ ** $ h_1 (n) ) $ Est défini comme suit.

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

La valeur de $ \ phi $ est le nombre d'or recommandé par Knuth $ (\ sqrt {5} -1) / 2 $, $ \ sqrt {2} / 2 $, $ \ sqrt {3} -1 $ Des nombres déraisonnables sont souvent utilisés [Burler 15].

La plage de valeurs (plage de définition) de la clé de $ h_1 $ et la plage de valeurs (plage de valeurs) de l'index sont toutes deux «[0, ..., m-1]».

La procédure de calcul de cette fonction s'exprime également comme suit [FG 00].

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

Aucun d'eux n'inclut $ + 1 $ ajouté dans la fonction de hachage de Mercari, mais dans ce qui suit, nous le considérons comme $ h_1 (n) $ sans ajouter 1.

L'implémentation Python du hachage multiplicateur (nombre réel) est illustrée ci-dessous.

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()

Sortie pour chaque combinaison de taille de table $ m = 4, 8, 16, 32, \ phi = (\ sqrt {5} -1) / 2, \ sqrt {2} / 2, \ sqrt {3} -1 $ Les résultats montrent certains des conflits d'index.

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 est unecollision trouvée (ph i, taille de la table), list [0, ..., m-1] lorsque les index entrent en collision avec une certaine combinaison de $ m $ et $ \ phi $. Répertorie les index pour et affiche les valeurs qui n'apparaissaient pas dans l'index en raison de la collision.

La multiplication des hachages (valeurs réelles) entraînait des collisions d'index, mais il est important de noter que les erreurs d'arrondi peuvent entraîner des résultats incorrects dans ces calculs utilisant des valeurs réelles. Par conséquent, multiplier les hachages sans erreurs d'arrondi (valeurs réelles) Integer value) est implémentée et comparée.

Multiplier le hachage (valeur entière)

Basé sur la page 6 de [DD 09], nous définissons un hachage multiplicatif qui ne calcule qu'avec des valeurs entières.

** Définition 3 ** Etant donné la taille de la table $ 2 ^ r = m $, impaire $ a $ longueur en bits du mot satisfaisant $ w $, $ 2 ^ {w-1} <a <2 ^ {w} $ respectivement ** Soit le hachage multiplicateur (valeur entière) ** $ h_2 (n) = (an \ mod 2 ^ w) \ gg (w - r) $. Cependant, $ t \ gg s $ est $ Représente une opération qui décale t $ vers la droite de $ s $.

$ a $ correspond à $ \ phi $ dans le hachage multiplicateur (nombre réel), et un nombre impair qui n'est pas très proche de $ 2 ^ {w − 1} $ ou $ 2 ^ w $ est recommandé [DD 09] ..

La relation entre le hachage de multiplication (valeur réelle) et le hachage de multiplication (valeur entière) est expliquée à partir de la page 5 de [Weiss 14].

Ici, le hachage de multiplication (valeur réelle) et le hachage de multiplication (valeur entière) sont comparés par une expérience informatique. Les index dans les mêmes conditions sont affichés côte à côte, et il est confirmé si une erreur s'est produite dans le hachage de multiplication (valeur réelle). Le code Python est illustré ci-dessous.

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()

Le résultat de l'exécution de ce code est indiqué ci-dessous.

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]

Dans les paramètres de variable que j'ai essayés avec ce code, le hachage du multiplicateur (valeur réelle) et le hachage du multiplicateur (valeur entière) ont renvoyé le même index et ont provoqué le même conflit.

** Proposition 3 ** Le hachage multiplicatif n'est pas parfait.

De plus, en regardant la liste des index multihash2.txt, il y a des endroits où les cotes et les nombres pairs apparaissent successivement, et la proposition 2 ne vaut pas pour $ h_1 (n) et h_2 (n) $. $ H_1 (n), h_2 (n) $ est perçu comme sacrifiant l'exhaustivité tout en augmentant la dispersion de l'indice.

Les différences entre la fonction de hachage de Mercari $ f (n) $ et le hachage multiplicateur (valeur entière) $ h_2 (n) $ peuvent être résumées dans les deux points suivants.

finalement

appendice

** Preuve du supplément 1 ** Prouver par absurdité. Pour certains $ n, n '$, supposons $ g (n) = g (n') $. Ensuite,

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

Puisque $ a et m $ sont premiers l'un par rapport à l'autre, $ n'-n $ doit être un multiple de $ m $ pour que cette différence soit nulle. Cependant, $ n, n '$ D'après la définition de $ 0 <n'-n <m $. Par conséquent, il n'y a pas de telle paire de $ n, n '$. $ \ Box $

** Une autre preuve de l'annexe 1 ** L'élément inverse de $ p $ sous la méthode $ m $ s'écrit $ p ^ {-1} $. $ N \ neq n '(0 \ leq n, n' \ Pour leq m-1) $, supposons que $ f (n) = f (n ') $ est valable. À ce stade,

\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*}

De $ n = n '$ tient, ce qui est contraire au choix de $ n, n' $. Par conséquent, l'hypothèse est incorrecte. $ \ Box $

** Preuve de la proposition 1 ** En utilisant la fonction $ g (n) $ du Supplément 1, vous pouvez écrire $ f (n) = g (n) + 1 $. Cependant, comme la zone de définition est différente, $ f (m) Soit = g (0) $. $ F $ et $ g $ une correspondance biunivoque, avec des valeurs $ g (n) $ différentes pour différents $ n (0 \ leq n \ leq m-1) $ Pour différents $ n (1 \ leq n \ leq m) $, $ f (n) $ prend également des valeurs différentes, comme nous le savons de l'annexe 1 à renvoyer. $ \ Box $

** Preuve du système 1 ** Effacer de la condition du supplément 1. $ \ Box $

** Preuve de la proposition 2 ** Soit $ q $ un entier positif qui satisfait $ p = 2q + 1 $.

(1) Quand $ n $ est impair. $ k $ est un entier qui satisfait $ n = 2k + 1 $ ($ 0 \ leq k <m / 2 $). Ce qui suit vaut pour $ 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*}

Puisque les deux $ 4kq $ et $ 2 (k + q) $ sont pairs, le reste de $ m $ pour eux est également pair, et $ f (2k + 1) $, qui est la somme de pair, est pair.

(2) Lorsque $ n $ est pair. $ k $ est un entier qui satisfait $ n = 2k $ ($ 0 <k \ leq m / 2 $). Ce qui suit vaut pour $ f (2k) $.

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

Puisque $ 4kq et 2k $ sont tous les deux pairs, le reste de ces $ m $ est également pair, et $ f (2k) $, qui est la somme d'entre eux et 1, est impair. $ \ Box $

** Preuve de la proposition 3 ** Prouver par le contre-exemple obtenu à partir de l'expérience informatique ci-dessus. $ R = 2, m = 4, w = 16, a = 2 \ cdot \ lfloor 2 ^ {w-1} (\ sqrt {5} -1) / 2) \ rfloor + 1 = 40503 $. À ce moment, $ h_2 (0) = h_2 (2) = 0 $ et les index entrent en collision. De plus, $ a $ est un nombre premier. Même si vous le remplacez par $ 40507 $, $ h_2 (0) = h_2 (2) = 0 $. $ \ Box $

Les références

Toute la littérature sur le net a été parcourue du 29 au 31 août 2017. De plus, [Knuth 73] n'a pas été parcouru.

[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, Preuve que le hachage multiplicatif Knuth est la plus petite fonction de hachage complète, Mercari Tech Blog, http://tech.mercari.com/entry/2017/08/29/115047.

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

[smoking186 17] smoking186, Hatena Bookmark Comment, 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

le hachage multiplicatif n'est pas parfait (certifié)
Le rond de Python n'est pas strictement rond
Time.time () n'est-il pas très précis?
TypeError: l'objet 'int' n'est pas en indice
La liste Python n'est pas une liste
NameError: le nom '__ fichier__' n'est pas défini