Java HashMap Internals (Part 1): Hashing Functions, Buckets & Separate Chaining

Suppose you are building an API Gateway for a social media platform handling 50,000 requests per second.

Each incoming API request carries an OAuth Bearer Token string like "usr_tok_89a1f2b4". Your gateway must look up the user’s permissions object associated with that token.

If you store user permissions inside a list of key-value pairs (List<Pair<String, UserPermissions>>), fetching permissions for a token forces a linear scan through up to 500,000 active sessions. Lookups take $O(N)$ time. At 50,000 requests per second, your gateway crashes within seconds.

Array lookups run in $O(1)$ constant time because you pass an integer index. But OAuth tokens are alphanumeric strings, not array indices.

A HashMap bridges that gap by transforming arbitrary key objects into valid array bucket indices.

---

Why You Need This in Real Life

HashMap is arguably the single most frequently used data structure in enterprise software:

• Database Query Caching: Mapping SQL query hash keys to cached result sets.
• Session Stores: Mapping user session IDs to active user data objects.
• Dependency Injection Containers: Mapping interface types (UserService.class) to singleton implementation instances.

Understanding hash math and collision handling is essential for diagnosing production latency spikes and security vulnerabilities.

---

The Core Concept: Key to Array Index Mapping

A HashMap stores key-value pairs inside an internal array of nodes called the bucket table.

Key Object ("usr_tok_89a1f2b4")
       |
       v
hashCode() calculation ----> 3,254,198
       |
       v
Bit Spread & Modulo (table size 16) ----> Index 6
       |
       v
table[6] bucket slot

Converting a key into an array slot requires two steps:

1. Compute key hash code via key.hashCode().
2. Map that 32-bit hash code to a valid array index within table.length.

---

Why Power-of-Two Table Sizes Rule

Java HashMap forces internal array capacities to be powers of two ($16, 32, 64, 128 \dots$).

Why? Because calculating modulo using integer division (hash % capacity) is CPU-expensive.

When capacity is a power of two, bitwise AND produces identical modulo results at native CPU speed:

$\text{index} = \text{hash} \ \& \ (\text{capacity} - 1)$

If capacity is $16$ (0001 0000), capacity - 1 is $15$ (0000 1111).

Hash Code:    0101 1011 1100 0110
AND Mask 15:  0000 0000 0000 1111
---------------------------------
Index:        0000 0000 0000 0110  (Decimal Index 6)

---

High-Bits Bit Spread Function

If a custom hashCode() only varies in its top bits, low bitwise AND masks produce hash collisions.

HotSpot JVM solves this by XORing the top 16 bits into the bottom 16 bits:

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

This bit-mixing spread step ensures high-order bit changes alter the final bucket index.

---

Separate Chaining for Hash Collisions

Different keys can generate identical bucket indices. This collision is unavoidable due to the Pigeonhole Principle.

MyHashMap handles collisions by maintaining a singly linked list of nodes at each array bucket index.

table[] Index
  [ 0 ] ---> null
  [ 1 ] ---> Node("cat", 40) ---> Node("dog", 99) ---> null
  [ 2 ] ---> null
  [ 3 ] ---> Node("bird", 12) ---> null

---

Step-by-Step Code: MyHashMap<K, V>

public class MyHashMap<K, V> {
    static class Node<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;
        }
    }

    private Node<K, V>[] table;
    private int size;
    private static final int DEFAULT_CAPACITY = 16;

    @SuppressWarnings("unchecked")
    public MyHashMap() {
        table = (Node<K, V>[]) new Node[DEFAULT_CAPACITY];
        size = 0;
    }

    public V put(K key, V value) {
        int hash = hash(key);
        int index = (table.length - 1) & hash;

        Node<K, V> head = table[index];
        if (head == null) {
            table[index] = new Node<>(hash, key, value, null);
            size++;
            return null;
        }

        Node<K, V> curr = head;
        while (curr != null) {
            if (curr.hash == hash && (curr.key == key || (key != null && key.equals(curr.key)))) {
                V oldValue = curr.value;
                curr.value = value; // Key exists! Update value in-place.
                return oldValue;
            }
            if (curr.next == null) break;
            curr = curr.next;
        }

        curr.next = new Node<>(hash, key, value, null); // Append collision node to bucket chain
        size++;
        return null;
    }

    public V get(K key) {
        int hash = hash(key);
        int index = (table.length - 1) & hash;

        Node<K, V> curr = table[index];
        while (curr != null) {
            if (curr.hash == hash && (curr.key == key || (key != null && key.equals(curr.key)))) {
                return curr.value;
            }
            curr = curr.next;
        }
        return null;
    }

    public boolean containsKey(K key) {
        return get(key) != null;
    }

    public int size() {
        return size;
    }

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

---

Quick Summary

• HashMap transforms key hashCode() values into array indices using hash & (capacity - 1).
• Bit-mixing (h ^ (h >>> 16)) spreads top-bit variations down to lower bits.
• Keys landing on identical bucket indices form a singly linked node chain.

References & Further Reading

1. Bayer, R. (1972). Symmetric Binary B-Trees for Space-Efficient Data Storage. Acta Informatica, 1(4), 290–306.
2. OpenJDK Repository. OpenJDK 21 Source Code: java.util.TreeMap. GitHub.
3. Sedgewick, R. (2008). Left-leaning Red-Black Trees. Princeton Computer Science Technical Report.

---