散列表O(1)摊销还是O(1)平均摊销？

Question

Edit：您可以假设hashtable使用基本链接，其中元素位于相应链表的末尾。我的真正问题是关于概率算法的摊销分析。

编辑2：我在quicksort上发现了这篇文章，“摊销运行时间和预期运行时间之间有一个微妙但重要的差异。使用随机枢轴的quicksort的预期运行时间为O（n log n）,但其最坏的运行时间为θ(n^2)。这意味着quicksort的成本很小，但随着n的增加，这种可能性接近于零。”我想这大概回答了我的问题。

Answer 1

理论上，每次插入都可能发生冲突，但这意味着哈希函数的性能很差，无法在键的“桶”之间空出值。一个理论上完美的哈希函数总是将一个新值放入一个新的bucket，这样每个键都将引用它自己的bucket。（我假设是一个链式哈希表，并将链字段称为“bucket”，这正是我所学到的）。理论上最坏的情况是，函数会将所有的键插入同一个桶中，从而在该桶中形成长度为n的链。

摊销背后的思想是，给定一个相当好的散列函数，您最终应该得到一个线性的插入时间，因为插入>O(1)的次数与插入简单和O(1)的次数相比会大大相形见绌。这并不是说插入不需要任何计算（散列函数仍然需要计算，在某些特殊情况下，散列函数的计算量可能比仅仅查看列表更大）。

最后，这给我们带来了big-O中的一个重要概念，即在计算时间复杂度时，需要查看最频繁执行的操作。在本例中，即插入与另一个哈希不冲突的值。