Java Full Course 2026: Set & Map Interfaces Deep Dive

This chapter explores the internal architecture, design patterns, and performance characteristics of the Set and Map interfaces in Java. We will demystify how HashMap, HashSet, LinkedHashMap, LinkedHashSet, TreeMap, and TreeSet manage data under the hood, analyze the mathematical contracts governing their operations, and trace their step-by-step execution workflows.

1. The Core Contracts of Set and Map Interfaces

The Java Collections Framework provides specialized data structures optimized for distinct access patterns. While lists (ArrayList, LinkedList) model ordered, index-accessible sequences, they perform poorly when searching for arbitrary elements. The Set and Map interfaces solve this lookup bottleneck.

The Set Contract

A Set represents a collection of elements with two fundamental guarantees:

1. No Duplicates Allowed: Attempting to add an element already present in the set will result in a no-op (returning false).
2. Average Constant-Time Lookup: Checking if an element exists (contains()) runs in average $O(1)$ time complexity, regardless of whether the set contains ten elements or ten million.

The Map Contract

A Map represents a mapping between unique keys and values. It guarantees:

1. Unique Keys: Each key can map to at most one value. Duplicate keys are not allowed.
2. Average Constant-Time Key Lookup: Retrieving a value by its key (get()) or checking key existence (containsKey()) runs in average $O(1)$ time complexity.

Real-Life Analogies

• Set: A list of unique email addresses registered on a website. If aditya@gmail.com tries to sign up again, the system rejects the duplicate.
• Map: A student database mapping a unique Roll Number (Key) to a Student Name (Value). While multiple students can share the name "Aditya", each roll number (e.g., 1001, 1002) is strictly unique.

Performance Comparison: List vs. Set/Map

In an ArrayList, elements are stored sequentially. Finding an element requires iterating through the array index-by-index, resulting in linear time complexity.

In contrast, a Set or Map uses hashing algorithms to jump directly to the target storage location, bypassing sequential iteration.

2. The Naive vs. Optimal Storage Mental Model

To understand how Java achieves $O(1)$ lookup, let us design a storage mechanism from scratch.

The Naive Approach: Direct Index Mapping

If we want to store integers and retrieve them in $O(1)$ time, we could allocate an array where the value itself acts as the index.

The Problem: Memory Explosion

If a user wants to store the number 1,000,000, we must allocate an array of size at least 1,000,001. Storing a single large integer would waste massive amounts of memory. Furthermore, this approach fails entirely for non-integer keys like String or custom objects.

The Optimal Approach: Modulo Arithmetic & Hashing

To bound memory usage, we allocate a fixed-size array of "buckets" (size $n$) and map any incoming integer key to an index within the range $[0, n-1]$ using the modulo operator:

If $n = 4$:

• Key 5 maps to: $5 \pmod 4 = 1$
• Key 6 maps to: $6 \pmod 4 = 2$
• Key 3 maps to: $3 \pmod 4 = 3$
• Key 4 maps to: $4 \pmod 4 = 0$

Regardless of how large the key is, the modulo operator guarantees it will map to a valid index within the allocated array.

3. Handling Collisions: The Chaining Mechanism

Because we map an infinite set of possible keys to a finite number of bucket indexes, two distinct keys will eventually map to the same index. This event is called a Collision.

For example, if $n = 4$:

• Key 4 maps to: $4 \pmod 4 = 0$
• Key 8 maps to: $8 \pmod 4 = 0$

Both keys demand storage at index 0. We cannot overwrite 4 with 8, as both must coexist in the structure.

The Solution: Separate Chaining

Instead of storing a single element directly in the bucket array, each bucket points to a Linked List of nodes. When a collision occurs, the new element is appended to the linked list at that bucket index.

Why Linked Lists instead of Array Lists for Chaining?

If we used dynamic arrays (like ArrayList) inside each bucket, deleting an element would require shifting subsequent elements to the left to maintain contiguous memory. This shifting operation runs in $O(k)$ time (where $k$ is the number of elements in the bucket).

A linked list allows us to delete a node in $O(1)$ time simply by updating pointer references, making it highly efficient for frequent insertions and deletions.

4. The Big Secret: Java's Set is Just a Map Wrapper

A common misconception is that Java implements HashSet and HashMap as two entirely independent data structures. In reality, Java does not have a native, independent implementation for Set.

Internally, a HashSet is merely a wrapper around a HashMap.

How HashSet Leverages HashMap

When you instantiate a HashSet, Java secretly instantiates a HashMap under the hood.

• The elements you add to the HashSet are stored as Keys in the internal HashMap.
• Because a Map requires both a key and a value, and a Set has no concept of values, Java associates every key with a constant dummy object called PRESENT.

Simplified Internal Implementation of HashSet

public class HashSet<E> implements Set<E> {
    // The backing HashMap
    private transient HashMap<E, Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    // Constructor instantiates the backing HashMap
    public HashSet() {
        map = new HashMap<>();
    }

    @Override
    public boolean add(E e) {
        // map.put returns null if the key was not previously present
        return map.put(e, PRESENT) == null;
    }

    @Override
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    @Override
    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
}

Memory Optimization of the Dummy PRESENT Object

By declaring PRESENT as a private static final Object, Java ensures that only one instance of the dummy object is allocated in the heap memory. No matter how many millions of elements you add to the HashSet, they all reference the exact same PRESENT object instance, minimizing memory overhead.

5. Internal Node Architecture of HashMap

To support separate chaining, the HashMap class defines a static nested class representing a single node in the linked list. In Java's source code, this class is named Node<K,V> (implementing Map.Entry<K,V>).

The Structure of a Node

Each node contains four fields:

1. final int hash: The precomputed hash code of the key. Storing this avoids recalculating the hash during lookups and resizing.
2. final K key: The key object.
3. V value: The value object (or the PRESENT dummy object in the case of HashSet).
4. Node<K,V> next: A reference to the next node in the chain (or null if it is the tail).

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

6. Step-by-Step Evolution of the Put Workflow

When you call map.put(key, value), Java executes a highly optimized workflow to place the node in the correct bucket.

Detailed Execution Steps

Step 1: Hash Code Generation

Java calls the key's hashCode() method to obtain a 32-bit integer. If the key is null, Java assigns it a hash value of 0.

Step 2: Hash Spreading (Supplemental Hash Function)

To prevent collisions from poorly written user hashCode() implementations, HashMap applies a bitwise spreading function:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

This shifts the higher 16 bits of the hash code to the right and XORs them with the original hash code, ensuring that both high and low bits contribute to the final index calculation.

Step 3: Index Mapping

Instead of using the slow modulo operator (%), Java uses a bitwise AND operator (&) to map the hash to a bucket index:

Note: This bitwise optimization only works when the array capacity $n$ is a power of 2 (e.g., 16, 32, 64). For example, if $n = 16$, then $n-1 = 15$ (binary 00001111). The bitwise AND operation acts as a fast mask, keeping only the lowest 4 bits of the hash.

Step 4: Collision Resolution & Insertion

• Case 1: Bucket is Empty Java instantiates a new Node and places it directly at the calculated array index.
• Case 2: Bucket is Occupied Java traverses the linked list starting at the bucket head. At each node, it checks if the incoming key matches the node's key.
  • If a match is found: The node's value is updated with the new value, and the old value is returned.
  • If no match is found: The traversal continues to the end of the list, and a new node is appended to the tail.

7. The Equals and HashCode Contract in Action

To correctly identify duplicate keys during traversal, Java relies on the strict mathematical contract between equals() and hashCode().

The Contract

1. If two objects are equal according to the equals(Object) method, calling hashCode() on each of them must produce the same integer result.
2. If two objects produce the same hash code, they are not guaranteed to be equal (this is a hash collision).

The Traversal Comparison Logic

During chain traversal, Java checks for key equality using the following condition:

if (node.hash == hash && (node.key == key || (key != null && key.equals(node.key))))

Why Check node.hash == hash First?

Comparing two integers (==) is a single CPU instruction, whereas calling .equals() can be computationally expensive (e.g., comparing two long strings character-by-character).

By checking if the precomputed hash codes match first, Java can immediately skip non-matching nodes without invoking the expensive .equals() method.

8. Collision Resolution: Chaining vs. Open Addressing

While Java uses separate chaining, another common collision resolution strategy is Open Addressing (specifically Linear Probing).

Linear Probing Explained

In linear probing, if a collision occurs at index $i$, the algorithm checks index $i+1$, then $i+2$, and so on, until it finds an empty slot in the array.

Why Java Prefers Separate Chaining

Linear probing suffers from Primary Clustering: long runs of adjacent filled slots build up, causing search times to degrade to $O(n)$.

Additionally, deleting elements in linear probing is highly complex; you cannot simply clear a slot, as doing so would break the probe path for subsequent keys. Instead, you must write dummy "deleted" markers, which complicates memory management. Separate chaining avoids these issues entirely.

9. Load Factor, Threshold, and the Rehashing Process

As more elements are added to a HashMap, the linked lists grow longer, and lookup performance degrades from $O(1)$ toward $O(n)$. To prevent this, Java dynamically resizes the bucket array.

Key Metrics

• Capacity: The total number of buckets in the array (default is 16).
• Size: The actual number of key-value pairs currently stored in the map.
• Load Factor ($LF$): A measure of how full the map is allowed to get before resizing (default is 0.75, or 75%).
• Threshold: The size at which resizing is triggered:

For a default map:

When the $13^{\text{th}}$ element is added, Java triggers a resize.

The Rehashing (Rehunging) Process

Resizing is not a simple array copy operation. Because the bucket index calculation depends on the array capacity ($\text{hash} \ \& \ (n-1)$), doubling the capacity changes the target index for most keys.

Step 1: Double the Capacity

Java allocates a new bucket array with twice the capacity of the old array (e.g., from 16 to 32).

Step 2: Rehash Every Node

Java iterates through every bucket in the old array, traverses each linked list, recalculates the new index for each node using the new capacity, and places the node into the new array.

Old Capacity: 16 (Index mask: 15)
Key Hash: 37
Old Index: 37 & 15 = 5

New Capacity: 32 (Index mask: 31)
Key Hash: 37
New Index: 37 & 31 = 5 (Remains at index 5)

Key Hash: 21
Old Index: 21 & 15 = 5
New Index: 21 & 31 = 21 (Moves to index 21)

This redistribution splits long chains across the new, larger array, keeping lookup times near $O(1)$.

10. Java 8+ Optimization: Treefication of Buckets

In Java 8, architects introduced an optimization to defend against hash collision attacks (where malicious users intentionally supply keys that produce identical hash codes to force $O(n)$ lookup times).

The Treefication Threshold

If a linked list in a single bucket grows beyond a threshold of 8 elements, and the total capacity of the map is at least 64, Java converts that linked list into a Red-Black Tree (a self-balancing binary search tree).

Why Red-Black Trees?

A Red-Black Tree guarantees $O(\log n)$ lookup, insertion, and deletion times even in the worst-case scenario of total hash collision.

Untreefication

If elements are removed and the tree size shrinks to 6 or fewer nodes, Java converts the Red-Black Tree back into a simple linked list to save memory overhead.

11. LinkedHashMap & LinkedHashSet: Preserving Insertion Order

Standard HashMap and HashSet make no guarantees about the order of elements during iteration. Iterating over them traverses the bucket array sequentially, which yields a seemingly random order.

LinkedHashMap and LinkedHashSet solve this by preserving the Insertion Order of elements.

The Doubly Linked List Overlay

To preserve order, LinkedHashMap maintains a global Doubly Linked List running through all its nodes, completely independent of the bucket array.

Node Architecture in LinkedHashMap

To support this doubly linked list, LinkedHashMap defines a node class that extends HashMap.Node by adding two pointer fields: before and after.

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; // Pointers to maintain insertion order
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

Performance Trade-off

• Pros: Iteration is faster because it traverses the doubly linked list directly, bypassing empty buckets. It also preserves insertion order.
• Cons: Higher memory footprint due to storing two additional pointers (before and after) per node, and slightly slower insertion/deletion times because the global doubly linked list pointers must be updated.

12. TreeMap & TreeSet: Hashing-Free Sorted Storage

TreeMap and TreeSet do not use hashing algorithms or bucket arrays. Instead, they store elements in a Red-Black Tree directly.

Performance Characteristics

• Time Complexity: $O(\log n)$ for search, insertion, and deletion.
• Sorting: Elements are maintained in sorted order, either by their natural ordering (implementing Comparable) or via a custom Comparator.

TreeMap Structure (Sorted Keys)
               [ 50 ]
              /      \
          [ 30 ]    [ 70 ]
          /    \    /    \
        [20]  [40][60]  [80]

Key Capabilities Unlocked by TreeMap/TreeSet

Because the underlying data structure is a sorted tree, it enables operations that are impossible with hash-based structures:

• Range Queries: Retrieve all keys between 20 and 60.
• Floor/Ceiling: Find the closest key less than or equal to a target.
• First/Last: Retrieve the minimum or maximum key in $O(1)$ time.

Custom Node Architecture in TreeMap

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK; // Red-Black Tree balancing color
}

13. Null Key and Value Support Across Implementations

Handling null values varies significantly across different map and set implementations due to their underlying data structures.

Null Support Matrix

14. Summary and Key Takeaways

• Set is a Wrapper: Java does not have a native Set implementation. HashSet, LinkedHashSet, and TreeSet are thin wrappers around HashMap, LinkedHashMap, and TreeMap respectively, using a static dummy PRESENT object as the map value.
• Separate Chaining: Java resolves hash collisions using separate chaining with linked lists.
• Optimization via Hash Comparison: During bucket traversal, Java compares integer hash codes (==) before invoking the more expensive .equals() method.
• Dynamic Resizing: When the number of elements exceeds the threshold ($\text{Capacity} \times \text{Load Factor}$), the map doubles its capacity and rehashes all existing nodes into the new array.
• Treefication: To defend against collision attacks, Java 8+ converts linked lists with more than 8 nodes into Red-Black Trees, reducing lookup times from $O(n)$ to $O(\log n)$.
• Order Preservation: LinkedHashMap uses a doubly linked list overlay to preserve insertion order, while TreeMap uses a Red-Black Tree to keep keys sorted.
• Null Key Restrictions: Hashing-based maps allow a single null key (stored at bucket index 0), whereas sorting-based maps (TreeMap) throw a NullPointerException because they cannot compare null keys.