Answer to Question #124455 in Algorithms for David

Question

Insert {1, 2, 5, 10, 17, 25, 36, 49} into empty hash table with Table Size = 16 using
a. Linear Probing
b. Quadratic Probing

Answer 1

Task:

Insert {1, 2, 5, 10, 17, 25, 36, 49} into empty hash table with Table Size: $S=16$

Once, we have a hash table with $S = 16$ , so hash function $h(x)$ for integers is: $h(x) = x \mod 16$

$$\begin{matrix} \bold{x} & 1 & 2 & 5& 10& 17& 25& 36& 49 \\ \bold{h(x)} & 1 &2& 5& 10& 1& 9& 4& 1 \end{matrix}$$

a) Linear probing

Insertion algorithm

1. Start at the cell at index $h(x)$ and continuing to the adjacent cells $ℎ(𝑥)+1, ℎ(𝑥)+2, \dots ,ℎ(𝑥)+𝑘$ until finding an empty cell.
2. insert in this empty cell.

For linear probing probe function is $𝑝(𝑥,𝑖)=(ℎ(𝑥)+𝑖 )\mod 𝑆$

Hash Table

$$\begin{matrix} \bold{Value} & - &1& 2& 17& 36& 5& 49& -& -& 25& 10& -& -& -& -& - \\ \bold{Index} & 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15 \end{matrix}$$

Explanation:

For $1,2,5,10,25,36$ insert value at index $ℎ(𝑥)$

For $17$ cell with index $ℎ(17)=1$ already filled.

Continuing to the adjacent cells:

$𝑝(17,1)=(ℎ(17)+1) \mod 𝑆=2$ -- also filled,

$𝑝(17,2)=(ℎ(17)+2) \mod 𝑆=3$  -- empty, fill it with 17

For $49$ same approach as for $17$ .

b) Quadratic probing

The Insertion algorithm is similar to Linear probing, only difference -- different probe function.

The probe function is some quadratic function:

$$p(x,i)=(h(x)+c_1i^2+c_2i+c_3) \mod S$$

for some choice of constants  $c1, 𝑐2, 𝑐3$. For $S=2^n$ , a good choice for the constants are $𝑐_1=𝑐_2=\frac{1}{2}$ as the values of $𝑝(x,𝑖)$  for $𝑖$ in $[0,𝑆−1]$ are all distinct. This leads to a probe sequence of

$$ℎ(𝑥),ℎ(𝑥)+1,ℎ(𝑥)+3,ℎ(𝑥)+6,\dots$$

the triangular numbers.

In our case we have $𝑆=16=2^4$ , so let's select $𝑐_1=𝑐_2=\frac{1}{2} .$ So we have probe function:

$$𝑝(𝑥,𝑖)= \left( ℎ(𝑥)+\frac{1}{2}𝑖^2+\frac{1}{2}𝑖 \right) \mod 𝑆$$

Hash Table

$$\begin{matrix} \bold{Value} & -& 1& 2& -& 36& 5& -& 17& -& 25& 10& 49& -& -& -& - \\ \bold{Index} & 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15 \end{matrix}$$

Explanation:

For $1,2,5,10,25,36$ insert value at index $h(x)$.

For $17$ cell with index $ℎ(17)=1$ already filled.

Continuing to the adjacent cells:

$𝑝(17,1)=2 \\ 𝑝(17,2)=4 \\ 𝑝(17,3)=7$ -- empty fill it with 17.

For $49$ same approach as for $17$.

$𝑝(49,4)=11$