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 个桶中(根据我的阅读，这真的很糟糕)，我们将有 20 万个条目和 1 个桶。
因为 200k + 200k > 200k + 1，这是否意味着如果我们应用上面的语句，1 个桶的性能超过20 万桶？
最佳答案
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相似的特性，但迭代时间仅与元素数量成正比。)
关于java - 与 "iteration is linear in the sum of the number of entries and the number of buckets"混淆，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8048410/