Comment choisir entre une table de hachage et un Trie (arbre de préfixe)?

Question

Donc, si je dois choisir entre une table de hachage ou un arbre de préfixes, quels sont les facteurs discriminants 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 entraîne une charge supplémentaire, car elle n’est pas stockée 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), elle peut être essentiellement O (1) (par rapport à la limite supérieure). Le mot anglais le plus long contient peut-être 50 caractères?

Les tables de hachage sont consultables instantanément une fois que vous obtenez l'index . Hacher la clé pour obtenir l’indice semble toutefois pouvoir être franchi en 50 étapes.

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

Answer 1

Avantages des essais:

Les bases:

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

Nouvelles opérations:

• Vous pouvez rapidement rechercher les 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 plusieurs préfixes communs, l'espace requis est partagé.
• Les tentatives immuables peuvent partager la structure. Au lieu de mettre à jour un test en place, vous pouvez en créer un nouveau différent le long d'une branche, pointant vers l'ancien test. Cela peut être utile pour la concurrence, plusieurs versions simultanées d'une table, etc.
• Un tri immuable est compressible. Autrement dit, il peut également partager la structure sur les suffixes , en utilisant le hachage.

Avantages des tables de hachage:

• Tout le monde connaît les hashtables, non? Votre système disposera déjà d’une belle implémentation bien optimisée, plus rapide que la plupart des tentatives.
• Vos clés n'ont pas besoin de structure particulière.
• Plus économe en espace que la structure de tri 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 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 relatives aux préfixes, alors une solution pourrait être la meilleure solution.

Answer 3

Tout le monde connaît la table de hachage et ses utilisations, mais il ne s’agit pas d’un temps de recherche constant, cela dépend de la taille de la table de hachage, de la complexité 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 dans lesquels même une faible latence / évolutivité (par exemple: trading haute fréquence). Vous devez également vous préoccuper des structures de données à optimiser pour l'espace occupé par la mémoire afin de réduire les erreurs de cache.

Un middleware de messagerie est un très bon exemple de solution répondant mieux aux besoins. Vous avez un million d'abonnés et d'éditeurs de messages dans différentes catégories (en termes JMS - Sujets 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 million de sujets. Une meilleure approche consiste à stocker les sujets dans trie. Ainsi, lorsque le filtrage est effectué en fonction de la correspondance de sujets, sa complexité est indépendante du nombre de sujets / abonnements / éditeurs (dépend uniquement de la longueur de la chaîne). J'aime cela parce que vous pouvez faire preuve de créativité avec cette structure de données pour optimiser les besoins en espace et ainsi réduire le nombre de cache manquants.

Answer 4

Utilisez un arbre:

1. Si vous avez besoin de la fonctionnalité de saisie automatique
2. Recherchez tous les mots commençant par "a" ou "ax", etc. "
3. Un arbre de suffixe est une forme spéciale d’arbre. Les arbres de suffixes offrent toute une liste d'avantages que le hachage ne peut pas couvrir.

Answer 5

L'implémentation

HashTable est peu encombrante par rapport à l'implémentation Trie de base. Mais avec des chaînes, la commande est nécessaire dans la plupart des applications pratiques. Mais HashTable perturbe totalement l'ordre lexographique. Désormais, si votre application effectue des opérations basées sur un ordre lexographique (comme une recherche partielle, toutes les chaînes avec un préfixe donné, tous les mots dans un ordre trié), vous devez utiliser Essais. HashTable ne doit être utilisé que pour la recherche (car il donne sans doute une durée de recherche minimale).

P.S.: En dehors de ceux-ci, les arbres de recherche ternaires (TST) constitueraient un excellent choix. Sa durée de consultation est supérieure à HashTable, mais elle est efficace dans toutes les autres opérations. En outre, il est plus efficace en termes d'espace que d'essais.

Answer 6

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 tentatives de différents types auront généralement des opérations O (k) , 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 " ferme " et " animaux de la ferme " pour hacher la même valeur, la fonction de hachage devra alors utiliser tous les bits de la clé, et ainsi hacher "les animaux de la ferme" devrait prendre environ deux fois plus de temps que " ferme " (sauf si vous êtes dans une sorte de scénario de hash roulant, mais il existe également des scénarios de sauvegarde d'opération similaires avec des tentatives). Et avec un essai à la vanille, il est clair que l'insertion des "animaux de la ferme" prendra environ deux fois plus longtemps que juste "ferme". Sur le long terme, il en va de même pour les essais compressés.

Answer 7

L'insertion et la recherche sur un tri 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 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.

Du point de vue des données, le tri est plus onéreux, mais vous pouvez choisir un tri compressé qui vous mettra à nouveau plus ou moins sur un lien avec la table de hachage.

Pour briser la cravate, posez-vous la question suivante: dois-je rechercher des mots entiers uniquement? 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 hash. 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 suffixes importent, optez pour un test.

Et si vous le faites juste pour le plaisir, la mise en oeuvre d’un essai vous permettrait de profiter pleinement d’un dimanche après-midi.

Answer 8

Certaines applications (généralement intégrées et 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 une durée d'exécution connue, tandis qu'une trie varie en fonction des données.