Ce qui est plus rapide de trouver un élément dans une table de hachage ou dans une liste triée?

Question

Ce qui est plus rapide de trouver un élément dans une table de hachage ou dans une liste triée?

Answer 1

complexité algorithme est une bonne chose à savoir, et hashage sont connus pour être O (1) tandis qu'un vecteur trié (dans votre cas, je pense qu'il est préférable d'utiliser un tableau trié qu'une liste ) fournira O (log n) temps d'accès.

Mais vous devez savoir que la notation de la complexité vous donne le temps d'accès N allant à l'infini. Cela signifie que si vous savez que vos données va continuer de croître , la notation de la complexité vous donne une indication sur l'algorithme de choisir.

Quand vous savez que vos données garderont une longueur assez faible: par exemple, ayant seulement quelques entrées dans votre tableau / Hashtable, vous devez aller avec votre montre et mesure. Donc, un test.

Par exemple, dans un autre problème: tri d'un tableau. quelques entrées tri à bulles tandis que O (N ^ 2) peut être plus rapide que .. le tri rapide, alors qu'il est O (n log n) .

En outre, en conséquence d'autres réponses, et en fonction de votre article, vous devez essayer de trouver la meilleure fonction de hachage pour votre instance Hashtable. Dans le cas contraire, il peut conduire à une performance dramatique mauvaise pour la recherche dans votre Hashtable (comme indiqué dans la réponse de Hank Gay).

Edit: Jetez un oeil sur cet article pour comprendre la signification de la notation Big O .

Answer 2

En supposant que par «liste triée vous voulez dire « accessible au hasard, triés collection ». Une liste a la propriété que vous ne pouvez le traverser élément par élément, ce qui se traduira par une O (N) complexité.

Le meilleur moyen de trouver un élément dans une collection indexable est triée par la recherche N-aire, O (logN), tandis qu'un Hashtable sans collissions a une complexité de trouver O (1).

Answer 3

A moins que l'algorithme de hachage est très lent (et / ou mauvais), la Hashtable sera plus rapide.

Mise à jour: Comme les commentateurs ont souligné, vous pouvez également obtenir une dégradation des performances de trop de collisions non pas parce que votre algorithme de hachage est mauvais, mais simplement parce que le Hashtable est pas assez grand. La plupart des implémentations de la bibliothèque (au moins dans les langues de haut niveau) augmentera automatiquement Hashtable dans les coulisses, qui causeront plus lent que prévu des performances sur l'insert qui déclenche la croissance, mais si vous rouler vos propres, il est certainement quelque chose à considérer.

Answer 4

L'opération de get dans un SortedList est O(log n) alors que la même opération e HashTable est O(1). Ainsi, normalement , le HashTable serait beaucoup plus rapide. Mais cela dépend de plusieurs facteurs:

• La taille de la liste
• Performance de l'algorithme de hachage
• Nombre de collisions / qualité de l'algorithme de hachage

Answer 5

Il dépend entièrement de la quantité de données que vous avez enregistré.

En supposant que vous avez assez de mémoire pour jeter à elle (donc la table de hachage est assez grand), la table de hachage localisera les données cibles en un montant fixe de temps, mais la nécessité de calculer le hachage va ajouter un peu (également fixe ) au-dessus.

Recherche d'une liste triée n'aura pas que les frais généraux hachant, mais le temps nécessaire pour faire le travail de localiser réellement les données cibles augmentera à mesure que la liste grandit.

Donc, en général, une liste triée sera généralement plus rapide pour les petits ensembles de données. (Pour les ensembles de données extrêmement petites qui sont fréquemment modifiées et / ou peu recherchés, un un triés liste peut être encore plus rapide, car elle évite la surcharge de faire le tri.) Comme l'ensemble de données devient grande, la croissance du temps de recherche de liste éclipse les frais généraux fixes de hachage, et la table de hachage devient plus rapide.

Lorsque ce point d'arrêt est varie en fonction de votre table de hachage spécifique et implémentations liste-recherche triés. Exécuter des tests et des performances de référence sur un certain nombre de données généralement de taille fixe pour voir ce qui en fait de meilleurs résultats dans votre cas particulier. (Ou, si le code fonctionne déjà « assez vite », ne pas. Il suffit d'utiliser celui que vous êtes plus à l'aise et ne vous inquiétez pas sur l'optimisation quelque chose qui n'a pas besoin d'être optimisé.)

Answer 6

Dans certains cas, cela dépend de la taille de la collection (et à un degré moindre, les détails de mise en œuvre). Si votre liste est très faible, 5-10 articles peut-être, je suppose que la liste serait plus rapide. Dans le cas contraire xtofl a raison.

Answer 7

Hashtable serait plus efficace pour la liste contenant plus de 10 articles. Si la liste a moins de 10 articles, les frais généraux en raison de algo hachant sera plus.

Dans le cas où vous avez besoin d'un dictionnaire rapide mais aussi besoin de garder les articles de façon ordonnée utiliser le OrderedDictionary. (Net 2.0 et suivantes)