Hash table mechanics

The **load factor** is n / m: entries divided by buckets. It is the one number that predicts speed. For separate chaining it is the average chain length; for open addressing it is the fraction of slots in use and must stay below 1.

Java's HashMap resizes when size > 0.75 × capacity. A lower limit wastes memory but keeps chains short; a higher limit saves memory but costs more probes. Under the standard uniform-hashing assumption the expected cost of a lookup grows with the load factor α as shown here.

When the load factor passes its limit, the table allocates a bigger array (usually twice the size) and **rehashes**: every key is hashed again with the new size and stored in its new bucket. Rehashing is necessary because the bucket index depends on the table size, so an entry cannot simply be copied to the same index.

Run the “Growing from 2 buckets” preset. Starting with 2 buckets and a limit of 0.75, the table doubles to 4, 8, 16 as keys arrive, and the final message counts the keys moved. Notice how keys that collided in the small table often separate after the resize.

1private void resize() {
2    LinkedList<Integer>[] old = table;
3    table = newTable(old.length * 2);                                   // double the number of buckets
4    for (LinkedList<Integer> chain : old)
5        for (int key : chain) table[Math.floorMod(key, table.length)].add(key);   // every key is rehashed
6}

1class ChainedSet {
2    private LinkedList<Integer>[] table; private int size; private final double maxLoad;
3    void add(int key) {
4        int b = Math.floorMod(key, table.length);
5        if (table[b].contains(key)) return;                          // already present
6        table[b].add(key); size++;
7        if (size > maxLoad * table.length) resize();                 // load factor too high
8    }
9    private void resize() {
10        LinkedList<Integer>[] old = table;
11        table = newTable(old.length * 2);                            // double the number of buckets
12        for (LinkedList<Integer> chain : old)
13            for (int key : chain) table[Math.floorMod(key, table.length)].add(key);   // every key is rehashed
14    }
15}

Capacity doubles on each resize. Doubling makes the growth geometric: after n insertions the total number of rehashed keys is at most about 2n, because each key is moved once per doubling and the sizes of earlier tables add up to less than the last one. That is why put is O(1) *amortised* even though a single put can cost O(n).

In Java the capacity of a HashMap is always a power of two (a request for 100 becomes 128) and a HashSet of 14 values added to a default table resizes once when the 13th value arrives (16 × 0.75 = 12). If you know the number of entries in advance, size the table to expected / 0.75 + 1 to avoid resizing at all. The animation shows exactly this for the 14-value preset.

1static <K, V> Map<K, V> presized(int expectedEntries) {
2    int capacity = (int) (expectedEntries / 0.75f) + 1;     // large enough that no resize happens
3    return new HashMap<>(capacity);
4}

1List<Integer> list = new ArrayList<>();
2Set<Integer> linked = new LinkedHashSet<>();
3Set<Integer> hash = new HashSet<>();
4Set<Integer> tree = new TreeSet<>();
5PriorityQueue<Integer> heap = new PriorityQueue<>();
6for (int x : arr) {
7    list.add(x);        // keeps insertion order, keeps duplicates
8    linked.add(x);      // keeps insertion order, drops duplicates
9    hash.add(x);        // order decided by hash buckets
10    tree.add(x);        // always sorted
11    heap.add(x);        // heap array: only the smallest is guaranteed first
12}
13System.out.println(list + " " + linked + " " + hash + " " + tree + " " + heap);

A hash table promises **expected O(1)** lookups: if the hash function spreads keys uniformly and the load factor is bounded by a constant, a lookup scans a constant number of entries on average. Expected is a statement about the average over random keys or a random hash function, not a guarantee for one operation.

Three costs are easy to confuse: *amortised* O(1) (put, averaged over a sequence that includes resizes), *expected* O(1) (lookup, averaged over the randomness of the hash), and *worst-case* O(n) (all keys in one bucket). Hash code computation itself costs time too: hashing a string of length L is O(L), so lookups of long strings are not truly constant.

If all keys hash to one bucket, the table is a linked list: every operation scans up to n entries. Pick the “Worst case: all collide” preset: the constant hash function puts all keys in bucket 0 and the search for the last key compares with every one before it.

Java mitigates this. Since Java 8 a HashMap bucket with 8 or more entries (in a table of at least 64 buckets) is converted into a red-black tree ordered by hash code and, for keys that implement Comparable, by compareTo. Lookups in such a bucket take O(log n) instead of O(n). Smaller tables resize instead of treeifying.

1class ChainedHashSet {
2    private final int m, variant, a;                                // m buckets
3    private final LinkedList<Integer>[] table;                      // one chain per bucket
4    int hash(int key) {                                             // the option picks one variant
5        switch (variant) {
6            case 0: return Math.floorMod(key, m);
7            case 1: return (int) (m * ((key * 0.6180339887) % 1.0));
8            case 2: return 0;                                       // worst case: every key collides
9            default: return ((a * key + 7) % 101) % m;              // universal-style family
10        }
11    }
12    boolean add(int key) {
13        LinkedList<Integer> chain = table[hash(key)];
14        if (chain.contains(key)) return false;                      // walk the chain: duplicate
15        chain.add(key); return true;                                // append to the chain
16    }
17    boolean contains(int key) { return table[hash(key)].contains(key); }
18    boolean remove(int key) { return table[hash(key)].remove((Integer) key); }
19}

A hash table spends memory on empty buckets and on bookkeeping. A Java HashMap stores each entry in a node object holding the cached hash, the key, the value and the next pointer, and boxes int keys and values as separate Integer objects. On a typical 64-bit JVM with compressed references that is roughly 32 bytes for the node, plus 16 bytes for each boxed Integer, plus 4 bytes per bucket in the array. A million Integer→Integer entries (keys beyond the small-value cache) therefore cost roughly 70 MB, compared with 4 MB for a plain int[].

This is why primitive-specialised or open-addressed maps (from libraries) can be several times smaller, and why a boolean[] or int[] count array beats a HashMap<Integer, Integer> when the keys form a small dense range. Measure with a tool such as JOL if the exact number matters.