Set Implementations: HashSet, LinkedHashSet, and TreeSet

Set Implementations: HashSet, LinkedHashSet, and TreeSet

A Set is a collection with no duplicate elements. It models the mathematical idea of a set, and Java offers three main implementations that differ in ordering guarantees and performance. Choosing the right one depends on whether you need raw speed, insertion order, or sorted order, and the trade-offs are easy to remember.

HashSet

HashSet is backed by a hash table and offers O(1) average time for add, remove, and contains. It makes no ordering promise, so iteration order can change when elements are added or when the table resizes. Use it when you only care about membership tests and uniqueness.

LinkedHashSet

LinkedHashSet is a HashSet with a linked list threading through the entries. It preserves insertion order while keeping near-hash-table performance. This makes it ideal for caches and for deduplication where you want to keep the first-seen order, such as a list of recently used items.

TreeSet

TreeSet is backed by a red-black tree and keeps elements sorted. All operations become O(log n), and elements must be mutually comparable or you must supply a Comparator. It also exposes navigational methods like first, last, higher, and subSet.

Set<String> hash = new HashSet<>();
Set<String> linked = new LinkedHashSet<>();
Set<String> sorted = new TreeSet<>();
String[] words = {"zebra", "apple", "mango", "apple"};
for (String w : words) { hash.add(w); linked.add(w); sorted.add(w); }
System.out.println(linked);
System.out.println(sorted);

Set rules to remember

All Set implementations rely on the element's equals and hashCode methods, except TreeSet, which relies on Comparable or a Comparator. Keep those contracts in mind when you place your own objects in a set - an inconsistent equals or hashCode silently breaks deduplication.

Key Points

• Set forbids duplicates and offers no indexing.
• HashSet gives the fastest membership tests but no ordering.
• LinkedHashSet preserves insertion order with near-hash speed.
• TreeSet maintains sorted order at O(log n) cost.
• Correct equals and hashCode are mandatory for hash-based sets.