Quels sont les avantages du hachage coucou par rapport au hachage parfait dynamique?

12

Les tables de hachage parfaites dynamiques et les tables de hachage de coucou sont deux structures de données différentes qui prennent en charge les recherches O (1) les plus défavorables et les insertions et suppressions de temps O (1) attendues. Les deux nécessitent un espace auxiliaire O (n) et un accès aux familles de fonctions de hachage pour leurs opérations.

Je pense que ces deux structures de données sont belles et brillantes en elles-mêmes, mais je ne suis pas sûr de voir comment et quand l'une d'elles serait préférable à l'autre.

Existe-t-il des contextes spécifiques dans lesquels l'une de ces structures de données a un net avantage sur l'autre? Ou sont-ils principalement interchangeables?

data-structures hash-tables templatetypedef
la source
Je ne sais pas si l'une ou l'autre de ces techniques est réellement utilisée dans la pratique. Habituellement, ces types de structures de données qui offrent les meilleures limites asymptotiques sont principalement d'intérêt pour la recherche, car elles ont généralement une grande constante cachée dans la -notation. En pratique, vous préférerez peut-être une technique plus simple et plus facile à implémenter avec une très petite constante plutôt qu'une plus compliquée avec une très grande constante. O ( log n ) O ( 1 )OO(log⁡n)O(1)
Tom van der Zanden
@TomvanderZanden C'est certainement vrai. Je suis également intéressé par les avantages théoriques d'une approche par rapport à l'autre - y a-t-il de belles propriétés théoriques que chaque approche a à offrir par rapport à l'autre?
templatetypedef du
@templatetypedef, je vous encourage donc à ajouter cela à la question. Les gens ne devraient pas avoir à lire les commentaires pour comprendre votre question - les commentaires sont transitoires et peuvent disparaître à tout moment.
DW
Oui, ces techniques sont effectivement utilisées dans la pratique, généralement dans des domaines de niche.
Pseudonyme
1
Un avantage du hachage de coucou est qu'il est facile à comprendre et à mettre en œuvre. De plus, à mon humble avis, il est beaucoup plus facile à analyser que le hachage parfait dynamique.
A.Schulz

Réponses:

3

Hachage parfait dynamique au sens de Dietzfelbinger et al. nécessite uniquement un hachage indépendant de 2 . Bien qu'il y ait quelques résultats sur le hachage simple pour les tables de hachage de coucou, tels que le hachage de tabulation torsadée et "Les familles de hachage explicites et efficaces suffisent pour le hachage de coucou avec une cachette", le hachage parfait dynamique d'origine est plus robuste dans un certain sens.

jbapple
la source
Voir le commentaire clarifiant d'OP: "Je suis également intéressé par les avantages théoriques d'une approche par rapport à l'autre - y a-t-il de belles propriétés théoriques que chaque approche a à offrir par rapport à l'autre?"
jbapple
3

Dans le hachage de coucou, les recherches peuvent être effectuées en parallèle, tandis que dans le schéma de hachage dynamique original de Dietzfelbinger et al., Les recherches nécessitent deux accès à la mémoire en chaîne, dans lesquels le deuxième accès utilise les informations récupérées du premier.

jbapple
la source
1

Il est relativement facile d'augmenter l'efficacité spatiale du hachage de coucou en permettant à chaque emplacement de contenir plus d'un élément. Pour les emplacements de taille 4, l'efficacité de l'espace est d'environ 95%. C'est-à-dire que les éléments peuvent être insérés jusqu'à ce que 95% de l'espace dans le tableau soit utilisé pour contenir des éléments, pas seulement les endroits où les éléments peuvent aller.

D'un autre côté, les limites de Dietzfelbinger et al. le papier sur le hachage parfait dynamique prouve seulement que les opérations d'insertion peuvent se poursuivre tant que la table n'est pas remplie à plus de 3%.

jbapple
la source
Vous voudrez peut-être combiner vos deux réponses ensemble. :-)
templatetypedef
0

Le hachage de coucou utilise des blocs de mémoire à tout moment et doit rarement libérer ou réallouer de la mémoire. Le hachage dynamique parfait au sens de Dietzfelbinger utilise des blocs de mémoire et utilisera plus d'espace dans la fragmentation interne et externe. Il existe des moyens d'éviter cela, mais ils ajoutent de la complexité à l'algorithme.O ( n )O(1)O(n)

jbapple
la source