What is the load factor in a HashMap, and what is the trade-off when you increase or decrease it?

## Buckets and hashing — the foundation A `HashMap` keeps entries in an internal array called the **bucket array** (or table). To find where a key goes, the map computes the key's **hash code**, then maps it to an index in that array. Ideally every key lands in its own bucket and lookup is O(1). But two different keys can map to the **same** bucket — a **collision**. Colliding entries are chained together in that bucket (a linked list, or since Java 8 a balanced tree once a chain gets long). The more crowded the buckets, the more collisions, and the longer those chains — so lookups degrade toward O(chain length). ## What the load factor is The **load factor** is a number between 0 and 1 that says: *how full may the bucket array get before we grow it?* The map resizes (doubles the bucket array and re-distributes every entry — "rehashing") when: ``` size > capacity * loadFactor ``` The default load factor is **0.75**. With the default capacity of 16, the map grows once it holds more than 12 entries. ## The trade-off, intuitively Think of buckets as parking spaces and entries as cars: - **High load factor (e.g. 0.9):** you let the lot get 90% full before building a bigger one. **Less memory** (fewer empty spaces), but cars cluster — more collisions, longer chains, **slower** lookups and inserts. - **Low load factor (e.g. 0.5):** you build a bigger lot when it's only half full. Cars are spread out — **fewer collisions, faster** access — but you keep lots of empty space (**more memory**) and you trigger growth/rehashing **more often** as you fill it. So the load factor trades **space against time**: | Load factor | Memory | Collisions / lookup time | Resize frequency | |---|---|---|---| | Low (0.5) | More used | Fewer / faster | More frequent | | Default (0.75) | Balanced | Balanced | Balanced | | High (0.9) | Less used | More / slower | Less frequent | ## Why 0.75 is the default 0.75 is an empirically chosen sweet spot: under a good hash distribution it keeps the average bucket chain very short (the probability of a bucket having many entries follows a Poisson distribution; at 0.75 the expected collisions are low) while keeping memory overhead modest (about 33% spare capacity). The JDK documentation explicitly notes it offers a good trade-off between time and space costs. ## Java 8 treeification softens the high end Since Java 8, when a single bucket's chain exceeds 8 entries (and the table is at least 64 buckets), that chain is converted from a linked list into a **red-black tree**, so worst-case lookup in that bucket is O(log n) instead of O(n). This makes a high load factor less dangerous than it used to be — pathological collisions are bounded — but it does not eliminate the memory-vs-collision trade-off in the common case. ## When to change it - **Raise it** only when memory is tight and you can tolerate slightly slower access (e.g. a huge map where footprint dominates). - **Lower it** only for a latency-critical, read-heavy map where you'll happily spend memory for fewer collisions. - **Otherwise: leave it at 0.75.** It is almost always correct, and most real wins come from setting the *initial capacity*, not from tuning the load factor. You set it via the constructor: `new HashMap<>(initialCapacity, loadFactor)`.