Finding the average running time of search in hash tables with chaining.
Felipe Vicencio-Heap October 21, 2019
Instead of finding the average number of elements in each slot, we will
look at the related problem of finding the average running time of search.
We have hash table T with slots 0 to m − 1, slot i has Li elements, a universe
called U , and a simple uniform hashing function h : U → {0, .., m − 1}. Thus
we know that the load factor α = n after inserting n elements, and that m
Pr[h(x) = i] = Pr[x] = 1 . We define the random variable N(x)
m
x∈U,h(x)=i
to be the number elements inspected when searching for x. The average running time of search(x) is:
E [s(x)] = Pr[x]·N(x) (1) x∈U
m−1
=( Pr[x]·N(x)) (2)
i=0 x∈U,h(x)=i m−1
≤( Pr[x]·Li) (3) i=0 x∈U,h(x)=i
m−1
=Li( Pr[x]) (4)
i=0 x∈U,h(x)=i m−1 1
= Li m i=0
1 m−1 n
(5)
= Li= =α (6)
m
m i=0
1
If we restrict the probability space to only x ∈ T we can do a similar analysis.
Due to our simple uniform hashing assumption we know that the probability
that x is the j-th element in slot Li, Pr[Li[j] = x] is 1 , Li
and P r[h(x) = i] = Li . We are further assuming that Li = α. n
E[s(x)] = Pr[x] · N(x) (7) x∈T
m−1 Li
= ( P r[h(x) = i] · j · P r[Li[j] = x]) (8)
i=0 j=1
m−1 L Li j
=(i ) (9) i=0 n j=1 Li
1m−1 Li
= j (10) n i=0 j=1
1 m−1 L (L + 1) =ii
(11) = 2 n ( L 2i + L i ) (12)
n i=0 2 1 m−1
m−1 i=0 i=0
1 m−1
= ( α2) +
1 2
(13)
2n i=0
m−1
1 1n2
=2+2ni=0 m2 (14) m−1
=1+ 1 n2 1 (15)
=1+n=α+1 (16) 2 2m 2
2
2 2nm2
i=0