Given. the hash function: h(x) = |3x - 2| mod M a bucket array of capacity N a s
ID: 3779313 • Letter: G
Question
Given. the hash function: h(x) = |3x - 2| mod M a bucket array of capacity N a set of objects with keys: 12, -44, 13, -88, 23, 94, 11, 39, -20, 16, 5 (to input from left to right) Write the hash table where M = N = 11 and collisions are handled using separate chaining. Write the hash table where M = N = 11 and collisions are handled using linear probing. Would a size N for the bucket array exist, such that no collisions would happen with the hash function hash function h(x) = |3x - 2| mod 11 and the keys above?Explanation / Answer
4a)
Hash function=|3x-2| mod M
Keys are:12,-44,13,-88,23,,94,11,39,-20,16,5
empty table Insert 12:|3*12-2|mod 11=1
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
12
Insert -44:|3*-44-2|mod 11= 2 Insert 13:|3*13-2|mod 11= 4
0
1
2
3
4
5
6
7
8
9
10
12
-44
0
1
2
3
4
5
6
7
8
9
10
12
-44
13
Insert 13:|3*13-2|mod 11= 4 Insert -88:|3*-88-2|mod 11= 0
0
1
2
3
4
5
6
7
8
9
10
12
-44
13
0
1
2
3
4
5
6
7
8
9
10
-88
12
-44
13
Insert 23:|3*23-2|mod 11= 1
Here collision is occurred so separate chaining is used Insert 94:|3*94-2|mod 11= 5
0
1
2
3
4
5
6
7
8
9
10
-88
12
-44
13
23
0
1
2
3
4
5
6
7
8
9
10
-88
12
-44
13
94
23
Insert 11:|3*11-2|mod 11= 9 Insert 39:|3*39-2|mod 11= 9
0
1
2
3
4
5
6
7
8
9
10
-88
12
-44
13
94
11
23
0
1
2
3
4
5
6
7
8
9
10
-88
12
-44
13
94
11
23
Insert -20 :|3*-20-2|mod 11= 7 Insert 16:|3*16-2|mod 11= 2
0
1
2
3
4
5
6
7
8
9
10
-88
12
-44
13
94
-20
11
23
0
1
2
3
4
5
6
7
8
9
10
-88
12
-44
13
94
11
23
16
5
Insert 5:|3*5-2|mod 11= 2
0
1
2
3
4
5
6
7
8
9
10
-88
12
-44
13
94
11
23
16
5
4b)
Insert 12:|3*12-2|+1 mod 11= 2
Insert -44:|3*-44-2|+2 mod 11= 4
Insert 13:|3*13-2|+3 mod 11= 7
Insert -88:|3*-88-2|+4 mod 11= 6
Insert 23:|3*23-2|+5 mod 11= 6
Insert 94:|3*94-2|+6 mod 11= 0
Insert 11:|3*11-2|+7 mod 11= 5
Insert 39:|3*39-2|+8 mod 11= 2
Insert -20:|3*-20-2|+9 mod 11= 5
Insert 16:|3*16-2|+10 mod 11= 1
Insert 5:|3*5-2|+11 mod 11= 2
After insertion
0
1
2
3
4
5
6
7
8
9
10
94
16
12
39
-44
11
-88
13
23
-20
5
Collision is occurred at 23 and 39 and 5 and -20 this are probed to next empty place
4c)
All inserted and without collisions if the bucket size is 11+4=15
0
1
2
3
4
5
6
7
8
9
10
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.