Enchaînés les Tables de Hachage vs Ouverte Adressée Tables de Hachage

L'article de Wikipedia sur les tables de hachage donne une nettement meilleure explication et présentation des différentes table de hachage régimes que les gens ont utilisé que je suis capable de désactiver le haut de ma tête. En fait, vous êtes probablement mieux de la lecture de cet article que de vous poser la question ici. 🙂

Cela dit...

Enchaînés, de la table de hachage des indices dans un tableau de pointeurs vers les têtes de listes chaînées. Chaque liste liée cellule a la clé pour laquelle il a été affecté et la valeur qui a été inséré pour cette clé. Lorsque vous souhaitez rechercher un élément particulier de sa clé, la clé de hachage est utilisée pour travailler sur la liste liée à suivre, et notamment alors que la liste est parcourue afin de trouver l'élément que vous êtes après. 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 de enchaînés de hachage est d'avoir à suivre des pointeurs dans le but de rechercher des listes liées. L'avantage est que enchaînés les tables de hachage seulement obtenir linéairement plus lent que le facteur de charge (le ratio d'éléments dans la table de hachage de la longueur de la benne tableau) augmente, même si elle s'élève au-dessus de 1.

Une ouverture d'adressage de la table de hachage des indices dans un tableau de pointeurs sur des couples (clé, valeur). Vous utilisez la touche de la valeur de hachage de la fente dans le tableau de regarder en premier. Si plus d'une clé dans la table de hachage a le même hash, puis vous utilisez un système à décider d'un autre logement de regarder dans la place. Par exemple, linéaire de sondage est l'endroit où vous regardez à la prochaine fente d'après l'élu, et puis la prochaine fente d'après, et ainsi de suite jusqu'à ce que vous trouver un logement qui correspond à la clé que vous recherchez, vous avez atteint un logement vide (dans ce cas, la clé ne doit pas être là).

Open-face est généralement plus rapide que la enchaînés de hachage lorsque le facteur de charge est faible parce que vous n'avez pas à suivre des pointeurs entre la liste des nœuds. Il fait très, très lent si le facteur de charge approches de 1, parce que vous vous retrouvez généralement d'avoir à chercher à travers de nombreux emplacements dans le seau de tableau avant de trouver la clé que vous cherchiez ou un emplacement vide. Aussi, vous ne pouvez jamais avoir plus d'éléments dans la table de hachage qu'il y a des entrées dans le seau tableau.

À composer avec le fait que toutes les tables de hachage au moins obtenir plus lent (et, dans certains cas, briser complètement) lors de leur facteur de charge approches 1, pratique de la table de hachage implémentations de faire le seau tableau plus grand (par l'attribution d'un nouveau seau de tableau, et copier des éléments de l'ancien dans le nouveau, puis de libérer l'ancien) lorsque le facteur de charge dépasse une certaine valeur (typiquement de l'ordre de 0,7).

Il ya beaucoup de variations sur l'ensemble de la ci-dessus. Encore une fois, consultez l'article de wikipedia, il est vraiment très bon.

Pour une bibliothèque qui est destiné à être utilisé par d'autres personnes, je fortement vous recommandons de tester. Car ils sont généralement assez la performance cruciale, vous êtes généralement mieux lotis de l'aide de quelqu'un d'autre de la mise en œuvre d'une table de hachage qui a déjà été soigneusement réglée. Il y a beaucoup de open source BSD, LGPL et GPL la licence de la table de hachage des implémentations.

Si vous travaillez avec GTK, par exemple, vous trouverez qu'il y a une bonne table de hachage dans GLib.

Ma compréhension (en termes simples) est que les deux méthodes a des avantages et des inconvénients, bien que la plupart des bibliothèques utiliser le Chaînage de stratégie.

Le Chaînage De Méthode:

Ici les tables de hachage de la matrice de cartes à une liste chaînée d'éléments. C'est efficace si le nombre de collision est assez petite. Le pire scénario est O(n) où n est le nombre d'éléments dans le tableau.

En Abordant avec Linéaire de la Sonde:

Ici lorsque la collision se produit, passez à la prochaine index jusqu'à ce que nous trouver un endroit ouvert. Ainsi, si le nombre de collision est faible, c'est très rapide et efficace de l'espace. La limitation ici est le nombre total d'entrées dans la table est limité par la taille de la matrice. Ce n'est pas le cas avec le chaînage.

Il y a une autre approche qui est Chaînage avec les binaires de recherche arbres. Dans cette approche, lorsque la collision se produit, ils sont stockés en binaire un arbre de recherche au lieu de la liste liée. Par conséquent, le pire scénario serait ici O(log n). Dans la pratique, cette approche est particulièrement adaptée lorsqu'il y a une extrêmement distribution non uniforme.

Si le nombre d'éléments qui seront insérées dans une table de hachage n'est pas connu au moment de la création de la table, enchaînés table de hachage est préférable d'ouvrir les aborder.

Augmenter le facteur de charge(nombre d'articles/taille de la table) les causes principales de la performance des pénalités ouverte adressée tables de hachage, mais les performances se dégradent que linéairement dans enchaîné les tables de hachage.

Si vous faites affaire avec peu de mémoire et que vous souhaitez réduire l'utilisation de la mémoire, aller de l'open d'adressage. Si vous n'êtes pas inquiet au sujet de la mémoire et veulent la vitesse, aller pour les chaînes de tables de hachage.

En cas de doute, utilisez enchaîné les tables de hachage. Ajout de davantage de données que vous aviez prévu de ne pas affecter les performances de ralentir à une exploration.