System Atlas
the atlas

How Java HashMaps work

Turn a key into an array index and you get near-instant lookups — until keys collide.

the gist

A HashMap stores key-value pairs in an array of buckets. It calls the key's hashCode(), spreads the bits, and maps the result to a bucket index for average O(1) put and get. When two keys land in the same bucket (a collision) they form a linked list, which Java 8+ converts to a balanced tree once it grows past a threshold. As the map fills past its load factor it resizes and rehashes everything into a larger array, and correct hashCode()/equals() are essential for it all to work.

ANALOGY // A library that shelves books by a formula on the title instead of scanning every shelf: the formula jumps you straight to the right shelf, and if several books share a shelf you scan just that short shelf.
living diagram01 / 05
Keyput(k, v)hashCode()+ spread bitsBucket indexhash & (n-1)Bucketlist or treeResizegrow + rehashValuestored / returned
01

Hash the key

When you put a key, the HashMap calls the key's hashCode() to get an integer, then applies an internal spreading function that mixes the high bits into the low bits. This mixing matters because the index is taken from the low bits, and it protects against hash codes that differ only in their upper half. The result is a well-distributed hash value.

02

Find the bucket

The spread hash is reduced to a bucket index, effectively hash modulo the array length (done with a fast bitmask since the array size is a power of two). That index points directly at one slot in the internal array — no scanning required. This direct addressing is what makes lookups average O(1).

03

Handle collisions

Different keys can map to the same bucket; this is a collision and is unavoidable given finitely many buckets. The HashMap stores colliding entries as a linked list hanging off that bucket. On get, it walks the short list calling equals() to find the exact key, so collisions cost a little search but stay correct.

04

Treeify hot buckets

If one bucket's list grows long (about 8 entries, usually from a poor hash), Java 8+ converts that list into a balanced red-black tree. Lookups within the bucket then cost O(log n) instead of O(n), containing the damage from a bad hashCode(). The tree reverts to a list if the bucket shrinks again.

05

Resize past the load factor

The map tracks its size against capacity times the load factor (default 0.75). Once entries exceed that threshold, the array doubles in size and every existing entry is rehashed into the larger array. Resizing is costly but infrequent, and it keeps buckets sparse so average operations stay O(1).

the full picture
01

The problem a hash map solves

Suppose you want to store key-value pairs — a username to a user record, a product ID to its price — and look them up fast. The naive option is a list you scan from the front, but finding a key means checking entries one by one, which is O(n): the more you store, the slower every lookup gets. Keeping the list sorted lets you binary-search in O(log n), but then inserts become expensive because you must shift elements to keep order. Neither is good enough for the countless places software needs instant keyed access.

A hash map achieves what feels impossible: average O(1) — constant time — for insert, lookup, and delete, regardless of how many entries it holds. It does this by giving up ordering and instead using a mathematical trick to compute *where* a key's value lives rather than searching for it. Java's HashMap is the workhorse implementation of this idea and one of the most-used data structures in the entire language, so understanding its mechanics — and its failure modes — is fundamental. The core insight is simple to state: if you can turn any key into an array index with a quick calculation, you can jump straight to the value instead of hunting for it.

02

Hashing a key into a bucket

Internally a HashMap is backed by an array, and each slot in that array is called a bucket. The magic is the function that decides which bucket a key belongs to.

When you call put(key, value), the map first calls the key's hashCode() method, which returns an int. Java does not use that value raw — it applies an internal spreading step that mixes the integer's high-order bits down into the low-order bits (an XOR of the value with its own upper half). This matters because the final index is derived from the *low* bits, and without spreading, two different hash codes that happen to share their low bits would collide needlessly. The spread hash is then reduced to an actual index with the equivalent of hash % arrayLength; because HashMap always keeps its array size a power of two, it can do this reduction with a fast bitwise hash & (length - 1) instead of a slow modulo. The result is a bucket index, and the entry is placed there. Reading works identically: get(key) recomputes the same index and goes straight to the right bucket — no scan of the other buckets ever happens, which is exactly why the average case is constant time.

03

Collisions and how they're handled

Because there are far more possible keys than buckets, two different keys will sometimes hash to the same bucket index. This is a collision, and it is not a bug — it is an unavoidable consequence of squeezing a large key space into a finite array. What matters is handling collisions gracefully so correctness and performance survive them.

Java uses separate chaining: each bucket holds not a single entry but a small collection of the entries that map there. Historically, and still for small buckets, this collection is a linked list. When you get a key, the map jumps to its bucket and then walks that short list, calling equals() on each entry to find the one whose key genuinely matches — hashing narrows you to a bucket, but equals() confirms the exact key, since different keys can share a hash. As long as buckets stay short, this extra walk is negligible. The danger is a poor hash function that funnels many keys into a few buckets: in the worst case every key lands in one bucket, the list grows to length n, and lookups degrade all the way back to O(n) — the very thing the hash map was supposed to prevent. This is why the quality of hashCode() directly determines whether a HashMap is fast or secretly linear.

04

Treeification, load factor, and resizing

Java 8 added two defenses that keep a HashMap fast even under stress. The first is treeification: if a single bucket's chain grows beyond a threshold (about 8 entries, and only once the table is reasonably large), the map converts that bucket's linked list into a balanced red-black tree. Lookups within a pathological bucket then cost O(log n) instead of O(n), so even a bad hash function or an adversarial set of keys cannot push a single bucket into linear-time territory. If the bucket later shrinks, it reverts to a plain list.

The second defense manages overall crowding through the load factor, which defaults to 0.75. The map watches the ratio of stored entries to array capacity, and once the number of entries exceeds capacity × loadFactor, it resizes: it allocates a new array of double the size and rehashes every existing entry into it, recomputing each one's bucket for the larger array. Resizing is genuinely expensive — it is O(n) work — but it happens rarely (each doubling covers exponentially more inserts), and it keeps the buckets sparse so the *average* cost per operation stays constant. The 0.75 default is a deliberate balance: lower load factors waste memory on empty buckets but reduce collisions, while higher ones pack tighter but collide more. If you know roughly how many entries you'll store, pre-sizing the map avoids repeated resizes entirely.

05

The hashCode/equals contract and practical guidance

Everything above rests on one contract that the programmer, not the map, is responsible for honoring: the relationship between hashCode() and equals(). The rule is that if two objects are equal by `equals()`, they must return the same `hashCode()`. If you violate it, the map breaks in maddening ways — you can put a key and then fail to get it, because the map hashes your lookup key to one bucket while the stored key sits in another, and the two equals()-equal objects never meet. This is the single most common HashMap bug, and it is why overriding equals() without also overriding hashCode() is a classic mistake. It is also why keys should ideally be immutable: if a key's fields change after insertion, its hash changes too, and it becomes stranded in the wrong bucket, effectively lost.

The practical guidance follows directly. Use good keys — types like String and Integer ship with well-distributed, correct hash implementations, which is why they are such common keys. When you write your own key class, override both methods together and derive them from the same fields (Objects.hash(...) makes this easy). Prefer immutable keys so their hash never drifts. And when performance matters, size the map up front to avoid resize churn. Do all that and a HashMap delivers exactly what it promises: near-instant keyed access at any scale. Get the hashing contract wrong, and it fails quietly rather than loudly, which is what makes understanding the mechanism — not just the API — genuinely worth it.

what to remember
01

A HashMap is an array of buckets; a key's hashCode() is spread and reduced to a bucket index.

02

Average put/get is O(1) because you compute the bucket directly instead of scanning.

03

Collisions (different keys, same bucket) are chained in a linked list within that bucket.

04

Java 8+ converts a bucket's list to a balanced (red-black) tree past ~8 entries, so a bad hash degrades to O(log n) not O(n).

05

Load factor (default 0.75) triggers resizing: the array doubles and every entry is rehashed into the bigger array.

06

Correct, consistent hashCode() and equals() are mandatory — break them and lookups silently fail or the map behaves wrongly.

check yourself

Quick quiz

Q1

How does a HashMap achieve average O(1) lookup?

Q2

What does Java 8+ do when one bucket accumulates too many colliding entries?

follow the thread