1. [6] Starting with an empty hash table with a fixed size of 11, insert the fol
ID: 3605020 • Letter: 1
Question
1. [6] Starting with an empty hash table with a fixed size of 11, insert the following keys in order into four distinct hash tables (one for each collision mechanism): 12, 9, 1, 0, 42, 98, 70, 3. You are only required to show the final result of each hash table. In the very 1ikely event that a collision resolution mechanism is unable to successfully resolve, simply record the state of the last successful insert and note that collision resolution failed. For each hashtable type, compute the hash as follows: hashkey(key) (key * key + 3) % 11 Separate Chaining (buckets 2 9 10 To probe, start at i-hashkey and do i++ if collisions continue Linear Probin robe(i')-(i + 1) % Tablesize 2 9 10 uadratic Probing: probe(i') = (i * 1 + 5) 96 TableSize 2 9 10 2. [3] For implementing a hash table. Which of these would probably be the best initial table size to pick? Table Sizes: 100 101 15 500 Why?Explanation / Answer
The hash table has fixed size of 11. The keys which are inserted into four distinct hash tables are as follows: {12, 9, 1, 0, 42, 98, 70, 3}
For each hash table type, the has is computed as follows:
hashkey(key)= (key * key +3)%11
Separate chaining(buckets)
3
0
12
9
70
0 1 2 3 4 5 6 7 8 9 10
For key = 12
Hashkey(key) = (12*12+3) % 11 = 147%11 = 4
For key = 9
Hashkey(key) = (9*9+3) % 11 = 84%11 = 7
For key = 1
Hashkey(key) = (1*1+3) % 11 = 4%11 = 4
For key = 0
Hashkey(key) = (0*0+3) % 11 = 3%11 = 3
For key = 42
Hashkey(key) = (42*42+3) % 11 = 1767 % 11 = 7
For key = 98
Hashkey(key) = (98*98+3) % 11 = 9607 % 11 = 4
For key = 70
Hashkey(key) = (70*70+3) % 11 = 4903 % 11 = 8
For key = 3
Hashkey(key) = (3*3+3) % 11 = 12 % 11 = 1
Here, the chaining is performed at positions 4 and 7 as the collision is detected.
Linear probing: probe(i) = (i+1) % 11
3
0
12
9
70
0 1 2 3 4 5 6 7 8 9 10
In linear probing, the collision is resolved by placing the new key into closest following empty cell.
In the previous exercise, the chaining is done for the keys which are colliding with the existing positions. In the present strategy, the keys which are colliding that is 1, 98 and 42 are placed in the adjacent closest bucket like: 1 is placed at position 5th, 98 is placed at the position 6th and 42 is placed at the position 9th. The position of the elements in the buckets is as follows:
3
0
12
1
98
9
70
42
0 1 2 3 4 5 6 7 8 9 10
Quadratic probing
probe(i) = (i* i + 5) % 11
42
0
12
3
9
70
1
98
0 1 2 3 4 5 6 7 8 9 10
3
0
12
9
70
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.