All topics
2 / 101
collections
intermediate

HashMap Internals

Understand the bucket array, hash collisions, and the treeify threshold so you can reason about HashMap performance.

A HashMap stores pairs: a key, and the value that belongs to it. Ask for a key and you get the value back, almost instantly, no matter how many pairs are stored.

A coat-check counter with numbered hooks. The ticket number tells you which hook (bucket); if two coats share a hook, you walk the chain hanging from it.

Key Concepts

1
How it finds things so fast. Inside is an array. Each slot in that array is called a bucket.
2
When you store a key, Java calls hashCode() on it, which turns the key into a number. That number is converted into a slot number, and the pair is put in that bucket. Looking up a key repeats the same calculation, goes straight to that bucket, and finds the pair. No searching.
hashCode()
3
What happens when two keys land in the same bucket. They will. There are far more possible keys than buckets.
4
Two keys in one bucket is called a collision, and the map handles it by keeping a small list in that bucket. Looking up then means going to the bucket and walking its short list.
5
That is fine when the lists stay short. If a bucket's list grows past 8 entries, and the array itself has at least 64 slots, Java converts that one bucket from a list into a balanced tree. Searching a tree of 1,000 items takes about 10 steps instead of 500.
6
Both conditions matter. In a small array, long lists usually mean the array is too small rather than the keys being unusual, so Java grows the array instead of building trees.
7
Why the array grows, and what it costs. When the map is about three-quarters full, the array doubles in size and every existing pair is moved to its new slot. The rule is: grow when entries exceed capacity x 0.75.
capacity x 0.75
8
Starting from the default of 16 slots and inserting a million entries triggers 16 growths, and copies roughly 1.5 million entries along the way.
9
You can avoid all of it. new HashMap<>(1_000_000 / 0.75 + 1) creates the array at the right size immediately.
new HashMap<>(1_000_000 / 0.75 + 1)
10
Why the hash gets scrambled first. The slot is chosen using only the lowest bits of the hash number. Some hashCode() implementations produce numbers that differ only in their high bits, and those would all land in the same slot.
hashCode()
11
So Java mixes the high bits down into the low bits before choosing the slot. That one line prevents a whole class of bad-performance bugs from ordinary-looking key classes.
12
Two threads must not write at once. HashMap is not built for it. Two threads writing at the same moment can lose entries and leave the size wrong.
HashMap
13
Use ConcurrentHashMap. Do not use Collections.synchronizedMap, which puts one lock around the whole map so only one thread can touch it at a time.
ConcurrentHashMapCollections.synchronizedMap
14
Never change a key after storing it. The pair sits in the bucket chosen from the key's hash at the time you stored it. Change a field that hashCode() depends on, and lookups now compute a different bucket and find nothing — while the entry still takes up space and still counts toward the size.
hashCode()
15
That is why String and Integer make good keys: they cannot change.
StringInteger
16
What the interviewer is probing.1. "How does HashMap work?" Probing: the mechanism, not the headline. Stalls: "It uses a hash to give O(1) access." Moves up: hash to a number, number to a bucket, collisions into a list, list into a tree past 8, array doubles at 75% full.
17
2. "What is the worst case for a lookup?" Probing: whether you know it degrades. Stalls: "O(1) always." Moves up: O(log n) once a bucket is treeified, O(n) before that, and a bad hashCode is what gets you there.
hashCode
18
3. "Why 0.75?" Probing: the trade-off. Stalls: "It is the default." Moves up: lower wastes memory on empty slots, higher makes the lists longer; 0.75 balances the two.
19
4. "Two threads put at the same time." Probing: whether you know it is unsafe. Stalls: "Use Collections.synchronizedMap." Moves up: lost entries and a wrong size; ConcurrentHashMap locks a bucket at a time rather than the whole map.
Collections.synchronizedMapConcurrentHashMap
20
5. "What must hashCode and equals promise?" Probing: the contract. Stalls: "They should match." Moves up: equal objects must give the same hash, different objects may share one, and neither may change while the key is in a map.
hashCodeequals
21
  Capacity growth from the default, inserting 1,000,000 entries
22
  capacity   resize at (x0.75)      entries copied
  --------------------------------------------------------
        16              12                      12
        32              24                      24
        64              48                      48
       ...             ...                     ...
   524,288         393,216                 393,216
  1,048,576         786,432                 786,432
  --------------------------------------------------------
  Resizes performed                                  16
  Total entries copied (sum)             ~1,572,000
23
  Pre-sized: new HashMap<>(1_000_000 / 0.75 + 1)
  Resizes performed                                   0
  Entries copied                                      0
24
  Memory, roughly, for 1M entries (64-bit JVM, compressed oops)
    Node: header 16 B + hash 4 + key ref 4 + value ref 4
          + next ref 4                          =  32 B
    Table array slot                            =   4 B
    1M nodes + 2M-slot table  (1M x 32) + (2M x 4)
                                                =  40 MB
    -- plus the keys and values themselves.
Use cases:HashMapPerformanceHashing