Answer to Question #124442 in Algorithms for kwame john

Question

1. 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

Hashing: store data in table slot T[n], where n = Hash(key) = key mod TableSize

Solution a:

n_i(x) = (Hash(x) + i) mod TableSize (i=0,1,2,...)

TableSize=16, data={1, 2, 5, 10, 17, 25, 36, 49}

Hash table using linear probing:

 

Solution b:

n_i(x) = (Hash(x) + i²) mod TableSize (i=0,1,2,...)

TableSize=16, data={1, 2, 5, 10, 17, 25, 36, 49}

Hash table using quadratic probing: