Introduction to Algorithms, Third Edition

Corollary 11.7
Inserting an element into an open-address hash table with load factor
˛
requires at
most
1=.1
˛/
probes on average, assuming uniform hashing.

---

276
Chapter 11
Hash Tables
Proof
An element is inserted only if there is room in the table, and thus
˛ < 1
.
Inserting a key requires an unsuccessful search followed by placing the key into the
first empty slot found. Thus, the expected number of probes is at most
1=.1
˛/
.
We have to do a little more work to compute the expected number of probes for
a successful search.
Theorem 11.8
Given an open-address hash table with load factor
˛ < 1
, the expected number of
probes in a successful search is at most
1
˛
ln
1
1
˛
;
assuming uniform hashing and assuming that each key in the table is equally likely
to be searched for.
Proof
A search for a key
k
reproduces the same probe sequence as when the
element with key
k
was inserted. By Corollary 11.7, if
k
was the
.i
C
1/
st key
inserted into the hash table, the expected number of probes made in a search for
k
is at most
1=.1
i=m/
D
m=.m
i /
. Averaging over all
n
keys in the hash table
gives us the expected number of probes in a successful search:
1
n
n
1
X
i
D
0
m
m
i
D
m
n
n
1
X
i
D
0
1
m
i
D
1
˛
m
X
k
D
m
n
C
1
1
k
1
˛
Z
m
m
n
.1=x/ dx
(by inequality (A.12))
D
1
˛
ln
m
m
n
D
1
˛
ln
1
1
˛
:
If the hash table is half full, the expected number of probes in a successful search
is less than
1:387
. If the hash table is
90
percent full, the expected number of probes
is less than
2:559
.

---

11.5
Perfect hashing
277