Consider search keys that are distinct integers. If the hash function is h(key) = key modulo 5
Question:
Consider search keys that are distinct integers. If the hash function is h(key) = key modulo 5 and separate chaining resolves collisions, where in the hash table do the following search keys appear after being added?
list a= 4, 6, 20, 14, 31, 29
index | bucket |
[0] | |
[1] | |
[2] | |
[3] | |
[4] |
hushTable
2. Using the same problem #8, use the hash function h(key) = key modulo 11 with a hashTable size eleven and
a) Linear probing to resolve collisions.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
b) Quadratic probing.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
c) Double hashing. h2(key) = 7 - ( key mod 7)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
(Continued next page.)
3. Using a list with more collisions, the same hash function, and the respective collision resolutions, show the resulting hashTables.
h(key) = key mod 11 list = 4, 6, 15, 26, 8, 5
a) Linear probing to resolve collisions.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
b) Quadratic probing.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
c) Double hashing. h2(key) = 7 - ( key mod 7)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
index | bucket |
[0] | |
[1] | |
[2] | |
[3] | |
[4] |
d) Separate chaining. h(key) = key mod 5
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest