Avantages des arborescences de recherche binaires par rapport aux tables de hachage

Quels sont les avantages des arbres de recherche binaires par rapport aux tables de hachage?

Les tables de hachage peuvent rechercher n'importe quel élément dans le temps Theta (1) et il est tout aussi facile d'ajouter un élément ... mais je ne suis pas sûr des avantages de l'inverse.

N'oubliez pas que les arbres de recherche binaires (basés sur des références) sont économes en mémoire. Ils ne réservent pas plus de mémoire que nécessaire.

Par exemple, si une fonction de hachage a une plage R(h) = 0...100, vous devez allouer un tableau de 100 éléments (pointeurs vers), même si vous ne faites que hacher 20 éléments. Si vous deviez utiliser une arborescence de recherche binaire pour stocker les mêmes informations, vous n'alloueriez que l'espace dont vous avez besoin, ainsi que certaines métadonnées sur les liens.

Un avantage que personne d'autre n'a souligné est que l'arbre de recherche binaire vous permet d'effectuer des recherches par plage de manière efficace.

Afin d'illustrer mon idée, je veux faire un cas extrême. Supposons que vous souhaitiez obtenir tous les éléments dont les clés sont comprises entre 0 et 5000. Et en fait, il n'y a qu'un seul élément de ce type et 10 000 autres éléments dont les clés ne sont pas dans la plage. BST peut effectuer des recherches par plage assez efficacement car il ne recherche pas un sous-arbre, ce qui est impossible d'avoir la réponse.

Alors, comment pouvez-vous effectuer des recherches par plage dans une table de hachage? Soit vous devez itérer chaque espace de compartiment, qui est O (n), soit vous devez rechercher si chacun des 1,2,3,4 ... jusqu'à 5000 existe. (qu'en est-il des clés entre 0 et 5000 sont un ensemble infini? par exemple, les clés peuvent être des décimales)

Un "avantage" d'un arbre binaire est qu'il peut être parcouru pour lister tous les éléments dans l'ordre. Ce n'est pas impossible avec une table de hachage, mais ce n'est pas une opération normale une conception dans une structure hachée.

En plus de tous les autres bons commentaires:

Les tables de hachage en général ont un meilleur comportement de cache nécessitant moins de lectures de mémoire par rapport à un arbre binaire. Pour une table de hachage, vous n'effectuez normalement qu'une seule lecture avant d'avoir accès à une référence contenant vos données. L'arbre binaire, s'il s'agit d'une variante équilibrée, nécessite quelque chose de l'ordre de k * lg (n) lectures de mémoire pour une constante k.

D'un autre côté, si un ennemi connaît votre fonction de hachage, l'ennemi peut imposer votre table de hachage pour faire des collisions, ce qui entrave considérablement ses performances. La solution de contournement consiste à choisir la fonction de hachage au hasard dans une famille, mais un BST ne présente pas cet inconvénient. De plus, lorsque la pression de la table de hachage augmente trop, vous avez souvent tendance à agrandir et à réallouer la table de hachage, ce qui peut être une opération coûteuse. Le BST a ici un comportement plus simple et n'a pas tendance à allouer soudainement beaucoup de données et à effectuer une opération de rehachage.

Les arbres ont tendance à être la structure de données moyenne ultime. Ils peuvent agir comme des listes, peuvent facilement être divisés pour un fonctionnement parallèle, ont une suppression, une insertion et une recherche rapides de l'ordre de O (lg n) . Ils ne font rien de particulièrement bien, mais ils n'ont pas non plus de comportement excessivement mauvais.

Enfin, les BST sont beaucoup plus faciles à implémenter dans des langages fonctionnels (purs) par rapport aux tables de hachage et ils ne nécessitent pas de mises à jour destructives pour être implémentées (l' argument de persistance de Pascal ci-dessus).

Les principaux avantages d'un arbre binaire par rapport à une table de hachage sont que l'arbre binaire vous donne deux opérations supplémentaires que vous ne pouvez pas faire (facilement, rapidement) avec une table de hachage

• trouver l'élément le plus proche (pas nécessairement égal à) d'une valeur clé arbitraire (ou le plus proche au-dessus / au-dessous)

• parcourir le contenu de l'arborescence dans un ordre trié

Les deux sont connectés - l'arbre binaire conserve son contenu dans un ordre trié, de sorte que les choses qui nécessitent cet ordre trié sont faciles à faire.

Un arbre de recherche binaire (équilibré) a également l'avantage que sa complexité asymptotique est en fait une limite supérieure, tandis que les temps "constants" pour les tables de hachage sont des temps amortis: si vous avez une fonction de hachage inadaptée, vous pourriez finir par se dégrader en temps linéaire , plutôt que constant.

Une table de hachage prendrait plus d'espace lors de sa création - elle disposera d'emplacements disponibles pour les éléments qui doivent encore être insérés (qu'ils soient insérés ou non), un arbre de recherche binaire ne sera aussi grand que nécessaire. être. De plus, lorsqu'une table de hachage a besoin de plus d'espace, l'expansion vers une autre structure peut prendre du temps, mais cela peut dépendre de l'implémentation.

Un arbre de recherche binaire peut être implémenté avec une interface persistante , où un nouvel arbre est renvoyé mais l'ancien arbre continue d'exister. Mis en œuvre avec soin, les anciens et les nouveaux arbres partagent la plupart de leurs nœuds. Vous ne pouvez pas faire cela avec une table de hachage standard.

Un arbre binaire est plus lent à rechercher et à insérer, mais a la très belle fonctionnalité de traversée d'infixe qui signifie essentiellement que vous pouvez parcourir les nœuds de l'arbre dans un ordre trié.

Itérer dans les entrées d'une table de hachage n'a tout simplement pas beaucoup de sens car elles sont toutes dispersées dans la mémoire.

From Cracking the Coding Interview, 6e édition

Nous pouvons implémenter la table de hachage avec un arbre de recherche binaire équilibré (BST). Cela nous donne un temps de recherche O (log n). L'avantage de cela est d'utiliser potentiellement moins d'espace, car nous n'allouons plus un grand tableau. Nous pouvons également parcourir les clés dans l'ordre, ce qui peut parfois être utile.

Les BST fournissent également les opérations «findPredecessor» et «findSuccessor» (pour trouver le prochain élément le plus petit et le suivant le plus grand) en temps O (logn), ce qui peut également être des opérations très pratiques. Hash Table ne peut pas fournir dans ce temps l'efficacité.

Si vous souhaitez accéder aux données de manière triée, une liste triée doit être maintenue en parallèle à la table de hachage. Un bon exemple est Dictionary in .Net. (voir http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx ).

Cela a pour effet secondaire non seulement de ralentir les insertions, mais cela consomme une plus grande quantité de mémoire qu'un b-tree.

De plus, comme un b-tree est trié, il est simple de trouver des plages de résultats, ou d'effectuer des unions ou des fusions.

Cela dépend aussi de l'utilisation, Hash permet de localiser la correspondance exacte. Si vous souhaitez interroger une plage, BST est le choix. Supposons que vous ayez beaucoup de données e1, e2, e3 ..... fr.

Avec la table de hachage, vous pouvez localiser n'importe quel élément en temps constant.

Si vous voulez trouver des valeurs de plage supérieures à e41 et inférieures à e8, BST peut le trouver rapidement.

L'élément clé est la fonction de hachage utilisée pour éviter une collision. Bien sûr, nous ne pouvons pas éviter totalement une collision, auquel cas nous recourons au chaînage ou à d'autres méthodes. Cela rend la récupération plus de temps constant dans le pire des cas.

Une fois pleine, la table de hachage doit augmenter sa taille de compartiment et recopier à nouveau tous les éléments. Il s'agit d'un coût supplémentaire non présent sur BST.

Les tables de hachage ne sont pas adaptées à l'indexation. Lorsque vous recherchez une plage, les BST sont meilleurs. C'est la raison pour laquelle la plupart des index de base de données utilisent des arbres B + au lieu des tables de hachage

Les arbres de recherche binaires sont un bon choix pour implémenter le dictionnaire si les clés ont un ordre total (les clés sont comparables) défini sur elles et que vous souhaitez conserver les informations de commande.

Comme BST préserve les informations de commande, il vous fournit quatre opérations de jeu dynamique supplémentaires qui ne peuvent pas être effectuées (efficacement) à l'aide de tables de hachage. Ces opérations sont:

1. Maximum
2. Le minimum
3. Successeur
4. Prédécesseur

Toutes ces opérations, comme toutes les opérations BST, ont une complexité temporelle de O (H). De plus, toutes les clés stockées restent triées dans le BST, vous permettant ainsi d'obtenir la séquence triée de clés simplement en parcourant l'arborescence dans l'ordre.

En résumé, si tout ce que vous voulez, ce sont des opérations d'insertion, de suppression et de suppression, la table de hachage est imbattable (la plupart du temps) en termes de performances. Mais si vous voulez une ou toutes les opérations énumérées ci-dessus, vous devez utiliser un BST, de préférence un BST auto-équilibré.

Le principal avantage de la table de hachage est qu'elle effectue presque toutes les opérations dans ~ = O (1). Et c'est très facile à comprendre et à mettre en œuvre. Il résout efficacement de nombreux «problèmes d'entrevue». Donc, si vous voulez craquer une interview de codage, faites-vous de meilleurs amis avec la table de hachage ;-)

Un hashmap est un tableau associatif d'ensemble. Ainsi, votre tableau de valeurs d'entrée est regroupé dans des compartiments. Dans un schéma d'adressage ouvert, vous avez un pointeur vers un compartiment, et chaque fois que vous ajoutez une nouvelle valeur dans un compartiment, vous découvrez où dans le compartiment il y a des espaces libres. Il y a plusieurs façons de faire cela: vous commencez au début du compartiment et incrémentez le pointeur à chaque fois et testez s'il est occupé. C'est ce qu'on appelle le palpage linéaire. Ensuite, vous pouvez effectuer une recherche binaire comme add, où vous doublez la différence entre le début du bucket et où vous doublez vers le haut ou vers le bas chaque fois que vous recherchez un espace libre. C'est ce qu'on appelle le sondage quadratique. D'ACCORD. Maintenant, le problème dans ces deux méthodes est que si le compartiment déborde dans l'adresse de compartiment suivante, vous devez alors-

1. Double la taille de chaque seau - malloc (N seaux) / modifier la fonction de hachage - Temps requis: dépend de l'implémentation de malloc
2. Transférez / copiez chacune des données de buckets précédentes dans les nouvelles données de buckets. Il s'agit d'une opération O (N) où N représente l'ensemble des données

D'ACCORD. mais si vous utilisez une liste liée, il ne devrait pas y avoir un tel problème, non? Oui, dans les listes liées, vous n'avez pas ce problème. Considérant que chaque bucket commence par une liste liée, et si vous avez 100 éléments dans un bucket, il vous faudra parcourir ces 100 éléments pour atteindre la fin de la liste liée, donc List.add (élément E) prendra du temps pour-

1. Hash l'élément dans un bucket - Normal comme dans toutes les implémentations
2. Prenez le temps de trouver le dernier élément de ladite opération seau-O (N).

L'avantage de l'implémentation de la liste liée est que vous n'avez pas besoin de l'opération d'allocation de mémoire et de transfert / copie O (N) de tous les compartiments comme dans le cas de l'implémentation d'adressage ouvert.

Ainsi, la façon de minimiser l'opération O (N) est de convertir l'implémentation en celle d'un arbre de recherche binaire où les opérations de recherche sont O (log (N)) et vous ajoutez l'élément à sa position en fonction de sa valeur. La caractéristique supplémentaire d'un BST est qu'il est trié!

Les arbres de recherche binaires peuvent être plus rapides lorsqu'ils sont utilisés avec des clés de chaîne. Surtout quand les cordes sont longues.

Arbres de recherche binaires utilisant des comparaisons pour moins / plus qui sont rapides pour les chaînes (lorsqu'elles ne sont pas égales). Ainsi, un BST peut répondre rapidement lorsqu'une chaîne n'est pas trouvée. Lorsqu'il est trouvé, il ne devra faire qu'une seule comparaison complète.

Dans une table de hachage. Vous devez calculer le hachage de la chaîne et cela signifie que vous devez parcourir tous les octets au moins une fois pour calculer le hachage. Puis à nouveau, lorsqu'une entrée correspondante est trouvée.