HashTable或字典查找时间

Question

HashTable或字典的查找时间总是O(1)吗，只要它有一个唯一的哈希码？

如果一个HashTable有一亿行，查找时间会和只有一行的东西相同吗？

Answer 1

不是的。这在技术上是可能的，但获得完全相同数量的开销将是极其罕见的。哈希表被组织成存储桶。Dictionary<> (和哈希表)使用如下表达式计算对象的存储桶号：

int bucket = key.GetHashCode() % totalNumberOfBuckets;

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

Dictionary<>会动态增加totalNumberOfBuckets的值，以保持存储桶搜索的效率。当你在字典中输入一亿个条目时，就会有数千个桶。当您添加项目时，存储桶为空的可能性将非常小。但是如果它是偶然的，那么，是的，它将花费同样长的时间来检索物品。

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

Answer 2

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

Answer 3

只要没有与散列发生冲突，就可以。