asp.net: est la complexité du temps de recherche d'une valeur par clé dans le dictionnaire constante de temps ou log2 (n)?

Question

i besoin d'un dotnet dans lequel structure de données que je peux rechercher un élément time.it constant signifie que devraient mettre en œuvre l'indexation structure de données internally.is dictionnaire USEFULL à cet effet ou d'un autre?

Answer 1

Oui, utiliser Dictionnaire <> (ou Hashtable si vous êtes sur une ancienne version de .NET). Assurez-vous que les objets que vous bourrage dans le dictionnaire ont une bonne valeur de hachage (en remplaçant GetHashCode regarder () et equals () pour vos objets que vous utilisez en tant que clés dans le dictionnaire). Si vos objets de données ont de mauvaises performances des codes de hachage commence à se dégrader. Et oui, pour répondre à votre question, semble ups dans un Hashtable / dictionnaire doit être relativement constant (livres disent généralement il est O (1), mais peut soutenir). La performance de recherche sera déterminée par de nombreux facteurs:

1. Fonction de hachage (détermine la distribution)
2. Comment la table gérer les collisions? Sondage? Seaux? (La plupart des implémentations utilisent des seaux).
3. Le tableau redimensionnable? Comment faut-il redimensionne? Les petits incréments? Puissance de 2? Les nombres premiers?
4. etc ...