HashSet如何提供常数时间的添加操作？

Question

我在阅读 HashSet 的 javadocs 时遇到了一个有趣的陈述：

该类为基本操作（添加、删除、包含和大小）提供了恒定时间性能

这让我非常困惑，因为我不明白如何可能对比较操作进行恒定时间，即 O(1)。以下是我的想法：

如果这是真的，那么无论我往我的 HashSet 中倾倒多少数据，我都能以恒定时间访问任何元素。也就是说，如果我将一个元素放入我的 HashSet，则查找它将花费与我有 googolplex 元素相同的时间。

然而，如果我有恒定数量的桶或者一致的哈希函数，这是不可能的，因为对于任意固定数量的桶，该桶中的元素数量将随着集合中的元素数量呈线性增长（如果数字足够大，则增长速度较慢）。

那么，这只有在每次插入元素时（或每隔一段时间）更改哈希函数才能实现。一个永远没有冲突的简单哈希函数将满足这个需求。对于字符串的一个玩具示例可以是：取字符串的 ASCII 值并将它们连接在一起（因为添加可能导致冲突）。

然而，对于足够大的字符串或数字等，这个哈希函数和任何其他类似的哈希函数都很可能失败。你可以形成的桶的数量立即受到堆栈/堆空间的限制等的影响。因此，无法无限地跳过内存位置，因此您最终必须填补间隙。

但是，如果在某个时刻重新计算哈希函数，则此操作所需的时间只能与找到通过 N 个点的多项式相同，即 O(nlogn)。

因此，我感到困惑。虽然我相信 HashSet 可以在 O(n/B) 时间内访问元素，其中 B 是它决定使用的桶的数量，但我不明白 HashSet 如何可能在 O(1) 时间内执行添加或获取函数。

注意：这篇文章和这篇文章都没有解决我所列举的问题。

- Teofrostus

---

如果我们假设每个操作的 O(N/B) 边界是正确的，那么很容易展示出 O(1) 摊销边界。例如，我们可以在 N 等于 B 时每次将桶的数量加倍。 - kraskevich

如果N达到B时你会将B加倍，那么如何创建一个哈希函数，使其均匀地哈希到B个桶中？假设我从B = 2和一个聪明的哈希函数开始，它将把前两个项均匀地分配到这两个桶中。然而，一旦我将B加倍到4，我应该使用什么函数来确保接下来的两个元素会落在桶3和4中？如果它们有“机会”落入1和2，则经过足够多次加倍后，桶将变得前重：更早创建的桶将具有更多的元素。如果你正在将元素重新映射到桶中，这将需要非常数时间。 - Teofrostus

我在谈论摊销（而不是最坏情况）的常数时间。是的，当我们将桶的数量加倍（或增加其他固定常数因子）时，它确实涉及完全重新分配和重新映射。 - kraskevich

它是常数时间，而不是O(1)。 HashSet不支持任意大的哈希表，因此复杂性理论不适用。 - Paul Hankin

Answer 1

桶的数量是动态的，大约为 ~2n，其中 n 是集合中元素的数量。

请注意，HashSet 提供的是 摊销分析 和平均时间性能为 O(1)，而不是最坏情况。这意味着，我们偶尔可能会遭受 O(n) 操作。
因此，当桶装得太满时，我们只需创建一个新的、更大的数组，并将元素复制到其中。
这需要 n 次操作，并且在集合中的元素数量超过 2n/2=n 时进行，因此，这个操作的平均成本被限制在 n/n=1，也就是一个常数。

此外，HashMap 提供的碰撞数量也是常数级别的 平均值。

假设您正在添加元素 x。填充 h(x) 的一个元素的概率为 ~n/2n = 1/2。填充三个元素的概率是 ~(n/2n)^2 = 1/4（对于大量的 n 值），依此类推。
这使得平均运行时间为 1 + 1/2 + 1/4 + 1/8 + ...。由于这个总和收敛于 2，所以这个操作的平均时间是常数级别的。

- amit

---

这是一个很好的回复。对于感兴趣的摊销复杂度的人来说，可以搜索摊销二进制计数器和数组列表分配，这些都是一些简单的例子，展示了它的重要性。 - ShellFish

Answer 2

我了解哈希结构需要一个良好的哈希函数来避免冲突，并且该结构不应该是满的。通常，哈希结构定义了一种填充限制，例如70%。当对象数量使结构填充超过此限制时，您应该扩展其大小以保持在限制以下并保证性能。通常情况下，在达到限制时，您将结构的大小加倍，以便结构大小增长速度快于元素数量，并减少需要执行的调整/维护操作数量。这是一种维护操作，它由重新哈希所有包含在结构中的元素以在调整大小后重新分配它们组成。当然，这有一个成本，其复杂度为O（n），其中n是存储在结构中的元素数量，但是此成本未集成到添加函数中，因此需要进行维护操作。

我还学到，哈希函数通常取决于用作参数的结构的大小（有类似于达到限制的最大元素数是结构大小的质数之一，以减少冲突概率之类的内容），这意味着您不会更改哈希函数本身，您只需更改其中一个参数。

回答您的评论，如果桶0或1已满，则没有保证当您调整大小为4个新元素时，它们将进入桶3和4。也许调整大小到4将使元素A和B现在在桶0和3中。

当然，以上都是理论性的，在现实生活中，您没有无限的内存，可能会发生冲突，并且维护成本等等，因此您需要对要存储的对象数量有一个概念，并与可用内存进行权衡，以尝试选择哈希结构的初始大小，这将限制执行维护操作的需求并允许您保持O（1）性能。

- Quicky