对于大多数操作，哈希表的摊销性能通常被认为是 O(1)。
在标准 LinkedList 实现上的搜索操作的摊销性能是多少？是 O(n) 吗？
我对如何计算它有点困惑，因为在最坏的情况下（假设说一个总是冲突的哈希函数），就搜索操作而言，哈希表几乎等同于 LinkedList（假设一个标准桶实现）。
我知道在实践中这永远不会发生，除非散列函数被破坏，因此平均性能在一系列操作中几乎是恒定的时间，因为冲突很少见。但是在计算摊销的最坏情况性能时，我们不应该考虑最坏情况下的最坏情况序列吗？
问问题
1822 次
2 回答
5
没有“摊销的最坏情况表现”这样的东西。摊销性能是长序列操作的一种“平均”性能。
使用哈希表，有时需要在长序列插入后调整哈希表的大小，这将花费 O(n) 时间。但是，由于它只发生在每个 O(n) 插入，因此该操作的成本分散在所有插入上以获得 O(1) 摊销时间。
是的，在散列函数损坏的最坏情况下，对于每个操作，散列表可能是 O(n)。但是，分析这样的哈希表是没有意义的，因为它不是典型的使用情况。
于 2013-02-18T23:53:50.093 回答
2
“最坏情况”有时取决于“在什么约束下的最坏情况”。
具有有效但愚蠢的哈希函数将所有键映射到 0 的哈希表的情况通常不是有意义的“最坏情况”，它不够有趣。因此，您可以在最小假设下分析哈希表的平均性能，即（出于实际目的）哈希函数将所有键的集合均匀地分布在所有哈希值的集合中。
如果散列函数相当合理但在密码学上不安全，则需要考虑单独的“最坏情况”。恶意或不知情的用户可以系统地提供哈希冲突的数据。对于“最坏情况输入”与“假设输入具有良好分布的散列”的最坏情况，您会得出不同的答案。
在对哈希表的给定插入序列中，其中一个可能会引发重新哈希。然后，您会认为那是该特定情况下的“最坏情况”。这与整体输入数据几乎没有关系——如果负载因子变得足够高，您最终会重新散列，但很少。这就是为什么“摊销”运行时间是一个有趣的衡量标准，只要您可以对总n运营成本设置更严格的上限，而不是仅n乘以一次操作的最严格上限。
即使散列函数在密码学上是安全的，您获得散列全部冲突的输入的可能性也可以忽略不计。这就是“对所有可能的输入进行平均”和“对具有最坏情况输入的一系列操作进行平均”之间存在差异的地方。所以“摊销”这个词也带有小字。根据我的经验，这通常意味着一系列操作的平均值，数据是好还是坏的问题不是摊销的一部分。nneonneo 说“没有摊销的最坏情况性能”，但根据我的经验，肯定存在最坏情况的摊销性能。所以准确地说，
当哈希表提出O(1)分期插入时，它们意味着n插入需要O(n)时间，要么（a）假设散列函数没有发生任何病理性不良事件，要么（b）n假设随机输入的预期插入时间。因为无论哪种方式，您都对哈希表得到相同的答案，所以很容易懒得说您在谈论哪个。
于 2013-02-19T00:29:04.163 回答