The same eight keys as in linear probing, but a key that collides now jumps further each time: 1 slot, then 4, then 9. Watch 81 escape the block.
Jumping further to find a seat
The same eight keys, probing 1, 4, 9 slots on
#define M 11 #ifndef KEYS#define KEYS 8#endif enum state { EMPTY, FULL, DELETED }; struct slot { int key; enum state state;}; static struct slot table[M];static int probes = 0; bool put(int key){ int target = -1; for (int i = 0; i < M; i++) { int s = (key % M + i * i) % M; probes++; if (table[s].state == FULL && table[s].key == key) return true; if (table[s].state == DELETED && target < 0) target = s; if (table[s].state == EMPTY) { if (target < 0) target = s; break; } } if (target < 0) return false; table[target].key = key; table[target].state = FULL; return true;} int find(int key){ for (int i = 0; i < M; i++) { int s = (key % M + i * i) % M; probes++; if (table[s].state == EMPTY) return -1; if (table[s].state == FULL && table[s].key == key) return s; } return -1;} void remove_key(int key){ int s = find(key); if (s >= 0) table[s].state = DELETED;} int main(void){ const int keys[9] = { 26, 37, 5, 59, 16, 72, 81, 9, 15 }; for (int i = 0; i < KEYS; i++) { probes = 0; put(keys[i]); printf("put %d: %d probes\n", keys[i], probes); } probes = 0; int a = find(48); printf("find 48: %d after %d probes\n", a, probes); remove_key(37); probes = 0; int b = find(59); printf("find 59: slot %d after %d probes\n", b, probes); return 0;}main has started: an empty table of 11 slots.
- key
- –
- probes
- 0
- α
- 0.00
Output
Describe this picture
A row of eleven slots, numbered 0 to 10, named struct slot table[11], with the code beside them, the line about to run marked. The clip takes about 32 seconds. The keys 26, 37, 5, 59, 16, 72, 81 and 9 are put in turn, each starting at its home slot, the key mod 11. A marker s stands on each slot probed; a taken slot is marked, and an arc joins it to the slot tried next, the arcs growing longer: 59, home 4, tries 4, then 5, then 8. 81, also home 4, follows exactly the same jumps, then one more of 9 slots, which wraps round to slot 2, outside the block of full slots. At the end slot 2 holds 81, slots 4 to 10 hold 26, 37, 5, 72, 59, 16 and 9, and slots 0, 1 and 3 are empty. Then the search for 48 jumps among slots 4, 5, 8, 2, 9 and 7 and gives up after 11 probes without ever reaching an empty slot. 37 is removed, leaving “del” in slot 5, and the search for 59 passes it and finds 59 in slot 8 after 3 probes. Under the picture are one sentence on the current step and the readouts “key”, “probes” and “α”. The transport plays and pauses, steps one beat back or forward, and scrubs; a paused step is kept in the page address as quadratic-probing.step.
Jumping further
Linear probing’s trouble is that a cluster catches every key whose home falls in it. Quadratic probing jumps over it: probe i goes i² slots from home,
so a key tries its home, then 1, 4, 9, 16, … slots on, wrapping round. Keys with nearby homes soon take different paths, and long runs of full slots break up.
The code and its cost
The program is linear probing’s with two edits. In both put and find, the probe slot becomes
int s = (key % M + i * i) % M;and the keys gain a ninth, 15, which main puts only when built with -DKEYS=9:
const int keys[9] = { 26, 37, 5, 59, 16, 72, 81, 9, 15 };With the eight keys:
| Key | 26 | 37 | 5 | 59 | 16 | 72 | 81 | 9 |
|---|---|---|---|---|---|---|---|---|
| Probes, quadratic | 1 | 2 | 2 | 3 | 3 | 2 | 4 | 2 |
| Probes, linear | 1 | 2 | 2 | 4 | 4 | 4 | 7 | 3 |
| Slot | 4 | 5 | 6 | 8 | 9 | 7 | 2 | 10 |
19 probes in all, against linear probing’s 27. 81 goes 4, 5, 8, then 4 + 9 = 13, which is slot 2.
Secondary clustering
The four keys with home 4 (26, 37, 59 and 81) still follow one path: 4, 5, 8, 2, … Each takes one more step along it than the one before. Keys with the same home share their whole probe sequence, because it depends only on the home. That is secondary clustering: milder than linear probing’s, since keys with different homes no longer pile onto one run.
The half-full guarantee
Quadratic probing does not visit every slot. With m prime, the first (m + 1)/2 probes reach different slots, so a table at most half full always has room for a new key. Beyond half full, a free slot may be unreachable.
Worked example
Which slots a key can reach. From home 4 in 11 slots, i² mod 11 for i = 0, 1, 2, … is 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1, so the probes go to slots 4, 5, 8, 2, 9, 7, 7, 9, 2, 8, 5. Only 6 of the 11 slots are ever probed: 2, 4, 5, 7, 8 and 9.
Fifteen does not fit. In the lesson’s table all six of those slots are full. Built with -DKEYS=9, the program tries to put 15, home 4, and prints put 15: 11 probes: every probe hits a full slot, and put gives up, although slots 0, 1 and 3 are free. The table is 8/11 full, more than half, so the guarantee does not hold. The search for 48 fails the same way, after 11 probes.
One check. How many probes does 81 take by linear probing? (7.) By quadratic? (4.)
Where it’s used
Open-addressing tables in libraries, usually with power-of-two sizes and triangular steps (1, 3, 6, …), which do visit every slot.
Reference card
| Code or idea | Meaning |
|---|---|
(key % M + i * i) % M | probe i: home, then 1, 4, 9, … slots on |
| secondary clustering | keys with the same home share their path |
| m prime, α ≤ 1/2 | a new key always finds a slot |
| beyond half full | a free slot may be unreachable |
| eight keys here | 19 probes, against linear probing’s 27 |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.