Pour quel type de données les opérations de table de hachage sont-elles O (1)?

18

Des réponses à (Quand) la recherche de table de hachage O (1)? , Je suppose que les tables de hachage ont un comportement pire des cas, au moins amorti, lorsque les données remplissent certaines conditions statistiques, et il existe des techniques pour aider à élargir ces conditions.O(1)

Cependant, du point de vue d'un programmeur, je ne sais pas à l'avance quelles seront mes données: elles proviennent souvent d'une source externe. Et j'ai rarement toutes les données à la fois: souvent les insertions et les suppressions se produisent à un taux qui n'est pas très inférieur au taux de recherches, donc le prétraitement des données pour affiner la fonction de hachage est désactivé.

Donc, en sortant: étant donné certaines connaissances sur la source de données, comment puis-je déterminer si une table de hachage a une chance d'avoir des opérations , et éventuellement quelles techniques utiliser sur ma fonction de hachage?O(1)

Gilles 'SO- arrête d'être méchant'
la source
Oh, et les tables de hachage par rapport aux arbres binaires sont liées, mais ici je me concentre sur les tables de hachage et quand elles sont (ou ne sont pas) à leur meilleur.
Gilles 'SO- arrête d'être méchant'
Le meilleur cas pour toute fonction de hachage est lorsque les données sont réparties uniformément.
0x0
@Sunil: Pas vrai. Vous pouvez avoir des fonctions de hachage personnalisées.
Raphael
Je pense que cette question est trop large. En particulier, pouvez-vous concrétiser à quoi ressembleraient les connaissances sur les sources de données?
Raphael
@Raphael Par exemple, si les clés sont des chaînes: noms de personnes, noms de fichiers dans un répertoire, balises XML, hachages de fichiers,…
Gilles 'SO- arrête d'être méchant'

Réponses:

4

Il existe plusieurs techniques qui garantissent que les recherches nécessiteront toujours des opérations O (1), même dans le pire des cas.

Comment puis-je déterminer si une table de hachage a une chance d'avoir des opérations O (1), et éventuellement quelles techniques utiliser sur ma fonction de hachage?

Le pire des cas se produit lorsqu'un attaquant malveillant (Mallory) vous donne délibérément des données que Mallory a spécifiquement sélectionnées pour ralentir le système.

Une fois que vous avez choisi une fonction de hachage particulière, il est probablement trop optimiste de supposer que Mallory ne saura jamais quelle fonction de hachage vous avez choisie. Une fois que Mallory découvre la fonction de hachage que vous avez choisie, si vous autorisez Mallory à vous donner beaucoup de données à insérer dans votre table de hachage à l'aide de cette fonction de hachage, alors vous êtes condamné: Mallory peut générer rapidement en interne des milliards d'éléments de données, les hacher avec votre fonction de hachage pour trouver les éléments de données susceptibles d'entrer en collision, puis vous fournir des millions d'éléments de données sur mille susceptibles de se heurter, ce qui entraîne des recherches beaucoup plus lentes que O (1).

Toutes les techniques qui garantissent "les recherches O (1) même dans le pire des cas" évitent ce problème en effectuant un peu de travail supplémentaire à chaque insertion pour garantir qu'à l'avenir, chaque recherche possible pourra réussir en temps O (1) . En particulier, nous supposons (dans le pire des cas) que Mallory découvrira tôt ou tard la fonction de hachage que nous utilisons; mais il n'a qu'une chance d'insérer quelques éléments de données avant de choisir une fonction de hachage différente - hachage de tabulation ou autre hachage universel - une que nous sélectionnons spécialement de telle sorte que toutes les données que nous avons jusqu'à présent puissent être consultées en 2 ou 3 sondes - c'est-à-dire O (1). Parce que nous sélectionnons cette fonction au hasard, nous pouvons être sûrs que Mallory ne saura pas quelle fonction nous avons choisie pendant un certain temps. Même si Mallorynous donne immédiatement des données qui, même avec cette nouvelle fonction de hachage, entrent en collision avec les données précédentes, nous pouvons ensuite en choisir une autre, une nouvelle fonction de hachage nouvelle de telle sorte qu'après ressassage, toutes les données précédentes que lui et tous les autres nous ont nourries peuvent maintenant être consultées dans 2 ou 3 sondes dans le pire des cas - c'est-à-dire O (1) dans le pire des cas.

Il est assez facile de sélectionner au hasard une nouvelle fonction de hachage et de ressasser la table entière assez souvent pour garantir que chaque recherche est toujours O (1). Bien que cela garantisse que chaque recherche est toujours O (1), ces techniques, lors de l'insertion du Nème élément dans une table de hachage qui contient déjà N-1 éléments, peuvent parfois nécessiter un temps O (N) pour cette insertion. Cependant, il est possible de concevoir le système de telle sorte que, même lorsque Mallory vous donne délibérément de nouvelles données qui, à l'aide de la nouvelle fonction de hachage, entrent en collision avec des données précédentes, le système peut accepter de nombreux éléments de Mallory et d'autres avant qu'il ne doive effectuer une reconstruction O (N) complète. Les techniques de table de hachage qui choisissent une nouvelle fonction et ressassent afin de garantir les recherches O (1), même dans le pire des cas, comprennent:

  • le hachage de coucou garantit que chaque recherche de clé réussit avec au plus 2 calculs de hachage et 2 recherches de table.
  • Le hachage hopscotch garantit que chaque recherche de clé réussit après avoir inspecté un petit nombre H (peut-être H = 32) d'entrées consécutives dans la table.
  • hachage parfait dynamique - l'article de 1994 de Dietzfelbinger est le premier que j'ai lu qui a souligné que, même s'il est ressuscité "fréquemment" afin de garantir que chaque recherche de clé réussit toujours avec 2 calculs de hachage et 2 recherches, il est possible pour effectuer une reprise complète si rarement que même si chaque reprise complète utilise O (n) de temps, le coût moyen prévu des insertions et de la suppression est O (1) amorti.

Structures de données / tables de hachage

David Cary
la source
5

O(1)

O(1)O(n2W)

O(Journaln/JournalJournaln)O(1)

À
la source
5

hune,b(X)=uneX+bmodp

Dans le passé, selon un article Usenix de Crosby et Wallach , les langages de programmation courants ne faisaient rien de tel, laissant de nombreuses applications Web (et autres serveurs) ouvertes à une attaque DoS basée sur des collisions de fabrication. (Le document date de 2003, mais il suggère que Dan Bernstein avait découvert la même idée un peu plus tôt.)

Une recherche rapide sur Google permet d'affirmer que l'état de l'art en termes d'implémentations s'est à la fois amélioré et non amélioré .

Un autre côté est que dans un monde à large bande passante, les attaques de synchronisation ne rendent pas si difficile la recherche de collisions en ligne (par opposition à hors ligne comme le suggère le lien Crosby-Wallach). Il me semble que Daniel Golovin a obtenu il y a quelques années des résultats sur des structures de données qui ne sont pas vulnérables aux attaques temporelles, mais je ne sais pas si elles sont largement utilisées.

Louis
la source
0

L'analyse de cas moyen pour les tables de hachage est faite sous l'hypothèse habituelle d'uniformité des entrées, ce qui est dû une fois au rasoir d'Occam.

Si vous avez des connaissances supplémentaires sur le domaine et la distribution des clés, vous pouvez effectuer la même analyse de cas moyen et remplacer la distribution uniforme par votre distribution et recalculer les attentes, au moins en théorie.

Bien sûr, la difficulté vient du fait qu'il est difficile de faire une analyse de cas moyenne non uniforme. Et votre «connaissance» peut ne pas être facilement exprimable comme une distribution qui peut être utilisée facilement dans une telle analyse.

De toute évidence, la simulation est la chose la plus simple à faire. Implémentez les tables de hachage et observez leurs performances pour votre ensemble typique d'entrées.

uli
la source
8
Je dois être en désaccord avec la première phrase. L'hypothèse standard est que la fonction de hachage est aléatoire, pas les données d'entrée. En supposant que les données uniformément réparties poussent l'analyse dans le domaine de la fantaisie - les données du monde réel ne sont jamais uniformes! Mais il existe des techniques classiques pour uniformiser suffisamment les fonctions de hachage. Voir hachage universel et spécifiquement hachage de tabulation .
JeffE
@JeffE Regardez l'analyse de cas moyen dans la réponse de Raphaël, il énonce cette hypothèse d'uniformité. Vous ne pouvez pas faire une analyse de cas moyen sans distribution. Vous devez en choisir un et si non, le rasoir d'Occam suggère l'uniforme.
uli
6
Bien sûr, vous avez une distribution; c'est la distribution que vous utilisez pour choisir la fonction de hachage. Choisir une distribution pour les données d'entrée, c'est comme chercher vos clés perdues sous le lampadaire; bien sûr, la lumière est meilleure, mais ce n'est probablement pas là que vous les avez déposés.
JeffE
@JeffE C'est ainsi que se fait une analyse de cas moyen, choisissez une distribution et commencez à calculer. Comme toujours, le choix de la distribution est discutable. Vous êtes les bienvenus pour faire une analyse de cas moyen non uniforme.
uli
4
Oui, je sais comment c'est fait. (Vérifiez mon profil.) Si vous voulez que votre analyse soit prédictive (c'est tout le point de l'analyse), vous devez randomiser la fonction de hachage. Ensuite, vous connaissez la distribution précise, car vous l'avez choisie.
JeffE