[SOLVED] algorithm chain Imperial College London Department of Computing

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(m1) is also constant. So, the time complexity
of an unsuccessful search is

N

4
+ (1) = (N).

1