当我遇到有趣的声明时，我正在阅读关于 HashSet 的 javadoc:
This class offers constant time performance for the basic operations (add, remove, contains and size)
这让我非常困惑，因为我不明白一个人怎么可能获得常数时间，O(1)，比较操作的性能。以下是我的想法:
如果这是真的，那么无论我将多少数据转储到我的 HashSet 中，我都能够在常数时间内访问任何元素。也就是说，如果我将 1 个元素放入我的 HashSet，找到它所花费的时间就好像我有一个 googolplex 元素一样。
但是，如果我有恒定数量的桶或一致的哈希函数，这将是不可能的，因为对于任何固定数量的桶，该桶中的元素数量将线性增长(尽管缓慢，如果数量足够大)与集合中的元素数量。
然后，唯一可行的方法是在每次插入元素(或每隔几次)时更改哈希函数。一个从不发生任何冲突的简单散列函数可以满足这种需求。字符串的一个玩具示例可能是:获取字符串的 ASCII 值并将它们连接在一起(因为添加可能会导致冲突)。
但是，对于足够大的字符串或数字等，此哈希函数和任何其他此类哈希函数可能会失败。您可以形成的桶数立即受到您拥有的堆栈/堆空间量的限制，等等。因此，不能无限期地允许跳过内存中的位置，因此您最终必须填补空白。
但是如果在某个时候重新计算哈希函数，这只能像找到一个通过 N 点的多项式一样快，或者 O(nlogn)。
我的困惑就这样来了。虽然我相信 HashSet 可以在 O(n/B) 时间内访问元素，其中 B 是它决定使用的桶数，但我看不出 HashSet 如何在 O(n/B) 时间内执行添加或获取功能1)时间。
最佳答案
桶的数量是动态的，大约是 ~2n，其中 n 是集合中元素的数量。
请注意 HashSet 给出 amortized和 O(1) 的平均时间性能，不是最坏的情况。这意味着，我们有时会遇到 O(n) 操作。
所以，当箱子太挤时，我们只需创建一个新的更大的数组，然后将元素复制到其中。
这花费了n 操作，当集合中的元素数量超过2n/2=n 时完成，所以这意味着，这个操作的平均成本以 n/n=1 为界，这是一个常量。
此外，HashMap 提供的冲突次数平均也是恒定的。
假设您要添加一个元素x。 h(x) 被一个元素填满的概率是~n/2n = 1/2。它被 3 个元素填满的概率是 ~(n/2n)^2 = 1/4(对于较大的 n 值)，依此类推很快。
这为您提供了 1 + 1/2 + 1/4 + 1/8 + ... 的平均运行时间。由于此总和收敛于 2，这意味着此操作平均需要常数时间。
关于algorithm - HashSet 如何提供恒定时间添加操作？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30504415/