14.02Beginner / Intermediate6 topics20 min5 interactive animations

Collision strategies

How hash tables resolve collisions: separate chaining and open addressing with linear probing, quadratic probing, double hashing and tombstones for deletion.

Learning goals

Insert, search and remove with separate chaining
Trace linear, quadratic and double-hash probe sequences
Explain why deletion in open addressing needs tombstones

Prerequisites

Hashing basics

14.02.1

Separate chaining

In **separate chaining** every bucket holds a collection of the entries that hashed to it, usually a linked list. Insert hashes the key, scans the chain for a duplicate and appends. Search and remove hash, then scan only that chain. The table never fills up: a bucket just gets a longer chain, and the load factor (entries per bucket) can exceed 1.

Java's HashMap uses separate chaining. Each chain starts as a linked list and is converted to a balanced tree when it grows long (see worst-case behaviour later in this chapter).

Java

1class ChainedSet {
2    private final LinkedList<Integer>[] table;
3    @SuppressWarnings("unchecked")
4    ChainedSet(int m) { table = new LinkedList[m]; for (int i = 0; i < m; i++) table[i] = new LinkedList<>(); }
5    private int hash(int key) { return Math.floorMod(key, table.length); }
6    boolean add(int key) {
7        LinkedList<Integer> chain = table[hash(key)];
8        if (chain.contains(key)) return false;               // walk the chain: duplicate
9        chain.add(key); return true;
10    }
11    boolean contains(int key) { return table[hash(key)].contains(key); }
12    boolean remove(int key) { return table[hash(key)].remove((Integer) key); }
13}

Best

O(1)

Average

O(1 + n/m)

Worst

O(n)

Space

O(n + m)

Hash table with separate chaining

Interactive · edit the input

bucket 0

∅

bucket 1

∅

bucket 2

∅

bucket 3

∅

bucket 4

∅

Setup

5 empty buckets. A hash function maps every key to a bucket index; keys that land in the same bucket share a chain.

Step 1 / 30

Java

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}

Live state

0 key comparisons

size

load factor

0.00

longest chain

No condition evaluated on this step

Execution trace (dry run table)Show 30 steps

Step	Line	State	What happens
1	L3	size=0 load factor=0.00 longest chain=0	5 empty buckets. A hash function maps every key to a bucket index; keys that land in the same bucket share a chain.
2	L6	size=0 load factor=0.00 longest chain=0 op=add(12) hash=2	add(12): hash = 12 % 5 = 2, so go to bucket 2.
3	L15	size=1 load factor=0.20 longest chain=1 op=add(12) return=true	12 is not in the chain (the bucket was empty): append it to bucket 2.
4	L6	size=1 load factor=0.20 longest chain=1 op=add(7) hash=2	add(7): hash = 7 % 5 = 2, so go to bucket 2.
5	L14	size=1 load factor=0.20 longest chain=1 op=add(7) hash=2	12 ≠ 7: keep walking the chain.
6	L15	size=2 load factor=0.40 longest chain=2 op=add(7) return=true	7 is not in the chain (1 comparison): append it to bucket 2.
7	L6	size=2 load factor=0.40 longest chain=2 op=add(22) hash=2	add(22): hash = 22 % 5 = 2, so go to bucket 2.
8	L14	size=2 load factor=0.40 longest chain=2 op=add(22) hash=2	12 ≠ 22: keep walking the chain.
9	L14	size=2 load factor=0.40 longest chain=2 op=add(22) hash=2	7 ≠ 22: keep walking the chain.
10	L15	size=3 load factor=0.60 longest chain=3 op=add(22) return=true	22 is not in the chain (2 comparisons): append it to bucket 2.
11	L6	size=3 load factor=0.60 longest chain=3 op=add(17) hash=2	add(17): hash = 17 % 5 = 2, so go to bucket 2.
12	L14	size=3 load factor=0.60 longest chain=3 op=add(17) hash=2	12 ≠ 17: keep walking the chain.
13	L14	size=3 load factor=0.60 longest chain=3 op=add(17) hash=2	7 ≠ 17: keep walking the chain.
14	L14	size=3 load factor=0.60 longest chain=3 op=add(17) hash=2	22 ≠ 17: keep walking the chain.
15	L15	size=4 load factor=0.80 longest chain=4 op=add(17) return=true	17 is not in the chain (3 comparisons): append it to bucket 2.
16	L6	size=4 load factor=0.80 longest chain=4 op=contains(22) hash=2	contains(22): hash = 22 % 5 = 2, so go to bucket 2.
17	L17	size=4 load factor=0.80 longest chain=4 op=contains(22) hash=2	12 ≠ 22: keep walking the chain.
18	L17	size=4 load factor=0.80 longest chain=4 op=contains(22) hash=2	7 ≠ 22: keep walking the chain.
19	L17	size=4 load factor=0.80 longest chain=4 op=contains(22) hash=2	22 equals 22: found after 3 comparisons.
20	L17	size=4 load factor=0.80 longest chain=4 op=contains(22) return=true	contains(22) is true.
21	L6	size=4 load factor=0.80 longest chain=4 op=remove(7) hash=2	remove(7): hash = 7 % 5 = 2, so go to bucket 2.
22	L18	size=4 load factor=0.80 longest chain=4 op=remove(7) hash=2	12 ≠ 7: keep walking the chain.
23	L18	size=4 load factor=0.80 longest chain=4 op=remove(7) hash=2	7 equals 7: found after 2 comparisons.
24	L18	size=3 load factor=0.60 longest chain=3 op=remove(7) return=true	7 unlinked from bucket 2.
25	L6	size=3 load factor=0.60 longest chain=3 op=add(32) hash=2	add(32): hash = 32 % 5 = 2, so go to bucket 2.
26	L14	size=3 load factor=0.60 longest chain=3 op=add(32) hash=2	12 ≠ 32: keep walking the chain.
27	L14	size=3 load factor=0.60 longest chain=3 op=add(32) hash=2	22 ≠ 32: keep walking the chain.
28	L14	size=3 load factor=0.60 longest chain=3 op=add(32) hash=2	17 ≠ 32: keep walking the chain.
29	L15	size=4 load factor=0.80 longest chain=4 op=add(32) return=true	32 is not in the chain (3 comparisons): append it to bucket 2.
30	L19	size=4 load factor=0.80 longest chain=4 return=[[],[],[12,22,17,32],[],[]]	4 keys in 5 buckets; the longest chain has 4. Lookup cost is the chain length, so the spread of the hash function decides the speed.

14.02.2

Open addressing

**Open addressing** keeps every entry inside the array itself. If the home slot is taken, a **probe sequence** names the next slot to try, then the next, until an empty slot is found. Search follows the same sequence and stops at the first empty slot (the key cannot be further along) or at the key.

There are no lists and no node objects, which saves memory and keeps data contiguous in the cache. The price: the table can become full, so it must stay well below capacity (load factor under about 0.7), and deletion needs care. The three probe sequences below differ only in how the *i*-th slot is computed.

Probe sequence	i-th slot	Main weakness
Linear	(h + i) % m	Primary clustering: runs of full slots grow
Quadratic	(h + i²) % m	Secondary clustering; may not reach every slot
Double hashing	(h1 + i · h2) % m	Needs a second hash that is never 0

14.02.3

Linear probing

Linear probing tries h, h+1, h+2, … modulo m. It is the simplest scheme and very cache-friendly, but full slots form clusters: a key hashing into a cluster must walk to its end and then extends it, so clusters grow faster than the load factor suggests.

Run the “Linear probing” preset: 10, 20 and 30 all hash to slot 0 of a 5-slot table, so they take slots 0, 1 and 2. The search for 30 then probes three slots. Try “Table fills up” to see insert fail when no slot is free.

Java

1static int linearSlot(int key, int i, int m) {
2    return (Math.floorMod(key, m) + i) % m;          // home slot, then one step further each time
3}

Open addressing: linear, quadratic and double hashing with tombstones

Interactive · edit the input

table[5]

Setup

An array of 5 slots, all empty. A key goes to its home slot; if that is taken, the probe sequence names the next slot to try. Linear: one step further each time.

Step 1 / 38

Java

1static final int EMPTY = -1, TOMBSTONE = -2;
2int[] table;     // length m, filled with EMPTY; mode 0 linear, 1 quadratic, 2 double hashing
3int slot(int key, int i) {                                    // the i-th slot to try
4    int h1 = Math.floorMod(key, m);
5    if (mode == 0) return (h1 + i) % m;                        // linear
6    if (mode == 1) return (h1 + i * i) % m;                    // quadratic
7    int h2 = 1 + Math.floorMod(key, m - 1);                    // double hashing: the step is never 0
8    return (h1 + i * h2) % m;
9}
10boolean insert(int key) {
11    int firstFree = -1;                                        // first tombstone seen on the way
12    for (int i = 0; i < m; i++) {
13        int s = slot(key, i);
14        if (table[s] == key) return false;                     // duplicate
15        if (table[s] == TOMBSTONE && firstFree < 0) firstFree = s;
16        if (table[s] == EMPTY) { table[firstFree >= 0 ? firstFree : s] = key; return true; }
17    }
18    if (firstFree >= 0) { table[firstFree] = key; return true; }
19    return false;                                              // no free slot: the table is full
20}
21boolean contains(int key) {
22    for (int i = 0; i < m; i++) {
23        int s = slot(key, i);
24        if (table[s] == EMPTY) return false;                   // an empty slot ends the search
25        if (table[s] == key) return true;                      // tombstones are stepped over
26    }
27    return false;
28}
29boolean remove(int key) {
30    for (int i = 0; i < m; i++) {
31        int s = slot(key, i);
32        if (table[s] == EMPTY) return false;
33        if (table[s] == key) { table[s] = TOMBSTONE; return true; }   // leave a marker, not a hole
34    }
35    return false;
36}

Live state

0 probes

keys

tombstones

No condition evaluated on this step

Execution trace (dry run table)Show 38 steps

Step	Line	State	What happens
1	L2	keys=0 tombstones=0	An array of 5 slots, all empty. A key goes to its home slot; if that is taken, the probe sequence names the next slot to try. Linear: one step further each time.
2	L13	keys=0 tombstones=0 op=insert(10) i=0 slot=0	insert(10), probe 0: slot = (0 + 0) % 5 = 0.
3	L16	keys=1 tombstones=0 op=insert(10) return=true	Slot 0 is empty, so 10 is not in the table. Store it in slot 0.
4	L13	keys=1 tombstones=0 op=insert(20) i=0 slot=0	insert(20), probe 0: slot = (0 + 0) % 5 = 0.
5	L15	keys=1 tombstones=0 op=insert(20) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
6	L13	keys=1 tombstones=0 op=insert(20) i=1 slot=1	insert(20), probe 1: slot = (0 + 1) % 5 = 1.
7	L16	keys=2 tombstones=0 op=insert(20) return=true	Slot 1 is empty, so 20 is not in the table. Store it in slot 1.
8	L13	keys=2 tombstones=0 op=insert(30) i=0 slot=0	insert(30), probe 0: slot = (0 + 0) % 5 = 0.
9	L15	keys=2 tombstones=0 op=insert(30) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
10	L13	keys=2 tombstones=0 op=insert(30) i=1 slot=1	insert(30), probe 1: slot = (0 + 1) % 5 = 1.
11	L15	keys=2 tombstones=0 op=insert(30) i=1	Slot 1 holds 20, a different key (a collision): try the next slot in the sequence.
12	L13	keys=2 tombstones=0 op=insert(30) i=2 slot=2	insert(30), probe 2: slot = (0 + 2) % 5 = 2.
13	L16	keys=3 tombstones=0 op=insert(30) return=true	Slot 2 is empty, so 30 is not in the table. Store it in slot 2.
14	L23	keys=3 tombstones=0 op=contains(30) i=0 slot=0	contains(30), probe 0: slot = (0 + 0) % 5 = 0.
15	L25	keys=3 tombstones=0 op=contains(30) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
16	L23	keys=3 tombstones=0 op=contains(30) i=1 slot=1	contains(30), probe 1: slot = (0 + 1) % 5 = 1.
17	L25	keys=3 tombstones=0 op=contains(30) i=1	Slot 1 holds 20, a different key (a collision): try the next slot in the sequence.
18	L23	keys=3 tombstones=0 op=contains(30) i=2 slot=2	contains(30), probe 2: slot = (0 + 2) % 5 = 2.
19	L25	keys=3 tombstones=0 op=contains(30) return=true	table[2] = 30: found after 3 probes.
20	L31	keys=3 tombstones=0 op=remove(20) i=0 slot=0	remove(20), probe 0: slot = (0 + 0) % 5 = 0.
21	L33	keys=3 tombstones=0 op=remove(20) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
22	L31	keys=3 tombstones=0 op=remove(20) i=1 slot=1	remove(20), probe 1: slot = (0 + 1) % 5 = 1.
23	L33	keys=2 tombstones=1 op=remove(20) return=true	table[1] becomes a tombstone ✗, not an empty slot: other keys' probe sequences may pass through here.
24	L23	keys=2 tombstones=1 op=contains(30) i=0 slot=0	contains(30), probe 0: slot = (0 + 0) % 5 = 0.
25	L25	keys=2 tombstones=1 op=contains(30) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
26	L23	keys=2 tombstones=1 op=contains(30) i=1 slot=1	contains(30), probe 1: slot = (0 + 1) % 5 = 1.
27	L25	keys=2 tombstones=1 op=contains(30) i=1	Slot 1 holds a tombstone: step over it and keep probing.
28	L23	keys=2 tombstones=1 op=contains(30) i=2 slot=2	contains(30), probe 2: slot = (0 + 2) % 5 = 2.
29	L25	keys=2 tombstones=1 op=contains(30) return=true	table[2] = 30: found after 3 probes.
30	L13	keys=2 tombstones=1 op=insert(25) i=0 slot=0	insert(25), probe 0: slot = (0 + 0) % 5 = 0.
31	L15	keys=2 tombstones=1 op=insert(25) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
32	L13	keys=2 tombstones=1 op=insert(25) i=1 slot=1	insert(25), probe 1: slot = (0 + 1) % 5 = 1.
33	L15	keys=2 tombstones=1 op=insert(25) i=1	Slot 1 holds a tombstone: remember it as reusable, but keep probing in case 25 is stored further along.
34	L13	keys=2 tombstones=1 op=insert(25) i=2 slot=2	insert(25), probe 2: slot = (0 + 2) % 5 = 2.
35	L15	keys=2 tombstones=1 op=insert(25) i=2	Slot 2 holds 30, a different key (a collision): try the next slot in the sequence.
36	L13	keys=2 tombstones=1 op=insert(25) i=3 slot=3	insert(25), probe 3: slot = (0 + 3) % 5 = 3.
37	L16	keys=3 tombstones=0 op=insert(25) return=true	Slot 3 is empty, so 25 is not in the table. Store it in slot 1 (the first tombstone passed on the way, reused).
38	L36	keys=3 tombstones=0 return=[10, 25, 30, _, _]	Final table: [10, 25, 30, _, _] (_ empty, x tombstone). 18 probes in total.

14.02.4

Quadratic probing

Quadratic probing tries h, h+1, h+4, h+9, … Jumps grow, so colliding keys no longer pile up in one contiguous block. If the table size is prime and at most half full, the sequence is guaranteed to find a free slot. With other sizes it may cycle through a subset of slots and miss free ones.

Choose “Quadratic probing” in the animation: 3, 10, 17 and 24 all hash to slot 3 of a 7-slot table. Key 10 steps to slot 4 (3 + 1), key 17 to slot 0 (3 + 4 = 7, wrapped) and key 24 to slot 5 (3 + 9 = 12, wrapped).

Open addressing: linear, quadratic and double hashing with tombstones

Interactive · edit the input

table[5]

Setup

An array of 5 slots, all empty. A key goes to its home slot; if that is taken, the probe sequence names the next slot to try. Linear: one step further each time.

Step 1 / 38

Java

1static final int EMPTY = -1, TOMBSTONE = -2;
2int[] table;     // length m, filled with EMPTY; mode 0 linear, 1 quadratic, 2 double hashing
3int slot(int key, int i) {                                    // the i-th slot to try
4    int h1 = Math.floorMod(key, m);
5    if (mode == 0) return (h1 + i) % m;                        // linear
6    if (mode == 1) return (h1 + i * i) % m;                    // quadratic
7    int h2 = 1 + Math.floorMod(key, m - 1);                    // double hashing: the step is never 0
8    return (h1 + i * h2) % m;
9}
10boolean insert(int key) {
11    int firstFree = -1;                                        // first tombstone seen on the way
12    for (int i = 0; i < m; i++) {
13        int s = slot(key, i);
14        if (table[s] == key) return false;                     // duplicate
15        if (table[s] == TOMBSTONE && firstFree < 0) firstFree = s;
16        if (table[s] == EMPTY) { table[firstFree >= 0 ? firstFree : s] = key; return true; }
17    }
18    if (firstFree >= 0) { table[firstFree] = key; return true; }
19    return false;                                              // no free slot: the table is full
20}
21boolean contains(int key) {
22    for (int i = 0; i < m; i++) {
23        int s = slot(key, i);
24        if (table[s] == EMPTY) return false;                   // an empty slot ends the search
25        if (table[s] == key) return true;                      // tombstones are stepped over
26    }
27    return false;
28}
29boolean remove(int key) {
30    for (int i = 0; i < m; i++) {
31        int s = slot(key, i);
32        if (table[s] == EMPTY) return false;
33        if (table[s] == key) { table[s] = TOMBSTONE; return true; }   // leave a marker, not a hole
34    }
35    return false;
36}

Live state

0 probes

keys

tombstones

No condition evaluated on this step

Execution trace (dry run table)Show 38 steps

Step	Line	State	What happens
1	L2	keys=0 tombstones=0	An array of 5 slots, all empty. A key goes to its home slot; if that is taken, the probe sequence names the next slot to try. Linear: one step further each time.
2	L13	keys=0 tombstones=0 op=insert(10) i=0 slot=0	insert(10), probe 0: slot = (0 + 0) % 5 = 0.
3	L16	keys=1 tombstones=0 op=insert(10) return=true	Slot 0 is empty, so 10 is not in the table. Store it in slot 0.
4	L13	keys=1 tombstones=0 op=insert(20) i=0 slot=0	insert(20), probe 0: slot = (0 + 0) % 5 = 0.
5	L15	keys=1 tombstones=0 op=insert(20) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
6	L13	keys=1 tombstones=0 op=insert(20) i=1 slot=1	insert(20), probe 1: slot = (0 + 1) % 5 = 1.
7	L16	keys=2 tombstones=0 op=insert(20) return=true	Slot 1 is empty, so 20 is not in the table. Store it in slot 1.
8	L13	keys=2 tombstones=0 op=insert(30) i=0 slot=0	insert(30), probe 0: slot = (0 + 0) % 5 = 0.
9	L15	keys=2 tombstones=0 op=insert(30) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
10	L13	keys=2 tombstones=0 op=insert(30) i=1 slot=1	insert(30), probe 1: slot = (0 + 1) % 5 = 1.
11	L15	keys=2 tombstones=0 op=insert(30) i=1	Slot 1 holds 20, a different key (a collision): try the next slot in the sequence.
12	L13	keys=2 tombstones=0 op=insert(30) i=2 slot=2	insert(30), probe 2: slot = (0 + 2) % 5 = 2.
13	L16	keys=3 tombstones=0 op=insert(30) return=true	Slot 2 is empty, so 30 is not in the table. Store it in slot 2.
14	L23	keys=3 tombstones=0 op=contains(30) i=0 slot=0	contains(30), probe 0: slot = (0 + 0) % 5 = 0.
15	L25	keys=3 tombstones=0 op=contains(30) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
16	L23	keys=3 tombstones=0 op=contains(30) i=1 slot=1	contains(30), probe 1: slot = (0 + 1) % 5 = 1.
17	L25	keys=3 tombstones=0 op=contains(30) i=1	Slot 1 holds 20, a different key (a collision): try the next slot in the sequence.
18	L23	keys=3 tombstones=0 op=contains(30) i=2 slot=2	contains(30), probe 2: slot = (0 + 2) % 5 = 2.
19	L25	keys=3 tombstones=0 op=contains(30) return=true	table[2] = 30: found after 3 probes.
20	L31	keys=3 tombstones=0 op=remove(20) i=0 slot=0	remove(20), probe 0: slot = (0 + 0) % 5 = 0.
21	L33	keys=3 tombstones=0 op=remove(20) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
22	L31	keys=3 tombstones=0 op=remove(20) i=1 slot=1	remove(20), probe 1: slot = (0 + 1) % 5 = 1.
23	L33	keys=2 tombstones=1 op=remove(20) return=true	table[1] becomes a tombstone ✗, not an empty slot: other keys' probe sequences may pass through here.
24	L23	keys=2 tombstones=1 op=contains(30) i=0 slot=0	contains(30), probe 0: slot = (0 + 0) % 5 = 0.
25	L25	keys=2 tombstones=1 op=contains(30) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
26	L23	keys=2 tombstones=1 op=contains(30) i=1 slot=1	contains(30), probe 1: slot = (0 + 1) % 5 = 1.
27	L25	keys=2 tombstones=1 op=contains(30) i=1	Slot 1 holds a tombstone: step over it and keep probing.
28	L23	keys=2 tombstones=1 op=contains(30) i=2 slot=2	contains(30), probe 2: slot = (0 + 2) % 5 = 2.
29	L25	keys=2 tombstones=1 op=contains(30) return=true	table[2] = 30: found after 3 probes.
30	L13	keys=2 tombstones=1 op=insert(25) i=0 slot=0	insert(25), probe 0: slot = (0 + 0) % 5 = 0.
31	L15	keys=2 tombstones=1 op=insert(25) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
32	L13	keys=2 tombstones=1 op=insert(25) i=1 slot=1	insert(25), probe 1: slot = (0 + 1) % 5 = 1.
33	L15	keys=2 tombstones=1 op=insert(25) i=1	Slot 1 holds a tombstone: remember it as reusable, but keep probing in case 25 is stored further along.
34	L13	keys=2 tombstones=1 op=insert(25) i=2 slot=2	insert(25), probe 2: slot = (0 + 2) % 5 = 2.
35	L15	keys=2 tombstones=1 op=insert(25) i=2	Slot 2 holds 30, a different key (a collision): try the next slot in the sequence.
36	L13	keys=2 tombstones=1 op=insert(25) i=3 slot=3	insert(25), probe 3: slot = (0 + 3) % 5 = 3.
37	L16	keys=3 tombstones=0 op=insert(25) return=true	Slot 3 is empty, so 25 is not in the table. Store it in slot 1 (the first tombstone passed on the way, reused).
38	L36	keys=3 tombstones=0 return=[10, 25, 30, _, _]	Final table: [10, 25, 30, _, _] (_ empty, x tombstone). 18 probes in total.

14.02.5

Double hashing

Double hashing uses a second hash function to set the **step size**: slot i is (h1 + i * h2) % m with h2 = 1 + key % (m - 1), which is never 0. Two keys with the same home slot usually have different steps, so they follow different paths. If m is prime every step size reaches every slot.

Select “Double hashing” in the animation with the same keys 3, 10, 17 and 24: they all collide at slot 3, but their steps are 1 + key % 6 = 5, 6 and 1 for 10, 17 and 24, so they end in slots 1, 2 and 4 instead of following one path.

Java

1static int doubleHashSlot(int key, int i, int m) {                  // m prime
2    int h1 = Math.floorMod(key, m);
3    int h2 = 1 + Math.floorMod(key, m - 1);                          // never 0
4    return (h1 + i * h2) % m;
5}

Open addressing: linear, quadratic and double hashing with tombstones

Interactive · edit the input

table[5]

Setup

An array of 5 slots, all empty. A key goes to its home slot; if that is taken, the probe sequence names the next slot to try. Linear: one step further each time.

Step 1 / 38

Java

1static final int EMPTY = -1, TOMBSTONE = -2;
2int[] table;     // length m, filled with EMPTY; mode 0 linear, 1 quadratic, 2 double hashing
3int slot(int key, int i) {                                    // the i-th slot to try
4    int h1 = Math.floorMod(key, m);
5    if (mode == 0) return (h1 + i) % m;                        // linear
6    if (mode == 1) return (h1 + i * i) % m;                    // quadratic
7    int h2 = 1 + Math.floorMod(key, m - 1);                    // double hashing: the step is never 0
8    return (h1 + i * h2) % m;
9}
10boolean insert(int key) {
11    int firstFree = -1;                                        // first tombstone seen on the way
12    for (int i = 0; i < m; i++) {
13        int s = slot(key, i);
14        if (table[s] == key) return false;                     // duplicate
15        if (table[s] == TOMBSTONE && firstFree < 0) firstFree = s;
16        if (table[s] == EMPTY) { table[firstFree >= 0 ? firstFree : s] = key; return true; }
17    }
18    if (firstFree >= 0) { table[firstFree] = key; return true; }
19    return false;                                              // no free slot: the table is full
20}
21boolean contains(int key) {
22    for (int i = 0; i < m; i++) {
23        int s = slot(key, i);
24        if (table[s] == EMPTY) return false;                   // an empty slot ends the search
25        if (table[s] == key) return true;                      // tombstones are stepped over
26    }
27    return false;
28}
29boolean remove(int key) {
30    for (int i = 0; i < m; i++) {
31        int s = slot(key, i);
32        if (table[s] == EMPTY) return false;
33        if (table[s] == key) { table[s] = TOMBSTONE; return true; }   // leave a marker, not a hole
34    }
35    return false;
36}

Live state

0 probes

keys

tombstones

No condition evaluated on this step

Execution trace (dry run table)Show 38 steps

Step	Line	State	What happens
1	L2	keys=0 tombstones=0	An array of 5 slots, all empty. A key goes to its home slot; if that is taken, the probe sequence names the next slot to try. Linear: one step further each time.
2	L13	keys=0 tombstones=0 op=insert(10) i=0 slot=0	insert(10), probe 0: slot = (0 + 0) % 5 = 0.
3	L16	keys=1 tombstones=0 op=insert(10) return=true	Slot 0 is empty, so 10 is not in the table. Store it in slot 0.
4	L13	keys=1 tombstones=0 op=insert(20) i=0 slot=0	insert(20), probe 0: slot = (0 + 0) % 5 = 0.
5	L15	keys=1 tombstones=0 op=insert(20) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
6	L13	keys=1 tombstones=0 op=insert(20) i=1 slot=1	insert(20), probe 1: slot = (0 + 1) % 5 = 1.
7	L16	keys=2 tombstones=0 op=insert(20) return=true	Slot 1 is empty, so 20 is not in the table. Store it in slot 1.
8	L13	keys=2 tombstones=0 op=insert(30) i=0 slot=0	insert(30), probe 0: slot = (0 + 0) % 5 = 0.
9	L15	keys=2 tombstones=0 op=insert(30) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
10	L13	keys=2 tombstones=0 op=insert(30) i=1 slot=1	insert(30), probe 1: slot = (0 + 1) % 5 = 1.
11	L15	keys=2 tombstones=0 op=insert(30) i=1	Slot 1 holds 20, a different key (a collision): try the next slot in the sequence.
12	L13	keys=2 tombstones=0 op=insert(30) i=2 slot=2	insert(30), probe 2: slot = (0 + 2) % 5 = 2.
13	L16	keys=3 tombstones=0 op=insert(30) return=true	Slot 2 is empty, so 30 is not in the table. Store it in slot 2.
14	L23	keys=3 tombstones=0 op=contains(30) i=0 slot=0	contains(30), probe 0: slot = (0 + 0) % 5 = 0.
15	L25	keys=3 tombstones=0 op=contains(30) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
16	L23	keys=3 tombstones=0 op=contains(30) i=1 slot=1	contains(30), probe 1: slot = (0 + 1) % 5 = 1.
17	L25	keys=3 tombstones=0 op=contains(30) i=1	Slot 1 holds 20, a different key (a collision): try the next slot in the sequence.
18	L23	keys=3 tombstones=0 op=contains(30) i=2 slot=2	contains(30), probe 2: slot = (0 + 2) % 5 = 2.
19	L25	keys=3 tombstones=0 op=contains(30) return=true	table[2] = 30: found after 3 probes.
20	L31	keys=3 tombstones=0 op=remove(20) i=0 slot=0	remove(20), probe 0: slot = (0 + 0) % 5 = 0.
21	L33	keys=3 tombstones=0 op=remove(20) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
22	L31	keys=3 tombstones=0 op=remove(20) i=1 slot=1	remove(20), probe 1: slot = (0 + 1) % 5 = 1.
23	L33	keys=2 tombstones=1 op=remove(20) return=true	table[1] becomes a tombstone ✗, not an empty slot: other keys' probe sequences may pass through here.
24	L23	keys=2 tombstones=1 op=contains(30) i=0 slot=0	contains(30), probe 0: slot = (0 + 0) % 5 = 0.
25	L25	keys=2 tombstones=1 op=contains(30) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
26	L23	keys=2 tombstones=1 op=contains(30) i=1 slot=1	contains(30), probe 1: slot = (0 + 1) % 5 = 1.
27	L25	keys=2 tombstones=1 op=contains(30) i=1	Slot 1 holds a tombstone: step over it and keep probing.
28	L23	keys=2 tombstones=1 op=contains(30) i=2 slot=2	contains(30), probe 2: slot = (0 + 2) % 5 = 2.
29	L25	keys=2 tombstones=1 op=contains(30) return=true	table[2] = 30: found after 3 probes.
30	L13	keys=2 tombstones=1 op=insert(25) i=0 slot=0	insert(25), probe 0: slot = (0 + 0) % 5 = 0.
31	L15	keys=2 tombstones=1 op=insert(25) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
32	L13	keys=2 tombstones=1 op=insert(25) i=1 slot=1	insert(25), probe 1: slot = (0 + 1) % 5 = 1.
33	L15	keys=2 tombstones=1 op=insert(25) i=1	Slot 1 holds a tombstone: remember it as reusable, but keep probing in case 25 is stored further along.
34	L13	keys=2 tombstones=1 op=insert(25) i=2 slot=2	insert(25), probe 2: slot = (0 + 2) % 5 = 2.
35	L15	keys=2 tombstones=1 op=insert(25) i=2	Slot 2 holds 30, a different key (a collision): try the next slot in the sequence.
36	L13	keys=2 tombstones=1 op=insert(25) i=3 slot=3	insert(25), probe 3: slot = (0 + 3) % 5 = 3.
37	L16	keys=3 tombstones=0 op=insert(25) return=true	Slot 3 is empty, so 25 is not in the table. Store it in slot 1 (the first tombstone passed on the way, reused).
38	L36	keys=3 tombstones=0 return=[10, 25, 30, _, _]	Final table: [10, 25, 30, _, _] (_ empty, x tombstone). 18 probes in total.

14.02.6

Tombstones

Removing a key from an open-addressed table by emptying its slot breaks later searches: a key that was stored *beyond* that slot because of a collision is now unreachable, since search stops at the first empty slot. The fix is a **tombstone**, a marker that means “was occupied”. Search steps over tombstones; insert may reuse the first tombstone it passed (after making sure the key is not stored further on).

Run “Tombstones keep searches working”: 3, 8 and 13 all hash to slot 3 in a table of 5, so they sit in slots 3, 4 and 0. Removing 8 leaves a tombstone ✗, and ?13 still finds 13 behind it. Too many tombstones slow searches down, so real tables rebuild themselves when they accumulate.

Open addressing: linear, quadratic and double hashing with tombstones

Interactive · edit the input

table[5]

Setup

An array of 5 slots, all empty. A key goes to its home slot; if that is taken, the probe sequence names the next slot to try. Linear: one step further each time.

Step 1 / 38

Java

1static final int EMPTY = -1, TOMBSTONE = -2;
2int[] table;     // length m, filled with EMPTY; mode 0 linear, 1 quadratic, 2 double hashing
3int slot(int key, int i) {                                    // the i-th slot to try
4    int h1 = Math.floorMod(key, m);
5    if (mode == 0) return (h1 + i) % m;                        // linear
6    if (mode == 1) return (h1 + i * i) % m;                    // quadratic
7    int h2 = 1 + Math.floorMod(key, m - 1);                    // double hashing: the step is never 0
8    return (h1 + i * h2) % m;
9}
10boolean insert(int key) {
11    int firstFree = -1;                                        // first tombstone seen on the way
12    for (int i = 0; i < m; i++) {
13        int s = slot(key, i);
14        if (table[s] == key) return false;                     // duplicate
15        if (table[s] == TOMBSTONE && firstFree < 0) firstFree = s;
16        if (table[s] == EMPTY) { table[firstFree >= 0 ? firstFree : s] = key; return true; }
17    }
18    if (firstFree >= 0) { table[firstFree] = key; return true; }
19    return false;                                              // no free slot: the table is full
20}
21boolean contains(int key) {
22    for (int i = 0; i < m; i++) {
23        int s = slot(key, i);
24        if (table[s] == EMPTY) return false;                   // an empty slot ends the search
25        if (table[s] == key) return true;                      // tombstones are stepped over
26    }
27    return false;
28}
29boolean remove(int key) {
30    for (int i = 0; i < m; i++) {
31        int s = slot(key, i);
32        if (table[s] == EMPTY) return false;
33        if (table[s] == key) { table[s] = TOMBSTONE; return true; }   // leave a marker, not a hole
34    }
35    return false;
36}

Live state

0 probes

keys

tombstones

No condition evaluated on this step

Execution trace (dry run table)Show 38 steps

Step	Line	State	What happens
1	L2	keys=0 tombstones=0	An array of 5 slots, all empty. A key goes to its home slot; if that is taken, the probe sequence names the next slot to try. Linear: one step further each time.
2	L13	keys=0 tombstones=0 op=insert(10) i=0 slot=0	insert(10), probe 0: slot = (0 + 0) % 5 = 0.
3	L16	keys=1 tombstones=0 op=insert(10) return=true	Slot 0 is empty, so 10 is not in the table. Store it in slot 0.
4	L13	keys=1 tombstones=0 op=insert(20) i=0 slot=0	insert(20), probe 0: slot = (0 + 0) % 5 = 0.
5	L15	keys=1 tombstones=0 op=insert(20) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
6	L13	keys=1 tombstones=0 op=insert(20) i=1 slot=1	insert(20), probe 1: slot = (0 + 1) % 5 = 1.
7	L16	keys=2 tombstones=0 op=insert(20) return=true	Slot 1 is empty, so 20 is not in the table. Store it in slot 1.
8	L13	keys=2 tombstones=0 op=insert(30) i=0 slot=0	insert(30), probe 0: slot = (0 + 0) % 5 = 0.
9	L15	keys=2 tombstones=0 op=insert(30) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
10	L13	keys=2 tombstones=0 op=insert(30) i=1 slot=1	insert(30), probe 1: slot = (0 + 1) % 5 = 1.
11	L15	keys=2 tombstones=0 op=insert(30) i=1	Slot 1 holds 20, a different key (a collision): try the next slot in the sequence.
12	L13	keys=2 tombstones=0 op=insert(30) i=2 slot=2	insert(30), probe 2: slot = (0 + 2) % 5 = 2.
13	L16	keys=3 tombstones=0 op=insert(30) return=true	Slot 2 is empty, so 30 is not in the table. Store it in slot 2.
14	L23	keys=3 tombstones=0 op=contains(30) i=0 slot=0	contains(30), probe 0: slot = (0 + 0) % 5 = 0.
15	L25	keys=3 tombstones=0 op=contains(30) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
16	L23	keys=3 tombstones=0 op=contains(30) i=1 slot=1	contains(30), probe 1: slot = (0 + 1) % 5 = 1.
17	L25	keys=3 tombstones=0 op=contains(30) i=1	Slot 1 holds 20, a different key (a collision): try the next slot in the sequence.
18	L23	keys=3 tombstones=0 op=contains(30) i=2 slot=2	contains(30), probe 2: slot = (0 + 2) % 5 = 2.
19	L25	keys=3 tombstones=0 op=contains(30) return=true	table[2] = 30: found after 3 probes.
20	L31	keys=3 tombstones=0 op=remove(20) i=0 slot=0	remove(20), probe 0: slot = (0 + 0) % 5 = 0.
21	L33	keys=3 tombstones=0 op=remove(20) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
22	L31	keys=3 tombstones=0 op=remove(20) i=1 slot=1	remove(20), probe 1: slot = (0 + 1) % 5 = 1.
23	L33	keys=2 tombstones=1 op=remove(20) return=true	table[1] becomes a tombstone ✗, not an empty slot: other keys' probe sequences may pass through here.
24	L23	keys=2 tombstones=1 op=contains(30) i=0 slot=0	contains(30), probe 0: slot = (0 + 0) % 5 = 0.
25	L25	keys=2 tombstones=1 op=contains(30) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
26	L23	keys=2 tombstones=1 op=contains(30) i=1 slot=1	contains(30), probe 1: slot = (0 + 1) % 5 = 1.
27	L25	keys=2 tombstones=1 op=contains(30) i=1	Slot 1 holds a tombstone: step over it and keep probing.
28	L23	keys=2 tombstones=1 op=contains(30) i=2 slot=2	contains(30), probe 2: slot = (0 + 2) % 5 = 2.
29	L25	keys=2 tombstones=1 op=contains(30) return=true	table[2] = 30: found after 3 probes.
30	L13	keys=2 tombstones=1 op=insert(25) i=0 slot=0	insert(25), probe 0: slot = (0 + 0) % 5 = 0.
31	L15	keys=2 tombstones=1 op=insert(25) i=0	Slot 0 holds 10, a different key (a collision): try the next slot in the sequence.
32	L13	keys=2 tombstones=1 op=insert(25) i=1 slot=1	insert(25), probe 1: slot = (0 + 1) % 5 = 1.
33	L15	keys=2 tombstones=1 op=insert(25) i=1	Slot 1 holds a tombstone: remember it as reusable, but keep probing in case 25 is stored further along.
34	L13	keys=2 tombstones=1 op=insert(25) i=2 slot=2	insert(25), probe 2: slot = (0 + 2) % 5 = 2.
35	L15	keys=2 tombstones=1 op=insert(25) i=2	Slot 2 holds 30, a different key (a collision): try the next slot in the sequence.
36	L13	keys=2 tombstones=1 op=insert(25) i=3 slot=3	insert(25), probe 3: slot = (0 + 3) % 5 = 3.
37	L16	keys=3 tombstones=0 op=insert(25) return=true	Slot 3 is empty, so 25 is not in the table. Store it in slot 1 (the first tombstone passed on the way, reused).
38	L36	keys=3 tombstones=0 return=[10, 25, 30, _, _]	Final table: [10, 25, 30, _, _] (_ empty, x tombstone). 18 probes in total.

Practice ladder

Now try it yourself

Easy

Insert 12, 7, 22, 17 into 5 chained buckets with key % 5
Insert 10, 20, 30 into a 5-slot table with linear probing

Medium

Design HashMap
Explain why open addressing cannot exceed load factor 1

Advanced

Implement open addressing with deletion and tombstone cleanup on resize

Key takeaways

Chaining stores colliding keys in a list per bucket; open addressing probes for another slot.
Linear, quadratic and double hashing differ only in the probe sequence.
Deleting in open addressing needs tombstones so later searches are not cut short.