Comment choisir entre une table de hachage et un trie (arborescence de préfixes)?

Question

Donc, si je dois choisir entre une table de hachage ou un arbre de préfixes, quels sont les facteurs de discrimination qui me conduiraient à choisir l'un par rapport à l'autre. De mon point de vue naïf, il semble que l'utilisation d'un trie ait un surcoût supplémentaire car il n'est pas stocké en tant que tableau mais en termes de temps d'exécution (en supposant que la plus longue clé est le plus long mot anglais). (1) (par rapport à la limite supérieure). Peut-être que le plus long mot anglais est 50 caractères?

Les tables de hachage sont recherchées instantanément une fois que vous obtenez l'index. Hashing la clé pour obtenir l'indice semble cependant qu'il pourrait facilement prendre près de 50 étapes. Est-ce que quelqu'un peut me fournir un point de vue plus expérimenté à ce sujet? Merci!

Answer 1

Avantages des essais:

Les bases:

• Prévisible O (k) lookup temps où k est la taille de la clé
• recherche peut prendre moins de temps k si ce n'est pas là
• Supports commandés traversal
• Pas besoin d'une fonction de hachage
• la suppression est simple

nouvelles opérations:

• Vous pouvez rechercher rapidement des préfixes de clés, énumérez toutes les entrées avec un préfixe donné, etc.

Avantages de la structure liée:

• S'il existe plusieurs préfixes communs, l'espace dont ils ont besoin est partagé.
• Les tentatives immuables peuvent partager la structure. Au lieu de mettre à jour un trie en place, vous pouvez en construire un nouveau qui n'est différent que le long d'une branche, d'autres pointant vers l'ancien trie. Cela peut être utile pour la simultanéité, plusieurs versions simultanées d'une table, etc.
• Un trie immuable est compressible. Autrement dit, il peut partager la structure sur les suffixes ainsi, par hachage.

Avantages de hashage:

• Tout le monde sait hashtables, non? Votre système aura déjà une mise en œuvre bien optimisée, plus rapide que les essais dans la plupart des cas.
• Vos clés n'ont pas besoin d'une structure spéciale.
• Plus d'espace-efficace que la structure arborescente liée évidente (voir les commentaires ci-dessous)

Answer 2

Tout dépend du problème que vous essayez de résoudre. Si tout ce que vous devez faire est des insertions et des recherches, aller avec une table de hachage. Si vous avez besoin de résoudre des problèmes plus complexes tels que les requêtes liées aux préfixes, alors une solution peut être la meilleure.

Answer 3

Certaines applications (généralement intégrées, en temps réel) nécessitent que le temps de traitement soit indépendant des données. Dans ce cas, une table de hachage peut garantir un temps d'exécution connu, tandis qu'un trie varie en fonction des données.

Answer 4

Utilisez un arbre:

1. Si vous avez besoin fonctionnalité complète auto
2. Trouver commençant tous les mots avec 'a' ou 'ax', etc.
3. Un arbre de suffixe est une forme spéciale d'un arbre. Les suffixes ont toute une liste d'avantages que les hash ne peuvent pas couvrir.

Answer 5

Tout le monde connaît la table de hachage et ses utilisations, mais ce n'est pas exactement le temps de recherche constant, cela dépend de la taille de la table de hachage, la complexité de calcul de la fonction de hachage. La création de tables de hachage gigantesques pour une recherche efficace n'est pas une solution élégante dans la plupart des scénarios industriels où même une petite latence/évolutivité est importante (par exemple: trading haute fréquence). Vous devez vous soucier des structures de données à optimiser pour l'espace qu'il prend en mémoire aussi pour réduire le manque de mémoire cache.

Un très bon exemple où trie répond mieux aux exigences est le middleware de messagerie. Vous avez un million d'abonnés et éditeurs de messages à différentes catégories (en termes JMS - Sujets ou échanges), dans ce cas si vous souhaitez filtrer les messages en fonction des rubriques (qui sont en fait des chaînes), vous ne voulez certainement pas créer une table de hachage pour le million d'abonnements avec des millions de sujets. Une meilleure approche consiste à stocker les rubriques dans Trie, de sorte que lorsque le filtrage est effectué en fonction de la correspondance de rubrique, sa complexité est indépendante du nombre de rubriques/abonnements/éditeurs (dépend uniquement de la longueur de chaîne). Je l'aime parce que vous pouvez être créatif avec cette structure de données pour optimiser les besoins d'espace et, par conséquent, avoir un manque de cache inférieur.

Answer 6

Il y a quelque chose que je n'ai vu personne mentionner explicitement que je pense qu'il est important de garder à l'esprit. Les tables de hachage et les essais de divers types auront généralement O(k) opérations, où k est la longueur de la chaîne en bits (ou de manière équivalente en caractères).

Cela suppose que vous avez une bonne fonction de hachage. Si vous ne voulez pas que "ferme" et "animaux de ferme" aient la même valeur, alors la fonction de hachage doit utiliser tous les bits de la clé, et donc "animaux de ferme" doit être deux fois plus long que "farm" (sauf si vous êtes dans une sorte de scénario de hachage roulant, mais il y a aussi des scénarios d'économie d'opération similaires avec des essais). Et avec un essai de vanille, il est clair pourquoi l'insertion des «animaux de la ferme» prendra environ deux fois plus longtemps que la «ferme». À long terme, c'est aussi vrai avec des essais compressés.

Answer 7

La mise en œuvre HashTable est peu encombrante par rapport à l'implémentation Trie de base. Mais avec les cordes, la commande est nécessaire dans la plupart des applications pratiques. Mais HashTable perturbe totalement l'ordre lexographique. Maintenant, si votre application effectue des opérations basées sur l'ordre lexographique (comme la recherche partielle, toutes les chaînes avec un préfixe donné, tous les mots dans l'ordre de tri), vous devriez utiliser Tries. Pour la recherche seulement, HashTable devrait être utilisé (comme discutablement, cela donne un temps de recherche minimum).

P.S .: Autre que ces derniers, ternaires Arbres de recherche (TST) serait un excellent choix. Son temps de recherche est plus que HashTable, mais il est efficace dans toutes les autres opérations. En outre, il est plus efficace que les essais.

Answer 8

L'insertion et la recherche sur un trie est linéaire avec la longueur de la chaîne d'entrée O (s).

Un hachage vous donnera un O (1) pour la recherche et l'insertion, mais vous devez d'abord calculer le hachage basé sur la chaîne d'entrée qui est de nouveau O (s).

En conclusion, la complexité temporelle asymptotique est linéaire dans les deux cas. Le trie a un peu plus de ressources en perspective de données, mais vous pouvez choisir un trie compressé qui vous mettra à nouveau, plus ou moins sur un lien avec la table de hachage. Pour rompre l'égalité, posez-vous cette question: Ai-je besoin de rechercher uniquement les mots complets? Ou dois-je retourner tous les mots correspondant à un préfixe? (Comme dans un système de saisie de texte prédictif). Pour le premier cas, optez pour un hachage. C'est un code plus simple et plus propre. Plus facile à tester et à maintenir. Pour un cas d'utilisation plus élaboré où les préfixes ou les sufixes sont importants, optez pour un trie.

Et si vous le faites juste pour le plaisir, la mise en œuvre d'un trie mettrait un dimanche après-midi à un bon usage.