HashTable或字典查找时间

Question

HashTable或Dictionary的查找时间是否始终为O（1），只要它具有唯一的哈希代码？

如果HashTable有1亿行，那么查找具有1行的内容需要相同的时间吗？

Answer 1

不可以。技术上可行，但获得完全相同的开销量极为罕见。哈希表被组织成桶。 Dictionary <>（和Hashtable）使用如下表达式计算对象的桶号：

int bucket = key.GetHashCode() % totalNumberOfBuckets;

因此，具有不同哈希码的两个对象可以在同一个桶中结束。存储桶是List <>，索引器接下来在该列表中搜索关键字O（n），其中n是存储桶中的项目数。

Dictionary <>动态增加totalNumberOfBuckets的值以保持存储桶搜索的效率。当您在字典中输入一亿个项目时，将会有数千个桶。添加项目时存储桶为空的几率非常小。但如果是偶然的话，是的，检索项目需要花费同样的时间。

随着项目数量的增加，开销量增长非常缓慢。这称为摊销O（1）。

Answer 2

只要没有与哈希的冲突，是的。

Answer 3

可能会有所帮助：.NET HashTable Vs Dictionary - Can the Dictionary be as fast?

Answer 4

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);

这两个案例都打印0。所以似乎答案是肯定的。 [模式化了所以我会更好地解释]

它似乎是不变的。但它取决于Hash函数在所有键中给出不同的结果。由于没有可以执行此操作的哈希函数，因此它归结为您提供给词典的数据。因此，您必须使用您的数据进行测试，看它是否不变。