Java LinkedHashSet
›Short versionOpen if you only have a minute.
- LinkedHashSet is a hash set plus a chain, so iteration follows first-insertion order.
- add, remove, and contains stay average constant time. The chain adds memory, not a slower lookup.
- Adding an element that is already present does not move it. Order records the first successful add.
- There is no access-order flag. Getting an element leaves its place in the chain alone.
- equals and hashCode still decide membership. The chain only decides iteration.
- Use it for distinct elements in the order they first appeared. Use HashSet when order is irrelevant.
A answers the same membership questions as HashSet and adds one promise: . Distinct words in the order they first showed up in a file is the usual job.
The extra are why iteration is predictable. They do not change the . An element the table cannot find is still lost, chain or not.
First insertion, not last touch
is the detail that separates this class from an access-ordered LinkedHashMap. A second add of “Ada” returns false. The iterator still yields “Ada” in its original place. People who want “move to most recent” want a map in access order, or an explicit remove followed by add.
Removal unlinks the element. A later add appends it, so it becomes the new tail. That is the supported way to reorder one element.
One null is allowed, and it occupies one place in the order, the place where it was first added. TreeSet would reject it under natural ordering and would also sort the other elements instead of preserving arrival.
Distinct, in arrival order
Set<String> seen = new LinkedHashSet<>();
seen.add("Ada");
seen.add("Grace");
seen.add("Ada"); // false; Ada stays first
seen.remove("Ada");
seen.add("Ada"); // Ada is now last
// iteration: Grace, AdaA loop calls contains on every word and, on a miss, add. Does a later repeat of an early word move that word to the end?
No. contains does not change order, and add of an existing word returns false without relinking it. The word stays where the first add placed it. Only remove plus add moves it to the tail.