Question

Write a program to insert the following elements into a hash table of size 17. The hash function is X mod 17 where X is the input element.  

6, 12, 34, 29, 28, 11, 23, 7, 0, 33, 30, 45

Use linear probing to resolve any collisions.

Answer 1

Q-> Write a program to insert the following elements into a hash table of size 17. The hash function is X mod 17 where X is the input element.  

6, 12, 34, 29, 28, 11, 23, 7, 0, 33, 30, 45

1. Insert 6: Index = 6 mod 17 = 6

Hash table =

0
1
2
3
4
5
6	6
7
8
9
10
11
12
13
14
15
16

2. Insert 12: Index = 12 mod 17 = 12

Hash table =

0
1
2
3
4
5
6	6
7
8
9
10
11
12	12
13
14
15
16

3. Insert 34: Index = 34 mod 17 = 0

Hash table =

0	34
1
2
3
4
5
6	6
7
8
9
10
11
12	12
13
14
15
16

4. Insert 29: Index = 29 mod 17 = 12

Collision occurred, use linear probing, => index = 13

Hash table =

0	34
1
2
3
4
5
6	6
7
8
9
10
11
12	12
13	29
14
15
16

5. Insert 28: Index = 28 mod 17 = 11

Hash table =

0	34
1
2
3
4
5
6	6
7
8
9
10
11	28
12	12
13	29
14
15
16

6. Insert 11: Index = 11 mod 17 = 11

Collision occurred: => use linear probing,=> index = 12

again Collision occurred: => use linear probing,=> index = 13

again Collision occurred: => use linear probing,=> index = 14

Hash table =

0	34
1
2
3
4
5
6	6
7
8
9
10
11	28
12	12
13	29
14	11
15
16

7. Insert 23: Index = 23 mod 17 = 6

Collision occurred: => use linear probing,=> index = 7

Hash table =

0	34
1
2
3
4
5
6	6
7	23
8
9
10
11	28
12	12
13	29
14	11
15
16

8. Insert 7: Index = 7 mod 17 = 7

Collision occurred: => use linear probing,=> index = 8

Hash table =

0	34
1
2
3
4
5
6	6
7	23
8	7
9
10
11	28
12	12
13	29
14	11
15
16

9. Insert 0: Index = 0 mod 17 = 0

Collision occurred: => use linear probing,=> index = 1

Hash table =

0	34
1	0
2
3
4
5
6	6
7	23
8	7
9
10
11	28
12	12
13	29
14	11
15
16

10. Insert 33: Index = 33 mod 17 = 16

Hash table =

0	34
1	0
2
3
4
5
6	6
7	23
8	7
9
10
11	28
12	12
13	29
14	11
15
16	33

11. Insert 30: Index = 30 mod 17 = 13

Collision occurred: => use linear probing,=> index = 14

Collision occurred: => use linear probing,=> index = 15

Hash table =

0	34
1	0
2
3
4
5
6	6
7	23
8	7
9
10
11	28
12	12
13	29
14	11
15	30
16	33

12. Insert 45: Index = 45 mod 17 = 11

next free index is 2 using linear probing

Final Hash table =

0	34
1	0
2	45
3
4
5
6	6
7	23
8	7
9
10
11	28
12	12
13	29
14	11
15	30
16	33