Meilleur moyen de supprimer une entrée d'une table de hachage

Question

Quel est le meilleur moyen de supprimer une entrée d'une table de hachage utilisant le sondage linéaire? Une façon de le faire serait d’utiliser un drapeau pour indiquer les éléments supprimés? Y a-t-il des moyens meilleurs que cela?

Answer 1

Une technique simple consiste à:

1. Recherchez et supprimez l'élément souhaité
2. Accédez au prochain seau
3. Si le compartiment est vide, quittez
4. Si le compartiment est plein, supprimez l'élément de ce compartiment et rajoutez-le dans la table de hachage en utilisant le moyen normal. L'élément doit être supprimé avant d'être rajouté, car il est probable que l'élément puisse être rajouté à son emplacement d'origine.
5. Répétez l'étape 2.

Cette technique maintient votre table bien rangée au détriment des suppressions un peu plus lentes.

Answer 2

Cela dépend de la façon dont vous gérez le débordement et si (1) l’élément supprimé est dans un emplacement de dépassement ou non, et (2) s’il existe des éléments en dépassement au-delà de l’élément supprimé, qu’ils possèdent la clé de hachage du élément en cours de suppression ou éventuellement une autre clé de hachage. [Ignorer cette double condition est une source commune de bogues dans les implémentations de suppression.]

Si les collisions débordent dans une liste chaînée, c'est assez simple. Vous affichez la liste (qui est peut-être vide) ou supprimez un membre du milieu ou de la fin de la liste liée. Ce sont amusants et pas particulièrement difficiles. Il peut exister d'autres optimisations pour éviter des allocations de mémoire excessives et des libérations pour rendre cela encore plus efficace.

Pour le sondage linéaire, Knuth suggère qu'une approche simple consiste à avoir un moyen de marquer un emplacement comme vide, supprimé ou occupé. Marquez un emplacement d'occupant supprimé comme supprimé, de sorte que le débordement par analyse linéaire passera au-delà, mais si une insertion est nécessaire, vous pouvez remplir le premier emplacement supprimé que vous avez traversé [The Art of Computer Programming, vol.3: Trier et rechercher , section 6.4 Le hachage, p. 533 (ed.2)]. Cela suppose que les suppressions sont plutôt rares.

Knuth donne un raffinement intéressant sous l’algorithme R6.4 [pp. 533-534] qui marque plutôt la cellule comme étant vide plutôt que supprimée, puis trouve le moyen de rapprocher les entrées du tableau de leur emplacement de sonde initial en déplaçant le trou qui vient d'être créé jusqu'à ce qu'il se trouve à côté d'un autre trou.

Knuth prévient que cela déplacera les entrées de logement existantes encore occupées et n’est pas une bonne idée si des pointeurs sur les logements sont maintenus en dehors de la table de hachage. [Si vous avez des références collectées ou d'autres références gérées dans les emplacements, il est correct de déplacer l'emplacement, car il s'agit de la référence utilisée en dehors de la table et peu importe l'emplacement de l'emplacement le même objet est dans la table.]

Answer 3

L’implémentation de la table de hachage Python (argumentable très rapidement) utilise des éléments factices pour marquer les suppressions. Si vous agrandissez ou réduisez une table (en supposant que vous ne faites pas une table de taille fixe), vous pouvez supprimer les maquettes en même temps.

Si vous avez accès à une copie, consultez l'article dans Beautiful Code sur la couleur.

Answer 4

Les meilleures solutions générales auxquelles je puisse penser sont:

• Si vous pouvez utiliser un itérateur non constant (ala C ++ STL ou Java), vous devriez pouvoir le supprimer au fur et à mesure que vous les rencontrez. Vraisemblablement, cependant, vous ne poseriez pas cette question à moins d’utiliser un itérateur constant ou un énumérateur qui serait invalidé si la collection sous-jacente est modifiée.
• Comme vous l'avez dit, vous pouvez marquer un indicateur supprimé dans l'objet contenu. Cela ne libère aucune mémoire et ne réduit pas le nombre de collisions sur la clé. Ce n'est donc pas la meilleure solution. Nécessite également l'ajout d'une propriété sur la classe qui n'appartient probablement pas vraiment à cette classe. Si cela vous dérange autant que moi, ou si vous ne pouvez simplement pas ajouter d'indicateur à l'objet stocké (vous ne contrôlez peut-être pas la classe), vous pouvez stocker ces indicateurs dans une table de hachage séparée. Cela nécessite l’utilisation la plus longue de la mémoire.
• Poussez les clés des éléments à supprimer dans une liste de vecteurs ou de tableaux tout en parcourant la table de hachage. Après avoir libéré l'énumérateur, parcourez cette liste secondaire et supprimez les clés de la table de hachage. Si vous avez beaucoup d’éléments à supprimer et / ou que les clés sont volumineuses (ce qu’elles ne devraient pas être), cela n’est peut-être pas la meilleure solution.
• Si vous devez supprimer plus d'éléments de la table de hachage que vous n'en laissez, il est peut-être préférable de créer une nouvelle table de hachage. Lorsque vous parcourez la table d'origine, ajoutez-la au nouveau hachage. Ne mettez que les objets que vous allez garder. Remplacez ensuite vos références à l'ancienne table de hachage par la nouvelle. Cela enregistre une itération de liste secondaire, mais n’est probablement efficace que si la nouvelle table de hachage contient beaucoup moins d’éléments que l’original, et cela ne fonctionne certainement que si vous pouvez modifier toutes les références à la table de hachage d’origine.
• Si votre table de hachage vous donne accès à sa collection de clés, vous pourrez peut-être les parcourir et supprimer des éléments de la table de hachage en un seul passage.
• Si votre table de hachage ou un assistant de votre bibliothèque vous fournit des modificateurs de collection basés sur des prédicats, vous pouvez avoir une fonction Remove () à laquelle vous pouvez passer une expression lambda ou un pointeur de fonction pour identifier les éléments à supprimer.

Answer 5

Une technique courante lorsque le temps est un facteur consiste à disposer d'un deuxième tableau d'éléments supprimés et à nettoyer le tableau principal lorsque vous en avez le temps. Communément utilisé dans les moteurs de recherche.

Answer 6

Pourquoi ne pas améliorer la table de hachage afin qu'elle contienne des pointeurs comme une liste chaînée? Lorsque vous insérez, si le compartiment est plein, créez un pointeur de ce compartiment vers le compartiment dans lequel le nouveau champ est stocké.

Lorsque vous supprimez quelque chose de la table de hachage, la solution sera équivalente à la façon dont vous écrivez une fonction pour supprimer un nœud de la liste liée.