Imperial College London – Department of Computing
MSc in Computing Science
580: Algorithms
Tutorial: Hash Tables
1. An open address hash table T has m = 12 slots and uses the hash function h(k) =
k mod m. Assuming collisions are resolved using linear probing, draw the table after
inserting the following keys, in this order: 82, 7, 47, 17, 49, 150, 34, 61, 107, 6.
2. A hash table T has a constant load factor, uses a hash function h and the chaining method
of collision resolution. Assume the following non-uniform hashing: the probability of a
key k hashing to h(k) = 1 is 1/2; the probabilities of k hashing to any other slot are all
equal. What is the expected time complexity for an unsuccessful search if T contains N
objects?
1