哈希表的时间复杂度

我对哈希表的时间复杂度感到困惑许多文章都指出它们是“分期付款O（1）”而非真实订单O（1）这在实际应用中意味着什么。在哈希表中操作的平均时间复杂度是多少，在实际实现中不是理论上的，为什么这些操作不是真实的O（1）？哈希表的时间复杂度

2010-10-16 marme

这是相关的，虽然不是完全一样的问题：http://stackoverflow.com/ question/2369467/why-are-hash-table-expansions-usually-done-by-doubling-the-size – 2010-10-16 14:34:40

这有助于回答插入，但并未解释有关其他操作的任何内容，我最感兴趣的解释是在散列表中查找的时间复杂度 – marme 2010-10-16 14:45:21

在散列函数的一些假设下，对于大多数散列表实现来说，查找是真正的O（1）时间。事实上，在有限的桶深度的一些实现中，它在设计上是恒定的。 – 2010-10-16 14:52:31

对于散列表的某些用途，不可能提前创建它们的“正确”大小，因为不知道在表的生命周期中需要同时保存多少个元素。如果您想保持快速访问，您需要随着元素数量的增长不时调整表格大小。调整大小的时间与表中已有元素的数量相关，并且通常在插入时完成，当数字元素通过阈值时。

这些调整大小的操作很少，以至于分摊的插入成本仍然保持不变（通过遵循表格大小的几何级数，例如每次调整大小时将其大小加倍）。但不时插入一个插入需要O（n）时间，因为它会触发调整大小。

实际上，除非您正在构建硬实时应用程序，否则这不是问题。

来源

2010-10-16 14:42:54

这不仅是考虑的尺寸 - 它也是散列碰撞。有不同的方式来处理它们，但无论你做什么，它都不会在O（1）时间发生。在实践中，平均情况仍然接近于O（1），尽管除非哈希表得到相当满。 – Jords 2010-10-16 14:58:14

@Jords我不知道“接近O（1）”是什么意思。此外，我相当相信文献中的“摊销O（1）”对应于哈希函数的假设，其中桶深度保持在固定边界以下，因此恒定时间。因为如果没有调整大小的查找不是恒定的时间，那么分期查找肯定不是恒定的时间。 – 2010-10-16 15:10:54

事先不可能知道你使用散列函数会得到多少冲突，以及需要调整大小等。这可以添加一个哈希表的性能不可预测的元素，使其不正确O（1）。然而，实际上所有的哈希表实现在广大，绝大多数的插入中提供了O（1）。这与插入数组相同 - 除非需要调整大小，否则它是O（n），加上碰撞的不确定性。

实际上，散列冲突是非常罕见的，您需要考虑这些细节的唯一条件是您的特定代码在其必须运行的时间窗口非常紧密时。对于几乎每个用例，哈希表都是O（1）。比O（1）插入更令人印象深刻的是O（1）查找。

来源

2010-10-16 14:48:08 Puppy

好吧，O（1）查找也是真的数组 – 2016-04-27 19:04:53

上平均情况下插入值划分为哈希表需要，，O（1）时间。计算散列函数，从散列表中选择bucked，然后插入项目。在最坏的情况下，所有的元素将被散列到相同的值，这意味着整个桶列表必须是遍历的 ，或者在开放寻址的情况下，必须探测整个表格直到一个空的点被发现。因此，在最坏的情况下，插入需要O（n）的时间

参阅：http://www.cs.unc.edu/~plaisted/comp550/Neyer%20paper.pdf（哈希表部分）

来源

2017-04-29 04:08:38

哈希表的时间复杂度

回答

相关问题