Question

Need help with algorithm homework, please answer with complete steps. Will give thumbs up to correct and complete answer, thanks!

Given a hash function h(x) = x mod 10 with inputs: 4491, 1443, 6293, 4319, 4464, 9799, 2109. Do the following:

(a) Hash table with quadratic probing

(b) Given new hash function h(x) = x mod 19, rehash part a, with order following the old hash table order, not original order at the beginning

Answer 1

Part A)

Hash Function is used to map the values in the hash table .

H(x) = x mod 10

where x is the value that needed to be mapped

Apply Hash Function to each value to get the slot

1 x = 4491

H(4491) = 4491 mod 10 = 1

So 4491 is stored at slot 1

2. x = 1443

H(1443) = 1443 mod 10 = 3

So 1443 is stored at slot 3

3.

x= 6293

H(6293) = 6293 mod 10 = 3

Now at slot 3 we already have 1443 so collision is there

Now Use quadratic probing to resolve resolution

Now Hash Function is H(x) = ( H(x) + i^2 ) mod 10 for all i >=1

First i = 1

H( 6293 ) = ( 3 + 1 x 1 ) mod 10 = 4

So now 6293 is stored at slot 4

4.

x=4319

H(4319 ) = 4319 mod 10 = 9

Now 4319 is stored at Slot 9

5.

x= 4464

H(4464) = 4464 mod 10 = 4

Now already at slot 4 6293 is stored so Collision Occurs

H(4464) = ( 4 + 1 x 1 ) mod 10 = 5

Hence 4464 is stored at slot 5

6.

x=9799

H( 9799) = 9799 mod 10 = 9

Now already 4319 is stored at slot 9 so collision occurs

Now

H(9799) = ( 9 + 1 x 1 )mod 10 = 0

Now 9799 is stored at Slot 0

7.

x=2109

H(2109 ) = 2109 mod 10 = 9

So collision occurs

For i =1

H( 2109 ) = ( 9 + 1x1 ) mod 10 = 0

Again Collision occurs at slot 0

For i =2

H( 2109 ) = ( 9 + 2 x 2 ) mod 10 = 3

Again Collision is there

For i = 3

H(2109 ) = ( 9 + 3 x 3 ) mod 10 = 18 mod 10 = 8

Now finally 2109 is stored at Slot 8

So now finally Hash Table is  

Index Value	Key Stored
0	9799
1	4491
2
3	1443
4	6293
5	4464
6
7
8	2109
9	4319

Part B )

Now sequence of Insertion Key in hash table is

9799, 4491 , 1443 , 6293 , 4464 , 2109 , 4319

Now Hash These values using Hash Function

H(x) = x mod 19

So mapping is

1.

x= 9799

H( 9799) = 9799 mod 19 = 14

So 9799 is stored at Slot 14

2.

x= 4491

H(4491) = 4491 mod 19 = 7

So 4491 is stored At Slot 7

3.

x= 1443

H(1443) = 1443 mod 19 = 18

So 1443 is stored at Slot 18

4.

x= 6293

H(6293) = 6293 mod 19 = 4

So 6293 is stored at Slot 4

5.

x= 4464

H(4464) = 4464 mod 19 = 18

So now collision occur

H(4464 ) = ( 18 + 1 x 1 )mod 19 = 0

So 4464 is stored at Slot 0

6.

x= 2109

H(2109 ) = 2109 mod 19 = 0

So collision occurs

H( 2109 ) = ( 0 + 1 x 1 ) mod 19 = 1

So 2109 is stored at Slot 1

7.

x = 4319

H(4319) = 4319 mod 19 = 6

So 4319 is stored at slot 6

So Finally Hash Table we get as

Index Value	Key Stored
0	4464
1	2109
2
3
4	6293
5
6	4319
7	4491
8
9
10
11
12
13
14	9799
15
16
17
18	1443

This is how you can do hashing on values and Make the Hash Table and here to resolve the collision we have used Quadratic Probing

If u like the answer do give it a thumbs up and have any doubt comment it