Exercise 11.4.1

Consider inserting the keys 10, 22, 31, 4, 15, 28, 17, 88, 59 into a hash table of length $m = 11$ using open addressing with the auxiliary hash function $h'(k) = k$. Illustrate the result of inserting these keys using linear probing, using quadratic probing with $c_1 = 1$ and $c_2 = 3$ and using double hashing with $h_1(k) = k$ and $h_2(k) = 1 + (k \bmod (m-1))$.

Here's a hand-rolled table:

   linear      quadratic   double
   +------+    +------+    +------+
 0 |  22  |    |  22  |    |  22  |
   +------+    +------+    +------+
 1 |  88  |    |      |    |      |
   +------+    +------+    +------+
 2 |      |    |  88  |    |  59  |
   +------+    +------+    +------+
 3 |      |    |  17  |    |  17  |
   +------+    +------+    +------+
 4 |   4  |    |   4  |    |   4  |
   +------+    +------+    +------+
 5 |  15  |    |      |    |  15  |
   +------+    +------+    +------+
 6 |  28  |    |  28  |    |  28  |
   +------+    +------+    +------+
 7 |  17  |    |  59  |    |  88  |
   +------+    +------+    +------+
 8 |  59  |    |  15  |    |      |
   +------+    +------+    +------+
 9 |  31  |    |  31  |    |  31  |
   +------+    +------+    +------+
10 |  10  |    |  10  |    |  10  |
   +------+    +------+    +------+

Here's some python code as well:

Python runner output

linear    :  22 | 88 |    |    |  4 | 15 | 28 | 17 | 59 | 31 | 10
quadratic :  22 |    | 59 | 15 |  4 | 17 | 28 |    | 88 | 31 | 10
double    :  22 |    | 59 | 17 |  4 | 15 | 28 | 88 |    | 31 | 10

Python code

def populate(m, keys, probe):
    table = [None] * m

    for key in keys:
        i = 0
        for _ in range(m):
            pos = probe(key, i)
            i += 1

            if table[pos] is None:
                table[pos] = key
                break
        else:
            raise RuntimeError(f"Could not put element {key} in {table!r}")

    return table


def linear(m):
    return lambda key, i: (key + i) % m


def quadratic(m, c1, c2):
    return lambda key, i: (key + i * c1 + i * c2 * c2) % m


def double(m):
    return lambda key, i: (key + i * (1 + key % (m - 1))) % m