Search code examples
javacollectionslinkedhashset

Why iteration time over a LinkedHashSet is not dependent on its capacity?

From the Java Docs of LinkedHashSet(LHS) class :

Iteration over a LinkedHashSet requires time proportional to the size of the set, regardless of its capacity. Iteration over a HashSet is likely to be more expensive, requiring time proportional to its capacity.

My question is why does iteration time over a LHS has no bearing on the capacity of the set ?

Solution

  • Because the LinkedHashSet comprises internally both a LinkedList and a Set. When iterating, you iterate over the (I believe, double) LinkedList, not the HashSet.