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. Peut-on expliquer cela?
4 réponses
L'utilisation de "FERMÉ" vs "ouvert" reflète si oui ou non nous sommes enfermé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, le "open" dans "Open addressing" nous indique l'index (aka. adresse) à laquelle 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 "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. Cela explique pourquoi "hachage fermé" et "adressage ouvert" sont des synonymes.
Contrastez ceci 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 qui est séparé 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. En passant," liste séparée "indique pourquoi le hachage ouvert est également connu sous le nom de "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é). Puis, à l'opposé de "fermé" est "ouvert", donc si vous n'avez pas de telles garanties, la la stratégie est considérée comme "ouverte".
Nom abordant désigne le fait que l'emplacement ("adresse") de l'élément n'est pas déterminée par sa valeur de hachage. (Cette méthode est également appelée hachage fermé).
Dans chaînage séparé , chaque compartiment est indépendant et possède une sorte D'ADT (liste, arborescence de recherche binaire, etc.) d'entrées avec le même index. Dans une bonne table de hachage, chaque compartiment a zéro ou une entrée, car nous avons besoin d'opérations d'ordre O (1) pour insert, search, etc.
Ceci est un exemple de chaînage séparé en utilisant C++ avec une fonction de hachage simple en utilisant l'opérateur mod (clairement, une mauvaise fonction de hachage)
Vous avez un tableau qui est la "table de hachage".
Dans le hachage ouvert, chaque cellule du tableau pointe vers une liste containg 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 une façon intelligente de sauter de collision à collision unitl vous trouvez ce que vous voulez. Et faites-le de manière reproductible / déterministe.
Eh bien, c'est si simple de comprendre le concept de hachage ouvert et fermé,
En hachage ouvert, il prend la propriété de link list qui fait référence si une clé d'index ayant déjà l'élément de données que nous pouvons insérer l'autre élément de données dans le même emplacement,clairement il est ouvert pour les données ayant le même emplacement après qu'il est déjà occupé par un autre.
Et à proximité, si les données obtiennent l'emplacement dans la table, aucune donnée ne peut l'utiliser adresse..
Résolu........facile na