Avantages des arbres binaires de recherche sur les tables de hachage

Question

Quels sont les avantages des arbres binaires de recherche sur les tables de hachage?

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

Answer 1

Rappelez-vous que arbres binaires de recherche (base de référence) sont efficaces mémoire. Ils ne réservent plus de mémoire que nécessaire.

Par exemple, si une fonction de hachage a une portée R(h) = 0...100, alors vous devez allouer un tableau de 100 (pointeurs-à) éléments, même si vous Hashage seulement 20 éléments. Si vous deviez utiliser un arbre de recherche binaire pour stocker les mêmes informations, vous n'allouez autant d'espace que vous avez besoin, ainsi que des métadonnées sur les liens.

Answer 2

Un avantage que personne n'a d'autre sur cet arbre est pointu de recherche binaire vous permet d'effectuer des recherches de portée efficace.

Afin d'illustrer mon idée, je veux faire un cas extrême. Dites que vous voulez obtenir tous les éléments dont les clés sont entre 0 à 5000. Et en réalité il n'y a qu'un seul élément et 10000 autres éléments dont les clés ne sont pas dans la gamme. BST peut effectuer des recherches de portée très efficace car il ne cherche pas un sous-arbre qui est impossible d'avoir la réponse.

Alors, comment pouvez-vous faire des recherches dans une gamme table de hachage? Vous avez besoin soit d'itérer chaque espace seau, qui est O (n), ou vous devez rechercher si chacun 1,2,3,4 ... jusqu'à 5000 existe. (Quid des clés entre 0 et 5000 sont un ensemble infini? Par exemple les touches peuvent être décimales)

Answer 3

Un « avantage » d'un arbre binaire est qu'il peut être traversé à la liste de tous les éléments dans l'ordre. Ceci est impossible avec une table de hachage, mais n'est pas une conception d'une opération normale dans une structure hachée.

Answer 4

En plus de tous les autres bons commentaires:

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

Par contre, si un ennemi connaît votre fonction de hachage l'ennemi peut appliquer votre table de hachage pour produire des collisions, ce qui entrave considérablement ses performances. La solution est de choisir la fonction de hachage au hasard d'une famille, mais un BST n'a pas cet inconvénient. En outre, lorsque la pression de la table de hachage augmente trop, vous avez souvent tendance à enlargen et réallouer la table de hachage qui peut être une opération coûteuse. Le BST a un comportement plus simple ici et n'a pas tendance à attribuer tout à coup un grand nombre de données et faire une opération de ressasser.

Les arbres ont tendance à être la structure de données moyen ultime. Ils peuvent agir comme des listes, peuvent être fendus facilement pour le fonctionnement en parallèle, ont le retrait rapide, insertion et recherche de l'ordre de : O (logn) . Ils ne font rien en particulier bien, mais ils n'ont ni aucun comportement trop mauvais.

Enfin, BSTS sont beaucoup plus faciles à mettre en œuvre (pur) langages fonctionnels par rapport aux tables-hachage et ils ne nécessitent pas des mises à jour destructrices à mettre en œuvre ( persistance argument Pascal ci-dessus).

Answer 5

Les principaux avantages d'un arbre binaire sur une table de hachage est 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 égale à) une valeur de clé arbitraire (ou le plus haut / bas)

• itérer à travers le contenu de l'arbre dans l'ordre de tri

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

Answer 6

A (équilibré) arbre binaire de recherche a aussi l'avantage que sa complexité asymptotique est en fait une limite supérieure, tandis que les temps de « constant » pour les tables de hachage sont fois amorti: Si vous avez une fonction de hachage ne convient pas, vous pourriez finir par dégradants en temps linéaire, plutôt que constante.

Answer 7

Une table de hachage prendrait plus d'espace quand il est créé - il aura emplacements disponibles pour les éléments qui ne sont pas encore à insérer (ou non ils sont jamais insérés), un arbre de recherche binaire ne sera aussi grand que il doit être. En outre, quand un hachage table a besoin de plus d'espace, en expansion à une autre structure pourrait prendre beaucoup de temps, mais cela pourrait dépendre de la mise en œuvre.

Answer 8

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

Answer 9

Un arbre binaire est plus lent à rechercher et insérer dans, mais a la particularité très agréable des infixes qui traversal essentiellement des moyens que vous pouvez parcourir à travers les nœuds de l'arbre dans un ordre de tri.

Itère les entrées d'une table de hachage n'a tout simplement pas beaucoup de sens parce qu'ils sont tous dispersés dans la mémoire.

Answer 10

BSTS fournissent également les opérations « findPredecessor » et « findSuccessor » (Pour le prochain plus petit et plus grands éléments suivants) O (logn) le temps, ce qui pourrait aussi être des opérations très pratiques. Hash Table ne peut pas fournir en temps que l'efficacité.

Answer 11

De Cracking l'entrevue de codage, 6e édition

Nous pouvons mettre en œuvre la table de hachage avec un arbre binaire équilibré (BST). Cela nous donne une O (log n) temps de recherche. L'avantage de ce potentiel est en utilisant moins d'espace, puisque nous n'allouons un large éventail. Nous pouvons également itérer les touches dans l'ordre, qui peuvent être parfois utiles.

Answer 12

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

Ceci a l'effet secondaire non seulement inserts ralentir, mais il consomme une plus grande quantité de mémoire qu'un b-arbre.

En outre, étant donné qu'un b-arbre est trié, il est simple de trouver des gammes de résultats, ou pour effectuer des syndicats ou des fusions.

Answer 13

Il dépend aussi de l'utilisation, Hash permet de localiser correspondance exacte. Si vous voulez requête pour une gamme alors BST est le choix. Supposons que vous avez un grand nombre de données e1, e2, e3 ..... en.

Avec table de hachage, vous pouvez trouver tout élément en temps constant.

Si vous voulez trouver des valeurs de portée supérieure à E41 et à moins de E8, BST peut rapidement constater que.

L'essentiel est la fonction de hachage utilisée pour éviter une collision. Bien sûr, nous ne pouvons pas éviter totalement une collision, dans ce cas, nous avons recours à d'autres méthodes ou Enchaînement. Cela rend la récupération plus rien de temps constant dans le pire des cas.

Une fois complète, table de hachage doit augmenter sa taille de seau et copier tous les éléments à nouveau. Ceci est un coût supplémentaire non présent sur BST.

Answer 14

A hashmap est un tableau associatif ensemble. Ainsi, votre tableau de valeurs d'entrée se mis en commun dans des seaux. Dans un système ouvert d'adressage, vous avez un pointeur sur un seau, et chaque fois que vous ajoutez une nouvelle valeur dans un seau, vous trouvez où dans le seau il y a des espaces libres. Il y a quelques façons de le faire vous this- commencer au début du seau et incrémenter le pointeur à chaque fois et tester si son occupation. Ceci est appelé linéaire sondage. Ensuite, vous pouvez faire une recherche binaire comme ajouter, où vous doublez la différence entre le début du seau et où vous doublez vers le haut ou vers le bas chaque fois que vous êtes à la recherche d'un espace libre. Ce sondage est appelé quadratique. D'ACCORD. Maintenant, les problèmes dans ces deux méthodes est que si le seau déborde dans l'adresse suivante seaux, alors vous devez -

1. Double SIZE- chaque seaux malloc (N seaux) / changer le hachage Fonction- Le temps nécessaire: dépend de la mise en œuvre malloc
2. Transfert / copier chacune des données Seaux antérieures dans les nouvelles données de seaux. Ceci est une opération O (N) où N représente l'ensemble des données

OK. mais si vous utilisez un chaînée il ne devrait pas être un tel droit de problème? Oui, listes chaînées vous n'avez pas ce problème. Compte tenu de chaque seau pour commencer par une liste chaînée, et si vous avez 100 éléments dans un seau, il vous oblige à traverser ces 100 éléments pour atteindre la fin de la liste chaînée d'où l'List.add (élément E) prendra du temps -

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

L'avantage de la mise en œuvre de chaînée est que vous n'avez pas besoin de l'opération d'allocation de mémoire et O (N) transfert / copie de tous les seaux comme dans le cas de la mise en œuvre ouverte d'adressage.

Ainsi, la façon de minimiser l'O (N) l'opération est de convertir la mise en œuvre à celle d'un binaire Recherche Arbre où les opérations de recherche sont O (log (N)) et que vous ajoutez l'élément dans sa position en fonction de la valeur de ce . La caractéristique supplémentaire d'un BST est qu'il vient triée!

Answer 15

tables de hachage ne sont pas bonnes pour l'indexation. Lorsque vous êtes à la recherche d'une gamme, BSTS sont mieux. C'est la raison pour laquelle la plupart des indices de base de données utilisent des arbres B + au lieu des tables de hachage

Answer 16

arbres binaires de recherche sont bon choix pour mettre en œuvre le dictionnaire si les clés ont un peu d'ordre au total (les clés sont comparables) définies sur eux et que vous voulez conserver les informations de commande.

BST préserve les informations de commande, il vous offre quatre opérations de réglage de dynamique supplémentaires qui ne peuvent pas être effectuées (efficacement) en utilisant des tables de hachage. Ces opérations sont:

1. Maximum
2. Minimum
3. Successeur
4. Prédécesseur

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

En résumé, si tout ce que vous voulez est des opérations insérer, supprimer et supprimer ensuite la table de hachage est imbattable (la plupart du temps) dans l'exécution. Mais si vous voulez tout ou partie des opérations énumérées ci-dessus, vous devez utiliser un BST, de préférence un BST auto-équilibrage.

Answer 17

arbres binaires de recherche peut être plus rapide quand il est utilisé avec les touches de chaîne. Surtout quand les chaînes sont longues.

arbres binaires de recherche utilisant des comparaisons moins / plus rapide qui sont pour les chaînes (quand ils ne sont pas égaux). Ainsi, un BST peut répondre rapidement lorsqu'une chaîne est introuvable. Quand il a trouvé qu'il devra faire 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 passer par tous les octets au moins une fois pour calculer le hachage. Là encore, lorsqu'une entrée correspondante est trouvée.

Answer 18

principal avantage de la table de hachage est qu'il fait presque toutes les opérations en ~ = O (1). Et il est très facile à comprendre et à mettre en œuvre. Il ne résout beaucoup de problèmes « d'interview » efficacement. Donc, si tu veux casser une entrevue de codage, faire les meilleurs amis avec table de hachage; -)