Comment choisir entre une table de hachage et un tri (arbre de préfixes) ?

Question

Donc, si je dois choisir entre une table de hachage et un arbre de préfixes, quels sont les facteurs discriminants qui me conduiraient à choisir l'un plutôt que l'autre. De mon point de vue naïf, il me semble que l'utilisation d'un trie a un coût supplémentaire puisqu'il n'est pas stocké comme un 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 limite supérieure). Peut-être que le mot anglais le plus long est de 50 caractères ?

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

Quelqu'un peut-il me donner un point de vue plus expérimenté sur ce sujet ? Merci !

Answer 1

Avantages des essais :

L'essentiel :

• Temps de consultation prévisible O(k), où k est la taille de la clé.
• La recherche peut prendre moins de temps que k s'il n'y en a pas.
• Supporte la traversée ordonnée
• Pas besoin d'une fonction de hachage
• La suppression est simple

Nouvelles opérations :

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

Avantages de la structure liée :

• S'il y a beaucoup de préfixes communs, l'espace qu'ils nécessitent est partagé.
• Les essais immuables peuvent partager la structure. Au lieu de mettre à jour une trie sur place, vous pouvez en construire une nouvelle qui n'est différente que le long d'une branche, et qui pointe ailleurs dans l'ancienne trie. Cela peut être utile pour la concurrence, les versions multiples et simultanées d'une table, etc.
• Un trie immuable est compressible. C'est-à-dire qu'il peut partager la structure sur le suffixes aussi bien, par le biais du hash-consing.

Les 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 essais pour la plupart des objectifs.
• Vos clés ne doivent pas avoir de structure particulière.
• Plus efficace du point de vue de l'espace que la structure évidente de trie liée ( voir les commentaires ci-dessous )

Answer 2

Tout dépend du problème que vous essayez de résoudre. Si vous n'avez besoin que d'insertions et de recherches, optez pour une table de hachage. Si vous devez résoudre des problèmes plus complexes, tels que des requêtes liées à des préfixes, une table de tri est peut-être la meilleure solution.

Answer 3

Tout le monde connaît les tables de hachage et leurs utilisations, mais le temps de recherche n'est pas exactement constant, il dépend de la taille de la table de hachage et de la complexité de calcul de la fonction de hachage.

La création d'énormes tables de hachage pour une consultation efficace n'est pas une solution élégante dans la plupart des scénarios industriels où même une petite latence/extensibilité a de l'importance (par exemple, le commerce à haute fréquence). Vous devez vous soucier de l'optimisation des structures de données en fonction de l'espace qu'elles occupent en mémoire afin de réduire les pertes de cache.

Le middleware de messagerie est un très bon exemple où trie répond mieux aux exigences. Vous avez un million d'abonnés et d'éditeurs de messages dans diverses catégories (en termes de JMS - Topics ou échanges), dans de tels cas, si vous voulez filtrer les messages en fonction des topics (qui sont en fait des chaînes), vous ne voulez certainement pas créer une table de hachage pour le million d'abonnements avec le million de topics. Une meilleure approche consiste à stocker les sujets dans un tableau, de sorte que lorsque le filtrage est effectué sur la base de la correspondance des sujets, sa complexité est indépendante du nombre de sujets/abonnements/éditeurs (elle dépend uniquement de la longueur de la chaîne). J'aime cette structure de données parce que vous pouvez être créatif avec elle pour optimiser l'espace requis et donc avoir moins de ratés de cache.

Answer 4

Utilisez un arbre :

1. Si vous avez besoin de la fonction de complétion automatique
2. Trouvez tous les mots commençant par 'a' ou 'axe' et ainsi de suite.
3. Un arbre de suffixes est une forme particulière d'arbre. Les arbres à suffixes ont toute une liste d'avantages que le hachage ne peut couvrir.

Answer 5

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, alors qu'un tableau varie en fonction des données.