# 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

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