est la durée de recherche pour une hache ou un dictionnaire toujours O (1) tant qu'il a un code de hachage unique?
Si une hache contient 100 millions de lignes, cela prendrait la même quantité de temps pour regarder comme quelque chose qui a une ligne?
4 Réponses :
Tant qu'il n'y a pas de collisions avec les hachages, oui.
var dict = new Dictionary<string, string>();
for (int i = 0; i < 100; i++) {
dict.Add("" + i, "" + i);
}
long start = DateTime.Now.Ticks;
string s = dict["10"];
Console.WriteLine(DateTime.Now.Ticks - start);
for (int i = 100; i < 100000; i++) {
dict.Add("" + i, "" + i);
}
start = DateTime.Now.Ticks;
s = dict["10000"];
Console.WriteLine(DateTime.Now.Ticks - start);
This prints 0 on both cases. So it seems the answer would be Yes.
[Got moded down so I'll explain better]It seems that it is constant. But it depends on the Hash function giving a different result in all keys. As there is no hash function that can do that it all boils down to the Data that you feed to the Dictionary. So you will have to test with your data to see if it is constant.
Cela ne veut rien dire. S'ils ont abouti aux mêmes numéros ne sont pas égaux à 0 d'autre part, il serait ...
Je soupçonne que cela imprimerait 0 même si la recherche était O (n).
Non. Il est techniquement possible mais il serait extrêmement rare d'obtenir exactement la même quantité de frais généraux. Une table de hachage est organisée en seaux. Dictionnaire <> (et hashtable) Calculez un numéro de godet pour l'objet avec une expression comme celle-ci: donc deux objets avec un le code de hachage peut finaliser le godet même . Un godet est une liste <>, l'indexeur suivant effectue des recherches sur cette liste de la clé O (n) où n est le nombre d'éléments dans le godet. Dictionnaire <> augmente dynamiquement la valeur de TotalNumberofbuckets garder le seau de recherche efficace. Lorsque vous pomperez cent millions d'articles dans le dictionnaire, il y aura des milliers de seaux. Les chances que le godet est vide lorsque vous ajoutez un article sera assez petit. Mais si c'est par hasard alors, oui, il faudra aussi longtemps pour récupérer l'article. La quantité de surcharge augmente très lentement car le nombre d'articles augmente. Ceci s'appelle amortis o (1).