Question

Assume that we define h₁(k) = k mod 13 and h₂(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) = (h₁(k) + i) mod m     for i = 0, 1, 2, …, m-1.

Quadratic Probing

      Uses a hashing function of the form

            h(k, i) = (h₁(k) + c₁i + c₂i² ) mod m,  

      where h₁ is an auxiliary hash function, c₁ and c₂≠ 0 are auxiliary constants c₁= 3 c₂ = 5,

     and i = 0, 1, 2, …, m-1.

Double hashing

      Uses a hashing function of the form

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

      where h₁ and h₂ are auxiliary hash functions.

      The value of h₂(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:

1. if linear probing is employed,
2. if quadratic probing is employed, and
3. if double hashing is employed.

Answer 1

1. Linear Probing

Hash position = (k mod 13 +i) % 13

k = {79, 69, 98, 72, 14, 50, 88, 99, 78, 65} --Set of keys, Taking key one by one from start

1. Hash position = (79 % 13 +0) % 13 = 1, Since 1 is empty

Insert 79 at position 1.

2. Hash position = (69%13+0) % 13 = 4, Since 4 is empty

Insert 69 at position 4.

3. Hash position = (98%13+0) % 13 = 7, Since 7 is empty

Insert 98 at position 7.

4. Hash position = (72%13+0) % 13 = 7, Since 7 is not empty

Hence insert (72%13 +1)% 13=73 % 13=8 at position 8

5. Hash position = (14%13+0) % 13 = 1, Since 1 is not empty

Insert (14%13+1) % 13= 15 % 13=2 at position 2

6. Hash position = (50%13+0) % 13 = 11, Since 11 is empty

Insert 50 at position 11.

7. Hash position = (88%13+0) % 13 = 10, Since 10 is empty

Insert 88 at position 10.

8. Hash position = (99%13+0) % 13 = 8, Since 8 is not empty

(99%13+1)%13=9

Insert 8 at position 9

9. Hash position = (78%13+0) % 13 = 0, Since 0 is empty

Insert 78 at position 0.

10. Hash position = (65%13+0) % 13 = 0

Since 0 is not empty, Try to insert at next one

(65%13+1) % 13=66 % 13=1

But 1 is also not empty, Hence Trying next one

(65%13+2) % 13=67%13=2

But 2 is also not empty, Hence trying at next one

(65%13+3) % 13=68%13=3

Since 3 is empty, Hence

Insert 65 at position 3.

FINAL HASH TABLE:

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

2. Quadratic Probing

Hash position = (h₁(k) + c₁i + c₂i² ) mod 13

where h₁(k)=k mod 13

c1= 3, c2=5

k = {79, 69, 98, 72, 14, 50, 88, 99, 78, 65} --Set of keys, Taking key one by one from start

1. Hash position = (79%13 +0+0) % 13 = 1%13=1 , Since 1 is empty

Insert 79 at position 1.

2. Hash position = (69%13 +0+0) % 13 = 4%13=4 , Since 4 is empty

Insert 69 at position 4.

3. Hash position = (98%13 +0+0) % 13 = 7%13=7 , Since 7 is empty

Insert 98 at position 7.

4. Hash position = (72%13 +0+0) % 13 = 7%13=7 , Since 7 is not empty

( 72%13 + 3*1 + 5*1²) % 13=(7+3+5) % 13= 15%13=2

Insert 72 at position 2.

5. Hash position = (14%13 +0+0) % 13 = 14%13=1 , Since 1 is not empty

( 14%13 + 3*1 + 5*1²) % 13=(1+3+5) % 13= 9%13=9, 9 is empty

Insert 14 at position 9

6. Hash position = (50%13 +0+0) % 13 = 11%13=11 , Since 11 is not empty

( 50%13 + 3*1 + 5*1²) % 13=(11+3+5) % 13= 19%13=6, 6 is empty

Insert 50 at position 6

7. Hash position = (88%13 +0+0) % 13 = 10%13=10 , Since 10 is not empty

Insert 88 at position 10

8. Hash position = (99%13 +0+0) % 13 = 8%13=10 , Since 8 is empty

Insert 99 at position 8

9. Hash position = (78%13 +0+0) % 13 = 0%13=0 , Since 0 is empty

Insert 78 at position 0

10. Hash position = (65%13 +0+0) % 13 = 0%13=0 , Since 0 is not empty

( 65%13 + 3*1 + 5*1²) % 13=(0+3+5) % 13= 8%13=8, 8 is not empty

( 65%13 + 3*2 + 5*2²) % 13=(0+6+20) % 13= 26%13=0, 0 is not empty

( 65%13 + 3*3 + 5*3²) % 13=(0+9+45) % 13= 54%13=2, 2 is not empty

( 65%13 + 3*4 + 5*4²) % 13=(0+12+80) % 13= 92%13=1, 1 is not empty

( 65%13 + 3*5 + 5*5²) % 13=(0+15+125) % 13= 140%13=10, 10 is not empty

( 65%13 + 3*6 + 5*6²) % 13=(0+18+180) % 13= 198%13=3, 3 is empty

Insert 65 at position 3

FINAL HASH TABLE

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

3. Double Hashing

Hash position = (h₁(k) + i * h2(k)) mod 13

where h₁(k)=k mod 13

h₂(k)=1+(k mod 11)

k = {79, 69, 98, 72, 14, 50, 88, 99, 78, 65} --Set of keys, Taking key one by one from start

1. Hash position = (79 % 13 +0 *(1+ 79 % 11)) % 13 = (1+0)%13=1%13=1 , Since 1 is empty

Insert 79 at position 1.

2. Hash position = (69 % 13 +0 *(1+ 69 % 11)) % 13 = (4+0)%13=4%13=4 , Since 4 is empty

Insert 69 at position 4.

3.. Hash position = (98 % 13 + 0 *(1+ 98 % 11) % 13 = (7+0)%13=7%13=7 , Since 7 is empty

Insert 98 at position 7.

4. Hash position = (72 % 13 + 0 *(1+ 72 % 11)) % 13 = (7+0)%13=7%13=7 , Since 7 is not empty

(72 % 13 + 1 *(1+ 72 % 11)) % 13 = (7+7)%13=14%13=1, 1 is also not empty

(72 % 13 + 2 *(1+ 72 % 11)) % 13 = (7+14)%13=21%13=8, Since 8 is empty

Insert 72 at position 8.

5.. Hash position = (14 % 13 +0 *(1+ 14 % 11)) % 13 = (1+0)%13=1%13=1 , Since 1 is not empty

(14 % 13 +1 *(1+ 14 % 11) % 13 = (1+4)%13=5%13=5, 5 is empty

Insert 14 at position 5..

6. Hash position = (50 % 13 + 0 *(1+ 50 % 11)) % 13 = (11+0)%13=11%13=12 , Since 11 is empty

Insert 50 at position 11.

7. Hash position = (88 % 13 + 0 *(1+ 88 % 11)) % 13 = (10+0)%13=10%13=10 , Since 10 is empty

Insert 88 at position 10.

8. Hash position = (99 % 13 + 0 *(1+ 99 % 11)) % 13 = (8+0)%13=8%13=8 , Since 8 is not empty

(99 % 13 + 1 *(1+ 99 % 11)) % 13 = (8+1)%13=9%13=9

Insert 99 at position 9.

9. Hash position = (78 % 13 + 0 *(1+ 78 % 11)) % 13 = (0+0)%13=0%13=0 , Since 0 is empty

Insert 78 at position 0.

10. Hash position = (65 % 13 + 0 *(1+ 65 % 11)) % 13 = (0+0)%13=0%13=0 , Since 0 is not empty

(65 % 13 + 1 *(1+ 65 % 11)) % 13 = (0+11)%13=11%13=10, Since 11 is not empty

(65 % 13 + 2 *(1+ 65 % 11)) % 13 = (0+22)%13=22%13=9, Since 9 is also not empty

(65 % 13 + 3 *(1+ 65 % 11)) % 13 = (0+33)%13=33%13=7, 7 is also not empty

(65 % 13 + 4 *(1+ 65 % 11)) % 13 = (0+44)%13=44%13=5, 5 is also not empty

(65 % 13 + 5 *(1+ 65 % 11)) % 13 = (0+55)%13=55%13=3, 3 is Empty

Insert 78 at position 3.

FINAL HASH TABLE

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