00:00

Help Us Improve

We're sorry this tutorial wasn't helpful. Please tell us what we can do better.

Difference Between HashSet and LinkedHashSet in Java

HashSet and LinkedHashSet are both hash-based Set implementations: they store unique elements, allow one null, and offer O(1) average add, remove and contains. The difference is iteration order:

  • HashSet makes no ordering guarantee; elements come out in an order determined by their hash codes, which may change as the set grows.
  • LinkedHashSet (a subclass of HashSet) also keeps a doubly linked list through its entries, so iteration follows insertion order.

1. Comparison Table

AspectHashSetLinkedHashSet
Iteration orderUnpredictableInsertion order
Internal structureBacked by HashMapBacked by LinkedHashMap (hash table + linked list)
HierarchyImplements SetExtends HashSet; implements SequencedSet (Java 21)
add / remove / containsO(1) averageO(1) average, slightly slower
Iteration costProportional to capacity + sizeProportional to size only
MemoryLowerHigher (two extra references per entry)
NullOne nullOne null
SinceJava 1.2Java 1.4

2. Order in Action

OrderDemo.java 
import java.util.*;

public class OrderDemo {
    public static void main(String[] args) {
        List<String> visits = List.of("Pune", "Delhi", "Kochi", "Agra", "Delhi", "Mumbai", "Pune");

        Set<String> hash = new HashSet<>(visits);
        Set<String> linked = new LinkedHashSet<>(visits);
        System.out.println("input         : " + visits);
        System.out.println("HashSet       : " + hash + "   <- order depends on hash codes");
        System.out.println("LinkedHashSet : " + linked + "   <- insertion order kept");

        linked.remove("Delhi");
        linked.add("Delhi");                    // re-adding moves it to the end
        linked.add("Kochi");                    // already present: position unchanged
        System.out.println("after remove + re-add Delhi: " + linked);

        // Java 21: SequencedSet methods on LinkedHashSet
        LinkedHashSet<String> seq = new LinkedHashSet<>(linked);
        System.out.println("getFirst/getLast: " + seq.getFirst() + " / " + seq.getLast());
        seq.addFirst("Goa");
        System.out.println("addFirst(Goa)   : " + seq + ", reversed: " + seq.reversed());
    }
}
Output
input         : [Pune, Delhi, Kochi, Agra, Delhi, Mumbai, Pune]
HashSet       : [Delhi, Kochi, Pune, Agra, Mumbai]   <- order depends on hash codes
LinkedHashSet : [Pune, Delhi, Kochi, Agra, Mumbai]   <- insertion order kept
after remove + re-add Delhi: [Pune, Kochi, Agra, Mumbai, Delhi]
getFirst/getLast: Pune / Delhi
addFirst(Goa)   : [Goa, Pune, Kochi, Agra, Mumbai, Delhi], reversed: [Delhi, Mumbai, Agra, Kochi, Pune, Goa]
  • Duplicates are removed by both; only LinkedHashSet keeps the first-seen order.
  • Re-inserting an existing element does not change its position; removing and adding it again moves it to the end.
  • Since Java 21, LinkedHashSet is a SequencedSet with getFirst, getLast, addFirst, addLast and reversed.

3. Performance

PerfDemo.java 
import java.util.*;

public class PerfDemo {
    static long ms(Runnable r) { long s = System.nanoTime(); r.run(); return (System.nanoTime() - s) / 1_000_000; }

    public static void main(String[] args) {
        int n = 1_000_000;
        Set<Integer> hash = new HashSet<>(), linked = new LinkedHashSet<>();
        long hAdd = ms(() -> { for (int i = 0; i < n; i++) hash.add(i); });
        long lAdd = ms(() -> { for (int i = 0; i < n; i++) linked.add(i); });
        long hIter = ms(() -> { long s = 0; for (int x : hash) s += x; });
        long lIter = ms(() -> { long s = 0; for (int x : linked) s += x; });
        System.out.printf("add 1M    : HashSet %4d ms | LinkedHashSet %4d ms%n", hAdd, lAdd);
        System.out.printf("iterate 1M: HashSet %4d ms | LinkedHashSet %4d ms%n", hIter, lIter);
    }
}
Output (sample run; timings vary)
add 1M    : HashSet   32 ms | LinkedHashSet   37 ms
iterate 1M: HashSet    9 ms | LinkedHashSet    5 ms

Adding is marginally slower for LinkedHashSet because it maintains links, while iteration can be faster because it follows the list instead of scanning empty buckets. The differences are small; choose based on whether you need ordering.

4. When to Use Which

  • HashSet: you only need uniqueness and fast membership tests, and order is irrelevant. It is the default choice.
  • LinkedHashSet: you need uniqueness and a predictable order, for example removing duplicates from a list while preserving order, or displaying unique items as they were entered.
  • TreeSet: you need elements sorted rather than in insertion order. See LinkedHashSet vs TreeSet.

5. Summary

  • Both store unique elements with O(1) average operations and allow one null.
  • HashSet has no defined order; LinkedHashSet keeps insertion order.
  • LinkedHashSet uses a bit more memory and adds Java 21 sequenced methods.
  • Neither is thread-safe.

Related Tutorials