哈希表运行时复杂性（插入，search和删除）
为什么我在哈希表上看到这些函数的不同运行时复杂性？
在维基上，search和删除是O（n）（我认为哈希表的重点是有恒定的查找，所以如果search是O（n），有什么意义）。
在某些课程笔记中，我看到了一些复杂性，取决于某些细节，包括所有的O（1）。 为什么如果我能得到所有的O（1），还有其他的实现呢？
如果我在像C ++或Java这样的语言中使用标准哈希表，我可以期望时间复杂度是多less？
哈希表是O(1) 平均和摊销情况的复杂性，但它遭受O(n) 最坏的情况下的时间复杂性。 [我认为这是你的困惑所在]
哈希表由于以下两个原因而遭受O(n)最差的时间复杂度：
- 如果太多的元素被散列到同一个键中：查看这个键的内部可能需要
O(n)次。 - 一旦散列表已经通过它的负载平衡 – 它必须重新哈希[创build一个新的更大的表，并重新插入每个元素到表]。
但是，据说O(1)平均和摊销情况是因为：
- 如果你select了一个好的哈希函数，而且你没有太大的负载平衡，很多项目将被哈希到相同的密钥是非常罕见的。
- 重新哈希操作，即
O(n)，最多可以在n/2操作后发生，这些操作全部假定为O(1)：因此，当您将每个操作的平均时间相加时，得到：(n*O(1) + O(n)) / n) = O(1)
请注意，由于重新哈希问题 – 实时应用程序和需要低延迟的应用程序 – 不应该使用散列表作为其数据结构。
编辑：散列表的其他问题： caching
另一个可能会在大型散列表中看到性能损失的问题是由于高速caching的性能。 哈希表遭受不良caching性能的影响 ，因此对于大量的收集 – 访问时间可能需要更长时间，因为您需要将表中的相关部分从内存重新加载回caching。
理想情况下，散列表是O(1) 。 问题是如果两个键不相等，但是它们导致相同的散列。
例如，假设string“这是最糟糕的时代”和“绿色鸡蛋和火腿”都产生了123的散列值。
插入第一个string时，将其置于存储区123中。插入第二个string后，将看到存储区123的值已存在。 然后，它会将新值与现有值进行比较，看看它们是不是相等的。 在这种情况下，为该密钥创build一个数组或链表。 此时，检索此值成为O(n)因为散列表需要遍历该桶中的每个值以find所需的值。
因此，在使用哈希表时，使用具有非常好的哈希函数的密钥非常重要，因为哈希函数速度很快，并且通常不会导致不同对象的重复值。
合理？
取决于你如何实现散列，在最坏的情况下，它可以去O（n），在最好的情况下，它是0（1）（一般来说，如果你的DS不那么容易就可以实现）
也许你正在看空间的复杂性？ 那是O（n）。 其他复杂性如哈希表条目所预期的那样。 search复杂性随着桶的数量增加而接近O（1）。 如果在最坏的情况下，散列表中只有一个桶，那么search复杂度是O（n）。
编辑回应评论我不认为这是正确的说O（1）是平均情况。 它确实是（如维基百科页面所说）O（1 + n / k）其中K是哈希表大小。 如果K足够大，那么结果就是O（1）。 但是假设K是10，N是100.在这种情况下，每个桶平均有10个条目，所以search时间肯定不是O（1）。 它是通过多达10个条目的线性search。
一些哈希表（杜鹃哈希）保证了O（1）查找
