Quelqu'un peut-il expliquer les principales différences entre (avantages/inconvénients) les deux implémentations?Tables de hachage chaînées vs tables de hachage ouvertes-ouvertes
Pour une bibliothèque, quelle implémentation est recommandée?
Wikipedia's article on hash tables donne une explication nettement meilleure et une vue d'ensemble des différents schémas de table de hachage que les gens ont utilisé que je suis capable de me sortir de la tête. En fait, vous feriez probablement mieux de lire cet article que de poser la question ici. :)
Cela dit ...
Un index de table de hachage enchaînée dans un tableau de pointeurs vers les têtes de listes chaînées. Chaque cellule de liste liée a la clé pour laquelle elle a été allouée et la valeur qui a été insérée pour cette clé. Lorsque vous voulez rechercher un élément particulier à partir de sa clé, le hachage de la clé est utilisé pour déterminer la liste chaînée à suivre, puis cette liste particulière est parcourue pour trouver l'élément que vous recherchez. Si plus d'une clé dans la table de hachage a le même hachage, alors vous aurez des listes liées avec plus d'un élément. L'inconvénient du hachage enchaîné est de devoir suivre des pointeurs pour rechercher des listes chaînées. L'avantage est que les tables de hachage chaînées ne deviennent linéairement plus lentes que le facteur de charge (le ratio des éléments dans la table de hachage à la longueur du tableau de seau) augmente, même s'il dépasse 1. index de table dans un tableau de pointeurs à paires de (clé, valeur). Vous utilisez la valeur de hachage de la clé pour déterminer quel emplacement du tableau doit être examiné en premier. Si plus d'une clé dans la table de hachage a le même hachage, alors vous utilisez un schéma pour décider d'un autre emplacement à regarder à la place. Par exemple, le sondage linéaire est l'endroit où vous regardez l'emplacement suivant après celui choisi, puis l'emplacement suivant après cela, et ainsi de suite jusqu'à ce que vous trouviez un emplacement correspondant à la clé que vous recherchez, ou vous frappiez un emplacement vide slot (auquel cas la clé ne doit pas être là).
L'adressage ouvert est généralement plus rapide que le hachage chaîné lorsque le facteur de charge est faible car vous n'avez pas besoin de suivre les pointeurs entre les nœuds de liste. Cela devient très, très lent si le facteur de charge se rapproche de 1, parce que vous finissez par devoir rechercher dans plusieurs emplacements du tableau de compartiments avant de trouver la clé que vous cherchiez ou un emplacement vide. En outre, vous ne pouvez jamais avoir plus d'éléments dans la table de hachage que d'entrées dans le tableau de baquets. Pour faire face au fait que toutes les tables de hachage deviennent au moins plus lentes (et dans certains cas cassent complètement) lorsque leur facteur de charge approche 1, les implémentations pratiques de table de hachage augmentent la taille du compartiment (en allouant un nouveau groupe de baies, et copier les éléments de l'ancien dans le nouveau, puis libérer l'ancien) lorsque le facteur de charge dépasse une certaine valeur (typiquement environ 0,7).
Il y a beaucoup de variations sur tout ce qui précède. Encore une fois, s'il vous plaît voir l'article wikipedia, c'est vraiment très bien.
Pour une bibliothèque qui est destinée à être utilisée par d'autres personnes, je recommande vivement d'expérimenter. Comme ils sont généralement très performants, il vaut mieux utiliser l'implémentation d'une table de hachage de quelqu'un d'autre qui a déjà été soigneusement réglée. Il existe de nombreuses implémentations de table de hachage sous licence open source BSD, LGPL et GPL.
Si vous travaillez avec GTK, par exemple, alors vous verrez qu'il y a un bon hash table in GLib.
Si le nombre d'éléments qui seront insérés dans une table de hachage n'est pas connu lors de la création de la table, la table de hachage chaînée est préférable pour ouvrir l'adressage.
L'augmentation du facteur de charge (nombre d'éléments/taille de table) entraîne des pénalités de performance majeures dans les tables de hachage adressées ouvertes, mais les performances ne se dégradent que linéairement dans les tables de hachage chaînées.
Si vous avez peu de mémoire et souhaitez réduire l'utilisation de la mémoire, optez pour l'adressage ouvert. Si vous n'êtes pas préoccupé par la mémoire et que vous voulez de la vitesse, optez pour des tables de hachage enchaînées.
En cas de doute, utilisez des tables de hachage chaînées. Si vous ajoutez plus de données que prévu, les performances ne ralentiront pas jusqu'à l'analyse.
Eh bien, si le nombre d'éléments n'est pas connu à l'avance, l'approche standard serait de simplement faire croître la table en facteurs de deux. Cela peut être fait avec des tables d'adressage ouvertes ou des tables de hachage chaînées. Aucune nécessité d'utiliser une table chaînée, ni de la conduire dans un état où la performance devient linéaire. – cmaster
Depuis une excellente explication est donnée, je aimerais ajouter visualisations provenant CLRS pour illustration supplémentaire:
adressage ouvert: 
Enchaînement: 
Je crois que le premier chiffre que vous avez mis en place est un diagramme de l'adressage direct au lieu de l'adressage ouvert. –
Ma compréhension (en termes simples) est que les deux méthodes ont des avantages et des inconvénients, même si la plupart des bibliothèques utilisent la stratégie de chaînage.
Enchaînement Méthode:
Ici, les tables de hachage cartes de tableau à une liste chaînée des articles. C'est efficace si le nombre de collision est assez petit. Le scénario le plus défavorable est O(n) où n est le nombre d'éléments de la table.
adressage ouvert avec sonde linéaire:
Ici lorsque la collision se produit, passez à l'index suivant jusqu'à ce qu'on trouve un endroit ouvert. Donc, si le nombre de collision est faible, c'est très rapide et efficace. La limitation ici est le nombre total d'entrées dans la table est limitée par la taille du tableau. Ce n'est pas le cas avec le chaînage.
Il existe une autre approche qui est Enchaînement avec les arbres de recherche binaires. Dans cette approche, lorsque la collision se produit, ils sont stockés dans l'arborescence de recherche binaire au lieu de la liste liée. Par conséquent, le pire des cas serait O(log n). En pratique, cette approche est la mieux adaptée lorsqu'il existe une distribution extrêmement non uniforme.
Excellente explication. Une chose que j'ai récemment appris que la plupart des résumés négligent de signaler est que les suppressions affectent négativement les performances dans les tables d'adressage ouvertes. Lorsque vous supprimez vous seulement marquer l'entrée comme supprimée. Lors de l'insertion, vous pouvez réutiliser une entrée supprimée, mais lors d'une recherche, vous ne pouvez pas vous arrêter sur une entrée supprimée. Si vous faites beaucoup d'insertions et de suppressions, vous accumulez au fil du temps des entrées supprimées qui comptent par rapport au facteur de charge. Ainsi, les performances se dégradent en O (n), même si la charge réelle reste faible. Si vous ne supprimez pas, l'adressage ouvert est génial. –
@Adrian Ceci n'est vrai que si vous utilisez cette méthode de marquage des suppressions. Si, à la place, vous supprimez l'élément que vous recherchez, puis que vous réinsérez tous les éléments de votre séquence de sondage après l'élément supprimé, la suppression sera plus lente mais n'affectera pas nécessairement l'insertion. Cependant, si votre implémentation est sujette à la mise en cluster, la suppression peut être assez lente. – Salgar
@AdrianMcCarthy - Je n'ai pas noté cela parce que je n'y avais pas pensé non plus à l'époque.Régler les performances de suppression de table de hachage semble être un peu subtile, mais pas du tout évidemment jusqu'à ce que vous commencez à penser au problème avec soin! –