Hash tables The same sequence of seven elements is used in the first two questio
ID: 3840934 • Letter: H
Question
Hash tables The same sequence of seven elements is used in the first two questions; the simple arithmetic has to be done only once. Sketch a hash table of size 11, where the hash function is hash index = key mod 11 and separate chaining is used to resolve collisions, after the following elements are inserted: 3, 16, 49, 56, 78, 84, 89 Sketch hash table of size 11, where the hash function is hash index = key mod 11 and a probing is used to resolve collisions, after the following elements are inserted: linear 49, 56, 78, 84, 89Explanation / Answer
h(k) = k mod 11
In chaining if we have collision then we will main a linked list at that position and we insert the value at end of linked list
h(3) = 3 mod 11 = 3
Hash
Index
0
1
2
3
3
4
5
6
7
8
9
10
h(16) = 16 mod 11 = 5
Hash
Index
0
1
2
3
3
4
5
16
6
7
8
9
10
h(49) = 49 mod 11 = 5
Hash
Index
0
1
2
3
3
4
5
16 --> 49
6
7
8
9
10
h(56) = 56 mod 11 = 1
Hash
Index
0
1
56
2
3
3
4
5
16 --> 49
6
7
8
9
10
h(78) = 78 mod 11 = 1
Hash
Index
0
1
56 --> 78
2
3
3
4
5
16 --> 49
6
7
8
9
10
h(84) = 84 mod 11 = 7
Hash
Index
0
1
56 --> 78
2
3
3
4
5
16 --> 49
6
7
84
8
9
10
h(89) = 89 mod 11 = 1
Hash
Index
0
1
56 --> 78 à 89
2
3
3
4
5
16 --> 49
6
7
84
8
9
10
Linear probing::
h(k) = k mod 11
In linear probing if collision occurs then we search of next empty slot and we insert the key in that sloc
h(3) = 3 mod 11 = 3
Hash
Index
0
1
2
3
3
4
5
6
7
8
9
10
h(16) = 16 mod 11 = 5
Hash
Index
0
1
2
3
3
4
5
16
6
7
8
9
10
h(49) = 49 mod 11 = 5 but 16 already there 5th slot so next free slot is at 6 so we have to insert 49 at 6
Hash
Index
0
1
2
3
3
4
5
16
6
49
7
8
9
10
h(56) = 56 mod 11 = 1
Hash
Index
0
1
56
2
3
3
4
5
16
6
49
7
8
9
10
h(78) = 78 mod 11 = 1
56 already there in index 1 so we have to find next free slot which is 2nd so we have insert 78 at 2nd location
Hash
Index
0
1
56
2
78
3
3
4
5
16
6
49
7
8
9
10
h(84) = 84 mod 11 = 7
Hash
Index
0
1
56
2
78
3
3
4
5
16
6
49
7
84
8
9
10
h(89) = 89 mod 11 = 1
56 is already in index 1 so we have to find next free slot which is 4th index so we have to insert it at 4th location
Hash
Index
0
1
56
2
78
3
3
4
89
5
16
6
49
7
84
8
9
10
h(k) = k mod 11
In chaining if we have collision then we will main a linked list at that position and we insert the value at end of linked list
h(3) = 3 mod 11 = 3
Hash
Index
0
1
2
3
3
4
5
6
7
8
9
10
h(16) = 16 mod 11 = 5
Hash
Index
0
1
2
3
3
4
5
16
6
7
8
9
10
h(49) = 49 mod 11 = 5
Hash
Index
0
1
2
3
3
4
5
16 --> 49
6
7
8
9
10
h(56) = 56 mod 11 = 1
Hash
Index
0
1
56
2
3
3
4
5
16 --> 49
6
7
8
9
10
h(78) = 78 mod 11 = 1
Hash
Index
0
1
56 --> 78
2
3
3
4
5
16 --> 49
6
7
8
9
10
h(84) = 84 mod 11 = 7
Hash
Index
0
1
56 --> 78
2
3
3
4
5
16 --> 49
6
7
84
8
9
10
h(89) = 89 mod 11 = 1
Hash
Index
0
1
56 --> 78 à 89
2
3
3
4
5
16 --> 49
6
7
84
8
9
10
Linear probing::
h(k) = k mod 11
In linear probing if collision occurs then we search of next empty slot and we insert the key in that sloc
h(3) = 3 mod 11 = 3
Hash
Index
0
1
2
3
3
4
5
6
7
8
9
10
h(16) = 16 mod 11 = 5
Hash
Index
0
1
2
3
3
4
5
16
6
7
8
9
10
h(49) = 49 mod 11 = 5 but 16 already there 5th slot so next free slot is at 6 so we have to insert 49 at 6
Hash
Index
0
1
2
3
3
4
5
16
6
49
7
8
9
10
h(56) = 56 mod 11 = 1
Hash
Index
0
1
56
2
3
3
4
5
16
6
49
7
8
9
10
h(78) = 78 mod 11 = 1
56 already there in index 1 so we have to find next free slot which is 2nd so we have insert 78 at 2nd location
Hash
Index
0
1
56
2
78
3
3
4
5
16
6
49
7
8
9
10
h(84) = 84 mod 11 = 7
Hash
Index
0
1
56
2
78
3
3
4
5
16
6
49
7
84
8
9
10
h(89) = 89 mod 11 = 1
56 is already in index 1 so we have to find next free slot which is 4th index so we have to insert it at 4th location
Hash
Index
0
1
56
2
78
3
3
4
89
5
16
6
49
7
84
8
9
10
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.