c# - Dicionary.ContainsKey() 的查找时间

Question

正如我在维基百科上读到的那样，哈希表的平均O(1)搜索时间。

因此，假设我有一个非常大的字典，其中可能包含数千万条记录。

如果我用来Dicionary.ContainsKey针对给定键提取值，它的查找时间是否真的是 1，或者由于 .NET 的一些不同的内部实现，它会像 log n 或其他东西。

Answer 1

大哦符号不会告诉您某件事需要多长时间。它告诉你它是如何扩展的。

最容易想象的是在 List<> 中搜索一个项目，它具有 O(n) 复杂度。如果在包含 100 万个元素的列表中查找一个项目平均需要 2 毫秒，那么如果列表具有 200 万个元素，您可以预期它需要 4 毫秒。它随着列表的大小线性缩放。

O(1) 预测在字典中查找元素的恒定时间。换句话说，它不依赖于字典的大小。如果字典是两倍大，则查找元素不需要两倍的时间，它需要（大约）同样多的时间。“大致”意味着它实际上确实需要更长的时间，它是摊销O(1)。

Answer 2

它仍然会接近O(1)，因为它仍然不取决于条目的数量，而是取决于您所拥有的冲突的数量。索引数组仍然是O(1)，无论您有多少项目。

此外，似乎存在Dictionary由实现引起的大小上限：如何实现 c#/.net 3.5 字典？

一旦我们通过了这个大小，下一步就会落在内部数组之外，它将手动搜索更大的素数。这会很慢。您可以使用 7199369（数组中的最大值）进行初始化，或者考虑字典中是否有超过 500 万个条目可能意味着您应该重新考虑您的设计。

Answer 3

关键是什么？如果密钥是 Int32，那么是的，它将接近订单 1。

如果存在哈希冲突，您只会得到少于 1 的订单。
Int32 作为键将具有零哈希冲突，但这并不能保证零哈希桶冲突。

小心产生散列冲突的键。
KVP 和 tuple 会产生大量的哈希冲突，并且不是很好的 key 候选者。