kuf*_*udo 1 algorithm performance computer-science data-structures
对于大多数操作,哈希表的摊销性能通常被认为是O(1).
比如标准的LinkedList实现,搜索操作的摊销性能是多少？是O(n)？
我对这是如何计算有点困惑,因为在最坏的情况下(假设总是碰撞的哈希函数),哈希表在搜索操作方面几乎等同于LinkedList(假设一个标准)斗式实施).
我知道在实践中这种情况永远不会发生,除非哈希函数被破坏,因此平均性能几乎是一系列操作的恒定时间,因为碰撞很少见.但在计算摊销的最坏情况时,我们不应该考虑最坏情况下的最坏情况序列吗？
没有"摊销的最坏情况表现"这样的事情.摊销绩效是一系列长期运营的"平均"绩效.
使用哈希表时,有时需要在长序列插入后调整哈希表的大小,这将花费O(n)时间.但是,由于它只发生在每个O(n)插入中,因此该操作的成本分散在所有插入上以获得O(1)摊销时间.
是的,在最坏的哈希函数情况下,哈希表对于每个操作都可以是O(n).但是,分析这样的哈希表是没有意义的,因为它不是典型用法的情况.