Question

Assume that we define h1(k) = k mod 13 and h2(k) = 1 + (k mod 11).
For the opening addressing, consider the following methods
Linear Probing
Given an ordinary hash function h’: U {0, 1, 2, …, m-1}, the method of linear probing
uses the hash function
   h(k, i) = (h1(k) + i) mod m for i = 0, 1, 2, …, m-1.
Quadratic Probing
Uses a hashing function of the form
   h(k, i) = (h1(k) + c1i + c2i2 ) mod m,   
where h1 is an auxiliary hash function, c1 and c2 0 are auxiliary constants c1 3 c2 = 5,
and i = 0, 1, 2, …, m-1.
Double hashing
Uses a hashing function of the form
    h(k, i) = (h1(k) + i h2(k) ) mod m,   
where h1 and h2 are auxiliary hash functions.
The value of h2(k) must never be zero and should be relatively prime to m for the sequence
to include all possible address.

Given K = {79, 69, 98, 72, 14, 50, 88, 99, 78, 65} and the size of a table is 13, with indices counting from 0, 1, 2, …, 12. Store the given K in a table with the size 13 counting the indices from 0, 1, 2, …, 12. Show the resultant table with 10 given keys for each method applied:
⦁   if linear probing is employed,
⦁   if quadratic probing is employed, and
⦁   if double hashing is employed.

Answer 1

K={79, 69, 98, 72, 14, 50, 88, 99, 78, 65}

BY linear probing we will save the key at the indices which comes as remainder

if collision occurs then will use h(k, i) = (h1(k) + i) mod m  this formula to find next empty space

m=12

h₁= 79 mod 12 = 7

h₂ = 69 mod 12 = 9

h₃ = 98 mod 12 = 2

h₄= 72 mod 12 = 0

h₅ = 14 mod 12 = 2 collision occurs so , will add 1 to hash key then as using linear probing

  h₅ = (14+1) mod 12 = 3

h₆ = 50 mod 12 = 2 collision occurs so , will add 1 to hash key then

h₆ = 50 +1 mod 12 = 3 collision

h₆ = 51+1  mod 12 = 4

h₇= 88 mod 12 = 4 collision occurs, As 4 is already occupied by hash key 50

h₇= 88 +1 mod 12 = 5

h₈= 99 mod 12 = 3  collision occurs, As 3 is already occupied by hash key 14

h₈= 99+1 mod 12 = 4

h₈= 100+1 mod 12 = 5

h₈= 101 + 1 mod 12 = 6

h₉ = 78 mod 12 = 6 collision occurs, As indicie 6 is already occupied by hash key 99

  h₉ = 78 +1 mod 12 = 7

h₉ = 79 + 1 mod 12 = 8

h₁₀= 65 mod 12 = 5  collision occurs, As 5 is already occupied by hash key 88

h₁₀= 65 +1 mod 12 = 6

h₁₀= 66 +1 mod 12 = 7

h₁₀= 67 +1 mod 12 = 8

h₁₀= 68 +1 mod 12 = 9

h₁₀= 69 +1 mod 12 = 10

HASH VALUE	HASH KEY
0	72
1
2	98
3	14
4	50
5	88
6	99
7	79
8	78
9	69
10	65
11
12

BY Quadratic probing we will save the key at the indices which comes as remainder

if collision occurs then will use h(k, i) = (h₁(k) + c₁i + c₂i² ) mod m this formula to find next empty space

m=12 ,c₁ =3 c₂ = 5

h₁= 79 mod 12 = 7

h₂ = 69 mod 12 = 9

h₃ = 98 mod 12 = 2

h₄= 72 mod 12 = 0

h₅ = 14 mod 12 = 2 collision occurs so , will add 1 to hash key then

  h₅ = ( 14 + (3*1)+ (5* 1²)) mod 12 = 22 MOD 12 = 10

h₆ = 50 mod 12 = 2 collision occurs so , will add 1 to hash key then

h₆ = ( 50 + (3*1)+ (5* 1²)) mod 12 = 58 MOD 12 = 10 collsion occurs

h₆ = ( 50 + (3*2)+ (5* 2²)) mod 12 = 76 mod 12 = 4

h₇= 88 mod 12 = 4 collision occurs, As 4 is already occupied by hash key 50

h₇= ( 88 + (3*1)+ (5* 1²)) mod 12 = 96 mod 12 =0 collsion occurs again

   h₇= ( 88 + (3*2)+ (5* 2²)) mod 12 = 114 mod 12 = 6

h₈= 99 mod 12 = 3  

h₉ = 78 mod 12 = 6 collision occurs, As indicie 6 is already occupied by hash key 88

h₉ = ( 78+ (3*1)+ (5* 1²)) mod 12 = 86 mod 12 =2 collision occurs as 98 is already at indices 2.

h₉ = ( 78 + (3*2)+ (5* 2²)) mod 12 = 114 mod 12 = 6 collision occurs as 88 is already at indices 6.

   h₉ = ( 78 + (3*3)+ (5* 3²)) mod 12 = 132 mod 12 = 0 collision occurs as 72 is already at indices 0.

h₉ = ( 78 + (3*4)+ (5* 4²)) mod 12 = 170 mod 12 = 2 collision occurs as 98 is already at indices 2.

h₉ = ( 78 + (3*5)+ (5* 5²)) mod 12 = 218 mod 12 = 2 collision occurs as 98 is already at indices 2.

h₉ = ( 78 + (3*6)+ (5* 6²)) mod 12 = 276 mod 12 = 0 collision occurs as 72 is already at indices 0.

h₉ = ( 78 + (3*7)+ (5* 7²)) mod 12 = 344 mod 12 = 8

h₁₀ = 65  mod 12 = 5  

HASH VALUE(Indices)	HASH KEY
0	72
1
2	98
3	99
4	50
5	65
6	88
7	79
8	78
9	69
10	14
11
12

BY Double Hashing we will save the key at the indices which comes as remainder

if collision occurs then will use    h(k, i) = (h₁(k) + i h₂(k) ) mod m,   this formula to find next empty space

h₂(k) this the second hash which we will find if collision occurs with the use of prime no. and then will put the value of i linearly.

m=12

h₁= 79 mod 12 = 7

h₂ = 69 mod 12 = 9

h₃ = 98 mod 12 = 2

h₄= 72 mod 12 = 0

h₅ = 14 mod 12 = 2 collision occurs so , As 98 is already at that place.

  h(k, i) = (h₅ + i hash₂(k) ) mod m,

hash₂(5) = 7 - (14 mod 7) = 7

h₅ = (2 + 1* 7) mod 12 = 9 mod 12 =2 collsion as 98 is already there at that place.

h₅ = (2 + 2* 7) mod 12 = 16 mod 12 =4

h₆ = 50 mod 12 = 2 collision occurs so , As 98 is already at that place

h(k, i) = (h₆ ​​​​​​​ + i hash₂(k) ) mod m,

hash₂(6) = 7 - (50 mod 7) = 6

h₆ = (2 + 1* 6) mod 12 = 8

h₇= 88 mod 12 = 4 collision occurs, As 4 is already occupied by hash key 50

h(k, i) = (h₆ ​​​​​​​ + i hash₂(k) ) mod m,

hash₂(7) = 7 - (88 mod 7) = 3

h₇ = (2 + 1* 3) mod 12 = 5

h₈= 99 mod 12 = 3  

h₉ = 78 mod 12 = 6

h₁₀= 65 mod 12 = 5  collision occurs, As 5 is already occupied by hash key 88

h(k, i) = (h₁₀ ​​​​​​​ + i hash₂(k) ) mod m,

hash₂(10) = 7 - (65 mod 7) = 5

h₁₀ = (2 + 1* 5) mod 12 = 7 collision occurs, As 7is already occupied by hash key 79

h₁₀ = (2 + 2* 5) mod 12 = 0 collision occurs, As 0 is already occupied by hash key 72

h₁₀ = (2 + 3* 5) mod 12 = 5 collision occurs, As 5 is already occupied by hash key 88

h₁₀ = (2 + 4* 5) mod 12 = 10 it is there.

HASH VALUE	HASH KEY
0	72
1
2	98
3	99
4	14
5	88
6	78
7	79
8	50
9	69
10	65
11
12