Hash Table Example

In the following hash table implementation, we will define functions for the following methods:

• Linear Probing:   \( h_\text{LP}(k,i) \)
• Quadratic Probing:  \( h_\text{QP}(k,i) \)
• Double Hashing:   \( h_\text{DH}(k,i) \)

We will define the auxiliary hash function \(h'(k) \) as the following: $$h'(k) = k$$ The following functions are defined for each of the respective open addressing method: $$ \begin{align} h_{\text{LP}}(k,i) &= (h'(k) + i) \text{ mod } m\\[1em] h_{\text{QP}}(k,i) &= (h'(k) + i\cdot c_1 + i^2 \cdot c_2 ) \text{ mod } m \qquad \text{ where } c_1 = 1 \text{ and } c_2 = 3\\[1em] h_{\text{DH}}(k,i) &= (h_1(k) + i\cdot h_2(k) ) \text{ mod } m \qquad \text{ where } h_1(k) = k \text{ and } h_2(k) = (1 + k) \text{ mod } (m-1) \\ \end{align} $$