HashMap Internal Working

A HashMap finds a value by its key almost instantly, even when it holds millions of entries. It does this with a technique called hashing: the key's hashCode is turned into the number of a bucket, and the entry is stored in that bucket. To find the key later, the map computes the same bucket number and looks only there. In this lesson, you will learn step by step what happens inside put and get, what a collision is, why the map resizes, and when a bucket turns into a tree. This is one of the most frequently asked Java interview topics.

The Building Blocks

A HashMap is made of:

• A bucket array (table): an array of slots. Its length, called the capacity, is always a power of two: 16, 32, 64...
• Nodes: each entry is stored as a node holding four things: the key's hash, the key, the value and a link to the next node in the same bucket.
• Size: the number of entries stored.
• Load factor (0.75 by default) and threshold = capacity x load factor. With 16 buckets, the threshold is 12.

Step 1: From Key to Bucket Index

When you call put(key, value) or get(key), the map first works out the bucket:

1. Call key.hashCode() to get an int.
2. Spread the bits: hash = h ^ (h >>> 16). This mixes the high bits into the low bits, so keys whose hash codes differ only in the high bits still land in different buckets.
3. Compute the index: index = (capacity - 1) & hash. Because the capacity is a power of two, this is the same as hash % capacity but faster, and always gives a number from 0 to capacity - 1.

Let's see an example that computes the buckets for a few keys in a map with 16 buckets.

public class BucketIndex {
    static int hash(Object key) {
        int h = key.hashCode();
        return h ^ (h >>> 16);
    }
 
    public static void main(String[] args) {
        String[] keys = {"Navika", "Srihitha", "Advitha", "Anamaneni"};
        for (String k : keys) {
            System.out.println(k + " -> bucket " + (hash(k) & 15));
        }
        System.out.println("Aa hashCode " + "Aa".hashCode()
            + ", BB hashCode " + "BB".hashCode());
    }
}

Navika -> bucket 4
Srihitha -> bucket 13
Advitha -> bucket 14
Anamaneni -> bucket 2
Aa hashCode 2112, BB hashCode 2112

Explanation: Each name lands in a different bucket, which is why the earlier HashMap example printed Anamaneni first: bucket 2 comes before bucket 4. The strings "Aa" and "BB" have the same hash code, so they would always share a bucket.

Step 2: What put Does

Once the bucket is known:

1. Bucket empty: create a node and place it there.
2. Bucket not empty: walk the nodes in that bucket. For each node, check whether its key is the same: first compare the stored hash, then call equals.
   • Same key found: replace its value and return the old value.
   • Not found: add a new node at the end of the bucket. This is a collision: two different keys in one bucket.
3. Check the size: if the size is now greater than the threshold, resize.

Step 3: What get Does

get(key) computes the same index, goes straight to that bucket, and walks its nodes, comparing the hash and then equals. If a node matches, its value is returned; otherwise the result is null. Because a good hash spreads keys evenly, most buckets hold zero or one node, so get usually checks just one node: O(1) on average.

Collisions: Linked List, Then Tree

A bucket with several nodes is kept as a linked list. If many keys collide, the list gets long and lookups slow down to O(n). Since Java 8, HashMap protects against this:

• When one bucket reaches 8 nodes (TREEIFY_THRESHOLD) and the table has at least 64 buckets (MIN_TREEIFY_CAPACITY), the bucket's list is converted into a red-black tree, so lookups in it take O(log n).
• If the table is smaller than 64, the map resizes instead, which usually spreads the keys out.
• When a tree bucket shrinks to 6 nodes or fewer (UNTREEIFY_THRESHOLD) during a resize, it turns back into a list.

Resizing and the Load Factor

When the number of entries goes above the threshold, the map doubles its bucket array and moves every node into the new array. With the default settings, this happens after the 12th, 24th, 48th entry and so on. We can watch it by reading the private table field with reflection:

import java.lang.reflect.Field;
import java.util.HashMap;
 
public class Table {
    static int buckets(HashMap<?, ?> map) throws Exception {
        Field f = HashMap.class.getDeclaredField("table");
        f.setAccessible(true);
        Object[] table = (Object[]) f.get(map);
        return table == null ? 0 : table.length;
    }
 
    public static void main(String[] args) throws Exception {
        HashMap<Integer, String> map = new HashMap<>();
        System.out.println("empty: buckets " + buckets(map));
        int last = -1;
        for (int i = 1; i <= 100; i++) {
            map.put(i, "v" + i);
            int n = buckets(map);
            if (n != last) {
                System.out.println("size " + map.size() + ": buckets " + n);
                last = n;
            }
        }
    }
}

java --add-opens java.base/java.util=ALL-UNNAMED Table.java

empty: buckets 0
size 1: buckets 16
size 13: buckets 32
size 25: buckets 64
size 49: buckets 128
size 97: buckets 256

Explanation: The bucket array is created lazily on the first put, with 16 buckets. When the 13th entry pushes the size above the threshold of 12, the table doubles to 32 (new threshold 24), and so on. Because the capacity doubles, each node either stays at the same index or moves to index + old capacity, which makes moving the nodes cheap. The --add-opens option is needed only for this learning trick; never read private fields in real code.

Why equals and hashCode Must Agree

The whole design depends on one rule: if two keys are equal, they must have the same hash code. If a key class breaks this rule, an equal key used in get computes a different bucket and the entry is never found. And if a key's fields change after it is stored, its hash changes too, so the entry becomes "lost" in the wrong bucket.

Common Mistakes

Assuming HashMap lookups are always O(1). A bad hashCode that returns the same number for many keys puts them all in one bucket.

Mutating a key after putting it in the map. The entry can no longer be found.

Saying collisions are "errors". They're normal; the map handles them with lists and trees.

Interview Corner

Practice

1. Easy: Using the BucketIndex program, find the buckets of five words of your choice in a table of 16 buckets, then in a table of 32 (use & 31).
2. Harder: Write a key class whose hashCode always returns 1. Put 10,000 entries into a HashMap and time 10,000 lookups. Compare with a proper hashCode.

Key Takeaways