AdvancedIn-depth4 min readUpdated 2 Oct 2026

How does HashMap work internally in Java?

SHORT ANSWER

HashMap stores entries in an array of buckets. It hashes the key, picks a bucket from that hash, and stores the entry there; keys that land in the same bucket form a linked list, which since Java 8 turns into a red-black tree when it gets long. When the map is 75% full it doubles the array and redistributes entries.

Explain it simply

Think of the pigeonhole mail racks in a college hostel. Each rack has a number. To find a student's letters, the warden takes the room number, works out which rack it belongs to, and looks only in that rack instead of searching the whole office. That is why lookups are fast.

Sometimes two students map to the same rack. Then their letters sit in the same slot, and the warden checks each name to find the right one. If one rack gets very crowded, the warden sorts it so searching stays quick. HashMap works the same way: the key's hash code picks the rack (bucket), and equals() finds the exact key inside it.

Example

java

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

public class ScoreBoard {
    public static void main(String[] args) {
        Map<String, Integer> runs = new HashMap<>();
        runs.put("Kohli", 82);
        runs.put("Rohit", 45);
        runs.put("Kohli", 101);                   // same key: value replaced

        System.out.println(runs.get("Kohli"));    // prints: 101
        System.out.println(runs.size());          // prints: 2
        System.out.println(runs.get("Gill"));     // prints: null
    }
}

How it works

put(key, value):

Call key.hashCode(). HashMap then mixes the high bits into the low bits (h ^ (h >>> 16)) so that keys whose hash codes differ only in high bits still spread out.
Find the bucket index with (n - 1) & hash, where n is the array length. n is always a power of two, so this is a fast version of hash % n.
If the bucket is empty, place a new node there.
If not, walk the nodes in that bucket. If a node has the same hash and equals() returns true, replace its value. Otherwise add a new node at the end.
If the size crosses the threshold (capacity × load factor), resize.

get(key) repeats steps 1 and 2, then checks only the nodes in that one bucket using equals().

Defaults: initial capacity 16, load factor 0.75, so the first resize happens after 12 entries. A resize doubles the array, and each entry either stays at the same index or moves to index + old capacity.

Treeification (Java 8+): if one bucket reaches 8 nodes and the table has at least 64 buckets, that bucket becomes a red-black tree, so a lookup there is O(log n) instead of O(n). If the table is smaller than 64, HashMap resizes instead. A tree shrinks back to a list when it drops to 6 nodes.

HashMap allows one null key (stored in bucket 0) and many null values.

Real-world use

Caching user sessions by token, counting word frequencies, storing a product ID to price lookup in a shopping cart, and grouping records by city. Average O(1) get and put make it the default map in most Java code.

Common mistakes

Using a mutable object as a key and changing it after insertion. Its hash changes, so the map can no longer find it.
Overriding equals() without hashCode(), so equal keys land in different buckets.
Using HashMap across threads without synchronisation. Use ConcurrentHashMap instead.
Expecting insertion order. HashMap gives no order guarantee; use LinkedHashMap for insertion order or TreeMap for sorted keys.

What to say in the interview

"HashMap is an array of buckets. On put, it takes the key's hashCode, spreads the bits, and uses (n - 1) & hash to pick a bucket. If another key is already there, it checks equals: same key means the value is replaced, otherwise the new entry is chained in that bucket. Get follows the same path, so on average both are O(1). Default capacity is 16 with a 0.75 load factor, and it doubles when it crosses the threshold. Since Java 8, a bucket with 8 or more entries becomes a red-black tree once the table has at least 64 buckets, so the worst case is O(log n) instead of O(n). It is not thread-safe, so for concurrent use I would pick ConcurrentHashMap."

Follow-up questions

Why must equals() and hashCode() be overridden together?
Why is the capacity always a power of two?
What happens if every key returns the same hash code?
How is ConcurrentHashMap different from Hashtable?
Why did Java 8 switch from inserting at the head of the bucket to the tail?

Go deeper

Read these once the basics above feel easy.

If you know roughly how many entries you will store, size the map up front so it never resizes. Because the threshold is 75%, you need capacity of about expected / 0.75. Java 19 added HashMap.newHashMap(expectedSize), which does this calculation for you. Also prefer immutable keys such as String, Integer or records, since their hash codes cannot change after insertion.

Treeification protects against hash-flooding, where many keys are crafted to collide. With plain chaining, n colliding keys make every lookup O(n), and an attacker sending such keys in request parameters could slow a server down badly. With trees, the worst case per bucket is O(log n). To order nodes inside the tree, HashMap compares hash values first, then uses compareTo if the keys implement Comparable, and finally a tie-breaking rule based on class name and identity hash code. In Java 7 and earlier, entries were inserted at the head of the chain, and a resize under concurrent writes could create a cycle in the list and hang get() in an infinite loop. Java 8 inserts at the tail and keeps relative order during resize, but HashMap is still not safe for concurrent writes.

#java #collections #hashmap #hashing