Hash Tables

A hash table turns the key into an array index and goes straight there. That one idea is what makes lookup O(1) instead of the O(n) of scanning a list, and it is why HashMap is the most-used collection in Java.

The idea

1. Compute key.hashCode() — an int.
2. Fold it into the array's range to get a bucket index.
3. Store the key and value there.

Lookup repeats the same arithmetic and lands in the same bucket. No searching.

    private int bucketFor(Object key, int length) {
        return key == null ? 0 : Math.floorMod(key.hashCode(), length);
    }

Math.floorMod, not %. A hashCode is routinely negative, and Java's % keeps the sign — -7 % 16 is -7, and that is an ArrayIndexOutOfBoundsException. It is a real bug in a lot of hand-written hash tables, and it only fires for keys that happen to hash negative, so it survives casual testing. ("polygenelubricants" is the well-known String whose hash is Integer.MIN_VALUE, where even Math.abs fails, because negating it overflows straight back to itself.)

Collisions

Two different keys can produce the same bucket. They must — there are 2³² possible hash codes and maybe 16 buckets. So a hash table is not "an array of values", it is an array of buckets, and this one makes each bucket a small linked list. That is separate chaining.

    public V put(K key, V value) {
        int index = bucketFor(key, buckets.length);
        for (Entry<K, V> e = buckets[index]; e != null; e = e.next) {
            if (equal(e.key, key)) {
                V previous = e.value;
                e.value = value; // a Map replaces, it does not duplicate
                return previous;
            }
        }
        Entry<K, V> head = new Entry<>(key, value);
        head.next = buckets[index];
        buckets[index] = head;
        size++;

        if ((double) size / buckets.length > MAX_LOAD_FACTOR) {
            resize();
        }
        return null;
    }

Note the scan of the chain before inserting: a map replaces an existing key rather than storing it twice. That scan is why the O(1) is an average.

Why O(1) is an average, not a guarantee

With a good hash and a bounded load factor, chains stay roughly one element long and a lookup is one array access plus one comparison.

With a terrible hash, every key lands in the same bucket, the table becomes one long linked list, and every operation is O(n). And return 0; is a perfectly legal hashCode — it satisfies the contract, since equal objects must have equal hashes and this trivially does. It just destroys the data structure.

The real HashMap mitigates this: since Java 8, a bucket that grows past eight entries converts from a linked list into a red-black tree, so the worst case degrades to O(log n) rather than O(n). That is a patch on bad hashing, not a substitute for good hashing.

Load factor and resizing

The load factor is size / buckets.length. As it rises, chains lengthen and the O(1) decays. The standard threshold — used here and in the JDK — is 0.75, a deliberate compromise between wasted memory and lengthening chains.

    @SuppressWarnings({"unchecked", "rawtypes"})
    private void resize() {
        Entry<K, V>[] old = buckets;
        Entry<K, V>[] bigger = new Entry[old.length * 2];
        for (Entry<K, V> bucket : old) {
            for (Entry<K, V> e = bucket; e != null; ) {
                Entry<K, V> next = e.next;
                int index = bucketFor(e.key, bigger.length);
                e.next = bigger[index];
                bigger[index] = e;
                e = next;
            }
        }
        buckets = bigger;
    }

Every key must be rehashed, not merely moved. The bucket index depends on the table length, so the same key belongs somewhere else in a bigger table. Copying buckets across verbatim is a silent corruption — nothing throws, and get then looks in the right place and finds nothing. The test grows a table from 2 buckets to hold 200 keys and checks every one still resolves:

        Check.eq(big.size(), 200, "all keys present after resizing");
        Check.isTrue(big.bucketCount() > 2, "table actually grew");

Because a resize touches every entry, a single put can be O(n). Amortised over the sequence it is still O(1) — the same argument as ArrayList. And as there, pre-sizing avoids the repeated rehashing entirely.

⚠️ equals and hashCode

The contract, and the two ways it goes wrong:

• Equal objects must have equal hash codes. Break this and lookup fails outright: you store with one hash, search with another, and the map says the key is not there while holding it.
• Unequal objects may share a hash code. That is just a collision — correct, only slower.

So overriding equals without hashCode is the classic bug, and it produces a map that appears to lose data.

The other trap is mutating a key after inserting it. If the mutated field is part of hashCode, the entry is now in the bucket for its old hash while lookups compute the new one. It is unreachable, and it is still counted in size(). Use immutable keys — which is exactly what makes record types and String such good ones, since both generate a correct pair and cannot change.

What Java gives you

"No order" means exactly that: HashMap iteration order is an accident of hashing and capacity, and it can change when the map resizes. Code that depends on it is code that will break after a deployment for no visible reason.

What to remember

• Hash the key to an index; that is the whole trick.
• Math.floorMod — a negative hash code otherwise indexes out of bounds.
• O(1) is an average and it depends on a decent hashCode.
• Resizing must rehash every key, and a resize makes one put O(n).
• Override equals and hashCode together; never mutate a key in a map.
• No iteration order. Use LinkedHashMap or TreeMap if you need one.