Hashing

The idea: from key to index

Think of a library where every book has a shelf number computed from its title. To find a book you do not walk along the shelves: you compute the number and go to that shelf.

A balanced search tree finds a key in O(log n) by comparing it with other keys. A hash table does not compare its way down at all: it computes an array index directly from the key and looks there.

key ──hash function──▶ int ──compression──▶ index in 0 … m−1 ──▶ table[index]

For example, with m = 7 slots and the key 22: 22 mod 7 = 1, so 22 is stored in slot 1. To find 22 later, compute 22 mod 7 = 1 again and look in slot 1 — one step, however many keys the table holds.

index:   0    1    2    3    4    5    6
       +----+----+----+----+----+----+----+
       |    | 22 |    |    |    |    |    |
       +----+----+----+----+----+----+----+

If every key landed in its own slot, put, get and remove would all be O(1). The whole chapter is about what happens when they do not.

The array has m slots (also called buckets); the table holds n keys. The ratio

α = n / m        (the load factor)

measures how full the table is, and almost every cost in this chapter is a function of α. For example, 6 keys in 11 slots give α = 6/11 ≈ 0.55: the table is a little more than half full.

Hash functions and compression

In plain words: the hash function is the "ticket machine". It must always give the same ticket for the same coat, it must be quick, and it should hand out tickets evenly so that no hook gets crowded.

A good hash function is deterministic (the same key always gives the same value), fast, and spreads keys evenly. In Java the first step is the key's hashCode(), which returns any int, possibly negative. The second step compresses it into the table:

index = h(k) mod m

Why a prime m helps. k mod m keeps only the "remainder information" of k. If the keys share a pattern with m, they pile up. Take the keys 8, 16, 24, 32, 40, 48:

m	Buckets used
16	only 0 and 8 (every key is a multiple of 8, and 8 divides 16)
17	six different buckets (6, 7, 8, 14, 15, 16)

Key by key: with m = 16 the indexes are 8, 0, 8, 0, 8, 0; with m = 17 they are 8, 16, 7, 15, 6, 14. Same keys, same effort — but with 16 slots only two are ever used.

A key sequence with stride s only reaches m / gcd(s, m) different buckets. With a prime m, gcd(s, m) = 1 for every stride that is not a multiple of m, so all buckets are reachable.

(For h = −7 and m = 5, Math.floorMod gives 3 and (h & 0x7fffffff) % m gives 1. They are different, but both are valid indexes, and each one always gives the same answer for the same key — which is all that matters.)

String.hashCode

In plain words: Java reads the string from left to right, and at each character it multiplies what it has so far by 31 and adds the new character code. Because of the multiplication, the position of each character matters.

For a string s of length n, Java computes a polynomial in 31 with the character codes as coefficients:

s[0]·31^(n−1) + s[1]·31^(n−2) + … + s[n−1]

evaluated with Horner's rule and ordinary int overflow:

int h = 0;
for (int i = 0; i < s.length(); i++) {
    h = 31 * h + s.charAt(i);
}

Worked example — "cat".hashCode() ('c' = 99, 'a' = 97, 't' = 116):

Step	Character	h = 31 · h + code
start		0
1	'c' (99)	31 · 0 + 99 = 99
2	'a' (97)	31 · 99 + 97 = 3166
3	't' (116)	31 · 3166 + 116 = 98262

So "cat".hashCode() is 98262, while "act" (same letters, different order) gives 96402.

So "AB".hashCode() is 65·31 + 66 = 2081 while "BA".hashCode() is 66·31 + 65 = 2111: the order of the characters matters, which a simple sum of character codes would ignore. Collisions still exist — "Aa" and "BB" both hash to 2112 — because infinitely many strings share 2³² possible values. String caches its hash after the first call, since strings are immutable.

Collisions

Two different keys with the same index collide. Collisions are unavoidable (more possible keys than slots), and they appear early: with only 23 random keys in 365 slots a collision is more likely than not (the birthday paradox). A hash table is therefore defined as much by its collision strategy as by its hash function. There are two families.

Separate chaining

In plain words: every locker is big enough to hold a small bag of items. When two keys get the same number, both go into the same bag — the chain.

Each slot holds a list (a chain) of all the entries that hashed there. Insert 15, 8, 22, 3, 10, 29 into m = 7 buckets (h(k) = k mod 7), appending to the end of each chain:

Insert	k mod 7	Chain after the insertion
15	1	1: 15
8	1	1: 15 → 8 (collision: appended)
22	1	1: 15 → 8 → 22
3	3	3: 3
10	3	3: 3 → 10
29	1	1: 15 → 8 → 22 → 29

Final table:

0: (empty)
1: 15 → 8 → 22 → 29
2: (empty)
3: 3 → 10
4: (empty)
5: (empty)
6: (empty)

get(k) hashes k, then searches only that chain with equals. get(29) computes 29 mod 7 = 1 and compares with 15, 8, 22, 29: four comparisons. get(5) computes 5 and finds an empty chain: zero comparisons, "not found". The average chain length is α, so a search costs O(1 + α) on average. α may exceed 1 — the chains just grow — but performance degrades linearly, so tables still resize.

(This small example is unlucky on purpose: four of the six keys leave remainder 1. With better-spread keys every chain would hold about α = 6/7 < 1 entries.)

Open addressing

All entries live in the array itself, at most one per slot, so α < 1 always. When the home slot h(k) is occupied, the table probes a sequence of other slots until it finds a free one. A search follows the same sequence and stops at the key or at an empty slot.

In all three examples below the keys are inserted in the order 22, 35, 13, 46, 57, 24 into m = 11 slots, with home slot h(k) = k mod 11. Notice that 35, 13, 46, 57 and 24 all have home slot 2 — a worst case, chosen to show the differences clearly. (A . means an empty slot. The tables were produced by a small Java program.)

Linear probing: try h(k), h(k) + 1, h(k) + 2, … (mod m). Insert 22, 35, 13, 46, 57, 24 into m = 11:

Key	h(k) = k mod 11	Slots probed	Final slot
22	0	0	0
35	2	2	2
13	2	2, 3	3
46	2	2, 3, 4	4
57	2	2, 3, 4, 5	5
24	2	2, 3, 4, 5, 6	6

The table after every insertion:

slot:       0   1   2   3   4   5   6   7   8   9  10
+22        22   .   .   .   .   .   .   .   .   .   .
+35        22   .  35   .   .   .   .   .   .   .   .
+13        22   .  35  13   .   .   .   .   .   .   .     (2 taken → 3)
+46        22   .  35  13  46   .   .   .   .   .   .     (2, 3 taken → 4)
+57        22   .  35  13  46  57   .   .   .   .   .     (2, 3, 4 taken → 5)
+24        22   .  35  13  46  57  24   .   .   .   .     (2 … 5 taken → 6)

Total probes: 1 + 1 + 2 + 3 + 4 + 5 = 16 for six keys. The run 2 … 6 grows by one with every insertion.

Linear probing is simple and cache-friendly, but it suffers from primary clustering: occupied slots form long runs, any key that hashes anywhere into a run lands at its end and makes it longer, and runs merge. Even keys with different home slots end up competing. (In the table above, a new key with home slot 4 — say 15 — would also have to walk to slot 7, although nothing else has home slot 4.)

Quadratic probing: try h(k) + 0², + 1², + 2², + 3², … (mod m). With the same keys: 46 probes 2, 3, 6; 57 probes 2, 3, 6, 0, 7 and lands in 7; 24 lands in 5. Runs of neighbours no longer form, but keys with the same home slot still follow the same sequence: secondary clustering. Quadratic probing also may not visit every slot. With a prime m and α ≤ ½ a free slot is always found; with m = 8, the keys 0, 8, 16, 24 only ever probe slots 0, 1 and 4, so 24 cannot be placed although five slots are free.

The table after every insertion (offsets 0, 1, 4, 9, 16, 25, … from the home slot 2, so the probed slots are 2, 3, 6, 11 mod 11 = 0, 18 mod 11 = 7, 27 mod 11 = 5, …):

slot:       0   1   2   3   4   5   6   7   8   9  10
+22        22   .   .   .   .   .   .   .   .   .   .     probes 0
+35        22   .  35   .   .   .   .   .   .   .   .     probes 2
+13        22   .  35  13   .   .   .   .   .   .   .     probes 2, 3
+46        22   .  35  13   .   .  46   .   .   .   .     probes 2, 3, 6
+57        22   .  35  13   .   .  46  57   .   .   .     probes 2, 3, 6, 0, 7
+24        22   .  35  13   .  24  46  57   .   .   .     probes 2, 3, 6, 0, 7, 5

Double hashing: the step size comes from a second hash function, try h(k), h(k) + s, h(k) + 2s, … with s = h₂(k). A common choice is h₂(k) = q − (k mod q) for a prime q < m, which is never 0. With q = 7 and the same keys, 46 (s = 3) goes to 5, 57 (s = 6) to 8 and 24 (s = 4) to 6: keys that share a home slot now take different paths, which removes both kinds of clustering. The step must never be 0 and must be coprime with m (again: choose m prime), or some slots are unreachable.

The step sizes are s = 7 − (k mod 7): 13 → 1, 46 → 3, 57 → 6, 24 → 4. The table after every insertion:

slot:       0   1   2   3   4   5   6   7   8   9  10
+22        22   .   .   .   .   .   .   .   .   .   .     probes 0
+35        22   .  35   .   .   .   .   .   .   .   .     probes 2
+13        22   .  35  13   .   .   .   .   .   .   .     step 1: probes 2, 3
+46        22   .  35  13   .  46   .   .   .   .   .     step 3: probes 2, 5
+57        22   .  35  13   .  46   .   .  57   .   .     step 6: probes 2, 8
+24        22   .  35  13   .  46  24   .  57   .   .     step 4: probes 2, 6

Compare the total number of probes for the same six keys: linear 16, quadratic 1 + 1 + 2 + 3 + 5 + 6 = 18 (this input is a worst case for it: every key shares home slot 2), double hashing 1 + 1 + 2 + 2 + 2 + 2 = 10.

Strategy	Probe sequence	Weakness
linear	h, h+1, h+2, …	primary clustering: long runs of full slots
quadratic	h, h+1, h+4, h+9, …	secondary clustering; may miss free slots
double hashing	h, h+s, h+2s, … with s = h₂(k)	needs a second hash; s must be coprime with m

Load factor and performance

In plain words: finding a free parking space is easy when the car park is half empty and very slow when it is 90% full. Open addressing behaves the same way.

For open addressing the expected number of probes explodes as α approaches 1. For linear probing (Knuth's estimates):

α	Successful search ≈ ½(1 + 1/(1−α))	Unsuccessful search ≈ ½(1 + 1/(1−α)²)
0.50	1.5	2.5
0.75	2.5	8.5
0.90	5.5	50.5

That is why implementations fix a maximum load factor (typically 0.5 for linear probing, 0.75 for HashMap's chaining) and grow before reaching it.

Rehashing and its amortized cost

In plain words: when the car park is too full, you build a bigger one and move every car. Each car gets a new space, because the space number depends on the size of the car park. Moving everybody is expensive, but if you double the size each time, it happens so rarely that the average cost per car stays constant — like paying rent every month instead of moving house every week.

To grow, allocate a larger array (about twice as big — HashMap exactly doubles, textbook tables often choose the next prime near 2m) and re-insert every entry. Entries cannot simply be copied to the same index, because the index depends on m: 15 is in bucket 1 when m = 7 but in bucket 0 when m = 15.

Worked example. The chaining table above (m = 7, α = 6/7) is rehashed into m = 17, the first prime after 2 · 7:

Key	old bucket (mod 7)	new bucket (mod 17)
15	1	15
8	1	8
22	1	5
3	3	3
10	3	10
29	1	12

The long chain 15 → 8 → 22 → 29 disappears: every key now has its own bucket, and α drops to 6/17 ≈ 0.35.

One resize costs O(n), but with doubling it happens rarely. Starting from m = 1, the resizes copy 1 + 2 + 4 + … + n/2 < n entries over n insertions — the same argument as for ArrayList's growth — so insertion is O(1) amortized. Growing by a constant (say 10 slots) instead would cost O(n²) in total, O(n) per insertion.

Deletion in open addressing: tombstones

In the linear-probing table above, suppose you delete 13 from slot 3 by setting it to null. A later get(46) starts at slot 2 (35, not it), moves to slot 3, finds it empty and wrongly concludes that 46 is absent — although 46 sits in slot 4. An empty slot means "the probe sequence ends here", so deleting must not create one.

slot:       0   1   2   3   4   5   6
wrong:     22   .  35   .  46  57  24     get(46): 2 → 3 is empty → "not found"  ✗
correct:   22   .  35   †  46  57  24     get(46): 2 → 3 is † (skip) → 4 found   ✓

(† marks the tombstone.)

Instead mark the slot with a tombstone (a special "deleted" marker):

• search: skip tombstones and keep probing; stop only at a truly empty slot;
• insert: a tombstone may be reused for a new key (after checking the key is not further along).

For example, inserting 68 (68 mod 11 = 2) into the "correct" table probes 2, then the tombstone in 3, keeps checking 4, 5, 6 and stops at the empty slot 7 to be sure 68 is not already stored, and then puts 68 into the tombstone slot 3.

Tombstones count towards the probe lengths, so a table with many deletions gets slow; rehashing into a fresh array discards them. Separate chaining has no such problem — you just remove the node from its chain.

Expected O(1) versus worst-case O(n)

In plain words: a hash table is like an express lift that is almost always fast — but if everybody presses the same floor button (all keys in one bucket), it becomes as slow as the stairs.

Operation	Expected (good hash, α bounded)	Worst case
get / contains	O(1)	O(n)
put	O(1) amortized	O(n)
remove	O(1)	O(n)
iterate in key order	not supported (sort first: O(n log n))	—

The worst case happens when many keys share an index: a poor hashCode (for instance one that returns a constant), a table size that matches a pattern in the keys, or keys crafted by an attacker. A balanced tree (TreeMap) is O(log n) guaranteed and keeps keys ordered; a hash table is faster on average but unordered.

Implementing MyHashMap<K,V> with chaining

In plain words: an array of small lists. hashCode tells you which list; equals tells you which entry in that list.

public class MyHashMap<K, V> {
    private static class Entry<K, V> {
        final K key;
        V value;
        Entry(K key, V value) { this.key = key; this.value = value; }
    }

    private LinkedList<Entry<K, V>>[] table;   // one chain per bucket
    private int size;

    private int indexFor(Object key, int m) {
        int h = (key == null) ? 0 : key.hashCode();
        return (h & 0x7fffffff) % m;            // never negative
    }

    public V get(K key) {
        for (Entry<K, V> e : table[indexFor(key, table.length)]) {
            if (e.key == null ? key == null : e.key.equals(key)) return e.value;
        }
        return null;
    }
    // put: search the chain; replace the value if the key is there,
    // otherwise append a new Entry, size++, and resize when size > 0.75 · m
}

Note the two steps: hashCode chooses which chain to look in; equals decides which entry in that chain is the key. (A generic array must be created as new LinkedList[m] with an unchecked cast, because Java cannot create arrays of a parameterised type.)

Here are the missing put and resize methods, following exactly the comment above (tested with the JDK: 20 keys trigger two resizes, 8 → 16 → 32 buckets, and every key is still found afterwards):

public V put(K key, V value) {
    LinkedList<Entry<K, V>> chain = table[indexFor(key, table.length)];
    for (Entry<K, V> e : chain) {
        if (e.key == null ? key == null : e.key.equals(key)) {
            V old = e.value;                // key already there: replace
            e.value = value;
            return old;
        }
    }
    chain.add(new Entry<>(key, value));     // new key: append
    size++;
    if (size > 0.75 * table.length) resize();
    return null;
}

@SuppressWarnings("unchecked")
private void resize() {
    LinkedList<Entry<K, V>>[] old = table;
    table = new LinkedList[old.length * 2];
    for (int i = 0; i < table.length; i++) table[i] = new LinkedList<>();
    for (LinkedList<Entry<K, V>> chain : old) {
        for (Entry<K, V> e : chain) {       // re-insert: the index depends on m
            table[indexFor(e.key, table.length)].add(e);
        }
    }
}

(The constructor creates the first array, for example new LinkedList[8], and fills every slot with an empty LinkedList, so that get never meets a null chain.)

Why equals and hashCode must agree — the implementer's view

In plain words: the coat-check attendant first goes to hook number hashCode, and only then looks at the coats on that hook with equals. If two "equal" coats get different hook numbers, the attendant goes to the wrong hook and never finds your coat.

In the Sets and Maps chapter you learnt the contract as a user: if a.equals(b) then a.hashCode() == b.hashCode(). Now you can see why it is non-negotiable. get only calls equals on the entries of one bucket, the one chosen by the key's hash. If two equal keys had different hash codes, put would store the entry in one bucket and get with an equal key would search a different bucket and return null, and a second put would create a duplicate entry.

You can see it happen with a class that overrides equals but forgets hashCode:

static class Point {
    final int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }
    @Override public boolean equals(Object o) {
        if (!(o instanceof Point)) return false;
        Point p = (Point) o;
        return x == p.x && y == p.y;
    }
    // no hashCode(): Object's version gives (almost always) different codes
}

Map<Point, String> map = new HashMap<>();
map.put(new Point(1, 2), "A");
System.out.println(map.get(new Point(1, 2)));    // null
map.put(new Point(1, 2), "B");
System.out.println(map.size());                  // 2

The fix is one line: @Override public int hashCode() { return Objects.hash(x, y); }.

The converse is not required: unequal keys may share a hash code (that is just a collision). And a key must not change its hash code while it is in the table — mutate a field used by hashCode and the entry is stranded in the wrong bucket.

HashMap in Java

In plain words: HashMap is exactly the chaining table of this chapter, plus a few speed tricks — a power-of-two size, a bit-mixing step, and a small tree for any bucket that becomes crowded.

• The table length is always a power of two (default 16), and the index is hash & (length − 1), a fast replacement for mod. Because that keeps only the low bits, HashMap first spreads the hash code: hash = h ^ (h >>> 16), so the high bits influence the index too.
• Collisions are handled by chaining. The default maximum load factor is 0.75: a new map resizes (doubles) when its size exceeds 16 · 0.75 = 12, i.e. on the 13th put, then again on the 25th, and so on.
• Since Java 8, a bucket that collects more than 8 entries is converted into a small red-black tree (treeification), provided the table has at least 64 buckets (otherwise the table is resized instead). This caps the damage of bad hash codes at O(log n) per bucket for Comparable keys.
• One null key is allowed (it hashes to 0), and iteration order is unspecified — use LinkedHashMap for insertion order or TreeMap for sorted order.

Worked example — where does "cat" go in a new HashMap (16 buckets)? Its hash code is 98262. Spreading: 98262 ^ (98262 >>> 16) = 98262 ^ 1 = 98263. Index: 98263 & 15 = 7 (the last four bits of 98263). So "cat" goes into bucket 7.

Key takeaways

• A hash table computes the index: index = h(k) mod m. With few collisions, put, get and remove are O(1) on average.
• Load factor α = n / m. Keep it bounded (0.75 for HashMap, about 0.5 for linear probing) by resizing; doubling makes resizing O(1) amortized, and every key must be re-hashed into the new array.
• Use a prime m, and never a negative index: Math.floorMod(h, m) or (h & 0x7fffffff) % m.
• Separate chaining: a list per bucket, search cost O(1 + α). Open addressing: one key per slot, follow a probe sequence — linear (primary clustering), quadratic (secondary clustering), double hashing (neither).
• Deleting in open addressing needs tombstones; an empty slot ends a search.
• hashCode chooses the bucket, equals finds the key in it: equal objects must have equal hash codes.
• Worst case is O(n) (all keys in one bucket). TreeMap gives guaranteed O(log n) and sorted keys; HashMap gives faster average time and no order.