Skip to content
Tutorials Center
My learning

Topics

Lesson 83 of 201 ยท Collections

How HashMap Works Inside

See how Java HashMap works inside - hash codes, buckets, collisions, load factor and resizing, treeified bins, why mutable keys break maps and what makes a good hashCode.

A HashMap can find one key among millions in roughly the time it takes to find one among ten. That feels like magic until you see the trick: it never searches. It turns the key into a number, uses the number to pick one small "bucket" out of an array, and only looks inside that bucket.

Understanding this design pays off well beyond curiosity. It explains why keys need correct equals and hashCode methods, why a mutated key vanishes, why iteration order seems random and changes, what the load factor and initial capacity really mean, and why a bad hashCode can make a map hundreds of times slower. This lesson walks through the real OpenJDK implementation, step by step, with programs you can run. Everything here also applies to HashSet, which is a HashMap with dummy values.

The big idea: an array of buckets

A HashMap keeps an internal array called the table. Each slot is a bucket that holds the entries whose keys landed there, as a small linked list of nodes:

TEXT
table (capacity 8)
 [0] -> null
 [1] -> ("pear", 3) -> null
 [2] -> null
 [3] -> ("fig", 7) -> ("kiwi", 2) -> null      <- a collision: two keys, one bucket
 [4] -> null
 [5] -> ("plum", 9) -> null
 [6] -> null
 [7] -> null

Each node stores four things: the key, the value, the key's (spread) hash, and a link to the next node in the same bucket. To find a key, the map:

  1. computes the key's hash,
  2. turns the hash into a bucket index,
  3. walks that bucket's short list, comparing hashes first and then calling equals.

If the hash codes spread the keys evenly, buckets hold zero, one or two entries, and step 3 is nearly free. That's why lookups are O(1) on average.

From hashCode to bucket index

Every object has a hashCode(): an int that equal objects must share (The Object Class). HashMap doesn't use it directly. First it spreads the bits by XOR-ing the high half into the low half:

Java
static int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Then it picks the bucket with a bit mask instead of %:

Java
int index = (table.length - 1) & hash;     // table length is always a power of two

With 16 buckets, length - 1 is binary 1111, so the index is simply the lowest 4 bits of the hash. That's much faster than division, and it's why the table length is always a power of two. It also explains the spreading step: without it, keys whose hash codes differ only in the high bits would all crowd into the same few buckets. A null key gets hash 0 and always lives in bucket 0.

Java Following keys from hashCode to bucket

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Two things to notice. "Aa" and "BB" have the same hash code (2112), so they always share a bucket: a genuine collision. And the same two Integer keys print in a different order after the table grows, because 18 moves from bucket 2 to bucket 18 while 3 stays in bucket 3. This is why you must never depend on HashMap iteration order.

Collisions and equals

Different keys landing in the same bucket is normal; with millions of keys and only 2ยณยฒ possible hash codes, collisions are unavoidable. Inside a bucket, the map tells keys apart in two steps: it compares the stored hash (a cheap int check) and, only if the hashes match, calls key.equals(other). This is the reason for the equals/hashCode contract:

  • If a.equals(b), then a.hashCode() == b.hashCode() must hold. Otherwise an equal key is looked for in the wrong bucket and never found.
  • Unequal objects may share a hash code. That's legal but costs speed.

The simplest way to see all of this is to build a tiny version yourself. The class below uses the same hash spreading, power-of-two table, chaining and doubling as the real one, but starts with 4 buckets so you can watch it fill and grow:

Java A mini HashMap you can watch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

After three keys the table is at its threshold (3 of 4 buckets' worth), and the fourth put triggers a resize to 8 buckets. The dump shows Aa and BB sharing one bucket no matter how big the table gets, because their hash codes are identical. The real HashMap adds new nodes at the tail of a bucket and splits buckets cleverly during resizing, but the logic is the same.

Load factor, capacity and resizing

The load factor (default 0.75) decides how full the table may get. When the number of entries exceeds capacity * loadFactor (the threshold), the map doubles the table and redistributes every entry.

  • The default capacity is 16, so the first resize happens at the 13th entry (threshold 12). The table itself is allocated lazily, on the first put.
  • Doubling keeps resizing cheap overall: each entry is moved only a handful of times as the map grows, so put stays O(1) amortized.
  • Because the length doubles, each entry either stays at its index or moves to index + oldCapacity, decided by a single bit of its hash. OpenJDK splits each bucket into a "low" and "high" list without recomputing anything.

A lower load factor means emptier buckets (faster lookups, more memory); a higher one packs entries tighter. 0.75 is a well-tested trade-off; you'll rarely change it.

Pre-sizing correctly

The constructor argument of new HashMap<>(n) is the initial capacity, not the number of entries. It's rounded up to a power of two, and the map resizes at 75% of that:

Java
new HashMap<>(16);                  // capacity 16 -> resizes when the 13th entry arrives
new HashMap<>(1_000);               // capacity 1,024 -> resizes after 768 entries
HashMap.newHashMap(1_000);          // Java 19+: sized so 1,000 entries fit without a resize

So to hold 1,000 entries without resizing, you'd need new HashMap<>(1_334). HashMap.newHashMap(int numMappings) (and HashSet.newHashSet) does that arithmetic for you. Pre-sizing matters only for big maps built in hot code; for everyday maps, the default is fine.

Treeified buckets

What if many keys land in one bucket, because of a poor hashCode or deliberately crafted keys (a known denial-of-service attack on web servers that put request parameters in a map)? A long linked list turns lookups into O(n) scans.

Since Java 8, HashMap defends itself. When a single bucket grows beyond 8 entries, and the table has at least 64 buckets, that bucket is converted into a small red-black tree of TreeNodes, making lookups in it O(log n). (If the table is smaller than 64, the map simply resizes instead, which usually spreads the keys out.) When a bucket shrinks to 6 or fewer entries during a resize, it turns back into a list.

Inside a tree bucket the keys are ordered by hash, and when hashes tie, by compareTo if the keys implement Comparable with the same class. Without Comparable, keys with identical hashes can't be ordered meaningfully, and lookups may still have to search much of the tree. You can measure all three cases:

Java What bad hash codes cost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The good keys are fastest. All keys of the other two types share one bucket, which becomes a tree; with Comparable keys the tree can be searched in O(log n), so it's slower but tolerable. Without Comparable, every lookup has to scan most of the bucket, and it's typically orders of magnitude slower. Run it a few times; exact numbers vary, but the ranking is stable. Treeification is a safety net, not a substitute for a good hashCode.

Why mutable keys break a map

A node remembers the hash that was computed when it was inserted, and it lives in the bucket chosen by that hash. If you change a key's fields afterward, its hashCode changes, but the entry stays where it was. Lookups now go to the wrong bucket:

Java A key that changes after insertion gets lost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The entry is still in the map (it shows up in size() and when printing), but neither the mutated key nor a fresh Badge("ana") can reach it: one goes to the wrong bucket, the other finds the right bucket but fails equals. Putting the key again even creates a second entry. The same applies to HashSet elements.

The fix is to use immutable keys: String, wrappers, enums, records with immutable components, or classes built along the lines of Immutable Classes. If a key must change, remove the entry, change the key, and put it back.

What makes a good hashCode

A good hashCode is consistent with equals (uses the same fields), stable while the object is in a collection, cheap to compute, and well spread, so different objects rarely share a value. In practice:

  • Let the language write it: records generate a good one, and IDEs generate Objects.hash(a, b, c)-style methods.
  • Combine fields with multiplication by an odd prime, the way String and Objects.hash use 31: 31 * x + y. Simply adding fields collides constantly, because (1, 2) and (2, 1) give the same sum.
  • Include every field that equals compares, and nothing that equals ignores.
  • For expensive objects, caching the hash in a field is fine if the object is immutable (String does this).
Java Counting distinct hash codes for a 100 x 100 grid

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The naive sum produces only 199 different hash codes for 10,000 points, so on average about 50 points share each value: a slow map. Multiplying by 31 gives thousands of distinct values; it isn't perfect for this grid (because y can be larger than 31), but it's far better. A collision-free hash isn't required, just a well-spread one.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A HashMap has 16 buckets. Into which bucket does a key with spread hash 37 go?

    The index is (16 - 1) & 37. 37 is binary 100101, and the low 4 bits 0101 are 5. That equals 37 % 16 for non-negative hashes.
  2. 2. With default settings, when does a new HashMap resize for the first time?

    The default capacity is 16 and the load factor 0.75, so the threshold is 12. Adding the 13th entry doubles the table to 32 buckets.
  3. 3. You change a field used by hashCode on a key that is already in a HashMap. What happens to map.get(key)?

    The entry stays in the bucket chosen by the old hash and keeps the old stored hash, so lookups with the changed key look in the wrong place.
  4. 4. Why do "Aa" and "BB" always end up in the same bucket?

    String.hashCode computes 31 * 'A' + 'a' = 31 * 65 + 97 = 2112, and 31 * 'B' + 'B' = 31 * 66 + 66 = 2112. Equal hashes always map to the same bucket.
  5. 5. What does new HashMap<>(1000) actually configure?

    The argument is a capacity, rounded up to a power of two. With load factor 0.75 the threshold is 768. Use HashMap.newHashMap(1000) to fit 1,000 entries.

Summary

  • A HashMap is an array of buckets; each bucket holds a short chain of nodes (key, value, hash, next).
  • The bucket index is (capacity - 1) & (h ^ (h >>> 16)), with h = key.hashCode(); capacity is always a power of two.
  • Lookups compare stored hashes first, then call equals, which is why equal objects must have equal hash codes.
  • The table doubles when size exceeds capacity ร— load factor (default 16 ร— 0.75 = 12); iteration order can change on every resize.
  • Buckets with more than 8 entries become red-black trees (table โ‰ฅ 64), which is O(log n) for Comparable keys.
  • Mutating a key after insertion strands its entry; use immutable keys such as strings and records.
  • Good hash codes use every field equals uses and mix them (records and Objects.hash do this for you).

Next: HashSet, the set built on top of HashMap, with fast membership tests and set operations.