Java Tutorials (Set Implementations)：

One thing worth keeping in mind about HashSet is that iteration is linear in the sum of the number of entries and the number of buckets (the capacity).

我发现此声明令人困惑,并且想知道是否有人可以澄清该声明的含义.据我了解,如果我们有x个存储桶,而每个存储桶中恰好有1个项目,则可以获得最佳的迭代性能.

设x = 200k.这给了我们20万个条目和20万个存储桶.

相反,如果所有项目都放在1个存储桶中(据我所读,这确实很可怕),我们将有200k条目数和1个存储桶.

由于200k 200k> 200k 1,是否表示如果应用上述陈述,则1个存储桶的性能要比200k存储桶的性能高？

解决方法:

Since 200k + 200k > 200k + 1, doesn’t that mean that if we apply the above statement, the performance of 1 bucket is more than the performance of 200k buckets?

是的,当遍历HashSet中的所有元素时,将它们分散在多个存储桶中的事实是不好的.

当他们说迭代在条目数和存储桶数的总和中是线性的时,他们的意思是迭代在O(n m)中进行,其中n是存储桶数,m是输入项数.常量不显示.例如,可能花费的时间是0.0001 * n m,即与元素数量的影响相比,铲斗数量的影响确实很小.

(顺便说一句,还有另一个名为LinkedHashSet的数据结构,其特性与HashSet相似,但是迭代时间仅与元素数成正比.)