HashMap and HashSet versus TreeMap and TreeSet

Hash-Based: `HashMap` and `HashSet`

HashMap and HashSet store elements using a hash table. When you insert a key (or an element in the case of HashSet), its hashCode() method is called to compute an integer hash value. The table maps this hash to a bucket — a position in an internal array. The element is placed in that bucket.

How Hashing Works

hashCode() returns an int for the key.
The map applies a supplemental hash function to reduce collisions from poor-quality hash codes.
The result is mapped to an array index: index = supplementalHash & (table.length - 1) (fast because table.length is always a power of 2).
If multiple keys map to the same bucket (a collision), the bucket stores a linked list or a balanced tree (since Java 8, when a bucket’s chain exceeds a threshold, it is converted to a red-black tree for $O(\log n)$ worst-case lookup).

Load Factor and Rehashing

The load factor (default 0.75) determines when the hash table resizes. When the number of entries exceeds capacity × load factor, the table is rehashed: a new array roughly double the size is allocated, and every entry is re-inserted into the new table (because the index mapping depends on the array length).

A load factor of 0.75 balances space and time — lower values reduce collisions at the cost of memory; higher values save memory but increase collision probability.

Performance

Operation	Average	Worst-Case
`put` / `add`	$O(1)$	$O(n)$ (all keys collide)
`get` / `contains`	$O(1)$	$O(n)$
`remove`	$O(1)$	$O(n)$

With a well-distributed hash function, operations are practically constant-time. The worst case occurs when all keys hash to the same bucket — degenerating to a linked list scan (or $O(\log n)$ if treeified).

Ordering

None. The iteration order of HashMap/HashSet is unspecified and may change when the table is resized. Do not rely on it.

Tree-Based: `TreeMap` and `TreeSet`

TreeMap and TreeSet are backed by a red-black tree — a self-balancing binary search tree. All operations maintain the tree balanced, guaranteeing $O(\log n)$ time.

How Red-Black Trees Work (Conceptual)

A red-black tree is a binary search tree with extra colouring constraints (each node is red or black) that ensure the tree remains approximately balanced. The longest path from root to leaf is at most twice the shortest path. After every insertion and deletion, the tree performs local rotations and recolourings to restore balance.

The practical result: the tree never degenerates into a linked list, so search, insertion, and deletion are always $O(\log n)$ .

Ordering Guarantee

This is the defining difference. TreeMap and TreeSet keep keys/elements in sorted order. The sorting key is determined by:

The natural ordering of the elements (via the Comparable interface), or
A Comparator supplied at construction time.

TreeSet<String> sorted = new TreeSet<>();
sorted.add("zebra");
sorted.add("aardvark");
sorted.add("monkey");
System.out.println(sorted);  // [aardvark, monkey, zebra]

Because the tree is ordered, TreeSet/TreeMap support operations that hash-based collections cannot efficiently provide:

first() / last() — smallest and largest elements
headSet(toElement) — elements strictly less than a bound
tailSet(fromElement) — elements greater than or equal to a bound
subSet(from, to) — elements in a range
floor(e) / ceiling(e) / lower(e) / higher(e) — nearest neighbours

These are all $O(\log n)$ on a tree but would require $O(n)$ scan on a hash table.

`LinkedHashMap` and `LinkedHashSet`

These combine the $O(1)$ performance of hashing with predictable iteration order. A doubly-linked list threads through all entries in either insertion order or access order (useful for LRU caches).

Map<String, Integer> ordered = new LinkedHashMap<>();
ordered.put("first", 1);
ordered.put("second", 2);
ordered.put("third", 3);
for (String key : ordered.keySet()) {
    System.out.println(key);  // first, second, third — insertion order
}

LinkedHashMap inherits all $O(1)$ hash operations from HashMap plus the predictable ordering from the linked list.

Comparison

Property	`HashMap` / `HashSet`	`TreeMap` / `TreeSet`	`LinkedHashMap` / `LinkedHashSet`
Implementation	Hash table	Red-black tree	Hash table + linked list
Average time	$O(1)$	$O(\log n)$	$O(1)$
Worst-case time	$O(n)$ (collisions)	$O(\log n)$	$O(n)$
Ordering	None (unspecified)	Sorted (natural or comparator)	Insertion order
`null` keys	One `null` key allowed	Not allowed (can’t be compared)	One `null` key allowed
`null` values	Allowed	Allowed	Allowed
Ordered operations	Not supported	`first()`, `last()`, `subSet()`, etc.	Not supported
Memory overhead	Moderate (array + entries)	Higher (tree nodes with parent/child pointers + colour)	Higher than `HashMap` (extra linked list pointers)

The Legacy `Hashtable`

Hashtable is a synchronised hash table from Java 1.0. It is generally superseded by HashMap (or ConcurrentHashMap for concurrent use). Key differences: Hashtable allows neither null keys nor null values; HashMap allows one null key and many null values.

Choosing Between Them

Use HashMap/HashSet for raw speed when ordering does not matter.
Use TreeMap/TreeSet when you need sorted keys/elements and range queries.
Use LinkedHashMap/LinkedHashSet when you need predictable iteration order (insertion or access) at near-HashMap speed.

Hash-Based: HashMap and HashSet