java - 为什么 LinkedHashSet 上的迭代时间不依赖于它的容量？

Question

来自LinkedHashSet(LHS)类的Java 文档：

LinkedHashSet 的迭代需要的时间与集合的大小成正比，无论其容量如何。HashSet 的迭代可能会更昂贵，需要的时间与其容量成正比。

我的问题是为什么 LHS 上的迭代时间与集合的容量无关？

Answer 1

因为 LinkedHashSet 内部包含 LinkedList 和 Set。迭代时，您迭代的是（我相信是双重的）LinkedList，而不是 HashSet。

Answer 2

创建一个容量为 1MB 的常规 HashSet (new HashSet(1024 * 1024)，添加 1 个元素并尝试迭代。虽然 HashSet 只有 1 个元素，但迭代器必须遍历底层 hastable 的所有 1MB 桶。但是如果它是一个 LinkedHashSet，迭代器不会遍历哈希表（该哈希表仅用于 get() 和 contains()），但会遍历 LinkedList（并行结构），其中只有一个元素。

Answer 3

遍历您需要（几乎）的 HashSet 遍历包含元素的桶，然后消除空值，这需要额外的时间。简而言之 - 有一些与将空元素排序相关的开销。

链接集合的本质是每个元素都指向下一个元素。所以，你从第一个开始，然后毫无问题地拉下一个，依此类推——这样你就可以轻松地迭代它们。