de Hashtable et la carte

Question

Hashtable et carte est Hashtable est mis en œuvre en fonction de hachage, mais la carte est implémenté comme un arbre.

Ma question est, dans quelle situation, Hashtable ne peut pas être utilisé, mais une carte est un must?

Answer 1

Une motivation pour le choix d'utiliser une carte sur une table de hachage est les contraintes que chacun des endroits sur le type de clé utilisé dans le modèle instanciation. Comme décrit dans the documentation for hash_map in the SGI implementation of STL, une hash_map instanciation exige la fourniture d'un foncteur qui hash K. La STL comprend un foncteur, std::hash, qui fait cela, mais il ne mis en œuvre pour un ensemble limité de types T.

d'instanciation de std: : map d'autre part ne nécessite qu'un foncteur qui compare les objets de type K pour générer un ordre faible. Le foncteur standard std::less fonctionnera pour tout T qui définit un opérateur <. Cela signifie que, pour de nombreux types définis par l'utilisateur, l'ajout du support nécessaire pour utiliser le type en tant que clé dans une carte std :: map est beaucoup moins important que celui requis pour l'utiliser dans une table std :: hash_map.

Mis à part la question des frais généraux,

1. Seulement std :: carte, non std :: hash_map, garantit que les clés seront commandés, donc si cela est une exigence, utilisez std :: carte
2. hash_map ne fait pas partie de la norme, donc si certaines implémentations STL l'incluent, ce n'est pas le cas de toutes les implémentations. L'utilisation de hash_map a donc un impact potentiel sur la portabilité de votre programme.

Answer 2

Lorsque vous dépend que les clés sont triées.

Answer 3

Je vais répondre en ce qui concerne std :: unordered_map (hashtable) et std :: map (arbre). Notez que ni l'un ni l'autre ne spécifie réellement les mécanismes d'implémentation. Fondamentalement, vous utilisez la carte lorsque vous devez accéder aux clés dans l'ordre trié, et unordered_map dans le cas contraire.

Answer 4

Il y a un certain nombre de raisons possibles.

• Lorsqu'il n'est pas possible ou du moins pas pratique de fournir une fonction de hachage raisonnable pour vos clés. Lorsque la commande spécifiée par std::map est nécessaire ou souhaitable.
• Lorsque vous avez uniquement accès à la bibliothèque standard et êtes limité quant aux autres bibliothèques que vous pouvez utiliser.

Answer 5

Les caractéristiques d'exécution sont différentes:

Une carte arborescente a toujours un moteur d'exécution (pire des cas, cas moyen) de l'ordre de O (log n), à savoir la hauteur de l'arbre de recherche binaire (équilibré).

Les tables de hachage, d'autre part, ont un comportement d'exécution beaucoup plus compliqué. Mais dans le cas habituel, une table de hachage a une attendu exécution de O (1), à savoir constante frais généraux.

En général, le pire des cas est O (n ), qui sonne mal. Cependant, on peut montrer que pour un bon choix de paramètres, ce pire cas devient si rare qu'il ne joue pas de rôle dans la pratique. "Rare" signifie ici vraiment rare, comme en gagnant la loterie dix fois de suite et ensuite être tué par une comète. En pratique, un mauvais choix de paramètres (technique de hachage, facteur de charge ...) peut considérablement augmenter cette probabilité.

Answer 6

Si vous avez besoin de trouver l'élément 'suivant' dans la structure de données, une hashtable ne peut pas être utilisée car elle ne conserve pas les éléments dans un ordre pouvant être traversé.