Table de hachage et arbre binaire équilibré

Question

Quels facteurs dois-je prendre en compte lorsque je dois choisir entre une table de hachage et un arbre binaire équilibré afin d'implémenter un ensemble ou un tableau associatif ?

Answer 1

Je crains qu'il soit impossible de répondre à cette question, en général.

Le problème est qu'il existe de nombreux types de tables de hachage et d'arbres binaires équilibrés, et que leurs performances varient considérablement.

La réponse naïve est donc : cela dépend de la fonctionnalité dont vous avez besoin. Utilisez une table de hachage si vous n'avez pas besoin d'ordonnancement et un arbre binaire équilibré sinon.

Pour une réponse plus élaborée, considérons quelques alternatives.

Table de hachage (voir l'entrée de Wikipédia pour quelques notions de base)

• Toutes les tables de hachage n'utilisent pas une liste chaînée comme seau. Une alternative populaire est d'utiliser un "meilleur" seau, par exemple un arbre binaire, ou une autre table de hachage (avec une autre fonction de hachage), ...
• Certaines tables de hachage n'utilisent pas du tout de buckets : voir l'adressage ouvert (elles présentent d'autres problèmes, évidemment).
• Il existe une méthode appelée "Linear re-hashing" (c'est un détail de qualité de mise en œuvre), qui permet d'éviter le piège "stop-the-world-and-rehash". En gros, pendant la phase de migration, vous n'insérez que dans la "nouvelle" table, et vous déplacez également une "ancienne" entrée dans la "nouvelle" table. Bien sûr, la phase de migration implique un double look-up etc...

Arbre binaire

• Le rééquilibrage est coûteux, vous pouvez envisager une liste de saut (également meilleure pour les accès multithreads) ou un arbre d'évasement.
• Un bon allocateur peut "empaqueter" les nœuds en mémoire (meilleur comportement de mise en cache), même si cela ne résout pas le problème de la consultation des pointeurs.
• B-Tree et ses variantes proposent également le "packing".

N'oublions pas que O(1) est une complexité asymptotique. Pour peu d'éléments, le coefficient est généralement plus important (en termes de performance). Ce qui est particulièrement vrai si votre fonction de hachage est lente...

Enfin, pour les ensembles, vous pouvez également envisager des structures de données probabilistes, telles que Filtres Bloom .

Answer 2

Les tables de hachage sont généralement préférables s'il n'est pas nécessaire de conserver les données dans un ordre quelconque. Les arbres binaires sont préférables si les données doivent être triées.

Answer 3

Un point digne d'intérêt sur une architecture moderne : Une table de hachage aura généralement, si son facteur de charge est faible, moins de lectures mémoire qu'un arbre binaire. Comme les accès à la mémoire ont tendance à être plutôt coûteux par rapport aux cycles de calcul du CPU, la table de hachage est souvent plus rapide.

Dans ce qui suit, on suppose que l'arbre binaire est auto-équilibré, comme un arbre rouge-noir, un arbre AVL ou un trépied. .

D'un autre côté, si vous devez tout remanier dans la table de hachage lorsque vous décidez de l'étendre, cela peut être une opération coûteuse qui se produit (amortie). Les arbres binaires n'ont pas cette limitation.

Les arbres binaires sont plus faciles à mettre en œuvre dans les langages purement fonctionnels.

Les arbres binaires ont un ordre de tri naturel et une façon naturelle de parcourir l'arbre pour tous les éléments.

Lorsque le facteur de charge de la table de hachage est faible, vous risquez de gaspiller beaucoup d'espace mémoire, mais avec deux pointeurs, les arbres binaires ont tendance à prendre plus de place.

Les tables de hachage sont presque O(1) (selon la façon dont vous gérez le facteur de charge) contre les arbres de Bin O(lg n).

Les arbres ont tendance à être des "exécutants moyens". Il n'y a rien qu'ils fassent particulièrement bien, mais aussi rien qu'ils fassent particulièrement mal.

Answer 4

Un arbre de recherche binaire nécessite une relation d'ordre total entre les clés. Une table de hachage nécessite uniquement une relation d'équivalence ou d'identité avec une fonction de hachage cohérente.

Si une relation d'ordre total est disponible, alors un tableau trié a des performances de consultation comparables à celles des arbres binaires, des performances d'insertion dans le pire des cas de l'ordre de celles des tables de hachage, et moins de complexité et d'utilisation de la mémoire que les deux.

La complexité d'insertion dans le pire des cas pour une table de hachage peut rester à O(1)/O(log K) (avec K le nombre d'éléments avec le même hachage) s'il est acceptable d'augmenter la complexité de consultation dans le pire des cas à O(K) ou O(log K) si les éléments peuvent être triés.

Les invariants pour les arbres et les tables de hachage sont coûteux à restaurer si les clés changent, mais moins de O(n log N) pour les tableaux triés.

Ce sont des facteurs à prendre en compte pour décider de la mise en œuvre à utiliser :

1. Disponibilité d'une relation de commande totale.
2. Disponibilité d'une bonne fonction de hachage pour la relation d'équivalence.
3. Connaissance du nombre d'éléments par A-priori.
4. Connaissance du taux d'insertions, de suppressions et de consultations.
5. Complexité relative des fonctions de comparaison et de hachage.

Answer 5

Les tables de hachage permettent des recherches plus rapides :

• Vous avez besoin d'une clé qui génère une distribution régulière (sinon, vous manquerez beaucoup de choses et devrez vous fier à autre chose qu'un hachage, comme une recherche linéaire).
• Les hachoirs peuvent utiliser beaucoup d'espace vide. Vous pouvez réserver 256 entrées mais n'en avez besoin que de 8 (jusqu'à présent).

Arbres binaires :

• Déterministe. O(log n) je pense...
• N'ont pas besoin d'espace supplémentaire comme les tables de hachage.
• Il faut les trier. Ajouter un élément au milieu signifie déplacer le reste.