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

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

Les tables de hachage sont une recherche instantanée une fois que vous obtenez l'index . Le hachage de la clé pour obtenir l'index semble cependant que cela pourrait facilement prendre près de 50 étapes.

Quelqu'un peut-il me donner une perspective plus expérimentée à ce sujet? Merci!

Avantages des essais:

Les bases:

• Temps de recherche prévisible O (k) où k est la taille de la clé
• La recherche peut prendre moins de k temps si ce n'est pas là
• Prend en charge la traversée ordonnée
• Pas besoin de fonction de hachage
• La suppression est simple

Nouvelles opérations:

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

Avantages de la structure liée:

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

Avantages des hashtables:

• Tout le monde connaît les hashtables, non? Votre système aura déjà une belle implémentation bien optimisée, plus rapide que les tentatives dans la plupart des cas.
• Vos clés ne doivent pas avoir de structure particulière.
• Plus efficace en espace que la structure de trie liée évidente ( voir les commentaires ci-dessous )

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

Tout le monde connaît la table de hachage et ses utilisations, mais ce n'est pas exactement un temps de recherche constant, cela dépend de la taille de la table de hachage, de la complexité de calcul de la fonction de hachage.

La création d'énormes tables de hachage 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 également vous soucier des structures de données à optimiser pour l'espace qu'elles prennent en mémoire afin de réduire les échecs de 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 d'éditeurs de messages dans différentes catégories (en termes JMS - Thèmes ou échanges), dans ce cas, si vous souhaitez filtrer les messages en fonction de sujets (qui sont en fait des chaînes), vous ne voulez certainement pas créer de table de hachage pour le million d'abonnements avec un million de sujets. Une meilleure approche consiste à stocker les sujets dans un tri, donc lorsque le filtrage est effectué en fonction de la correspondance des sujets, sa complexité est indépendante du nombre de sujets / abonnements / éditeurs (ne dépend que de la longueur de la chaîne). Je l'aime parce que vous pouvez être créatif avec cette structure de données pour optimiser les besoins en espace et donc réduire le manque de cache.

Utilisez un arbre:

1. Si vous avez besoin de la fonction de saisie semi-automatique
2. Trouvez tous les mots commençant par «a» ou «ax» ainsi de suite.
3. Un arbre de suffixe est une forme spéciale d'arbre. Les arbres de suffixes ont toute une liste d'avantages que le hachage ne peut pas couvrir.

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

Cela suppose que vous ayez une bonne fonction de hachage. Si vous ne voulez pas que les mots «ferme» et «animaux de la ferme» aient la même valeur, alors la fonction de hachage devra utiliser tous les bits de la clé, et le hachage des «animaux de la ferme» devrait donc prendre environ deux fois plus de temps que "ferme" (sauf si vous êtes dans une sorte de scénario de hachage roulant, mais il existe des scénarios de sauvegarde d'opération quelque peu similaires avec des essais également). Et avec un trie de vanille, il est clair pourquoi l'insertion des «animaux de la ferme» prendra environ deux fois plus de temps que simplement «de la ferme». À long terme, c'est également vrai avec les essais compressés.

L'insertion et la recherche sur un trie sont linéaires 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 en fonction de la chaîne d'entrée qui est à nouveau O (s).

En conclusion, la complexité temporelle asymptotique est linéaire dans les deux cas.

Le trie a un peu plus de surcharge du point de vue des 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 briser la cravate, posez-vous cette question: Dois-je rechercher uniquement les mots complets? Ou dois-je renvoyer 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 à entretenir. Pour un cas d'utilisation plus détaillé où les préfixes ou les suffixes comptent, optez pour un essai.

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

L' implémentation HashTable est peu encombrante par rapport à l' implémentation de base de Trie . Mais avec les chaînes, 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 trié), vous devez utiliser Tries. Pour la seule recherche, HashTable doit être utilisé (comme on peut le dire, cela donne un temps de recherche minimum).

PS: En dehors de ceux-ci, les arbres de recherche ternaires (TST) seraient un excellent choix. Son temps de recherche est supérieur à celui de HashTable, mais il est efficace dans toutes les autres opérations. En outre, son plus d'espace que les essais.

Certaines applications (généralement embarquées, en temps réel) exigent 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.