How HashMap Works Internally in Java
IntermediateA HashMap stores key-value pairs and gives you average O(1) get and put. It does this with an array of buckets: the key hashCode is spread and mapped to a bucket index, and the entry is stored there. When multiple keys land in the same bucket (a collision), they form a linked list — and since Java 8, a bucket with too many entries converts to a balanced red-black tree so lookups stay fast even under heavy collisions.
Think of a HashMap as a coat check
At a coat check, your ticket number (the hash) tells the attendant exactly which numbered hook (bucket) your coat is on — no searching required. If several coats share a hook, they hang in a small row (a chain) and the attendant checks tags (equals) to find yours. When one hook gets crowded, a smart cloakroom reorganises that row into a sorted rack (a tree) so it is still quick to find the right coat.
Step by Step
Key Concepts
Bucket
One slot in the internal array. Each bucket holds zero or more entries whose keys hash to that index — as a linked list, or a red-black tree once it grows large.
Load Factor
The fullness threshold (default 0.75) that triggers a resize. Lower means fewer collisions but more memory; higher means less memory but longer chains.
equals() and hashCode() contract
Two equal keys must return the same hashCode. Break this and HashMap may store duplicates or fail to find your key — the single most common HashMap bug.
Treeification
Converting an over-full bucket (>8 entries) into a red-black tree so worst-case lookup in that bucket is O(log n) instead of O(n). Reverts to a list if it shrinks below 6.
Key Facts
- Average get/put is O(1); worst case was O(n) before Java 8 and is O(log n) after treeification.
- HashMap is not thread-safe. Under concurrent writes it can corrupt or (pre-Java 8) infinite-loop. Use ConcurrentHashMap for shared maps.
- Using a mutable object as a key and then mutating it changes its hashCode, orphaning the entry — you can never retrieve it again.
Real-World Applications
Caching lookups by ID
A HashMap keyed by user ID gives near-instant reads for an in-memory cache. Just ensure the key type has correct equals/hashCode — records and primitives-wrapped keys are ideal.
Counting frequencies
map.merge(word, 1, Integer::sum) is the idiomatic word-count. It relies on hashing to bucket each distinct word in O(1) average time.
Frequently Asked Questions
Why must equals() and hashCode() be consistent?
HashMap uses hashCode to pick the bucket and equals to find the exact key within it. If two equal objects return different hash codes, they land in different buckets and the map treats them as different keys — so you cannot retrieve what you stored.
What is the time complexity of HashMap operations?
get, put, and remove are average O(1) thanks to hashing. In pathological collision cases the bucket lookup is O(log n) after Java 8 treeification (previously O(n)).
Why is HashMap capacity always a power of two?
It lets HashMap compute the bucket index with a fast bitmask (hash & (capacity-1)) instead of a modulo, and combined with the spread function it distributes entries evenly.
What is the difference between HashMap and ConcurrentHashMap?
HashMap is not thread-safe and can corrupt under concurrent modification. ConcurrentHashMap allows safe concurrent access using fine-grained locking/CAS, permitting many readers and writers without locking the whole map.