algorithm - 哈希排序与快速排序的比较

Question

我正在阅读 Algorithims in Nutshell 中有关哈希排序与快速排序比较的性能，如下所示。

https://www.safaribooksonline.com/library/view/algorithms-in-a/9780596516246/ch04s08.html

With 26 buckets, once n >256, Hash sort begins to quadruple its performance as the problem size doubles, showing how too few buckets leads to O(n^2) performance.

    n     26 buckets    676 buckets     quick sort    256   0.000051      0.000062        0.000045    512   0.000108      0.000093        0.000098

注意，n为输入次数，时间单位为秒。

我的问题是，作者所说的“随着问题规模的翻倍，灰分排序的性能开始翻两番”是什么意思？，以及几个桶是 O(n^2)

Answer 1

有两种不同类型的哈希表:开放式和封闭式。看来您指的是开放。

在具有 k 个“桶”(或“槽”)的开放哈希表中，每个桶通常实现为(单)链表。空槽包含空指针。当多个条目散列到同一个槽(冲突)时，它们会在检查重复项后附加到链表中[通常重复项不会被再次计算]。对于插入，退化情况下的时间复杂度可以是 O(1) 到 O(n) [见下文]。

让我们考虑一个具有 n 个条目和 k 个槽的开放哈希表。对于单个 查找，可能存在导致 O(n) 的退化情况，例如，当所有条目散列到同一个槽时，散列表的行为就像一个无序列表。即使哈希函数或多或少均匀地分隔数据，如果 n >> k 那么时间复杂度对于单个查找 是 O(n/k)，但是由于 k是一个常数，这与 O(n) 相同。

我可以设想 O(n^2) 行为的唯一方法是在多个 查找的上下文中。我认为，这是一种查看哈希表时间复杂度的非标准方式。然而，如果一个人的观点是在 n 次插入之后查看一批 n 次查找，在退化的情况下，我认为批处理复杂度可以被视为 O(n^2)。

顺便说一句，避免第二种退化情况的常用方法是将槽(桶)的数量加倍，并在 n 大于(初始)k 时重新哈希。这种调整(增大)散列大小的操作需要 O(n) 时间，并且需要可以使其输出范围加倍的动态散列函数。此操作会随着时间的推移进行分摊，从而导致 O(log(n)) 分摊插入——优点是可以保留 O(1) 分摊查找。