Dictionary.ContainsKey()的查找时间

Big Oh表示法不会告诉您某件事需要多长时间。它告诉您它是如何缩放的。

最容易想象的是在列表<>中搜索项目，它具有O（n）复杂性。如果在包含一百万个元素的列表中找到一个项目平均需要2毫秒，那么如果列表包含两百万个元素，则可能需要4毫秒。它与列表的大小成线性比例。

O（1）预测在字典中查找元素的恒定时间。换句话说，它不取决于字典的大小。如果字典是原来的两倍大，那么查找元素所需的时间不会是原来的一倍，而是（大致）花了同样多的时间。"粗略"意味着它实际上需要更长的时间，它是摊销O（1）。

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

此外，实现似乎对Dictionary的大小有一个最高限制：c#/.net 3.5字典是如何实现的？

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

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

如果存在哈希冲突，则只能得到小于阶数1的值
Int32作为密钥将具有零散列冲突，但这不能保证零散列桶冲突。

小心会产生哈希冲突的密钥
KVP和tuple可能会产生大量哈希冲突，并且不是密钥的好候选者。