Linear probing

No chains this time: every key goes in the array itself. Watch what a key does when its slot is taken, and how one collision makes the next one more likely.

⋯4#define M 115 6#ifndef KEYS7#define KEYS 88#endif9 10enum state { EMPTY, FULL, DELETED };11 12struct slot {13    int key;14    enum state state;15};16 17static struct slot table[M];18static int probes = 0;19 20bool put(int key)21{22    int target = -1;23    for (int i = 0; i < M; i++) {24        int s = (key % M + i) % M;25        probes++;26        if (table[s].state == FULL && table[s].key == key)27            return true;28        if (table[s].state == DELETED && target < 0)29            target = s;30        if (table[s].state == EMPTY) {31            if (target < 0)32                target = s;33            break;34        }35    }36    if (target < 0)37        return false;38    table[target].key = key;39    table[target].state = FULL;40    return true;41}42 43int find(int key)44{45    for (int i = 0; i < M; i++) {46        int s = (key % M + i) % M;47        probes++;48        if (table[s].state == EMPTY)49            return -1;50        if (table[s].state == FULL && table[s].key == key)51            return s;52    }53    return -1;54}55 56void remove_key(int key)57{58    int s = find(key);59    if (s >= 0)60        table[s].state = DELETED;61}62 63int main(void)64{65    const int keys[8] = { 26, 37, 5, 59, 16, 72, 81, 9 };66    for (int i = 0; i < KEYS; i++) {67        probes = 0;68        put(keys[i]);69        printf("put %d: %d probes\n", keys[i], probes);70    }71    probes = 0;72    int a = find(48);73    printf("find 48: %d after %d probes\n", a, probes);74    remove_key(37);75    probes = 0;76    int b = find(59);77    printf("find 59: slot %d after %d probes\n", b, probes);78    return 0;79}

Keys in the array itself

Open addressing keeps every key in the table’s array, with no lists. Each slot is empty, full, or deleted. To put a key, start at its home slot, k mod m. If that slot is taken, try the next one, and the next, wrapping round from the last slot to slot 0:

This is linear probing. A search follows the same sequence and stops at the key, or at an empty slot: had the key been put, it would have gone there or earlier.

The keys must not be negative here: in C, the % of a negative number is negative, which is no slot.

The code and its cost

bool put(int key)
{
    int target = -1;
    for (int i = 0; i < M; i++) {
        int s = (key % M + 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) % M;
        probes++;
        if (table[s].state == EMPTY)
            return -1;
        if (table[s].state == FULL && table[s].key == key)
            return s;
    }
    return -1;
}

main puts the eight keys into a table of 11 slots and counts each put’s probes:

That is 27 probes, 3.4 per key.

Clustering

Four of the keys have home 4 and two have home 5, so slots 4 to 10 fill as one run. A run like this is a cluster, and it grows faster the longer it is: any key whose home falls anywhere in it lands at its end, making it longer still, and two clusters that meet merge. That is primary clustering, and it is why 81 needed 7 probes. Keep α, the share of full slots, below about 0.7.

Removal and tombstones

Removing a key cannot simply empty its slot. A search stops at an empty slot, so emptying slot 5 would hide every key that had passed it on the way to its own slot. Removal leaves a tombstone instead: the slot is marked deleted. A search passes a tombstone, and put remembers the first one it meets and reuses it if the key turns out to be new.

main removes 37 from slot 5, then searches for 59: home 4, past the tombstone at 5, past 6, found in slot 7 after 4 probes. find 48 had already crossed the cluster from slot 4 to the empty slot 1: 9 probes for a key that is not there.

The expected cost

If keys hash independently and evenly, a successful search makes about

probes. At α = 8/11 that is 2.3. The lesson’s keys did worse, 3.4, because they were chosen to collide: four share one home.

Worked example

Without the tombstone. If removing 37 had emptied slot 5, the search for 59 would start at slot 4, find 26, move to slot 5, find it empty and stop: 59 would be reported missing, though it sits in slot 7.

The formula at other loads. At α = 0.5, 1.5 probes; at α = 0.9, 5.5. The cost rises steeply as the table fills.

A missing key. At α = 8/11, the search for 48 crossed 9 slots before it found an empty one.

Two checks. Where would 15 go after the eight keys? (Home 4, the same path as the search for 48: slot 1, after 9 probes.) Why can’t probing fail while a slot is free? (It tries all m slots.)

Where it’s used

Fast in-memory hash tables: keys side by side in one array make probing cheap for the memory cache.

Language runtimes, many of whose dictionaries use open addressing.

Reference card

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.