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.
Answer:
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?
Answer: If T currently has m slots, the probability that an object x is in the chain
T [i] is
P{i} =
{
0.5 when i = 1
0.5/(m− 1) otherwise
So, the expected length of the chain at T [i] is
l[i] =
{
N/2 when i = 1
N/2(m− 1) otherwise
The probability that the search key k will hash to i is the same as the probability that
x will be found in T [i]. So, the expected number of keys that k will be compared to
is:
N
4
+
m∑
i=2
N
4(m− 1)2
=
N
4
+
N
4(m− 1)
Since T has a constant load factor, N/4(m−1) is also constant. So, the time complexity
of an unsuccessful search is
N
4
+ Θ(1) = Θ(N).
1