当我遇到有趣的语句时，我正在阅读HashSet上的javadocs：
此类为基本操作（添加、删除、包含和大小）提供恒定的时间性能
这让我非常困惑，因为我不明白一个比较操作怎么可能得到恒定的时间，O（1），性能。以下是我的想法：
如果这是真的，那么无论我在HashSet中倾倒了多少数据，我都能够在恒定的时间内访问任何元素。也就是说，如果我在HashSet中放入1个元素，找到它所花费的时间与我有一个googolplex元素相同。
然而，如果我有一个恒定数量的桶，或者一个一致的哈希函数，这是不可能的，因为对于任何固定数量的桶，桶中的元素数量都会随着集合中元素的数量线性增长（尽管速度很慢，如果数量足够大的话）。
那么，实现这一点的唯一方法是每次插入元素时（或每隔几次）都有一个不断变化的散列函数。一个从不发生任何冲突的简单散列函数可以满足这一需求。字符串的一个玩具示例可以是：获取字符串的ASCII值并将它们连接在一起（因为添加可能会导致冲突）。
但是，对于足够大的字符串或数字等，此哈希函数和任何其他此类哈希函数可能会失败。您可以形成的桶的数量立即受到您拥有的堆栈/堆空间量等的限制。因此，不能无限期地跳过内存中的位置，因此您最终必须填补空白。
但是，如果在某个时候重新计算散列函数，这只能与找到通过N个点或O（nlogn）的多项式一样快。
我的困惑由此而来。虽然我相信HashSet可以在O（n/B）时间内访问元素，其中B是它决定使用的桶数，但我不明白HashSet如何在O（1）时间内执行添加或获取函数。
注意：这篇文章和这篇文章都没有解决我列出的问题…
桶的数量是动态的，大约为~2n，其中n是集合中元素的数量。
请注意，HashSet给出了O（1）的摊销和平均时间性能，而不是最坏的情况。这意味着，我们可能会不时遭受O（n）操作。
所以，当bins过于打包时，我们只需创建一个新的、更大的数组，并将元素复制到其中。
这需要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%。当对象的数量使结构被填充超过这个限制时，您应该扩展它的大小以保持低于限制和保证性能。通常，当达到限制时，您将结构的大小加倍，以便结构大小的增长速度快于元素的数量，并减少要执行的调整大小/维护操作的数量
这是一种维护操作，包括重新散列包含在结构中的所有元素，以将它们重新分布在调整大小的结构中。当然，这有一个成本，其复杂性为O（n），其中n存储在结构中的元素数量，但这个成本没有集成在add函数中，这将使维护操作需要
我想这是什么打扰你。
我还了解到散列函数通常取决于用作参数的结构的大小（有一些东西，比如最大元素数达到极限是结构大小的素数，以减少碰撞的概率或类似的东西），这意味着你不改变散列函数本身，你只是改变它的参数。
为了回答您的评论，如果桶0或1被填满，则不保证当您调整大小为4时，新元素将进入桶3和4。也许调整大小为4会使元素A和B现在位于桶0和3中
当然，以上所有都是理论上的，在现实生活中，你没有无限的内存，你可以有碰撞和维护成本等，所以这就是为什么你需要有一个关于你将存储的对象数量的想法，并与可用内存进行权衡，以尝试选择散列结构的初始大小，这将限制执行维护操作的需要，并允许你保持O（1）性能
