How HashMap Works Internally in Java (Complete Guide)
If you've ever been asked "How does HashMap work internally in Java?" in an interview, you already know it's one of the most common — and most poorly answered — Core Java questions. Most candidates can say "it uses hashing," but few can explain what actually happens when you call map.put() or map.get().
This guide breaks it down step by step, with the internal source code, diagrams in plain English, and the exact changes Java 8 made that interviewers love to ask about.
What You'll Learn
- What a HashMap actually looks like in memory
- How
put()andget()work internally, step by step - What a collision is and how Java resolves it
- Why Java 8 changed linked lists to trees (treeification)
- How resizing and load factor affect performance
- Common interview questions with answers
What Is a HashMap, Really?
A HashMap is Java's implementation of a hash table. It stores data as key-value pairs and gives you near-instant lookup — average O(1) time complexity for put(), get(), and remove() — regardless of how many entries it holds.
Internally, a HashMap is not a list of key-value pairs sitting side by side. It's an array of buckets, where each bucket can hold one or more entries.
transient Node<K,V>[] table;
Each slot in that array is a bucket. Each bucket holds a linked list (or, since Java 8, sometimes a tree) of Node objects:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
Every Node stores four things: the precomputed hash of the key, the key itself, the value, and a reference to the next node in the same bucket (used when collisions happen).
Step-by-Step: What Happens When You Call put()
Say you run:
map.put("Java", 8);
Here's exactly what happens internally:
- Null check. If the key is
null, Java stores it at bucket index0, sincenullhas no real hash code. - Hash calculation. Java calls
"Java".hashCode()to get a raw hash code, then applies an internal spreading function:
This XOR-shift step spreads the higher bits of the hash into the lower bits, which reduces collisions when the table is small.static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);} - Bucket index calculation. The spread hash is converted into an array index using:
whereindex = (n - 1) & hashnis the current capacity (always a power of 2). This bitwise AND is a fast equivalent ofhash % n. - Check the bucket. If the bucket is empty, a new
Nodeis placed there directly. - Handle a collision. If the bucket already has entries, Java walks the list and calls
.equals()on each key. If a match is found, the value is overwritten. If no match is found, the new entry is appended to the end of the list (or inserted into the tree, if the bucket has been treeified).
What Happens When You Call get()
Retrieval mirrors insertion:
- Java computes the hash of the key and finds the bucket index the same way as above.
- It walks the bucket's list (or tree) and compares each stored key using
.equals(). - The first match returns its value. If nothing matches,
get()returnsnull.
This is why overriding hashCode() without also overriding equals() correctly is a classic source of HashMap bugs — two "equal" objects can end up hashing to different values, or unrelated objects can collide and get treated as equal.
What Is a Hash Collision?
A collision happens when two different keys produce the same bucket index. This is unavoidable — with a fixed number of buckets and effectively unlimited possible keys, collisions are a matter of when, not if.
Before Java 8, every bucket was a simple linked list. In the worst case (many keys landing in the same bucket), lookups degraded to O(n) — effectively turning your HashMap into a slow linear search.
The Java 8 Change: Treeification
Java 8 introduced a major performance fix. When a single bucket accumulates 8 or more entries (the TREEIFY_THRESHOLD) and the table has at least 64 buckets, that bucket's linked list is converted into a red-black tree.
This changes worst-case lookup time in that bucket from O(n) to O(log n) — a significant improvement for hash-flooding scenarios or poorly distributed keys. If entries are later removed and the bucket shrinks below 6 entries, it converts back to a linked list.
Bucket with 8+ collisions:
Before Java 8: [A] → [B] → [C] → [D] → [E] → [F] → [G] → [H] (O(n) lookup)
Java 8+: balanced red-black tree (O(log n) lookup)
Load Factor and Resizing
Two settings control when a HashMap grows:
- Initial capacity: 16 by default (always a power of 2)
- Load factor: 0.75 by default
The threshold for resizing is capacity × load factor. With defaults, that's 16 × 0.75 = 12. Once you insert the 13th entry, the HashMap doubles its capacity to 32 and rehashes every existing entry into the new, larger table.
| Capacity | Load Factor | Resize Threshold |
|---|---|---|
| 16 | 0.75 | 12 |
| 32 | 0.75 | 24 |
| 64 | 0.75 | 48 |
Resizing is an expensive O(n) operation since every entry must be rehashed. If you know roughly how many entries you'll store, initializing the HashMap with a sufficient capacity upfront (new HashMap<>(expectedSize)) avoids repeated resizes.
Why 0.75? It's a deliberate space-vs-speed tradeoff. A lower load factor wastes memory on mostly-empty buckets. A higher one increases collisions and chain length. 0.75 keeps most buckets holding zero or one entry, which is what makes the average O(1) performance hold up in practice.
HashMap vs Hashtable vs ConcurrentHashMap
A frequent interview follow-up:
| Feature | HashMap | Hashtable | ConcurrentHashMap |
|---|---|---|---|
| Thread-safe | No | Yes (synchronized) | Yes (segment/bucket-level locking) |
| Null keys/values | 1 null key, multiple null values | Not allowed | Not allowed |
| Performance | Fastest (single-threaded) | Slow (fully locked) | Fast under concurrency |
| Introduced | Java 1.2 | Java 1.0 | Java 1.5 |
If you need thread safety, prefer ConcurrentHashMap over Hashtable — it offers far better performance because it doesn't lock the entire map for every operation.
Common Interview Questions
Q: What's the time complexity of HashMap operations?
Average O(1) for put(), get(), and remove(). Worst case is O(log n) since Java 8 (was O(n) before), when many keys collide into the same bucket.
Q: Can a HashMap have duplicate keys? No. Inserting a value with an existing key overwrites the previous value. Values can be duplicated freely.
Q: Is HashMap ordered?
No. Iteration order is not guaranteed and can change after resizing. If you need insertion order, use LinkedHashMap. If you need sorted order, use TreeMap.
Q: What happens if you don't override equals() and hashCode() for a custom key object?
Java falls back to the default Object implementations, which compare by memory reference. Two logically identical objects will be treated as different keys, causing lookups to silently fail.
Q: Why is HashMap capacity always a power of 2?
Because (n - 1) & hash only works correctly as a substitute for hash % n when n is a power of 2 — it guarantees every bit of the hash can influence the bucket index.
Key Takeaways
- HashMap is an array of buckets, each holding a linked list or (since Java 8) a red-black tree.
- Collisions are resolved via chaining, with
.equals()used to identify exact key matches. - Java 8 added tree-based buckets to fix worst-case O(n) performance under heavy collisions.
- Load factor (0.75 by default) balances memory usage against collision frequency.
- Resizing doubles capacity and rehashes all entries — expensive, so size your HashMap upfront when you can.
Next in this series: Internal Working of ConcurrentHashMap in Java — how Java achieves thread safety without locking the entire map.
0 Comments