哈希表或字典查找时间

Question

只要哈希表或字典具有唯一的哈希码，查找时间是否始终为O（1）？

如果哈希表有1亿行，查找所需的时间是否与仅有1行的情况相同？

- jquery auth

Answer 1

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

int bucket = key.GetHashCode() % totalNumberOfBuckets;

因此，哈希码不同的两个对象可能会出现在同一个桶中。每个桶都是一个List<>，索引器接下来将在该列表中查找键，其时间复杂度为O(n)，其中n是桶中项的数量。

Dictionary<>动态增加totalNumberOfBuckets的值以保持桶搜索的高效性。当您向字典添加一亿个项目时，将有数千个桶。添加项目时桶为空的概率非常小。但如果碰巧为空，则检索项所需的时间将与桶中项的数量成比例。

随着项目数量的增长，开销的增加速度非常缓慢，这被称为分摊的O(1)。

- Hans Passant

Answer 2

可能会有帮助：.NET HashTable Vs Dictionary - 字典能否像哈希表一样快？

- PRR

Answer 3

只要散列没有冲突，就是的。

- spender

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。因此，答案似乎是肯定的。 [被评为负分，所以我会解释得更好]

看起来它是恒定的。但这取决于哈希函数在所有键中给出不同的结果。由于没有哈希函数可以做到这一点，所有问题都归结为您向字典提供的数据。因此，您必须使用自己的数据进行测试，以查看是否恒定。

- gfelisberto

---

那并没有什么意义。然而，如果它们产生的数字相同且不等于0，那就是有意义的。 - Grozz

我怀疑即使查找是O(n)，这也会打印出0。 - LukeH