哈希表运行时复杂度（插入，搜索和删除）
为什么我在哈希表上仍然看到这些函数的不同运行时复杂性？
在Wiki上，搜索和删除均为O（n）（我认为哈希表的要点是具有恒定的查找，因此，如果搜索为O（n）的意义是什么）。
在不久前的一些课程笔记中，我看到了许多复杂的情况，具体取决于某些细节，包括所有O（1）。如果我可以全部获得O（1），为什么还要使用其他实现？
如果我以C ++或Java之类的语言使用标准哈希表，那么我期望的时间复杂度是多少？
回答：
哈希表是O(1) 情况下的复杂性，但是它遭受O(n)
时间复杂性的困扰。[我认为这就是您的困惑所在]
O(n)由于以下两个原因，哈希表的时间复杂度最差：
- 如果将太多元素散列到同一个键中：在此键中查找可能会花费一些
O(n)时间。 - 哈希表通过其负载平衡后 -必须重新哈希[创建一个更大的新表，并将每个元素重新插入到该表中]。
但是，这被认为是O(1)平均和摊销的情况，因为：
- 很少有很多项目会被散列到相同的键[如果您选择了一个好的散列函数，并且负载平衡不大。
- 重新哈希运算
O(n)（）最多可以在n/2ops 之后进行，而ops都是假设的O(1)：因此，当您将每个op的平均时间相加时，将得到：(n*O(1) + O(n)) / n) = O(1)
请注意，由于存在重新哈希问题-
实时应用程序和需要低延迟的应用程序-
不应将哈希表用作其数据结构。
哈希表的另一个问题：缓存
您可能会在大型哈希表中看到性能损失的另一个问题是由于缓存性能所致。
，因此对于大型集合来说，访问时间可能会更长，因为您需要将表的相关部分从内存重新加载到缓存中。
以上是 哈希表运行时复杂度（插入，搜索和删除） 的全部内容， 来源链接： utcz.com/qa/414456.html
