In quadratic probing, keys with the same home follow the same path. Here each key gets its own step size. Watch 37 and 59 collide at slot 4, then go separate ways.
Each key with its own stride
The same eight keys; each probes with a step from a second hash
#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 * (1 + key % (M - 1))) % 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 * (1 + key % (M - 1))) % 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[8] = { 26, 37, 5, 59, 16, 72, 81, 9 }; 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
- –
- stride
- –
- 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 30 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, and stepping by its own stride, 1 + the key mod 10. A marker s stands on each slot probed; a taken slot is marked, and an arc joins it to the slot tried next. 26 lands in slot 4. 37, home 4, finds it taken and steps 8 slots on, wrapping round to slot 1. 59, also home 4, steps 10 slots on, to slot 3: the two arcs from slot 4 fan out to different slots. 81, stride 2, goes 4, 6, 8, 10. At the end slots 1, 3, 4, 5, 6, 8, 9 and 10 hold 37, 59, 26, 5, 72, 16, 9 and 81, and slots 0, 2 and 7 are empty. Then the search for 48 tries slot 4, steps 9 to the empty slot 2, and stops after 2 probes; 37 is removed, leaving “del” in slot 1; and the search for 59 finds it in slot 3 after 2 probes. Under the picture are one sentence on the current step and the readouts “key”, “stride”, “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 double-hashing.step.
A stride from a second hash
Double hashing takes the step between probes from a second hash of the key, h₂:
Two keys with the same home usually have different strides, so after one collision they go separate ways. A shared home no longer means a shared path.
The second hash must meet two conditions. It must never be 0, or the key would probe its home slot again and again. And it must share no factor with m: with m prime, every stride from 1 to m − 1 visits all m slots before it repeats one.
The code and its cost
The program is linear probing’s with one edit. In both put and find, the probe slot becomes
int s = (key % M + i * (1 + key % (M - 1))) % M;key % (M - 1) is the key mod 10, from 0 to 9, so the stride 1 + key mod 10 runs from 1 to 10: never 0, and with M = 11 prime, it shares no factor with M except 1.
| Key | 26 | 37 | 5 | 59 | 16 | 72 | 81 | 9 |
|---|---|---|---|---|---|---|---|---|
| Stride | 7 | 8 | 6 | 10 | 7 | 3 | 2 | 10 |
| Probes | 1 | 2 | 1 | 2 | 3 | 1 | 4 | 1 |
| Slot | 4 | 1 | 5 | 3 | 8 | 6 | 10 | 9 |
15 probes in all, against quadratic probing’s 19 and linear probing’s 27 on the same keys.
The three schemes on a larger table
Eight keys show the paths, not the costs. The second picture puts the same keys, in the same order, into three tables of 1009 slots, one per scheme, and measures the average probes per key at each tenth of the table. That average is also what a search for one of the keys costs, since a search retraces the key’s path.
Probes per key as the table fills
Linear, quadratic and double hashing in 1009 slots
An empty table of 1009 slots. Keys are put in the same order under all three schemes.
- α
- 0
- linear
- –
- quadratic
- –
- double
- –
Describe this picture
A plot of probes per key, from 0 to 6, against the keys in 1009 slots, from 0 to 1009, with no code. The clip takes about 14 seconds. A dot is added for each scheme at every tenth of the table, the newest ringed: linear probing, quadratic probing and double hashing, each in its own colour and named in the legend. Up to half full the three stay close, between 1.08 and 1.50 probes per key. Then they part: at 908 keys, α = 0.9, linear probing takes 5.25 probes per key, quadratic probing 2.81 and double hashing 2.52. Under the picture are one sentence on the current step and the readouts “α”, “linear”, “quadratic” and “double”. The transport plays and pauses, steps one beat back or forward, and scrubs; a paused step is kept in the page address as probe-costs.step.
The keys come from a fixed pseudo-random sequence, and these are the counts of one run. Linear probing’s clusters cost it most as the table fills; quadratic probing breaks them up, and double hashing, whose probes behave most nearly like independent random choices, does a little better still.
Worked example
81’s path. Home 4, stride 1 + 81 mod 10 = 2: slots 4, 6, 8, 10. The first three are full, and 81 lands in slot 10 after 4 probes.
A stride that shares a factor. With m = 10, which is not prime, and a stride of 5, the probes go h, h + 5, h, h + 5, …: a key only ever tries two slots, and fails if both are full.
One check. Why 1 + (k mod (m − 1)) and not k mod (m − 1)? (k mod (m − 1) could be 0, and the key would never move.)
Where it’s used
Open-addressing tables where clustering must stay low even when the table is quite full.
Reference card
| Code or idea | Meaning |
|---|---|
(key % M + i * h2) % M | probe i: home, then strides of h₂ |
| h₂ here | 1 + key mod (M − 1): from 1 to M − 1 |
| h₂ ≠ 0 | or the key never leaves home |
| m prime | every stride visits all m slots |
| a shared home | no longer a shared path |
| eight keys here | 15 probes; quadratic 19, linear 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.