哈希表的时间复杂度是 O(1) 平均摊还还是 O(1) 均摊？

Question

哈希表的时间复杂度是 O(1) 平均摊还还是 O(1) 均摊？

4

这个问题可能有点学究，但我一直在努力深入了解分摊分析，对于哈希表的插入为什么是O(1)分摊有些困惑。(注意：我不是在谈论表扩容，我理解那部分)

使用这个定义，“分摊分析给出了每个操作在最坏情况下的平均性能(随时间变化)。” 对于N个插入到哈希表中，最坏情况似乎会导致每个操作都发生碰撞。我相信当负载保持较低时，通用哈希可以保证1/m的碰撞率，但是是否仍然存在理论上每次插入都会发生碰撞的可能性呢？

从技术上讲，哈希表插入的平均分摊分析似乎是O(1)。

编辑：您可以假设哈希表使用基本链接，在相应的链表末尾放置元素。我的真正问题涉及概率算法的分摊分析。

编辑2：我找到了一篇关于快速排序的this帖子， “此外，摊销运行时间和期望运行时间之间存在微妙但重要的差异。随机枢轴的快速排序需要O（nlogn）的期望运行时间，但其最坏情况下的运行时间为Θ（n ^ 2）。这意味着快速排序可能会花费（n ^ 2）美元的概率很小，但是随着n的增大，发生这种情况的概率趋近于零。” 我认为这可能回答了我的问题。

- K.Enfield

2

有许多实现哈希表的方法，而实现的选择会产生差异。例如，如果哈希桶是（未排序的）链表，则插入始终为O(1)，假设您从不调整表的大小。 - psmears

不同的实现方式会以不同的方式处理冲突。例如，冲突可能会进入下一个可用位置，或者它可以通过链接列表存储在相同的位置，或者类似但是通过树来存储。请指定如何处理冲突，以便我们有一个固定的目标进行分析。 - TheGreatContini

严格来说，根据问题中给出的“分摊”的定义，你是完全正确的。因此，如果哈希算法通过链表处理冲突，则其“分摊”复杂度将为O(n)。通常情况下，该术语的含义是指你所提供的“平均分摊”。 - Jardel Lucca

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ford prefect · Accepted Answer

您理论上可以在每次插入时发生冲突，但这意味着您的哈希函数性能较差，未能将值在键的“桶”中分散。理论上完美的哈希函数始终会将新值放入新的桶中，以便每个键都引用自己的桶。（我假设使用链式哈希表，并将链字段称为“桶”，这是我学到的方法）。理论上最坏的情况是将所有键都放入同一个桶中，导致该桶中的链长度达到N。

摊销背后的思想是，假设有一个相当好的哈希函数，您应该得到线性时间的插入，因为插入次数大于O（1）的次数将远远小于插入次数简单且O（1）的次数。这并不意味着插入没有任何计算（哈希函数仍然必须计算，在某些特殊情况下，哈希函数可能比查找列表更加繁琐）。

最重要的一点是，这使我们了解了大O符号中的一个重要概念，即计算时间复杂度时需要查看最常执行的操作。在这种情况下，最常执行的操作是插入一个与另一个哈希值不冲突的值。