Avantages de Binaires de Recherche Arbres de plus de Tables de Hachage
Quels sont les avantages de binaires de recherche arbres de plus de tables de hachage?
Tables de hachage pouvez consulter n'importe quel élément dans Thêta(1) le temps et il est tout aussi facile d'ajouter un élément....mais je ne suis pas sûr de les avantages d'aller dans l'autre sens.
- pour les tables de hachage de ce que sont le temps d'exécution pour les trouver() insert() et remove()? theta(1) theta(1) et theta(1) droit?
- Presque toujours, oui. Si vous exécutez dans un grand nombre de collisions, ces temps peuvent croître jusqu'à O(n).
- Ces délais dépendent également de votre fonction de hachage. Si, pour une raison étrange, il n'est pas O(1), de toute évidence vos activités ont une limite minimale quelle que soit l'efficacité de votre fonction de hachage de course.
- Je dirais plus grands avantages de la STB est qu'il est dans une triés structure de données. Détail de cas d'utilisation déjà répertoriés here.
- Double Possible de des Arbres Binaires vs Listes Liées vs Tables de Hachage
Vous devez vous connecter pour publier un commentaire.
Oubliez pas que les Binaires de Recherche Arbres (de référence) sont efficace de la mémoire. Ils ne réservent pas plus de mémoire que nécessaire.
Par exemple, si une fonction de hachage a une gamme
R(h) = 0...100, alors vous avez besoin d'allouer un tableau de 100 (pointeurs de-à) des éléments, même si vous êtes juste de hachage de 20 éléments. Si vous deviez utiliser un arbre de recherche binaire pour stocker la même information, vous ne allouer tout l'espace dont vous avez besoin, ainsi que certaines métadonnées sur les liens.Un avantage que personne ne l'a souligné, c'est que les binaires un arbre de recherche vous permet de faire des recherches de manière efficace.
Pour 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 effectivement 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 pouvez faire des recherches assez efficacement, car elle ne recherche pas une sous-arborescence, ce qui est impossible d'avoir la réponse.
Alors, comment pouvez-vous faire des recherches sur une table de hachage? Vous devez effectuer une itération chaque seau de l'espace, qui est en O(n), ou vous avez besoin de rechercher si chacun de 1,2,3,4... jusqu'à 5000 existe.
(ce sur les touches entre 0 et 5000 sont un ensemble infini? par exemple, les touches peuvent être décimales)
Un "avantage" d'un arbre binaire, c'est qu'il peut être parcouru à la liste de tous les éléments dans l'ordre. Ce n'est pas impossible avec une table de Hachage, mais n'est pas un fonctionnement normal d'une conception dans un hachage de la structure.
En plus de tous les autres bons commentaires:
Les tables de hachage en général ont un meilleur comportement du cache, nécessitant moins de lectures de mémoire par rapport à un arbre binaire. Pour une table de hachage, normalement, vous n'engagera qu'une seule lecture avant d'avoir accès à une référence de la tenue de vos données. L'arbre binaire, si elle est équilibrée variante, exige quelque chose de l'ordre de k * lg(n) mémoire de lit pour une constante k.
D'autre part, si un ennemi qui sait votre fonction de hachage que l'ennemi peut faire exécuter votre table de hachage pour faire des collisions, entravent considérablement ses performances. La solution de contournement est de choisir la fonction de hachage au hasard d'une famille, mais un BST n'a pas cet inconvénient. Aussi, lorsque la table de hachage la pression augmente trop, vous avez souvent tendance à enlargen et de réaffecter la table de hachage qui peut être une opération coûteuse. Le BST a plus simple comportement ici et n'a pas tendance à soudainement allouer beaucoup de données et de faire une redéfinition de l'opération.
Les arbres ont tendance à être l'ultime moyen de structure de données. Ils peuvent agir comme des listes, peuvent être divisés en parallèle rapide de suppression, d'insertion et de recherche sur l'ordre de O(lg n). Ils ne font rien particulièrement bien, mais ils n'ont pas trop mauvais comportement.
Enfin, techniciennes se chargent sont beaucoup plus faciles à mettre en œuvre (pur), les langages fonctionnels par rapport à hash-tables et ils ne nécessitent pas de mises à jour destructive pour être mis en œuvre (persistance argument par Pascal ci-dessus).
BSTs are much easier to implement in (pure) functional languages compared to hash-tables- vraiment? Je veux apprendre un langage fonctionnel maintenant!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 le faire (facile, rapide) avec une table de hachage
trouver l'élément le plus proche (pas nécessairement égal à) certains arbitraire de la valeur de la clé (ou la plus proche au-dessus/en-dessous)
parcourir le contenu de l'arbre dans l'ordre de tri
Les deux sont connectés-l'arbre binaire conserve son contenu dans un ordre trié, donc les choses qui exigent que l'ordre de tri sont faciles à faire.
Un (équilibré) binaire un arbre de recherche a également pour avantage de sa complexité asymptotique est en fait une limite supérieure, tandis que la "constante" temps pour les tables de hachage sont amortis fois: Si vous avez une inadaptés fonction de hachage, vous pourriez vous retrouver dégradants dans le temps linéaire, et non constante.
Une table de hachage prendrait plus de place quand il est tout d'abord créé - il aura des créneaux disponibles pour les éléments qui ne sont pas encore insérés (qu'ils soient ou non déjà insérée), un arbre de recherche binaire uniquement être aussi grand qu'il doit être. Aussi, quand une table de hachage besoin de plus d'espace, d'élargir à une autre structure pourrait prendre beaucoup de temps, mais cela peut dépendre de la mise en œuvre.
Un arbre de recherche binaire peut être mis en œuvre avec un persistante interface, où un nouvel arbre est retourné, mais le vieil arbre continue à 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 un standard de la table de hachage.
Un arbre binaire est plus lent de la recherche et de l'insérer dans, mais il a la caractéristique très intéressante de l'infixe de la traversée qui signifie essentiellement que vous pouvez parcourir les nœuds de l'arbre dans un ordre trié.
Une itération à travers les entrées d'une table de hachage n'est tout simplement pas beaucoup de sens parce qu'ils sont tous dispersés dans la mémoire.
Techniciennes se chargent également de fournir à l' "findPredecessor" et "findSuccessor" les opérations (Pour trouver la prochaine plus petite et la plus proche des éléments) en O(logn) le temps, ce qui pourrait également être très pratique opérations. Table de hachage ne peut pas fournir en ce que l'efficacité dans le temps.
De Les fissures de Codage Interview, 6e Édition
Nous pouvons mettre en œuvre la table de hachage avec un équilibre binaire un arbre de recherche (BST) . Cela nous donne un O(log n) temps de recherche. L'avantage, c'est potentiellement en utilisant moins d'espace, nous n'en avons plus allouer un grand tableau. Nous pouvons également faire une itération sur les touches dans l'ordre, ce qui peut parfois être utile.
Si vous souhaitez accéder aux données dans une triés manière, une liste triée doit être maintenu en parallèle à la table de hachage. Un bon exemple est le Dictionnaire .Net. (voir http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx).
Cela a pour effet non seulement de ralentir insère, mais il consomme une plus grande quantité de mémoire qu'un b-arbre.
De plus, depuis un b-arbre est trié, il est simple de trouver des plages de résultats, ou à exécuter des syndicats ou de fusion.
Il dépend aussi de l'utilisation, de Hachage permet de localiser exactement. Si vous voulez une requête pour une plage alors BST est le choix. Supposons que vous avez un grand nombre de données e1, e2, e3 ..... fr.
Avec table de hachage, vous pouvez recherchez n'importe quel élément de la constante de temps.
Si vous voulez trouver les valeurs de plage de plus de e41 et moins de e8, BST pouvez trouver rapidement ce que.
La clé, c'est la fonction de hachage utilisée pour éviter une collision. Bien sûr, on ne peut totalement éviter une collision, dans ce cas, nous avons recours à chaînage ou d'autres méthodes. Cela rend la récupération plus la constante de temps dans le pire des cas.
Une fois pleine, d'une table de hachage doit augmenter sa taille de paquet et une copie sur tous les éléments de nouveau. C'est un coût supplémentaire de ne pas présenter plus de BST.
Une table de hachage est un ensemble de tableau associatif. Donc, votre tableau de valeurs d'entrée devient commun dans des seaux. Dans un schéma d'adressage, vous avez un pointeur vers un seau, et chaque fois que vous ajoutez une nouvelle valeur dans un seau, à vous de trouver où dans le seau, il y a des places libres. Il ya quelques façons de le faire - vous commencer au début du seau et incrémenter le pointeur à chaque fois et de tester si son occupé. Ceci est appelé linéaire de détection. Ensuite, vous pouvez faire une recherche binaire telles que l'ajout, où vous avez le double de la différence entre le début du seau et où vous doubler ou de retour vers le bas chaque fois que vous êtes à la recherche d'un espace libre. Ceci est appelé quadratique de sondage.
OK. Maintenant, les problèmes de ces deux méthodes est que si le seau déborde sur le côté des seaux d'adresse, alors vous avez besoin à
Temps requis: dépend de la fonction malloc de la mise en œuvre
OK. mais si vous utilisez une linkedlist il ne devrait pas être un problème de droit? Oui, Dans les listes chaînées vous n'avez pas ce problème. Considérant chaque seau de commencer avec une liste chaînée, et si vous disposez de 100 éléments dans un seau qu'on vous demande de parcourir les 100 éléments pour arriver à la fin de la linkedlist donc la Liste.add(Element E) prendra du temps à
L'avantage de la linkedlist mise en œuvre, c'est que vous n'avez pas besoin de la mémoire de l'allocation de fonctionnement et de O(N) transfert/copie de tous les compartiments, comme dans le cas de l'abordant la mise en œuvre.
Donc, la façon de réduire le temps O(N), l'opération consiste à convertir la mise en œuvre de celle d'un Arbre de Recherche Binaire où les opérations de recherche en O(log(N)) et que vous ajoutez l'élément dans sa prise de position sur la base de sa valeur. L'ajout d'un BST est qu'il est livré triés!
Tables de hachage ne sont pas bonnes pour l'indexation. Lorsque vous êtes à la recherche pour une gamme, techniciennes se chargent mieux. C'est la raison pour laquelle la plupart des index de base de données l'utilisation de B+ arbres à la place des Tables de Hachage
Binaires de recherche arbres sont de bons choix pour mettre en œuvre dictionnaire si les clés ont certains total de la commande (les touches sont comparables) définie sur eux et que vous souhaitez conserver les informations de commande.
Comme BST conserve les informations de commande, il vous offre avec l'ajout de quatre dynamique de l'ensemble des opérations qui ne peut être exécutée (efficacement) à l'aide de tables de hachage. Ces opérations sont:
Toutes ces opérations comme chaque BST une opération de complexité temporelle de O(H). De plus, toutes les clés stockées restent triés dans la BST de sorte que vous pouvez obtenir le triée séquence de touches tout simplement en parcourant l'arbre dans l'ordre.
En résumé si vous souhaitez des opérations d'insérer, de supprimer et de retirer ensuite de la table de hachage est imbattable (la plupart du temps) dans la performance. Mais si vous voulez toutes les opérations énumérées ci-dessus, vous devez utiliser un BST, de préférence un auto-équilibrage de la BST.
Arbres binaires peut être plus rapide lorsqu'il est utilisé avec des clés de chaîne. Surtout quand les chaînes sont longues.
Arbres binaires à l'aide de comparaisons pour le moins/une plus grande qui sont rapides pour cordes (quand ils ne sont pas égales). Ainsi, un BST peut répondre rapidement à quand une chaîne n'est pas trouvée.
Quand il est trouvé, il aura besoin de faire qu'une 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 la valeur de hachage. Puis, quand une entrée correspondante.
principal avantage de la table de hachage est qu'il n'a presque tous les pf ~=O(1). Et il est très facile à comprendre et à mettre en œuvre. Il n'résoudre de nombreux "interview" les problèmes de manière efficace. Donc, si tu veux casser un codage interview, profitez des meilleurs amis avec la table de hachage 😉