Card 05/ 09
HashMap Resizing: The Load Factor and the Rebuild
At twelve entries a new map doubles its buckets and moves every entry, unless you sized it ahead.
A HashMap rebuilds itself when it holds more entries than its buckets times its load factor, the fullness it will tolerate, 0.75 by default. The rebuild doubles the number of buckets and moves every entry into the new array. Following it step by step explains why a put is cheap on average and occasionally slow.
You start with an empty HashMap with default settings, and keep putting new entries into it.
From an empty map to one that has doubled its buckets
A new map has sixteen buckets and a load factor of 0.75
Map<String, Integer> counts = new HashMap<>();Sixteen buckets (the slots a HashMap sorts entries into) at 0.75 gives a threshold of twelve entries: not twelve per bucket, twelve in total.
The put that passes the threshold triggers a rebuild
Up to here every put has been a hash, a bucket and a write. The put that takes the map past twelve entries triggers the rebuild, and nothing in your code shows which put it was.
A new array of buckets is allocated, twice as long
Thirty-two buckets, and a new threshold of twenty-four. The old buckets are still holding everything.
Every entry is moved into the new buckets
Each entry's bucket is worked out again, because the bucket number depends on how many buckets there are. This is the expensive step, and it touches every entry in the map.
Sizing ahead skips all of it
Map<String, Integer> counts = HashMap.newHashMap(200_000);Telling the map how many entries to expect makes it allocate enough buckets at the start: filling this one with 200,000 entries causes no rebuild at all. For a large map built once and read many times, this is the cheapest performance change available.
The buckets double and every entry moves. Because the threshold doubles too, rebuilds get further apart as the map grows, which is why a put is constant on average and occasionally much slower. You know you have sized a map well when it never rebuilds while you fill it. The plain constructor takes a number of buckets, not entries: new HashMap<>(200_000) starts with 262,144 buckets, a threshold of 196,608, and still rebuilds once before it holds 200,000 entries. HashMap.newHashMap(200_000), added in Java 19, takes the number of entries instead; on Java 17, write new HashMap<>((int) (200_000 / 0.75f) + 1).
- Java
- Hash Tables
- Performance
← → move through sections and cards