Hachage dynamique parfait

En informatique , le hachage dynamique parfait est une technique de programmation permettant de résoudre les collisions dans une structure de données de table de hachage . Bien que plus gourmande en mémoire que ses homologues de table de hachage, cette technique est utile dans les situations où des requêtes, des insertions et des suppressions rapides doivent être effectuées sur un grand ensemble d'éléments.

Le problème du hachage statique optimal a été résolu pour la première fois en général par Fredman, Komlós et Szemerédi. Dans leur article de 1984, ils détaillent un schéma de table de hachage à deux niveaux dans lequel chaque compartiment de la table de hachage (de premier niveau) correspond à une table de hachage de second niveau distincte. Les clés sont hachées deux fois : la première valeur de hachage correspond à un certain compartiment dans la table de hachage de premier niveau ; la deuxième valeur de hachage donne la position de cette entrée dans la table de hachage de second niveau de ce compartiment. La table de second niveau est garantie sans collision (c'est-à-dire avec un hachage parfait ) lors de sa construction. Par conséquent, le coût de recherche est garanti O(1) dans le pire des cas .

Dans le cas statique, on nous donne à l'avance un ensemble avec un total de x entrées, chacune avec une clé unique. Fredman, Komlós et Szemerédi choisissent une table de hachage de premier niveau avec des buckets de taille.

Pour construire, les entrées x sont séparées en s compartiments par la fonction de hachage de niveau supérieur, où . Ensuite, pour chaque compartiment avec k entrées, une table de second niveau est allouée avec des emplacements, et sa fonction de hachage est sélectionnée au hasard dans un ensemble de fonctions de hachage universelles de sorte qu'elle soit sans collision (c'est-à-dire une fonction de hachage parfaite ) et stockée à côté de la table de hachage. Si la fonction de hachage sélectionnée au hasard crée une table avec des collisions, une nouvelle fonction de hachage est sélectionnée au hasard jusqu'à ce qu'une table sans collision puisse être garantie. Enfin, avec le hachage sans collision, les k entrées sont hachées dans la table de second niveau.

La taille quadratique de l' espace garantit que la création aléatoire d'une table avec des collisions est peu fréquente et indépendante de la taille de k , ce qui permet un temps de construction amorti linéaire. Bien que chaque table de second niveau nécessite un espace quadratique, si les clés insérées dans la table de hachage de premier niveau sont uniformément distribuées , la structure dans son ensemble occupe l'espace attendu, car les tailles de compartiment sont petites avec une probabilité élevée .

La fonction de hachage de premier niveau est spécifiquement choisie de telle sorte que, pour l'ensemble spécifique de x valeurs de clés uniques, l'espace total T utilisé par toutes les tables de hachage de deuxième niveau ait l'espace attendu, et plus précisément . Fredman, Komlós et Szemerédi ont montré qu'étant donné une famille de fonctions de hachage universelles , au moins la moitié de ces fonctions ont cette propriété.

Dietzfelbinger et al. présentent un algorithme de dictionnaire dynamique selon lequel, lorsqu'un ensemble de n éléments est ajouté progressivement au dictionnaire, les requêtes d'appartenance s'exécutent toujours en temps constant et donc dans le pire des cas, le stockage total requis est (linéaire) et le temps d'insertion et de suppression amorti attendu ( temps constant amorti ).

Dans le cas dynamique, lorsqu'une clé est insérée dans la table de hachage, si son entrée dans sa sous-table respective est occupée, on dit qu'une collision se produit et la sous-table est reconstruite en fonction de son nouveau nombre total d'entrées et de la fonction de hachage sélectionnée de manière aléatoire. Étant donné que le facteur de charge de la table de deuxième niveau est maintenu faible , la reconstruction est peu fréquente et le coût attendu amorti des insertions est de . De même, le coût attendu amorti des suppressions est de .

De plus, les tailles finales de la table de niveau supérieur ou de l'une des sous-tables ne sont pas connues dans le cas dynamique. Une méthode pour maintenir l'espace attendu de la table consiste à déclencher une reconstruction complète lorsqu'un nombre suffisant d'insertions et de suppressions ont eu lieu. D'après les résultats de Dietzfelbinger et al., tant que le nombre total d'insertions ou de suppressions dépasse le nombre d'éléments au moment de la dernière construction, le coût attendu amorti de l'insertion et de la suppression reste le même, même si le réassemblage complet est pris en compte.

L'implémentation du hachage dynamique parfait par Dietzfelbinger et al. utilise ces concepts, ainsi que la suppression paresseuse , et est présentée dans le pseudo-code ci-dessous.

fonction Locate( x ) est 
j := h( x ) si (position h j ( x ) du sous-tableau T j contient x (non supprimé)) return ( x est dans S ) fin si 
sinon 
return ( x n'est pas dans S ) fin sinon 
fin

Lors de l'insertion d'une nouvelle entrée x à j , le compteur d'opérations globales, count , est incrémenté.

Si x existe à j , mais est marqué comme supprimé, alors la marque est supprimée.

Si x existe au niveau j ou au niveau de la sous-table T _j et n'est pas marqué comme supprimé, alors une collision est dite se produire et la table de deuxième niveau T _j du j ^{ème bucket est reconstruite avec une fonction de hachage} h _j sélectionnée aléatoirement différente .

fonction Insérer( x ) est 
count = count + 1; si ( count > M ) FullRehash( x ); fin si 
sinon 
j = h( x ); si (Position h j (x) du sous-tableau T j contient x ) si ( x est marqué comme supprimé) supprimer le marqueur de suppression ; fin si 
fin si 
sinon 
b j = b j + 1 ; si ( b j <= m j ) si la position h j ( x ) de T j est vide stocker x dans la position h j ( x ) de T j ; fin si 
sinon Placer tous les éléments non marqués de T j dans la liste L j ; Ajouter x à la liste L j ; b j = longueur de L j ; répéter 
h j = fonction choisie au hasard dans H sj ; jusqu'à ce que 
h j soit injective sur les éléments de L j ; pour tout y sur la liste L j stocker y dans la position h j ( y ) de T j ; fin pour 
fin sinon 
fin si 
sinon 
m j = 2 * max{1, m j }; s j = 2 * m j * ( m j - 1); si la somme totale de tous les s j ≤ 32 * M 2 / s ( M ) + 4 * M Allouer s j cellules pour T j ; Mettre tous les éléments non marqués de T j dans la liste L j ; Ajouter x à la liste L j ; b j = longueur de L j ; répéter 
h j = fonction choisie au hasard dans H sj ; jusqu'à ce que 
h j soit injectif sur les éléments de L j ; pour tout y sur la liste L j stocker y en position h j ( y ) de T j ; fin pour 
fin si 
sinon FullRehash( x ); fin sinon fin 
sinon 
fin 
sinon 
fin

La suppression de x marque simplement x comme supprimé sans suppression et incrémente count . Dans le cas des insertions et des suppressions, si count atteint un seuil M la table entière est reconstruite, où M est un multiple constant de la taille de S au début d'une nouvelle phase . Ici phase fait référence au temps entre les reconstructions complètes. Notez qu'ici le -1 dans "Delete( x )" est une représentation d'un élément qui ne fait pas partie de l'ensemble de tous les éléments possibles U .

fonction Delete( x ) est 
count = count + 1; j = h( x ); si la position h j ( x ) du sous-tableau Tj contient x marquer x comme supprimé; fin si 
sinon 
renvoyer (x n'est pas un membre de S); fin sinon 
si ( count >= M ) FullRehash(-1); fin si 
fin

Une reconstruction complète de la table de S commence d'abord par supprimer tous les éléments marqués comme supprimés, puis en définissant la valeur de seuil suivante M à un multiple constant de la taille de S. Une fonction de hachage, qui partitionne S en s ( M ) sous-ensembles, où la taille du sous-ensemble j est s _j , est choisie de manière aléatoire à plusieurs reprises jusqu'à ce que :

Enfin, pour chaque sous-tableau T _{j ,} une fonction de hachage h _j est choisie aléatoirement de manière répétée dans H _sj jusqu'à ce que h _j soit injective sur les éléments de T _j . Le temps attendu pour une reconstruction complète du tableau de S de taille n est O( n ).

fonction FullRehash( x ) est Placer tous les éléments non marqués de T dans la liste L ; si ( x est dans U ) ajouter x à L ; terminer si 
count = longueur de la liste L ; M = (1 + c ) * max{ count , 4} ; répéter h = fonction choisie au hasard dans H s(M) ; pour tout j < s ( M ) former une liste L j pour h( x ) = j ; b j = longueur de L j ; m j = 2 * b j ; s j = 2 * m j * ( m j - 1) ; terminer 
jusqu'à ce que la somme totale de tous les s j ≤ 32 * M 2 / s ( M ) + 4 * M 
pour tout j < s ( M ) Allouer de l'espace s j pour le sous-tableau T j ; répéter 
h j = fonction choisie au hasard dans H sj ; jusqu'à ce que 
h j soit injectif sur les éléments de la liste L j ; fin pour 
pour tout x sur la liste L j stocker x dans la position h j ( x ) de T j ; fin pour 
fin