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 internally it creates an array of 16 Node slots, indexed from 0 to 15. Every slot starts as null. Nothing is stored yet.

You can also provide your own initial capacity:

Map<Integer, String> map = new HashMap<>(3); // array of size 3: index 0, 1, 2

Using a smaller size makes the examples easier to follow, so let us use size 3 to trace through how insertion actually works.

---

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 replace hash % N with the bitwise operation hash & (N - 1). These two expressions produce identical results, but the bitwise AND 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 to 8 nodes AND the total table capacity is at least 64, HashMap converts that bucket's linked list into a Red Black Tree. A Red Black Tree is a self balancing binary search tree that guarantees O(log n) operations regardless of input.

When deletions shrink the tree back down to 6 nodes, 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 reason the true worst case is O(log n) and not O(n) is because Java 8 converts long chains to Red Black Trees at the threshold of 8. You almost never reach O(n) in a real HashMap.

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 the internal array of Node<K,V> objects wrapped as Set<Map.Entry<K,V>>. 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 6

   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
         -> Go to step 6

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

      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 chain length is now >= 8 AND table.length >= 64
              -> Convert this bucket from linked list to Red Black Tree

5. Increment size (number of entries).

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

---

Common Interview Questions on HashMap

Q: What is the default initial capacity of HashMap?

16. It is always a power of 2.

Q: What is the default load factor?

0.75. When the number of entries exceeds capacity * 0.75, the map resizes.

Q: What happens during rehashing?

The internal array is doubled in size. Every existing entry has its bucket index recomputed using the new array length. Entries are redistributed across the new larger array. This is an expensive operation but it happens infrequently due to the load factor.

Q: What is the treeify threshold?

8. When a bucket's linked list grows to 8 nodes AND the total table capacity is at least 64, that bucket is converted to a Red Black Tree.

Q: What is the average and worst case time complexity of get() and put()?

Average case is O(1). Worst case in Java 8 and later is O(log n) due to treeification. The absolute worst case without treeification would be O(n) but this is avoided by the threshold mechanism.

Q: Can HashMap have null keys? Can Hashtable?

HashMap allows exactly one null key and any number of null values. Hashtable throws NullPointerException for both null keys and null values.

Q: What happens if you override equals() but not hashCode()?

Two objects that are logically equal (same field values, equals() returns true) will have different hash codes because Object.hashCode() uses the memory address. They will land in different buckets. When you try to look up one using the other as a key, the HashMap will go to the wrong bucket and return null even though the entry exists. Data is effectively lost.

Q: Why is HashMap not thread safe?

Multiple threads can simultaneously modify the internal array without synchronization, leading to data corruption, infinite loops in the linked list (in older Java versions during resize), and lost updates. Use ConcurrentHashMap for thread safe access.

Q: What is the difference between Hashtable and ConcurrentHashMap?

Both are thread safe, but Hashtable uses a single lock on the entire map for every operation (even reads), making it a bottleneck. ConcurrentHashMap uses bucket level locking and CAS operations, allowing concurrent reads and fine grained writes. Hashtable also rejects null keys and values, as does ConcurrentHashMap.

Q: Why does HashMap use a power of 2 for capacity?

To replace the expensive modulo operation hash % capacity with the equivalent but much faster bitwise AND hash & (capacity - 1). This only works when capacity is a power of 2.

Q: What is hash perturbation and why does it exist?

The index is computed from only the low order bits of the hash. Without perturbation, keys whose hash values differ only in high order bits would all land in the same bucket. The perturbation step XORs the hash with its own upper 16 bits shifted down, spreading the influence of high bits into the low bits that determine the bucket index.

Q: What is the relationship between HashSet and HashMap?

HashSet is backed by a HashMap. When you add an element to a HashSet, it calls hashMap.put(element, PRESENT) where PRESENT is a dummy constant object. The elements become keys in the internal HashMap. This is why HashSet has the same O(1) average performance and the same uniqueness guarantee as HashMap keys.

---

A Mental Model to Remember Everything

Think of a HashMap as a large hotel with 16 floors (buckets). When a guest (key value pair) checks in, the receptionist computes a room number from the guest's name using a hash function, then takes that number modulo 16 to pick a floor. The guest goes to that floor.

If two guests get the same floor assignment (collision), they share the floor by standing in a line (linked list). When the line on one floor gets too long (8 people), the hotel converts that floor from a single file line into an organized tree shaped seating arrangement so you can find anyone in O(log n) time instead of O(n).

When the hotel reaches 75% occupancy (12 out of 16 floors meaningfully occupied), management doubles the hotel to 32 floors and reassigns everyone to their new floors. This keeps the lines short and operations fast.

The hotel does not let two guests have the same name (duplicate keys), but two guests can have the same room assignment (hash collision). The name is verified with a signature check (equals()), not just the room number (hash).

That is HashMap. From the inside out.