HashMap Internal Working in Java

Before you can understand how a Set works in Java, you have to understand Map. This is not optional. HashSet internally uses a HashMap. LinkedHashSet internally uses a LinkedHashMap. TreeSet internally uses a TreeMap. So if you skip the map, the entire set family becomes a black box to you. That is why this article exists, and that is why HashMap internals are consistently the most asked topic in Java interviews.

Let us go all the way inside.

---

Why Map Is Not Part of the Collections Hierarchy

You might have noticed that List, Queue, Stack, and Set all extend from Collection. But Map does not. People find this strange at first, but the reason is logical once you think about it.

The entire Collection interface is designed around one thing: a container of values. You have a list of values, a stack of values, a set of values. All the methods in Collection work with individual values. You add a value, you remove a value, you check if a value exists.

A Map is fundamentally different. A Map stores key and value together as a pair. Every operation requires thinking about two things at once. The methods you need are completely different: you want to get a value by key, you want to put a key and value together, you want to check if a key exists. None of that fits naturally into the Collection interface.

That is why Map is a completely separate interface with its own method family. It does not inherit from Collection, and every concrete map class implements Map directly.

---

The Map Interface and Its Implementations

Map is an interface. You cannot create a Map directly. You need one of its concrete implementations:

// Map interface with key of type Integer, value of type String
Map<Integer, String> studentRoster = new HashMap<>();

// You can also use:
// LinkedHashMap   -> preserves insertion order
// TreeMap         -> keeps keys sorted
// Hashtable       -> thread safe, legacy class

The most important property of any map is this: keys must be unique. Values can repeat all you want, but no two entries can share the same key. If you try to insert a key that already exists, the new value overwrites the old one. The key stays, the value changes.

---

The Core Map Methods

At a surface level, the map gives you these essential operations:

Map<Integer, String> m = new HashMap<>();

// Check how many key-value pairs exist
int count = m.size();

// Check if the map has nothing in it
boolean empty = m.isEmpty();

// Check if a particular key exists
boolean hasTwo = m.containsKey(2);

// Insert a key-value pair (or overwrite if key exists)
m.put(1, "SJ");
m.put(2, "KJ");
m.put(3, "PJ");

// Retrieve the value associated with a key
String name = m.get(2); // returns "KJ"

// Remove a key-value pair and get the removed value back
String removed = m.remove(1); // returns "SJ", key 1 is gone

This is the surface level. Now let us go into the level that actually matters for interviews and for understanding what your code is doing.

---

What Is Actually Inside a HashMap

When you create a HashMap, it does not create some magical structure. It creates an array. Specifically, it creates an array of Node objects. This is the internal structure:

// This is the actual field inside java.util.HashMap
transient Node<K,V>[] table;

And each Node is defined as a static inner class that implements the Map.Entry interface:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;   // the computed hash of the key
    final K key;      // the actual key you provided
    V value;          // the actual value you provided
    Node<K,V> next;   // pointer to the next node (for collision chaining)
}

Notice that next points to another Node. This is how chaining works when two keys land on the same position in the array. More on that in a moment.

The map interface also defines a sub interface called Entry. You might wonder what the purpose of having a nested interface inside Map is. The answer is simple: it is a way to represent one key value pair as a single object. In HashMap, this pair is represented by Node<K,V>, which implements Map.Entry<K,V>.

---

Default Capacity and What It Means

When you do this:

Map<Integer, String> map = new HashMap<>();

You did not specify a size, so Java uses the default. Looking inside the HashMap source code:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

So the internal array will have 16 Node slots, indexed from 0 to 15. (The array is actually created lazily, on the first put.) Every slot starts as null.

You can also provide your own initial capacity:

Map<Integer, String> map = new HashMap<>(3);

HashMap always rounds the capacity up to a power of 2, so new HashMap<>(3) really gets a table of 4. To keep the walkthrough simple, the example below pretends the table has exactly 3 slots and uses hash % 3; the real index formula is explained in "Why Capacity Is Always a Power of 2".

---

How put() Works Step by Step

Imagine you have a HashMap<Integer, String> with an internal array of size 3, and you call:

map.put(1, "SJ");

Here is exactly what happens internally:

Step 1: Compute the hash of the key.

The key is 1. Java computes a hash value for this key. Internally, the HashMap uses this formula:

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

Let us say the hash computed for 1 is some number like 1234567. This number does not need to map directly to your array. It is just a raw hash.

Step 2: Compute the bucket index.

To turn that hash into a valid array index, the map does:

index = hash % size_of_table
index = 1234567 % 3
index = 1  (for example)

So the key 1 maps to bucket index 1.

Step 3: Place the node.

At table[1], there is currently nothing (null). So the map creates a new Node with hash 1234567, key 1, value "SJ", and next = null, and places it at table[1].

Now you call:

map.put(5, "PJ");

The hash of 5 is computed. Let us say after modding by 3, the index comes out to 2. So the node for key 5 with value "PJ" goes at table[2]. No problem.

---

What Happens When Two Keys Land on the Same Index: Collision

Now you call:

map.put(10, "KJ");

The hash for 10 is computed. After modding by 3, let us say the index comes out to 1. But table[1] already has the node for key 1.

This is a collision. Two different keys ended up in the same bucket.

Here is what HashMap does:

1. It checks if the existing key at that bucket is the same as the key you are inserting. It compares the hash AND uses equals() to verify. Key 10 is not the same as key 1, so this is a genuine collision, not an overwrite.

2. It creates a new Node for key 10, value "KJ", and then makes the next pointer of the existing node at index 1 point to this new node.

The bucket now looks like a linked list:

table[1] -> Node(hash=1234567, key=1, value="SJ", next=->)
                                                         |
                                                         v
                                              Node(hash=515100, key=10, value="KJ", next=null)

This technique is called chaining. When collisions happen, the nodes are chained together using the next pointer, forming a linked list within a single bucket.

If you insert yet another element whose hash also maps to index 1, it gets appended to this chain. The chain can keep growing.

---

How get() Works

Now say you call:

map.get(5);

Step 1: Compute the hash of the key 5. The hash function always produces the same output for the same input, so you get the same hash you got during put. Let us say the hash was 984120.

Step 2: Compute the index: 984120 % 3 = 2.

Step 3: Go to table[2]. Check the node there. Compare both the hash and the key using equals(). If they match, return the value. If that node's key does not match, follow the next pointer and check the next node in the chain. Repeat until you find a match or reach the end of the chain.

In this case, table[2] has exactly one node for key 5, so it returns "PJ" immediately.

---

The Contract Between hashCode() and equals()

This is one of the most important concepts in Java, and it shows up in virtually every senior interview.

There are two contracts you must know:

Contract 1: If two objects are equal according to equals(), then their hashCode() MUST return the same value.

This is why get() works. When you call map.get(5), Java computes the hash of 5. The hash function always returns the same value for the same input, guaranteed by this contract. So the computed hash during get matches the hash stored in the node during put, which leads Java to the correct bucket.

Contract 2: If two objects have the same hashCode(), that does NOT mean they are equal.

This is why collisions can happen. Two completely different keys can produce the same hash. That is why after finding the right bucket using the hash, HashMap still uses equals() to confirm the actual key match.

What Breaks When You Violate the Contract

Say you create a custom class and override equals() but forget to override hashCode():

class UserKey {
    private final String username;

    public UserKey(String username) {
        this.username = username;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof UserKey)) return false;
        return username.equals(((UserKey) o).username);
    }

    // BUG: hashCode() not overridden!
    // The inherited Object.hashCode() uses the memory address of the object.
    // Two distinct UserKey("admin") objects have different memory addresses,
    // so they produce different hash codes even though equals() says they are the same.
}

public class BrokenLookup {
    public static void main(String[] args) {
        Map<UserKey, String> roles = new HashMap<>();

        UserKey key1 = new UserKey("admin");
        UserKey key2 = new UserKey("admin");

        roles.put(key1, "SuperAdmin");

        // key1.equals(key2) is true, they are logically the same
        System.out.println(key1.equals(key2)); // true

        // But their hash codes differ because Object.hashCode() uses memory addresses
        System.out.println(key1.hashCode()); // some number like 12345678
        System.out.println(key2.hashCode()); // a completely different number

        // The lookup fails because key2's hash takes you to a different bucket
        System.out.println(roles.get(key2)); // null -- data is effectively lost
    }
}

The rule is absolute: if you override equals(), you must override hashCode().

---

Load Factor and Rehashing

There is a serious problem with having a small array and many elements. If you have a 3-slot array and you put 100 elements in it, every bucket ends up being a long linked list. Finding any element means traversing the entire list. That defeats the whole point of a hash map.

This is where the load factor comes in.

The default load factor in HashMap is 0.75. This means: when the number of entries reaches 75% of the current capacity, resize the array.

Default capacity:     16
Default load factor:  0.75
Threshold:            16 x 0.75 = 12

When you insert the 13th element, HashMap automatically rehashes: it doubles the internal array from 16 to 32, then recomputes the index for every existing entry and places them into the new larger array.

Why double, specifically? Because the capacity is always kept as a power of 2. After 16 comes 32, then 64, then 128, and so on. This is not arbitrary. Read the next section to understand why.

The benefit of rehashing is that a larger array means more buckets, which means the same number of elements spread across more slots, which means fewer collisions and shorter chains. This keeps your operations fast.

---

Why Capacity Is Always a Power of 2

Computing hash % N where N is the array length is mathematically correct, but division and modulo operations are expensive at the CPU level. They take many clock cycles.

There is a trick: when N is a power of 2, you can use the bitwise operation hash & (N - 1) instead of hash % N. For non-negative values they give identical results, the AND never produces a negative index, and it takes a single CPU instruction.

N = 16, so N - 1 = 15 = 0000...00001111 in binary

hash = 1234567 = 0000 0000 0001 0010 1101 0110 1000 0111
& mask (15) =    0000 0000 0000 0000 0000 0000 0000 1111
---------------------------------------------------------
result       =   0000 0000 0000 0000 0000 0000 0000 0111 = 7

Only the last 4 bits survive (because 16 gives a 4-bit mask). This means if two hash values differ only in their upper bits and share the same lower 4 bits, they land in the same bucket regardless of how different they actually are.

That is why HashMap applies hash perturbation before computing the index:

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

The XOR with the upper 16 bits shifted down ensures that variations in the upper half of the hash also influence the lower bits that actually determine the bucket. This spreads keys more evenly across buckets.

---

Treeification: The Java 8 Performance Fix

Even with rehashing, a worst case scenario is possible: a hash function that sends all keys to the same bucket, resulting in a single linked list holding every element. Searching that list is O(n), not O(1).

In Java 7, this was not just a theoretical concern. Attackers could deliberately craft input strings whose hash codes all collide, forcing a server side HashMap into O(n) behavior and causing a Denial of Service.

Java 8 solved this with treeification.

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

Here is how it works: when a single bucket's linked list grows beyond 8 nodes (TREEIFY_THRESHOLD) AND the table capacity is at least 64, HashMap converts that bucket's linked list into a Red Black Tree. If the table is still smaller than 64, it resizes the table instead. A Red Black Tree is a self balancing binary search tree with O(log n) operations.

When a tree bucket becomes small again (6 or fewer nodes, UNTREEIFY_THRESHOLD, checked when the table is resized), HashMap converts it back to a linked list to save memory.

The visual difference:

Before treeification (linked list, O(n) worst case):
table[0] -> Node1 -> Node2 -> Node3 -> Node4 -> Node5 -> Node6 -> Node7 -> Node8

After treeification (Red Black Tree, O(log n) worst case):
table[0] -> TreeNode(root)
               /        \
          TreeNode    TreeNode
           /    \      /    \
        ...     ...  ...    ...

In a binary search tree, every search decision cuts the remaining candidates in half. You always go left or right, never through the full list. That is why searching takes O(log n) steps instead of O(n).

---

Time Complexity of HashMap Operations

Now you can give a complete and accurate answer:

Average case (well-distributed keys):
  put()    -> O(1)
  get()    -> O(1)
  remove() -> O(1)

Worst case (extreme collisions, linked list bucket):
  put()    -> O(n)
  get()    -> O(n)
  remove() -> O(n)

Worst case in practice (after treeification threshold):
  put()    -> O(log n)
  get()    -> O(log n)
  remove() -> O(log n)

The reason we say average case is O(1) is because with a good hash function and proper load factor management, collisions are rare. Most operations go straight to the correct bucket and find the element immediately.

The worst case drops to O(log n) because Java 8 converts long chains to Red Black Trees past the threshold of 8 (the tree search works best when keys are Comparable).

When interviewers ask about HashMap time complexity, tell them this full picture. Do not just say O(1). Explain the average, the worst case, and the treeification mechanism.

---

null Key Support

HashMap allows one null key. When you call put(null, value), the hash function returns 0 for null (look at the implementation: return (key == null) ? 0 : ...). So null always maps to bucket index 0.

Map<Integer, String> map = new HashMap<>();

// null key is allowed
map.put(null, "test");

// null value is allowed
map.put(0, null);

// Even both null
map.put(1, null);

This is one of the key differences from Hashtable and ConcurrentHashMap, which reject null keys and null values entirely.

---

A Complete Working Example

Let us put everything together with a full example that shows all the major operations:

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo {
    public static void main(String[] args) {
        // Integer is key, String is value
        Map<Integer, String> map = new HashMap<>();

        // put with null key and non-null value
        map.put(null, "test");

        // put with non-null key and null value
        map.put(0, null);

        // Regular insertions
        map.put(1, "a");
        map.put(2, "b");
        map.put(3, "c");

        // putIfAbsent: only inserts if key is absent OR its value is null
        map.putIfAbsent(null, "overwrite"); // null key exists and value is non-null: IGNORED
        map.putIfAbsent(0, "zero");         // key 0 exists but value is null: WRITTEN
        map.putIfAbsent(3, "c-duplicate"); // key 3 exists and value is non-null: IGNORED

        // Iterate using entrySet()
        // entrySet() returns a Set of Map.Entry objects (which are Node<K,V> internally)
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
        // Output order is not guaranteed in HashMap

        // isEmpty
        System.out.println("isEmpty: " + map.isEmpty()); // false

        // size: number of key-value mappings
        System.out.println("size: " + map.size()); // 5

        // containsKey
        System.out.println("contains 3: " + map.containsKey(3)); // true

        // get: computes hash, finds bucket, iterates chain, compares with equals
        System.out.println("get(1): " + map.get(1)); // "a"

        // getOrDefault: returns a fallback if key is absent
        System.out.println("get(9) or default: " + map.getOrDefault(9, "not found")); // "not found"

        // remove: removes entry and returns the removed value
        String removedValue = map.remove(null);
        System.out.println("removed null key, value was: " + removedValue); // "test"

        // After removal, iterate again
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }

        // keySet: a Set containing only the keys
        System.out.println("Keys: " + map.keySet()); // [0, 1, 2, 3]

        // values: a Collection containing only the values
        System.out.println("Values: " + map.values()); // [zero, a, b, c]
    }
}

A few things worth highlighting in this example:

entrySet() returns a Set<Map.Entry<K,V>> view over the map's internal Node<K,V> objects. When you iterate over it, each entry is actually a Node with hash, key, value, and next. You access key and value via getKey() and getValue().

putIfAbsent() has a nuanced rule: it treats a key as absent if either the key does not exist in the map, or if the key exists but its associated value is null. So a key with a null value is considered absent for the purpose of this method.

getOrDefault() does not insert anything. It just returns the fallback value if the key is not found. Unlike putIfAbsent, it leaves the map unchanged.

---

Iterating a HashMap: Three Styles

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
scores.put("Carol", 92);

// Style 1: entrySet (gives you both key and value together, most efficient)
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// Style 2: keySet (gives you keys; use get() to fetch values, less efficient)
for (String key : scores.keySet()) {
    System.out.println(key + ": " + scores.get(key));
}

// Style 3: values only (when you only need values and do not care about keys)
for (int score : scores.values()) {
    System.out.println(score);
}

Prefer entrySet() when you need both keys and values. Using keySet() and then calling get() inside the loop forces a second hash lookup for every iteration, which is wasteful.

---

HashMap vs Hashtable vs ConcurrentHashMap

This comparison comes up in almost every Java interview that touches on concurrency or legacy code.

Feature	HashMap	Hashtable	ConcurrentHashMap
Thread safety	Not thread safe	Thread safe	Thread safe
Null keys	One null key allowed	No null keys	No null keys
Null values	Multiple null values allowed	No null values	No null values
Performance	High (no locking)	Low (global lock on every method call)	High (bucket level locking, CAS operations)
Iteration	Fail fast (throws ConcurrentModificationException)	Fail fast	Weakly consistent (never throws CME)
Ordering	No guaranteed order	No guaranteed order	No guaranteed order

Hashtable is the synchronized version of HashMap. It wraps every method with a synchronized block on the entire object. This means only one thread can call any method at a time, even reads. In most modern applications, this is far too conservative and creates a bottleneck.

ConcurrentHashMap is the modern thread safe alternative. Instead of locking the entire map, it uses fine grained locking at the bucket level, combined with CAS (Compare and Swap) operations. Multiple threads can read and write to different buckets simultaneously. It is dramatically faster than Hashtable under concurrent load.

If you are writing single threaded code, use HashMap. If you are writing multithreaded code, use ConcurrentHashMap. Do not use Hashtable in new code. It exists for historical reasons and is considered a legacy class.

---

The put() Algorithm, Written Out Precisely

Here is the complete decision tree that HashMap.put() follows internally. This is what you need to be able to explain in an interview:

1. Is the key null?
   Yes  -> hash = 0
   No   -> hash = key.hashCode() XOR (key.hashCode() >>> 16)

2. Is the table itself null or empty (first insert ever)?
   Yes  -> initialize the table with default capacity 16

3. Compute bucket index:
   index = (table.length - 1) & hash

4. Look at table[index]:
   Case A: table[index] is null (empty bucket)
      -> Create new Node(hash, key, value, null)
      -> Place it at table[index]
      -> Go to step 5

   Case B: table[index] is not null
      Sub-case B1: The first node in this bucket matches the key
                   (same hash AND key.equals() returns true)
         -> Overwrite the value of that node
         -> Return the old value (size does not change)

      Sub-case B2: The bucket is a Red Black Tree (treeified bucket)
         -> Delegate to tree insertion (O(log n))

      Sub-case B3: The bucket is a linked list
         -> Walk the chain node by node
         -> If you find a matching key -> overwrite value, done
         -> If you reach the end -> append new Node at the tail
         -> If the chain now has more than 8 nodes:
              table.length >= 64 -> convert this bucket to a Red Black Tree
              otherwise          -> resize the table instead

5. Increment size (number of entries).

6. If size > threshold (capacity * loadFactor):
   -> Double the capacity and rehash all entries into the new array.

Check yourself

1. Why is Map not part of the Collection hierarchy?
2. What is inside a HashMap, and what does each Node hold?
3. Walk through put(key, value): how is the bucket chosen, and what happens on a collision?
4. What is the hashCode()/equals() contract, and what breaks if you override only equals()?
5. What are the default capacity and load factor, and when does a HashMap resize?
6. Why is the capacity always a power of 2?
7. When does a bucket turn into a Red Black Tree, and why was this added in Java 8?
8. How does HashMap handle null keys? How do Hashtable and ConcurrentHashMap differ?

Answers

1. A Collection holds single values; a Map holds key-value pairs and needs different operations.
2. An array (table) of Node objects; each node has hash, key, value and next.
3. Compute hash = h ^ (h >>> 16), then index = hash & (n - 1). If the bucket is empty, store a new node. If a node with an equal key (same hash and equals) exists, replace its value. Otherwise append a new node to the chain.
4. Equal objects must have equal hash codes (the reverse is not required). With only equals() overridden, two equal keys can land in different buckets, so get returns null.
5. Capacity 16, load factor 0.75, threshold 12: inserting the 13th entry doubles the table to 32 and rehashes.
6. So hash & (n - 1) can replace the slower % and always gives a valid index.
7. When a chain grows past 8 nodes and the table has at least 64 buckets (otherwise the table is resized instead). It makes the worst case O(log n) instead of O(n), for example against deliberately colliding keys.
8. One null key is allowed and goes to bucket 0; null values are allowed. Hashtable and ConcurrentHashMap reject null keys and values; Hashtable locks the whole map, ConcurrentHashMap uses fine-grained locking and CAS.