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

Question

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 ?

Answer 1

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

Answer 2

Create a regular HashSet with a capacity of 1MB (new HashSet(1024 * 1024), add 1 element and try to iterate. Though the HashSet has only 1 element the iterator will have to go over all 1MB buckets of the underlying hastable. But if it was a LinkedHashSet the iterator would not go over the hashtable (that one is used only for get() and contains()) but would go thru the LinkedList (parallel structure) and there is only one element in it.

Answer 3

Iterating over a HashSet you need (pretty much) iterate over the buckets that contain the elements, then to eliminate empty values, which requires additional time. Briefly - there is some overhead associated with sorting empty elements out.

The nature of Linked collections is so that every element points to the next one. So, you start with the first and without much problems pull the next, and so on - this way you easily iterate them all.