cover image
Java Internals

Why Is Java HashMap Not Always O(1)?

Sarvar Musazade9 min read—views

HashMap operations are O(1) on average, not under every possible condition. Hash collisions can increase the number of comparisons, one insertion can trigger an O(n) resize, and expensive hashCode() or equals() implementations add their own cost.

Let us build the correct mental model without getting lost in the OpenJDK source code.

1. The basic idea: calculate a bucket, then search inside it

A HashMap contains an internal array. Each position in that array is called a bucket.

When you write:

map.put("user:42", user);

Java conceptually performs these steps:

  1. Call the key's hashCode() method.
  2. Process the hash and calculate a bucket index.
  3. Go directly to that bucket.
  4. Store or find the entry inside it.

During get(), Java repeats the process and uses equals() when necessary to identify the exact key.

If keys are distributed well, most buckets contain zero or one entry. Java calculates an index, visits one small location, and returns the value. This is why lookup is normally described as O(1).

The important assumption is good hash distribution. Oracle's documentation describes constant-time get() and put() performance only when the hash function disperses elements properly among buckets. Java HashMap documentation

2. The problem: different keys can land in the same bucket

The result of hashCode() is an int, but a HashMap has a limited number of buckets. Different keys can therefore choose the same bucket. This is a hash collision.

A collision does not mean that the keys are equal. It only means that their bucket index is the same.

Imagine four employees:

Employee sarvar = new Employee(1, "Sarvar"); Employee aysel = new Employee(2, "Aysel"); Employee murad = new Employee(3, "Murad"); Employee leyla = new Employee(4, "Leyla");

With good hash codes, they may land in different buckets. With a poor hash function, all four may land in bucket 5. To find Leyla, the map may need to compare Sarvar, Aysel, Murad, and finally Leyla.

That is no longer one small unit of work. If a bucket contains n entries in a linked structure, searching its last entry can take O(n) comparisons.

Here is an intentionally bad key implementation:

public final class EmployeeKey { private final int id; public EmployeeKey(int id) { this.id = id; } @Override public int hashCode() { return 1; // Every key produces the same hash } @Override public boolean equals(Object other) { return this == other || other instanceof EmployeeKey key && id == key.id; } }

The map still works because equals() distinguishes the keys, but all entries compete for the same bucket. The lookup becomes slower as that bucket grows.

3. Modern Java can turn a crowded bucket into a tree

Modern JDK implementations can transform a heavily populated bucket from a linked list into a balanced red-black tree. This process is called treeification.

Why does this help?

In a list, Java may inspect entries one after another. In a balanced tree, every comparison eliminates a large part of the remaining search area. A collision-heavy lookup can therefore move from O(n) toward O(log n).

OpenJDK currently uses these notable constants:

TREEIFY_THRESHOLD = 8; UNTREEIFY_THRESHOLD = 6; MIN_TREEIFY_CAPACITY = 64;

A bucket reaching eight entries does not automatically become a tree in every situation. If the table capacity is below 64, HashMap generally prefers resizing first. These values are implementation details and should not control application logic. OpenJDK HashMap source

Treeification limits the damage caused by collisions, but it does not make key design irrelevant. Well-distributed, immutable keys remain the better starting point.

Image prompt 3 — Why a tree is faster than a chain

Create a simple 16:9 Java educational infographic titled “FROM COLLISION CHAIN TO TREE”. Pure white background with a before-and-after comparison. Left panel: eight employee-ID cards connected in one long vertical linked chain inside a crowded bucket; show a search for employee ID 80 checking many cards one by one. Label: “Linked search: may approach O(n)”. Right panel: the same IDs arranged as a small balanced red-black tree; show the search path visiting only a few nodes. Label: “Tree search: approaches O(log n)”. Between the panels, show a clear transformation arrow labelled “treeification”. Add a small note: “Considered near 8 entries when table capacity is at least 64 — implementation detail.” Use orange for the crowded chain, subtle purple and red/black nodes for the tree, Spring green for the successful match, large phone-readable typography, clean arrows and premium editorial vector design. Avoid mathematical vector diagrams, dense code, dark backgrounds, mascots, logos and watermarks.

4. One put() can trigger an O(n) resize

Collisions are not the only hidden cost.

A HashMap has a capacity and a load factor. With the common default load factor of 0.75, a table with 16 buckets has a resize threshold of approximately 12 mappings:

16 × 0.75 = 12

When the threshold is crossed, the map creates a larger table and redistributes existing entries. Processing those entries makes that particular put() potentially O(n).

However, resizing does not happen on every insertion. Most insertions are cheap, while an occasional one is expensive. When the cost is averaged across a long sequence of insertions, put() remains amortized O(1).

So both statements can be true:

If you know the expected number of entries, choosing a suitable initial capacity can reduce unnecessary resizing. Recent JDKs also provide HashMap.newHashMap(expectedMappings) for this purpose.

5. hashCode() and equals() have their own cost

Complexity explanations often assume that hashCode() and equals() themselves are O(1). That is not guaranteed.

If a key calculates its hash from a large list, hashing may require visiting every element:

public final class LargeKey { private final List<Integer> values; @Override public int hashCode() { return values.hashCode(); } }

If values contains m elements, computing the hash may cost O(m). The practical lookup cost is therefore closer to:

hashCode() cost + bucket search cost + equals() cost

HashMap cannot turn an expensive key operation into constant time.

6. Mutable keys can make entries appear to disappear

Suppose a key's email field participates in both equals() and hashCode(). You insert the key and later change the email:

UserKey key = new UserKey("old@example.com"); map.put(key, "Sarvar"); key.setEmail("new@example.com"); System.out.println(map.get(key)); // may print null

The object was stored in the bucket calculated from the old email. After the mutation, get() calculates a new hash and searches a different bucket. The entry still exists, but the map can no longer find it through that mutated key.

Fields used by equals() and hashCode() should therefore remain immutable while the key is inside the map.

What should you remember in production?

HashMap is still an excellent general-purpose data structure. You simply need to respect the assumptions behind its performance:

  1. Implement equals() and hashCode() consistently.
  2. Distribute unequal keys across hashes reasonably well.
  3. Keep key fields used by equals() and hashCode() immutable.
  4. Avoid unnecessarily expensive key comparisons and hash calculations.
  5. Choose a suitable initial capacity when the expected size is known.
  6. Remember that HashMap is not thread-safe for shared concurrent mutation.

The Object.hashCode() contract requires equal objects to have equal hash codes. Unequal objects may share a hash code, although fewer collisions generally improve hash-table performance. Java Object documentation

Final mental model

Do not memorize only this:

HashMap = O(1)

Remember the complete version:

Situation

Expected complexity

Good hash distribution

Average O(1)

Collision-heavy linked bucket

Up to O(n)

Treeified bucket

Around O(log n)

One insertion that triggers resize

O(n)

Long sequence of insertions

Amortized O(1)

The lesson is not that HashMap is slow. The lesson is that performance claims come with assumptions.

HashMap is fast when keys spread across buckets and key operations are cheap. Break those assumptions, and the complexity changes.

Follow My Content

If you enjoy content about Java, backend engineering, concurrency, computer architecture, and system design, you can follow my work on:

Comments (0)

0/1000

Loading comments...