Chaining and open addressing

Why it exists

Two keys with the same hash value must both be stored and both be found later. There are two basic ideas. Chaining gives every slot a list, so collisions simply share a list. Open addressing keeps all keys in the table itself and, when the home slot is taken, probes other slots by a fixed rule. Chaining is simple and degrades gracefully; open addressing saves the pointers and has good cache behaviour but fails if the table fills up and needs care when deleting. GATE asks about the exact table after a sequence of insertions, about probe sequences, and about what goes wrong with deletion.

Prerequisites

You need hash functions, collisions and the load factor (hashing) and linked lists (linked lists).

Precise definitions

Chaining (separate chaining). Slot $j$ of the table holds the head of a linked list of all keys $k$ with $h(k) = j$.

• Insert: compute $h(k)$ and put the new node at the front of that list: $\Theta(1)$ (after checking that the key is not already present, if duplicates are not allowed, which costs a search).
• Search: walk down the list of slot $h(k)$ comparing keys.
• Delete: find the node and unlink it (a doubly linked list gives $\Theta(1)$ once the node is found).

Open addressing. At most one key per slot, so $n \le m$ always. A probe sequence $h(k, 0), h(k, 1), \ldots, h(k, m-1)$ says which slots to try for key $k$. For correctness it must be a permutation of $0, \ldots, m-1$ (every slot is eventually tried).

• Insert: try the slots of the probe sequence until one is empty (or deleted).
• Search: try the slots in order until the key is found (success) or an empty slot is reached (failure: if the key were present it would have been placed there or earlier).
• Delete: the slot is marked DELETED (a tombstone), never just emptied.

The three standard probe sequences, with $h'(k) = k \bmod m$:

Clustering. Primary clustering: in linear probing a run of occupied slots grows whenever a key hashes anywhere into it, so long runs get longer. Secondary clustering: in quadratic probing keys with the same home slot follow the same sequence. Double hashing avoids both because the step depends on the key.

How it works

Chaining in action

The animation inserts $45, 16, 29, 78, 33, 60, 14, 92$ into $11$ buckets with $h(k) = k \bmod 11$ and then searches for $78, 45, 100, 9$. The code is the real code; the picture is read from the real list nodes. New nodes go to the front, so $78$ stands before $45$.

An unsuccessful search for $100$ (bucket $1$) walks the whole chain, $2$ comparisons; for $9$ (bucket $9$, empty) it makes no comparison. The cost of a search is the length of one chain: $\Theta(1 + \alpha)$ on average, $\Theta(n)$ if all keys share a bucket. The table never becomes "full": $\alpha$ may exceed $1$.

Open addressing in action

The same eight keys, then $56$, are inserted with linear probing; then $78$ is deleted and $56$ and $100$ are searched. A blank slot is empty, an x is a tombstone. Watch the keys $78$ and $60$ (home slots $1$ and $5$ already taken, so they move one slot on), and the eight probes of key $56$: its home slot $1$ is the start of a run of occupied slots (slots $1$ to $7$), and it has to walk through all of them. The final search for the absent key $100$ (home slot $1$ as well) takes nine probes, because it stops only at the empty slot $9$.

Why deletion needs a tombstone. After $78$ is deleted from slot $2$, the key $56$ (home slot $1$, stored in slot $8$) must still be found: its probe sequence is $1, 2, 3, \ldots, 8$. If slot $2$ were set to empty, the search for $56$ would stop at slot $2$ ("an empty slot, so the key is absent") and report the wrong answer. A tombstone says "continue". Searches pass over tombstones; insertions may reuse them. The price: tombstones lengthen searches, so the table is rebuilt from time to time. (With chaining none of this arises.)

The three probe rules side by side

The program below inserts the same ten keys into an empty table of $11$ slots with the three rules (linear; quadratic with $c_1 = 0, c_2 = 1$; double hashing with $h_2(k) = 1 + (k \bmod 10)$, which lies between $1$ and $10$ and is coprime to the prime $11$) and prints the probes used by each key and the final table. It also counts how many different slots the first $11$ probes of one key visit.

#include <stdio.h>
 
#define M 11
#define EMPTY (-1)
 
static int table[M];
 
/* slot examined at probe number i (i = 0, 1, 2, ...) for the given key and scheme */
static int slot(int scheme, int key, int i) {
    int h1 = key % M;
    if (scheme == 0) return (h1 + i) % M;                    /* linear probing */
    if (scheme == 1) return (h1 + i * i) % M;                /* quadratic probing, h + i^2 */
    int h2 = 1 + key % (M - 1);                              /* double hashing: step between 1 and 10 */
    return (h1 + i * h2) % M;
}
 
int main(void) {
    const char *name[3] = {"linear", "quadratic", "double"};
    int keys[10] = {45, 16, 29, 78, 33, 60, 14, 92, 56, 23};
    for (int s = 0; s < 3; s++) {
        for (int b = 0; b < M; b++) table[b] = EMPTY;
        printf("%-10s probes per key:", name[s]);
        int total = 0;
        for (int k = 0; k < 10; k++) {
            int i = 0;
            while (i < M && table[slot(s, keys[k], i)] != EMPTY) i++;
            if (i == M) { printf(" fail"); continue; }
            table[slot(s, keys[k], i)] = keys[k];
            printf(" %d", i + 1);
            total += i + 1;
        }
        printf("  (total %d)\n           table:", total);
        for (int b = 0; b < M; b++) {
            if (table[b] == EMPTY) printf("  .");
            else printf(" %2d", table[b]);
        }
        printf("\n");
    }
    printf("\nnumber of different slots visited by the first %d probes of the key 5:\n", M);
    for (int s = 0; s < 3; s++) {
        int seen[M] = {0}, count = 0;
        for (int i = 0; i < M; i++) {
            int b = slot(s, 5, i);
            if (!seen[b]) { seen[b] = 1; count++; }
        }
        printf("%-10s %d of %d\n", name[s], count, M);
    }
    return 0;
}

linear     probes per key: 1 1 1 2 1 2 1 1 8 9  (total 27)
           table: 33 45 78 14 92 16 60 29 56 23  .
quadratic  probes per key: 1 1 1 2 1 2 1 1 4 fail  (total 14)
           table: 33 45 78 14 92 16 60 29  .  . 56
double     probes per key: 1 1 1 2 1 2 1 1 2 3  (total 15)
           table: 33 45  . 14 92 16 60 29 56 23 78
 
number of different slots visited by the first 11 probes of the key 5:
linear     11 of 11
quadratic  6 of 11
double     11 of 11

Three observations. Linear probing used $27$ probes: the keys $56$ and $23$ both had to cross the run of occupied slots (probes $8$ and $9$). Double hashing needed only $15$, because the step differs from key to key, so keys from the same run take different paths. Quadratic probing with $h + i^2$ failed to insert the last key although slots $8$ and $9$ were empty: its sequence visits only $6$ of the $11$ slots (the last line of the output) and all six were occupied. A probe sequence that is not a permutation of the slots can miss free slots.

When do the sequences cover the whole table?

• Linear probing: always.
• Double hashing: exactly when $\gcd(h_2(k), m) = 1$. Standard ways: $m$ prime and $1 \le h_2 \le m - 1$, or $m = 2^p$ and $h_2$ odd.
• Quadratic probing: for $m$ prime, $h + i^2$ visits only $(m + 1)/2$ slots; $h + (i + i^2)/2$ (that is, the triangular numbers) visits every slot when $m$ is a power of two. So the constants and $m$ must be chosen together.

Which tables are possible? For a table built by insertions only (no deletions) with linear probing, every key sits at a slot such that all slots from its home slot up to its own slot are occupied (otherwise it would have been placed earlier). This is a quick necessary test for "which of the following tables could result from inserting these keys" questions; the order of insertion decides which of two keys with the same home slot comes first.

Resizing. When $\alpha$ grows too large the table is rebuilt with a larger $m$ (often doubled) and every key is rehashed, because $h$ depends on $m$. The cost of rebuilding, $\Theta(n)$, is spread over the insertions that led to it, so the amortized cost per insertion stays constant. Open addressing is usually resized at $\alpha \approx 0.5$ to $0.75$; chaining tolerates $\alpha \approx 1$ or more.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The hash functions and the idea of the load factor are in hashing; the expected costs of these schemes as a function of $\alpha$ are in load factor and expected probes. Chaining uses linked lists and open addressing uses arrays.

PYQs

Consider a hash table P[0, 1, ..., 10] that is initially
empty. The hash table is maintained using open
addressing with linear probing. The hash function
used is :
h(x) = (x + 7) mod 11. Consider the following
sequence of insertions performed on
P: 1, 13, 22, 15, 11, 24
Which of the following positions in the hash table
is/are empty after these insertions are performed?
collisions. Let k be the number of keys, m be the
number of slots in the hash table, and k>m.
Which one of the following is the best hashing
strategy to counteract the adversary?

The keys 5, 28, 19, 15, 26, 33, 12, 17, 10 are
inserted into a hash table using the hash function
h(k) = k mod 9. The collisions are resolved by
chaining. After all the keys are inserted, the length
of the longest chain is
.

In a double hashing scheme, h1(k) = k mod 11
and h2(k) = 1 + (k mod 7) are the auxiliary hash
functions. The size m of the hash table is 11. The
hash function for the i-th probe in the open address
table is
[h1(k) + ih2(k)] mod m The following keys are
inserted in the given order: 63, 50, 25, 79, 67, 24.
The slot at which key 24 gets stored is
.
(Answer in integers)

Consider a double hashing scheme in which the
primary hash function is h1(k) = k mod 23, and
the secondary hash function is h2(k) = 1 +
(kmod19). Assume that the table size is 23. Then
the address returned by probe 1 in the probe
sequence (assume that the probe sequence begins at
probe 0) for key value k=90 is
.

A hash table of length 10 uses open addressing with
hash function h(k) = k mod 10, and linear
probing. After inserting 6 values into an empty hash
table, the table is as shown below

How many different insertion sequences of the key
values using the same hash function and linear
probing will result in the hash table shown above?

Which one of the following choices gives a possible
order in which the key values could have been
inserted in the table?

Consider a hash table with 9 slots. The hash function
is h(k) = k mod 9. The collisions are resolved by
chaining. The following 9 keys are inserted in the
order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum,
minimum, and average chain lengths in the hash
table, respectively, are

The keys 12,18,13,2,3,23,5 and 15 are inserted
into an initially empty hash table of length 10 using
open addressing with hash function h(k) = k mod
10 and linear probing. What is the resultant hash
table ?

Consider a hash table of size seven, with starting
index zero, and a hash function h(x) = (3x + 4) mod
7 . Assuming the hash table is initially empty, which
of the following is the contents of the table when the
sequence 1, 3, 8, 10 is inserted into the table using
closed hashing?
Note that "–" denotes an empty location in the table.

Self-check

Revision card

References