資料結構及演算法

Consider a hash table of size $M = 20$ (slots indexed from 0 to 19). The primary hash function is defined as: $h_1(k) = k \bmod 20$. The secondary hash function is defined as: $h_2(k) = (k \bmod 7) + 1$. Assume the hash table is initially empty before each part of the question. We will insert the following sequence of keys $S$ in the order given:

$S = [8, 38, 3, 5, 28, 18, 65, 83, 25]$

(a) (5%) Assuming we use double hashing for collision resolution, determine the final structure of the hash table after all keys in $S$ have been inserted. Note: The probe sequence is given by:

$h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod M$

where $i$ is the probe number.

(b) (5%) If we search for 48, what is the total number of probes made during the search?

(c) (10%) Suppose we are given $n$ keys, $m$ hash table slots, and two uniform hash functions $h_a$ and $h_b$. Further suppose hashing scheme uses $h_a$ for the odd keys and $h_b$ for the even keys. What is the expected number of keys in a slot?