The hash function: h(x) = |3x + 1| mod M a bucket array of capacity N a set of o
ID: 3824243 • Letter: T
Question
The hash function: h(x) = |3x + 1| 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) = |2x + 5| mod 11 and the keys above?Explanation / Answer
A
M=N=11
Using separate chaining
Element 12
( 12*3+1 ) mod 11=4
Element 44
44*3+1 = 133 mod 11=1
Element 13.
(13 *3 + 1) mod 11=7
Element 88.
(88 *3 + 1) mod 11=1
Element 23.
(23 *3 + 1) mod 11=4
Element 94.
(94 *3 + 1) mod 11=8
Element 11.
(11 *3 + 1) mod 11=1
Element 39.
(39 *3 + 1) mod 11=8
Element 20.
(20 *3 + 1) mod 11=6
Element 16.
(16 *3 + 1) mod 11=5
Element 5
(5 *3 + 1) mod 11=5
a:
Separate chaining
0
1
2
3
4
5
6
7
8
9
10
44
88
11
12
23
16
5
20
13
39
94
B
M=N=11
Using Linear probing
Element 12
( 12*3+1 ) mod 11=4
Element 44
44*3+1 = 133 mod 11=1
Element 13.
(13 *3 + 1) mod 11=7
Element 88.
(88 *3 + 1) mod 11=1
Element 23.
(23 *3 + 1) mod 11=4
Element 94.
(94 *3 + 1) mod 11=8
Element 11.
(11 *3 + 1) mod 11=1
Element 39.
(39 *3 + 1) mod 11=8
Element 20.
(20 *3 + 1) mod 11=6
Element 16.
(16 *3 + 1) mod 11=5
Element 5
(5 *3 + 1) mod 11=5
a:
Linear probing
0
1
2
3
4
5
6
7
8
9
10
6
44
88
11
12
23
20
13
94
39
16
C
Element 12
( 12*2+1 ) mod 11=3
Element 44
44*2+1 = 133 mod 11=1
Element 13.
(13 *2 + 1) mod 11=5
Element 88.
(88 *2 + 1) mod 11=1
Element 23.
(23 *2 + 1) mod 11=3
Element 94.
(94 *2 + 1) mod 11=8
Element 11.
(11 *2 + 1) mod 11=1
Element 39.
(39 *2 + 1) mod 11=2
Element 20.
(20*2 + 1) mod 11=8
Element 16.
(16 *2 + 1) mod 11=0
Element 5
(5 *2 + 1) mod 11=0
So cleary no matter what would be size of N collision will occur as value of |2x+1| mod 11 are same for few elements.
0
1
2
3
4
5
6
7
8
9
10
44
88
11
12
23
16
5
20
13
39
94
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.