performance - LinkedList 与 HashMap 的摊销性能

Question

对于大多数操作，哈希表的摊销性能通常被认为是 O(1)。

例如，标准 LinkedList 实现的搜索操作的摊销性能是多少？是 O(n) 吗？

我对这是如何计算的有点困惑，因为在最坏的情况下(假设哈希函数总是冲突)，哈希表在搜索操作方面几乎等同于 LinkedList (假设一个标准的存储桶实现)。

我知道在实践中，除非哈希函数被破坏，否则这种情况永远不会发生，因此在一系列操作中，平均性能几乎是恒定的时间，因为碰撞很少见。但是在计算摊销的最坏情况性能时，我们不应该考虑最坏情况序列和最坏情况实现吗？

Answer 1

没有“摊销的最坏情况性能”这样的东西。摊销性能是一种长期操作序列的“平均”性能。

对于哈希表，有时需要在一长串插入之后调整哈希表的大小，这将花费 O(n) 时间。但是，由于它只在每次 O(n) 次插入时发生，因此该操作的成本分摊到所有插入以获得 O(1) 的摊销时间。

是的，在散列函数损坏的最坏情况下，散列表的每个操作都可能是 O(n)。但是，分析这样的哈希表是没有意义的，因为它不是典型用法的情况。