Tables de hachage versus arbres binaires

30

Lors de la mise en œuvre d'un dictionnaire («Je souhaite rechercher les données client par leur identifiant client»), les structures de données typiques utilisées sont des tables de hachage et des arbres de recherche binaires. Je sais par exemple que la bibliothèque C ++ STL implémente des dictionnaires (ils les appellent des cartes) en utilisant des arbres de recherche binaires (équilibrés), et le framework .NET utilise des tables de hachage sous le capot.

Quels sont les avantages et les inconvénients de ces structures de données? Existe-t-il une autre option raisonnable dans certaines situations?

Notez que je ne suis pas particulièrement intéressé par les cas où les clés ont une structure sous-jacente forte, disons, ce sont tous des entiers compris entre 1 et n ou quelque chose.

Alex ten Brink
la source
1
Je vais vous exaspérer mais vous ne pouvez pas simplement dire "entiers entre 1 et n" car dans ce cas un tableau dépassera toutes les autres structures de données :-). "Strings" semble juste et couvre la plupart des situations.
jmad
@jmad, il a dit qu'il n'était pas intéressé par cette affaire.
Joe
@Joe J'ai pensé qu'il était clair que j'en tenais compte. Quoi qu'il en soit, ce n'est pas une raison pour donner le pire exemple de clé possible.
jmad
1
En fait, .NET a à la fois des dictionnaires implémentés à l'aide d'arbres et des dictionnaires implémentés à l'aide de tables de hachage (tout comme C ++ depuis la norme 2011).
sepp2k
Même chose possible sur SO: stackoverflow.com/questions/371136/…
Ciro Santilli 新疆 改造 中心 法轮功 六四 事件

Réponses:

26

Un traité entier pourrait être écrit sur ce sujet; Je vais juste couvrir quelques points saillants, et je vais garder la discussion sur d'autres structures de données au minimum (il existe en effet de nombreuses variantes). Tout au long de cette réponse, est le nombre de clés dans le dictionnaire.n

La réponse courte est que les tables de hachage sont plus rapides dans la plupart des cas , mais peuvent être très mauvaises au pire. Les arbres de recherche présentent de nombreux avantages, y compris le comportement du pire des cas , mais sont un peu plus lents dans les cas typiques.

Les arbres de recherche binaires équilibrés ont une complexité assez uniforme: chaque élément prend un nœud dans l'arbre (généralement 4 mots de mémoire), et les opérations de base (recherche, insertion, suppression) prennent temps (asymptotique garanti borne supérieure). Plus précisément, un accès dans l'arbre prend environ l o g 2 ( n ) comparaisons.O(lg(n))log2(n)

Les tables de hachage sont un peu plus variables. Ils nécessitent un tableau d'environ pointeurs. L'accès à un élément dépend de la qualité de la fonction de hachage. Le but d'une fonction de hachage est de disperser les éléments. Une table de hachage «fonctionne» si tous les éléments que vous souhaitez y stocker ont des hachages différents. Si tel est le cas, les opérations de base (recherche, insertion, suppression) prennent O ( 1 ) , avec une constante assez petite (un calcul de hachage plus une recherche de pointeur). Cela rend les tables de hachage très rapides dans de nombreux cas typiques.2nO(1)

Un problème général avec les tables de hachage est que la complexité n'est pas garantie.O(1)

  • De plus, il y a un point où la table est pleine; lorsque cela se produit (ou, mieux, un peu avant cela), la table doit être agrandie, ce qui nécessite de déplacer tous ses éléments, pour un coût . Cela peut introduire un comportement «saccadé» lorsque de nombreux éléments sont ajoutés.O(n)
  • O(1)

Lorsque vous jetez la localité de données dans le mélange, les tables de hachage fonctionnent mal. Ils fonctionnent précisément parce qu'ils stockent des éléments connexes très éloignés, ce qui signifie que si l'application recherche des éléments partageant un préfixe dans l'ordre, elle ne bénéficiera pas des effets de cache. Cela n'est pas pertinent si l'application effectue des recherches essentiellement aléatoires.

Un autre facteur en faveur des arbres de recherche est qu'ils sont une structure de données immuable : si vous avez besoin de prendre une copie d'un arbre et d'y modifier quelques éléments, vous pouvez partager la plupart de la structure de données. Si vous prenez une copie d'une table de hachage, vous devez copier tout le tableau de pointeurs. De plus, si vous travaillez dans un langage purement fonctionnel, les tables de hachage ne sont souvent pas une option.

k1k2h(k1)=h(k2)

En particulier, si vous avez besoin de l' ordre des clés, par exemple si vous souhaitez pouvoir répertorier les clés par ordre alphabétique, les tables de hachage ne vous seront d'aucune aide (vous devrez les trier), tandis que vous peut simplement parcourir un arbre de recherche dans l'ordre.

Vous pouvez combiner des arbres de recherche binaires et des tables de hachage sous la forme d' arbres de hachage . Un arbre de hachage stocke les clés dans un arbre de recherche en fonction de leur hachage. Ceci est utile, par exemple, dans un langage de programmation purement fonctionnel où vous souhaitez travailler sur des données qui n'ont pas de relation d'ordre facile à calculer.

Lorsque les clés sont des chaînes (ou des entiers), un trie peut être une autre option. Un trie est un arbre, mais indexé différemment d'un arbre de recherche: vous écrivez la clé en binaire, et allez à gauche pour un 0 et à droite pour un 1. Le coût d'un accès est donc proportionnel à la longueur de la clé. Les essais peuvent être compressés pour supprimer les nœuds intermédiaires; ceci est connu comme un arbre de patricia trie ou radix . Les arbres Radix peuvent surperformer les arbres équilibrés, en particulier lorsque de nombreuses clés partagent un préfixe commun.

Gilles 'SO- arrête d'être méchant'
la source
2
Les BST n'ont-ils pas également une mauvaise localisation des données?
svick
@svick Ils peuvent ou non, selon la façon dont les nœuds sont alloués. L'augmentation de l'arité de l'arbre peut aider sans compromettre le temps d'exécution (le coût est un code plus grand et plus complexe).
Gilles 'SO- arrête d'être méchant'
2
Sur un BST, il est facile de mettre les éléments "en ordre", pour une table de hachage, il est hors de question.
vonbrand
Autre que pour des raisons de sécurité, pourquoi est-ce important si les tables de hachage ont un mauvais temps dans le pire des cas si leur cas moyen est meilleur que celui des arbres binaires? J'imagine que la commodité utilitaire / utilisateur a une relation à peu près linéaire avec le temps qu'il faut à l'arbre pour terminer, donc la valeur attendue (moyenne) devrait être tout ce qui compte.
Kelmikra
@ Kyth'Py1k Qu'entendez-vous par «l'arbre à finir»? Le point des tables de hachage est d'accéder à une valeur à la fois, pas à l'arborescence entière, sinon une liste ou un tableau fonctionnerait mieux. Même dans les situations où la valeur moyenne est ce qui compte (ce qui n'est pas toujours le cas, par exemple lorsque vous avez des contraintes en temps réel), c'est la moyenne des demandes qui sont faites dans une situation donnée, qui ne sont souvent pas du tout uniformes sur la table. - par exemple biaisé à un certain préfixe.
Gilles 'SO- arrête d'être méchant'