哈希表是
O(1)平均和
摊销的情况下的复杂性，但是它遭受
O(n)
最坏情况下的 时间复杂性的困扰。[我认为这就是您的困惑所在]
O(n)由于以下两个原因，哈希表的时间复杂度最差：
- 如果将太多元素散列到同一个键中：在此键中查找可能会花费一些
O(n)
时间。 - 哈希表通过其负载平衡后 -必须重新哈希[创建一个更大的新表，并将每个元素重新插入到该表中]。
但是，这被认为是
O(1)平均和摊销的情况，因为：
- 很少有很多项目会被散列到相同的键[如果您选择了一个好的散列函数，并且负载平衡不大。
- 重新哈希运算
O(n)
（）最多可以在n/2
ops 之后进行，而ops都是假设的O(1)
：因此，当您将每个op的平均时间相加时，将得到：(n*O(1) + O(n)) / n) = O(1)
请注意，由于存在重新哈希问题-
实时应用程序和需要低延迟的应用程序-
不应将哈希表用作其数据结构。
编辑： 哈希表的另一个问题：缓存
您可能会在大型哈希表中看到性能损失的另一个问题是由于缓存性能所致。 哈希表的缓存性能很差
，因此对于大型集合来说，访问时间可能会更长，因为您需要将表的相关部分从内存重新加载到缓存中。
