Les tables de hachage peuvent-elles vraiment être O (1)?

Il semble être de notoriété publique que les tables de hachage peuvent atteindre O (1), mais cela n'a jamais eu de sens pour moi. Quelqu'un peut-il l'expliquer? Voici deux situations qui me viennent à l'esprit:

A. La valeur est un entier plus petit que la taille de la table de hachage. Par conséquent, la valeur est son propre hachage, il n'y a donc pas de table de hachage. Mais s'il y en avait, ce serait O (1) et serait toujours inefficace.

B. Vous devez calculer un hachage de la valeur. Dans cette situation, l'ordre est O (n) pour la taille des données recherchées. La recherche peut être O (1) après avoir effectué le travail O (n), mais cela revient toujours à O (n) à mes yeux.

Et à moins que vous n'ayez un hachage parfait ou une grande table de hachage, il y a probablement plusieurs éléments par seau. Donc, cela se transforme de toute façon en une petite recherche linéaire à un moment donné.

Je pense que les tables de hachage sont géniales, mais je n'obtiens pas la désignation O (1) à moins qu'elle ne soit juste censée être théorique.

L' article de Wikipedia sur les tables de hachage fait systématiquement référence à un temps de recherche constant et ignore totalement le coût de la fonction de hachage. Est-ce vraiment une mesure juste?

Edit: Pour résumer ce que j'ai appris:

• C'est techniquement vrai parce que la fonction de hachage n'est pas obligée d'utiliser toutes les informations de la clé et pourrait donc être un temps constant, et parce qu'une table suffisamment grande peut ramener les collisions à un temps presque constant.

• C'est vrai en pratique, car au fil du temps, cela fonctionne aussi longtemps que la fonction de hachage et la taille de la table sont choisies pour minimiser les collisions, même si cela signifie souvent ne pas utiliser une fonction de hachage à temps constant.

Vous avez ici deux variables, m et n, où m est la longueur de l'entrée et n est le nombre d'éléments dans le hachage.

La revendication de performances de recherche O (1) fait au moins deux hypothèses:

• Vos objets peuvent être à égalité par rapport au temps O (1).
• Il y aura peu de collisions de hachage.

Si vos objets sont de taille variable et qu'un contrôle d'égalité nécessite de regarder tous les bits, les performances deviendront O (m). La fonction de hachage n'a cependant pas besoin d'être O (m) - elle peut être O (1). Contrairement à un hachage cryptographique, une fonction de hachage à utiliser dans un dictionnaire n'a pas besoin de regarder chaque bit de l'entrée pour calculer le hachage. Les implémentations sont libres de ne regarder qu'un nombre fixe de bits.

Pour suffisamment d'éléments, le nombre d'éléments deviendra supérieur au nombre de hachages possibles et vous obtiendrez alors des collisions provoquant une augmentation des performances au-dessus de O (1), par exemple O (n) pour un simple parcours de liste chaînée (ou O (n * m) si les deux hypothèses sont fausses).

En pratique, bien que l'allégation O (1), bien que techniquement fausse, soit approximativement vraie pour de nombreuses situations du monde réel, et en particulier les situations où les hypothèses ci-dessus sont valables.

Vous devez calculer le hachage, donc l'ordre est O (n) pour la taille des données recherchées. La recherche peut être O (1) après avoir effectué le travail O (n), mais cela revient toujours à O (n) à mes yeux.

Quoi? Le hachage d'un seul élément prend un temps constant. Pourquoi serait-ce autre chose? Si vous insérez des néléments, alors oui, vous devez calculer des nhachages, et cela prend du temps linéaire ... pour rechercher un élément, vous calculez un seul hachage de ce que vous recherchez, puis trouvez le compartiment approprié avec cela . Vous ne recalculez pas les hachages de tout ce qui se trouve déjà dans la table de hachage.

Et à moins que vous n'ayez un hachage parfait ou une grande table de hachage, il y a probablement plusieurs éléments par seau, donc cela se transforme de toute façon en une petite recherche linéaire à un moment donné.

Pas nécessairement. Les buckets ne doivent pas nécessairement être des listes ou des tableaux, ils peuvent être de n'importe quel type de conteneur, tel qu'un BST équilibré. Cela signifie le O(log n)pire des cas. Mais c'est pourquoi il est important de choisir une bonne fonction de hachage pour éviter de mettre trop d'éléments dans un même compartiment. Comme l'a souligné KennyTM, en moyenne, vous obtiendrez toujoursO(1) temps, même si vous devez parfois creuser dans un seau.

Le compromis des tables de hachage est bien sûr la complexité de l'espace. Vous échangez de l'espace contre du temps, ce qui semble être le cas habituel en informatique.

Vous mentionnez l'utilisation de chaînes comme clés dans l'un de vos autres commentaires. Vous êtes préoccupé par le temps qu'il faut pour calculer le hachage d'une chaîne, car il se compose de plusieurs caractères? Comme quelqu'un d'autre l'a encore souligné, vous n'avez pas nécessairement besoin de regarder tous les caractères pour calculer le hachage, bien que cela puisse produire un meilleur hachage si vous le faisiez. Dans ce cas, s'il y a en moyenne des mcaractères dans votre clé, et que vous les avez tous utilisés pour calculer votre hachage, alors je suppose que vous avez raison, ces recherches prendraient O(m). Si m >> nalors vous pourriez avoir un problème. Vous seriez probablement mieux avec un BST dans ce cas. Ou choisissez une fonction de hachage moins chère.

Le hachage est de taille fixe - la recherche du seau de hachage approprié est une opération à coût fixe. Cela signifie que c'est O (1).

Le calcul du hachage ne doit pas être une opération particulièrement coûteuse - nous ne parlons pas ici de fonctions de hachage cryptographique. Mais c'est par le passé. Le calcul de la fonction de hachage lui-même ne dépend pas du nombre n d'éléments; bien que cela puisse dépendre de la taille des données dans un élément, ce n'est pas ce à quoi n fait référence. Le calcul du hachage ne dépend donc pas de n et vaut également O (1).

Le hachage est O (1) uniquement s'il n'y a qu'un nombre constant de clés dans la table et que d'autres hypothèses sont faites. Mais dans de tels cas, cela présente un avantage.

Si votre clé a une représentation sur n bits, votre fonction de hachage peut utiliser 1, 2, ... n de ces bits. Penser à une fonction de hachage qui utilise 1 bit. L'évaluation est O (1) à coup sûr. Mais vous ne partitionnez que l'espace clé en 2. Vous mappez donc jusqu'à 2 ^ (n-1) clés dans le même bac. en utilisant la recherche BST, cela prend jusqu'à n-1 étapes pour localiser une clé particulière si elle est presque pleine.

Vous pouvez étendre cela pour voir que si votre fonction de hachage utilise K bits, votre taille de bac est de 2 ^ (nk).

donc fonction de hachage de K bits ==> pas plus de 2 ^ K bacs effectifs ==> jusqu'à 2 ^ (nK) clés de n bits par bac ==> (nK) étapes (BST) pour résoudre les collisions. En fait, la plupart des fonctions de hachage sont beaucoup moins "efficaces" et nécessitent / utilisent plus de K bits pour produire 2 ^ k bins. Donc même cela est optimiste.

Vous pouvez l'afficher de cette façon - vous aurez besoin de ~ n étapes pour être en mesure de distinguer de manière unique une paire de clés de n bits dans le pire des cas. Il n'y a vraiment aucun moyen de contourner cette limite de la théorie de l'information, table de hachage ou non.

Cependant, ce n'est PAS comment / quand vous utilisez la table de hachage!

L'analyse de complexité suppose que pour les clés à n bits, vous pouvez avoir O (2 ^ n) clés dans le tableau (par exemple 1/4 de toutes les clés possibles). Mais la plupart du temps, sinon tout le temps, nous utilisons une table de hachage, nous n'avons qu'un nombre constant de clés de n bits dans la table. Si vous voulez seulement un nombre constant de clés dans la table, disons que C est votre nombre maximum, alors vous pouvez former une table de hachage de bins O (C), qui garantit la collision constante attendue (avec une bonne fonction de hachage); et une fonction de hachage utilisant ~ logC des n bits de la clé. Ensuite, chaque requête est O (logC) = O (1). C'est ainsi que les gens prétendent que "l'accès à la table de hachage est O (1)" /

Il y a quelques captures ici - d'abord, dire que vous n'avez pas besoin de tous les bits peut être seulement une astuce de facturation. Tout d'abord, vous ne pouvez pas vraiment passer la valeur de clé à la fonction de hachage, car cela déplacerait n bits dans la mémoire qui est O (n). Vous devez donc faire par exemple un passage de référence. Mais vous devez toujours le stocker quelque part déjà, ce qui était une opération O (n); vous ne le facturez tout simplement pas au hachage; votre tâche de calcul globale ne peut pas éviter cela. Deuxièmement, vous faites le hachage, trouvez le bac et trouvez plus d'une clé; votre coût dépend de votre méthode de résolution - si vous faites une comparaison basée (BST ou List), vous aurez une opération O (n) (la clé de rappel est de n bits); si vous faites un deuxième hachage, eh bien, vous avez le même problème si le deuxième hachage a une collision.

Considérez l'alternative, par exemple BST, dans ce cas. il y a des clés C, donc un BST équilibré sera O (logC) en profondeur, donc une recherche prend des étapes O (logC). Cependant, la comparaison dans ce cas serait une opération O (n) ... il semble donc que le hachage soit un meilleur choix dans ce cas.

TL; DR: garantie des tables de hachage O(1) pire des cas si vous choisissez votre fonction de hachage uniformément au hasard dans une famille universelle de fonctions de hachage. Le pire cas attendu n'est pas le même que le cas moyen.

Disclaimer: Je ne prouve pas formellement que les tables de hachage le sont O(1), pour cela jetez un œil à cette vidéo de coursera [ 1 ]. Je ne parle pas non plus de l' amorti aspects des tables de hachage. C'est orthogonal à la discussion sur le hachage et les collisions.

Je vois une confusion étonnamment grande autour de ce sujet dans d'autres réponses et commentaires, et j'essaierai de rectifier certaines d'entre elles dans cette longue réponse.

Raisonner le pire des cas

Il existe différents types d'analyse des pires cas. L'analyse que la plupart des réponses ont faite jusqu'ici n'est pas le pire des cas, mais plutôt le cas moyen [ 2 ]. L' analyse de cas moyenne a tendance à être plus pratique. Peut-être que votre algorithme a une mauvaise entrée du pire des cas, mais fonctionne bien pour toutes les autres entrées possibles. En bout de ligne, votre exécution dépend de l'ensemble de données sur lequel vous exécutez.

Considérez le pseudocode suivant de la getméthode d'une table de hachage. Ici, je suppose que nous gérons la collision par chaînage, donc chaque entrée de la table est une liste chaînée de (key,value)paires. Nous supposons également que le nombre de compartiments mest fixe mais l'est O(n), où nest le nombre d'éléments dans l'entrée.

function get(a: Table with m buckets, k: Key being looked up)
  bucket <- compute hash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

Comme d'autres réponses l'ont souligné, cela fonctionne dans la moyenne O(1)et dans le pire des cas O(n). Nous pouvons faire un petit croquis d'une preuve par défi ici. Le défi est le suivant:

(1) Vous donnez votre algorithme de table de hachage à un adversaire.

(2) L'adversaire peut l'étudier et se préparer aussi longtemps qu'il le souhaite.

(3) Enfin, l'adversaire vous donne une entrée de taille nà insérer dans votre table.

La question est: à quelle vitesse votre table de hachage est-elle sur l'entrée de l'adversaire?

À partir de l'étape (1), l'adversaire connaît votre fonction de hachage; lors de l'étape (2), l'adversaire peut élaborer une liste d' néléments avec celui-ci hash modulo m, par exemple en calculant de manière aléatoire le hachage d'un groupe d'éléments; puis dans (3) ils peuvent vous donner cette liste. Mais voilà, puisque tous les néléments sont hachés dans le même compartiment, votre algorithme prendra du O(n)temps pour parcourir la liste liée dans ce compartiment. Peu importe le nombre de fois que nous relançons le défi, l'adversaire gagne toujours, et c'est à quel point votre algorithme est mauvais, dans le pire des cas O(n).

Comment se fait-il que le hachage soit O (1)?

Ce qui nous a déconcertés dans le défi précédent, c'est que l'adversaire connaissait très bien notre fonction de hachage et pouvait utiliser ces connaissances pour créer la pire entrée possible. Et si au lieu de toujours utiliser une fonction de hachage fixe, nous avions en fait un ensemble de fonctions de hachage H, que l'algorithme pouvait choisir au hasard au moment de l'exécution? Au cas où vous êtes curieux, Hon appelle cela une famille universelle de fonctions de hachage [ 3 ]. Très bien, essayons d'ajouter un peu de hasard à cela.

Supposons d'abord que notre table de hachage comprenne également une graine ret rsoit affectée à un nombre aléatoire au moment de la construction. Nous l'attribuons une fois, puis il est corrigé pour cette instance de table de hachage. Revenons maintenant à notre pseudocode.

function get(a: Table with m buckets and seed r, k: Key being looked up)
  rHash <- H[r]
  bucket <- compute rHash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

Si nous essayons le défi une fois de plus: à partir de l'étape (1), l'adversaire peut connaître toutes les fonctions de hachage que nous avons H, mais maintenant la fonction de hachage spécifique que nous utilisons dépend r. La valeur de rest privée pour notre structure, l'adversaire ne peut pas l'inspecter au moment de l'exécution, ni la prédire à l'avance, donc il ne peut pas concocter une liste qui est toujours mauvaise pour nous. Supposons que l' étape (2) l'adversaire choisit une fonction hashdans Hau hasard, il artisanat alors une liste des ncollisions sous hash modulo met envoie que pour l' étape (3), qui croise les doigts lors de l' exécution H[r]seront les mêmes hashqu'ils ont choisi.

C'est un pari sérieux pour l'adversaire, la liste qu'il a créée se heurte hash, mais ne sera qu'une entrée aléatoire sous toute autre fonction de hachage dans H. S'il gagne ce pari, notre temps d'exécution sera le pire des cas O(n)comme avant, mais s'il perd, alors nous recevons juste une entrée aléatoire qui prend le O(1)temps moyen . Et en effet la plupart du temps l'adversaire perdra, il ne remportera qu'une seule fois tous les |H|défis, et nous pouvons faire |H|être très gros.

Comparez ce résultat à l'algorithme précédent où l'adversaire a toujours remporté le défi. Agitant un peu la main ici, mais comme la plupart du temps l'adversaire échouera, et cela est vrai pour toutes les stratégies possibles que l'adversaire peut essayer, il s'ensuit que bien que le pire des cas soit O(n), le pire des cas attendus est en fait O(1).

Encore une fois, ce n'est pas une preuve formelle. La garantie que nous obtenons de cette analyse du pire cas attendu est que notre temps d'exécution est désormais indépendant de toute entrée spécifique . Il s'agit d'une garantie vraiment aléatoire, contrairement à l'analyse de cas moyenne où nous avons montré qu'un adversaire motivé pouvait facilement créer de mauvaises entrées.

Il existe deux paramètres sous lesquels vous pouvez obtenir les temps les plus défavorables O (1) .

1. Si votre configuration est statique, le hachage FKS vous donnera les pires garanties O (1) . Mais comme vous l'avez indiqué, votre paramètre n'est pas statique.
2. Si vous utilisez le hachage Cuckoo, alors les requêtes et les suppressions sont dans le pire des cas O (1) , mais l'insertion est seulement O (1) attendue. Le hachage de coucou fonctionne assez bien si vous avez une limite supérieure sur le nombre total d'inserts et que vous définissez la taille de la table pour qu'elle soit environ 25% plus grande.

Copié d' ici

Il semble basé sur la discussion ici, que si X est le plafond de (# d'éléments dans la table / # de bacs), alors une meilleure réponse est O (log (X)) en supposant une implémentation efficace de la recherche de bac.

A. La valeur est un entier plus petit que la taille de la table de hachage. Par conséquent, la valeur est son propre hachage, il n'y a donc pas de table de hachage. Mais s'il y en avait, ce serait O (1) et serait toujours inefficace.

C'est un cas où vous pouvez mapper de manière triviale les clés vers des compartiments distincts, de sorte qu'un tableau semble être un meilleur choix de structure de données qu'une table de hachage. Pourtant, les inefficacités n'augmentent pas avec la taille de la table.

(Vous pouvez toujours utiliser une table de hachage parce que vous ne faites pas confiance aux entiers pour rester plus petits que la taille de la table à mesure que le programme évolue, vous voulez rendre le code potentiellement réutilisable lorsque cette relation ne tient pas, ou vous ne le faites tout simplement pas. veulent que les gens qui lisent / maintiennent le code gaspillent leurs efforts mentaux pour comprendre et maintenir la relation).

B. Vous devez calculer un hachage de la valeur. Dans cette situation, l'ordre est O (n) pour la taille des données recherchées. La recherche peut être O (1) après avoir effectué le travail O (n), mais cela revient toujours à O (n) à mes yeux.

Nous devons faire la distinction entre la taille de la clé (par exemple en octets) et la taille du nombre de clés stockées dans la table de hachage. Les affirmations selon lesquelles les tables de hachage fournissent des opérations O (1) signifient que les opérations (insérer / effacer / rechercher) n'ont pas tendance à ralentir davantage à mesure que le nombre de clés passe de centaines à des milliers à des millions à des milliards (du moins pas si toutes les données est accessible / mis à jour dans un stockage tout aussi rapide, que ce soit de la RAM ou du disque - les effets de cache peuvent entrer en jeu, mais même le coût d'un échec de cache dans le pire des cas a tendance à être un multiple constant du meilleur cas).

Prenons un annuaire téléphonique: il se peut que vous ayez des noms assez longs, mais que le livre contienne 100 ou 10 millions de noms, la longueur moyenne des noms sera assez cohérente, et le pire des cas de l'histoire ...

Le record du monde Guinness du nom le plus long utilisé par quiconque a été établi par Adolph Blaine Charles David Earl Frederick Gerald Hubert Irvin John Kenneth Lloyd Martin Nero Oliver Paul Quincy Randolph Sherman Thomas Uncas Victor William Xerxes Yancy Wolfeschlegelsteinhausenbergerdorff, Senior

... wcme dit que c'est 215 caractères - ce n'est pas une limite supérieure dure à la longueur de la clé, mais nous n'avons pas à nous soucier qu'il y en ait massivement plus.

Cela vaut pour la plupart des tables de hachage du monde réel: la longueur moyenne des clés n'a pas tendance à augmenter avec le nombre de clés utilisées. Il y a des exceptions, par exemple une routine de création de clé peut renvoyer des chaînes intégrant des entiers incrémentiels, mais même dans ce cas, chaque fois que vous augmentez le nombre de clés d'un ordre de grandeur, vous n'augmentez la longueur de la clé que d'un caractère: ce n'est pas significatif.

Il est également possible de créer un hachage à partir d'une quantité de données clés de taille fixe. Par exemple, Visual C ++ de Microsoft est livré avec une implémentation de bibliothèque standard de std::hash<std::string>qui crée un hachage incorporant seulement dix octets régulièrement espacés le long de la chaîne, donc si les chaînes ne varient que sur d'autres index, vous obtenez des collisions (et donc en pratique des comportements non O (1) côté recherche post-collision), mais le temps de création du hachage a une limite supérieure dure.

Et à moins que vous n'ayez un hachage parfait ou une grande table de hachage, il y a probablement plusieurs éléments par seau. Donc, cela se transforme de toute façon en une petite recherche linéaire à un moment donné.

Généralement vrai, mais ce qui est génial avec les tables de hachage, c'est que le nombre de clés visitées lors de ces "petites recherches linéaires" est - pour l' approche de chaînage séparé des collisions - une fonction du facteur de charge de la table de hachage (rapport des clés aux compartiments).

Par exemple, avec un facteur de charge de 1,0, la durée moyenne de ces recherches linéaires est d'environ 1,58, quel que soit le nombre de clés (voir ma réponse ici ). Pour le hachage fermé, c'est un peu plus compliqué, mais pas bien pire lorsque le facteur de charge n'est pas trop élevé.

C'est techniquement vrai parce que la fonction de hachage n'est pas obligée d'utiliser toutes les informations de la clé et pourrait donc être un temps constant, et parce qu'une table suffisamment grande peut ramener les collisions à un temps presque constant.

Ce genre de manque le point. Tout type de structure de données associative doit parfois effectuer des opérations sur chaque partie de la clé (l'inégalité peut parfois être déterminée à partir d'une seule partie de la clé, mais l'égalité nécessite généralement que chaque bit soit pris en compte). Au minimum, il peut hacher la clé une fois et stocker la valeur de hachage, et s'il utilise une fonction de hachage suffisamment forte - par exemple MD5 64 bits - il peut pratiquement ignorer même la possibilité de hacher deux clés à la même valeur (une entreprise J'ai travaillé pour faire exactement cela pour la base de données distribuée: le temps de génération de hachage était encore insignifiant par rapport aux transmissions sur le réseau WAN). Donc, il n'y a pas trop d'intérêt à être obsédé par le coût de traitement de la clé: c'est inhérent au stockage des clés quelle que soit la structure des données, et comme dit ci-dessus - n'est-ce pas?

Quant aux tables de hachage suffisamment grandes pour réduire les collisions, cela manque également le point. Pour un chaînage séparé, vous avez toujours une longueur de chaîne de collision moyenne constante à n'importe quel facteur de charge donné - elle est juste plus élevée lorsque le facteur de charge est plus élevé, et cette relation n'est pas linéaire. L'utilisateur de SO Hans commente ma réponse également liée ci - dessus :

la longueur moyenne du godet conditionnée sur des godets non vides est une meilleure mesure de l'efficacité. C'est a / (1-e ^ {- a}) [où a est le facteur de charge, e est 2,71828 ...]

Ainsi, le facteur de charge à lui seul détermine le nombre moyen de clés en collision dans lesquelles vous devez rechercher pendant les opérations d'insertion / d'effacement / de recherche. Pour un chaînage séparé, il ne s'agit pas seulement d'être constant lorsque le facteur de charge est faible - il est toujours constant. Pour l'adressage ouvert, bien que votre revendication ait une certaine validité: certains éléments en collision sont redirigés vers des compartiments alternatifs et peuvent ensuite interférer avec les opérations sur d'autres clés, de sorte qu'à des facteurs de charge plus élevés (en particulier> .8 ou .9), la longueur de la chaîne de collision s'aggrave de manière plus dramatique.

C'est vrai en pratique, car au fil du temps, cela fonctionne aussi longtemps que la fonction de hachage et la taille de la table sont choisies pour minimiser les collisions, même si cela signifie souvent ne pas utiliser une fonction de hachage à temps constant.

Eh bien, la taille de la table devrait entraîner un facteur de charge raisonnable étant donné le choix d'un hachage proche ou d'un chaînage séparé, mais aussi si la fonction de hachage est un peu faible et que les clés ne sont pas très aléatoires, avoir un nombre premier de seaux permet souvent de réduire les collisions aussi ( hash-value % table-sizepuis s'enroule de telle sorte que les changements uniquement vers un ou deux bits de poids fort dans la valeur de hachage se résolvent toujours à des compartiments répartis de manière pseudo-aléatoire sur différentes parties de la table de hachage).