Signification du hachage ouvert et du hachage fermé

Hachage ouvert (chaînage séparé):

Dans le hachage ouvert, les clés sont stockées dans des listes liées attachées aux cellules d'une table de hachage.

Hachage fermé (adressage ouvert):

Dans le hachage fermé, toutes les clés sont stockées dans la table de hachage elle-même sans l'utilisation de listes liées.

Je suis incapable de comprendre pourquoi ils sont appelés ouverts, fermés et séparés. Quelqu'un peut-il l'expliquer?

L'utilisation de «fermé» ou «ouvert» indique si nous sommes ou non bloqués dans l'utilisation d'une certaine position ou structure de données (c'est une description extrêmement vague, mais j'espère que le reste aide).

Par exemple, «open» dans «open adressing» nous indique l'index (aka. Address) auquel un objet sera stocké dans la table de hachage n'est pas complètement déterminé par son code de hachage. Au lieu de cela, l'index peut varier en fonction de ce qui est déjà dans la table de hachage.

Le «fermé» dans le «hachage fermé» fait référence au fait que nous ne quittons jamais la table de hachage; chaque objet est stocké directement à un index dans le tableau interne de la table de hachage. Notez que cela n'est possible qu'en utilisant une sorte de stratégie d'adressage ouverte. Ceci explique pourquoi «hachage fermé» et «adressage ouvert» sont des synonymes.

Comparez cela avec le hachage ouvert - dans cette stratégie, aucun des objets n'est réellement stocké dans le tableau de la table de hachage; à la place, une fois qu'un objet est haché, il est stocké dans une liste distincte du tableau interne de la table de hachage. «open» fait référence à la liberté que nous obtenons en quittant la table de hachage et en utilisant une liste séparée. À propos, la "liste séparée" indique pourquoi le hachage ouvert est également appelé "chaînage séparé".

En bref, «fermé» fait toujours référence à une sorte de garantie stricte, comme lorsque nous garantissons que les objets sont toujours stockés directement dans la table de hachage (hachage fermé). Ensuite, l'opposé de «fermé» est «ouvert», donc si vous n'avez pas de telles garanties, la stratégie est considérée comme «ouverte».

Vous avez un tableau qui est la "table de hachage".

Dans Open Hashing, chaque cellule du tableau pointe vers une liste contenant les collisions. Le hachage a produit le même index pour tous les éléments de la liste liée.

Dans le hachage fermé, vous n'utilisez qu'un seul tableau pour tout. Vous stockez les collisions dans le même tableau. L'astuce consiste à utiliser un moyen intelligent de passer d'une collision à l'autre.Vous trouverez ce que vous voulez. Et faites-le de manière reproductible / déterministe.

L' adressage ouvert de nom fait référence au fait que l'emplacement («adresse») de l'élément n'est pas déterminé par sa valeur de hachage. (Cette méthode est également appelée hachage fermé).

Dans un chaînage séparé , chaque compartiment est indépendant et possède une sorte d'ADT (liste, arbres de recherche binaires, etc.) d'entrées avec le même index. Dans une bonne table de hachage, chaque bucket a zéro ou une entrée, car nous avons besoin d'opérations d'ordre O (1) pour l'insertion, la recherche, etc.

Ceci est un exemple de chaînage séparé utilisant C ++ avec une fonction de hachage simple utilisant l'opérateur mod (clairement, une mauvaise fonction de hachage)