Pourquoi une recherche de table de hachage (sans collision) est-elle vraiment O (1)?

10

Avertissement: je sais qu'il y a déjà des questions de sondage similaires ici et sur Stackoverflow. Mais ce sont toutes des collisions, ce qui n'est pas ce que je demande.

Ma question est: pourquoi est par collision moins lookup O(1)en premier lieu?

Supposons que j'ai cette table de hachage:

Hash  Content
-------------
ghdjg Data1
hgdzs Data2
eruit Data3
xcnvb Data4
mkwer Data5
rtzww Data6

Maintenant, je cherche la clé kh(k)donne la fonction de hachage h(k) = mkwer. Mais comment la recherche "sait" que le hachage mkwerest en position 5? Pourquoi ne doit-il pas faire défiler toutes les touches O(n)pour le trouver? Les hachages ne peuvent pas être de véritables adresses matérielles car je perdrais la capacité de déplacer les données. Et pour autant que je sache, la table de hachage n'est pas triée sur les hachages (même si c'était le cas, la recherche prendrait également O(log n))?

En quoi la connaissance d'un hachage aide-t-elle à trouver la bonne place dans la table?

Foo Bar
la source

Réponses:

24

La fonction de hachage ne renvoie pas de chaîne telle que mkwer. Il renvoie directement la position de l'élément dans le tableau. Si, par exemple, votre table de hachage a dix entrées, la fonction de hachage renverra un entier compris entre 0 et 9.

David Richerby
la source
1
Merci. :) Mon erreur était de penser à une fonction de hachage de table de hachage comme MD5 ou SHA. Mais un hachage peut bien sûr être une position entière, à laquelle je n'ai pas pensé. Maintenant que je sais quoi chercher, j'ai même rapidement trouvé un bon exemple: la fonction de hachage de PHP: github.com/php/php-src/blob/PHP-5.6.10/Zend/zend_hash.h#L237
Foo Bar
13
@FooBar: MD5 et SHA calculent également des nombres simples à partir de l'entrée, il est tellement courant de parler des hachages sous forme hexadécimale. Tout comme les adresses mémoire sont rarement considérées en décimal.
nperson325681
4
De plus, MD5, etc. sont trop longs pour être utilisés directement comme index de tableau. Il serait possible d'utiliser une partie du hachage, comme les n bits inférieurs .
chirlu
6

La fonction de hachage calcule la position du tableau à partir d'une chaîne donnée . Si c'est un hachage parfait, cela signifie qu'il n'y a certainement pas de collisions, le tableau est probablement au moins deux fois plus grand que le nombre d'éléments.

Par exemple, je donnerai un hachage très médiocre pour les lettres, juste pour illustrer le mécanisme:
0) 1) pour chaque caractère de la chaîne, prendre la valeur ascii, soustraire «a» s'il est en minuscules, soustraire «A» si les majuscules, ajouter la valeur à x. 2) le nombre résultant, par exemple 15 est l'indice du tableau. x = x m o d 52x=0;
x=xmod52

Ce hachage très simple (limité et sujet aux collisions) diffère des autres hachages par le mécanisme de hachage, ne tient pas compte de l'entrée donnée. Dans un schéma plus avancé, le hachage est un plus grand nombre, ajusté au nombre d'éléments. Un hachage parfait est généré pour toutes les entrées afin de garantir l'absence de collisions.

Il s'agit de car le calcul du hachage à partir d'une chaîne dépend de la sophistication de la fonction calculée, mais ne dépend pas du nombre d'éléments.O(1)

En cas de hachage parfait, lorsque des éléments sont ajoutés, est recalculé, le cas le plus simple avec des collisions lorsque la charge du tableau est grande, la taille du tableau augmente, la fonction prend un plus grand module de sortie et les éléments sont déplacés vers les nouveaux emplacements.h(k)

Le tableau est un fragment de mémoire continue, pour obtenir le élément, vous prenez l'adresse du premier élément (début du tableau), puis vous ajoutez à cette adresse pour avoir une cellule de mémoire explicite.n * ( de i z e o f e l e m e n t )nthn(sizeofelement)

Mal
la source
1
Et comment la recherche sait-elle où se trouve le hachage dans la table? Ce ne sont ni des adresses ordonnées ni matérielles.
Foo Bar
Vous donnez une chaîne, par exemple "xcnvb", pour que le hachage calculé donne l'indice du tableau, "xcnvb" est votre élément à rechercher, 8 est l'index dans la table. Il est ordonné par signe de tête, le hachage renvoie la place pour récupérer l'élément. Cet élément a été mis là par la même fonction. Le matériel n'a rien à voir ici. Vous fournissez un tableau, une fonction de hachage et un hachage de calcul pour obtenir l'index dans le tableau, de même pour la récupération. Le tableau n'est pas trié, il n'est également jamais plein. h("xcnvb")=8
Evil
Mais tous les index ne seront pas remplis. Si les hachages 1, 4, 8, 90 et 223 sont remplis de données, comment une recherche trouve-t-elle le bon endroit? Dans ce cas, l'index "90" est en position 4 car la plupart des autres index n'existent pas. Et une table de hachage vide n'est pas de taille infinie ayant toutes les positions possibles!?
Foo Bar
Oui, le tableau nous permet de supposer 512 éléments de long, 9 bits utilisés pour la fonction de hachage, et vous n'avez que 4 éléments. L'index 90 a la position 90 dans le tableau, comme dans l'exemple - presque toutes les cellules sont vides. Si votre tableau est vous l' = vos données pour "xcnvb"HaHa(h("xcnvb"))=Ha[90]
Evil
La fonction de hachage ne renvoie pas d'index dans le tableau. Au lieu de cela, il renvoie un nombre prévisible qui peut être mappé dans le tableau. Cela se fait généralement en utilisant l' opérateur de module avec le nombre de compartiments de table de hachage comme l'autre opérande.
Christopher Schultz
3

Pour développer la réponse de David Richerby, le terme " fonction de hachage " est un peu surchargé. Souvent, lorsque nous parlons d'une fonction de hachage, nous pensons à MD5, SHA-1, ou quelque chose comme la .hashCode()méthode Java , qui transforme certaines entrées en un seul nombre. Cependant, le domaine de ce nombre (c'est-à-dire la valeur maximale) a très peu de chances d'être de la même taille que la table de hachage dans laquelle vous essayez de stocker des données. (MD5 est de 16 octets, SHA-1 est de 20 octets et .hashCode()est un int- 4 octets).

Votre question porte donc sur la prochaine étape - une fois que nous avons une fonction de hachage qui peut mapper des entrées arbitraires sur des nombres, comment les placer dans une structure de données d'une taille particulière? Avec une autre fonction, également appelée "fonction de hachage"!

Un exemple trivial d'une telle fonction est modulo ; vous pouvez facilement mapper un certain nombre de tailles arbitraires à un index spécifique dans un tableau avec modulo. Ceci est introduit dans CLRS comme "la méthode de division":

Dans la méthode de division pour créer des fonctions de hachage, nous mappons une clé dans l'un des emplacements en prenant le reste de divisé par . Autrement dit, la fonction de hachage estkmkm

h(k)=k mod .m

...

Lors de l'utilisation de la méthode de division, nous évitons généralement certaines valeurs de . Par exemple, ne devrait pas être une puissance de 2, car si alors n'est que les bits de poids faible de .m m = 2 p h ( k ) p kmmm=2ph(k)pk

~ Introduction aux algorithmes, §11.3.1 - CLRS

Le modulo n'est donc pas une excellente fonction de hachage, car il limite les tailles que nous pouvons utiliser en toute sécurité pour notre structure de données sous-jacente. La section suivante présente une "méthode de multiplication" légèrement plus complexe, qui utilise également le modulo mais est avantageuse car "la valeur de n'est pas critique". Cependant, cela fonctionne mieux avec une connaissance préalable des «caractéristiques des données hachées» - quelque chose que nous ne savons souvent pas.m

Java HashMaputilise une version modifiée de la méthode de division qui effectue une étape de prétraitement pour tenir compte des .hashCode()implémentations faibles afin de pouvoir utiliser des tableaux de taille deux. Vous pouvez voir exactement ce qui se passe dans la .getEntry()méthode (les commentaires sont les miens):

 // hash() transforms key.hashCode() to protect against bad hash functions
 int hash = (key == null) ? 0 : hash(key.hashCode());
 // indexOf() converts the resulting hash to a value between 0 and table.length-1
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
     ...

Java 8 a apporté une réécriture HashMapqui est encore plus rapide, mais un peu plus difficile à lire. Il utilise cependant le même principe général pour la recherche d'index.

dimo414
la source