HashSet 如何提供恒定时间添加操作？
How can a HashSet offer constant time add operation?
我在阅读 HashSet 上的 javadoc 时遇到了有趣的声明：
This class offers constant time performance for the basic operations (add, remove, contains and size)
这让我很困惑，因为我不明白一个人怎么可能得到常数时间，O(1)，比较操作的性能。以下是我的想法：
如果这是真的，那么无论我将多少数据转储到我的 HashSet 中，我都将能够在恒定时间内访问任何元素。也就是说，如果我将 1 个元素放入我的 HashSet，找到它所花费的时间就好像我有一个 googolplex 元素一样。
但是，如果我有恒定数量的桶或一致的哈希函数，这将是不可能的，因为对于任何固定数量的桶，该桶中的元素数量将线性增长（尽管缓慢，如果数量足够大）与集合中的元素数量。
那么，唯一可行的方法是在每次插入元素（或每隔几次）时更改哈希函数。一个从不发生任何冲突的简单散列函数可以满足这种需求。字符串的一个玩具示例可能是：获取字符串的 ASCII 值并将它们连接在一起（因为添加可能会导致冲突）。
但是，对于足够大的字符串或数字等，此哈希函数和任何其他此类哈希函数可能会失败。您可以形成的桶数立即受到 stack/heap 数量的限制space 你有，等等。因此，不能无限期地允许跳过内存中的位置，所以你最终必须填补空白。
但是如果在某个时候重新计算散列函数，这只能和找到一个通过 N 点的多项式一样快，或者 O(nlogn)。
我的困惑就这样来了。虽然我相信 HashSet 可以在 O(n/B) 时间内访问元素，其中 B 是它决定使用的桶数，但我看不出 HashSet 如何可能在O(1) 次。
注意： and this post两者都没有解决我列出的问题..
桶的数量是动态的，大约为 ~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，这意味着这个操作平均需要常数时间。
我对散列结构的了解是，要保持 O(1) 的插入删除复杂度，你需要有一个好的散列函数来避免冲突，并且结构不应该是满的（如果结构是满的，你会发生碰撞）。
通常散列结构定义了一种填充限制，例如 70%。
当对象的数量使结构填充超过此限制时，您应该扩展它的大小以保持在限制和保证性能以下。通常，在达到限制时将结构的大小加倍，以便结构大小的增长速度快于元素的数量，并减少要执行的 resize/maintenance 操作的数量
这是一种维护操作，包括重新散列包含在结构中的所有元素，以在调整大小的结构中重新分配它们。可以肯定的是，这有一个复杂度为 O(n) 的成本，n 是结构中存储的元素数量，但这个成本没有集成到 add 函数中，这将使维护操作成为需要
我想这就是打扰你的地方。
我还了解到，散列函数通常取决于用作参数的结构的大小（有类似达到限制的最大元素数是结构大小的质数，以减少冲突的可能性或类似的东西）意味着你不改变散列函数本身，你只是改变它的参数。
为了回答您的评论，如果桶 0 或 1 已填充，则不能保证当您将大小时调整为 4 时，新元素将进入桶 3 和 4。也许调整为 4 会使元素 A 和 B 现在位于桶中0 和 3
当然以上都是理论上的，在现实生活中你没有无限的内存，你可能会发生碰撞并且维护需要成本等等，所以这就是为什么你需要了解你将要使用的对象的数量存储并与可用内存进行权衡以尝试选择散列结构的初始大小，这将限制执行维护操作的需要并允许您保持 O(1) 性能
我在阅读 HashSet 上的 javadoc 时遇到了有趣的声明：
This class offers constant time performance for the basic operations (add, remove, contains and size)
这让我很困惑，因为我不明白一个人怎么可能得到常数时间，O(1)，比较操作的性能。以下是我的想法：
如果这是真的，那么无论我将多少数据转储到我的 HashSet 中，我都将能够在恒定时间内访问任何元素。也就是说，如果我将 1 个元素放入我的 HashSet，找到它所花费的时间就好像我有一个 googolplex 元素一样。
但是，如果我有恒定数量的桶或一致的哈希函数，这将是不可能的，因为对于任何固定数量的桶，该桶中的元素数量将线性增长（尽管缓慢，如果数量足够大）与集合中的元素数量。
那么，唯一可行的方法是在每次插入元素（或每隔几次）时更改哈希函数。一个从不发生任何冲突的简单散列函数可以满足这种需求。字符串的一个玩具示例可能是：获取字符串的 ASCII 值并将它们连接在一起（因为添加可能会导致冲突）。
但是，对于足够大的字符串或数字等，此哈希函数和任何其他此类哈希函数可能会失败。您可以形成的桶数立即受到 stack/heap 数量的限制space 你有，等等。因此，不能无限期地允许跳过内存中的位置，所以你最终必须填补空白。
但是如果在某个时候重新计算散列函数，这只能和找到一个通过 N 点的多项式一样快，或者 O(nlogn)。
我的困惑就这样来了。虽然我相信 HashSet 可以在 O(n/B) 时间内访问元素，其中 B 是它决定使用的桶数，但我看不出 HashSet 如何可能在O(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，这意味着这个操作平均需要常数时间。
我对散列结构的了解是，要保持 O(1) 的插入删除复杂度，你需要有一个好的散列函数来避免冲突，并且结构不应该是满的（如果结构是满的，你会发生碰撞）。
通常散列结构定义了一种填充限制，例如 70%。 当对象的数量使结构填充超过此限制时，您应该扩展它的大小以保持在限制和保证性能以下。通常，在达到限制时将结构的大小加倍，以便结构大小的增长速度快于元素的数量，并减少要执行的 resize/maintenance 操作的数量
这是一种维护操作，包括重新散列包含在结构中的所有元素，以在调整大小的结构中重新分配它们。可以肯定的是，这有一个复杂度为 O(n) 的成本，n 是结构中存储的元素数量，但这个成本没有集成到 add 函数中，这将使维护操作成为需要
我想这就是打扰你的地方。
我还了解到，散列函数通常取决于用作参数的结构的大小（有类似达到限制的最大元素数是结构大小的质数，以减少冲突的可能性或类似的东西）意味着你不改变散列函数本身，你只是改变它的参数。
为了回答您的评论，如果桶 0 或 1 已填充，则不能保证当您将大小时调整为 4 时，新元素将进入桶 3 和 4。也许调整为 4 会使元素 A 和 B 现在位于桶中0 和 3
当然以上都是理论上的，在现实生活中你没有无限的内存，你可能会发生碰撞并且维护需要成本等等，所以这就是为什么你需要了解你将要使用的对象的数量存储并与可用内存进行权衡以尝试选择散列结构的初始大小，这将限制执行维护操作的需要并允许您保持 O(1) 性能