Watching a Map Rebuild Itself When It Passes the Load Factor

Buckets are fixed in number and entries are not, so at some point there are too many entries for the buckets there are. What the map does about it explains two numbers in its documentation and one line you should write more often.

From an empty map to one that has doubled its buckets

Step 1 of 5

A new map has sixteen buckets and a load factor of 0.75

java

Map<String, Integer> counts = new HashMap<>();

The load factor is the fullness the map will tolerate. Sixteen buckets at 0.75 gives a threshold of twelve entries — not twelve per bucket, twelve in total.

The twelfth put crosses the threshold

Up to here every put has been a hash, a bucket and a write. The twelfth is the one that triggers the rebuild, and nothing in your code can tell 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 recalculated, because the bucket number depends on how many buckets there are. This is the expensive step and it touches every entry in the map — one put in twelve pays for the eleven before it.

Sizing ahead skips all of it

java

Map<String, Integer> counts = new HashMap<>(200_000);

Telling the map how many entries to expect makes it allocate enough buckets at the start. For a large map built once and read many times, this is the cheapest performance change available.

The run to remember: 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 when averaged out and occasionally very much not.

Java
Hash Tables
Performance