CHAPTER 9
Hashing Functions: Examples and Evaluation
9.1 OVERVIEW: THE TRADEOFF OF RANDOMIZATION VERSUS COMPUTATIONAL SIMPLICITY
The models of collision-resolution protocols to be described in the remaining chapters of Part II assume that the hashing function h : 
→ 
n is uniformly
distributed; that is, 
for 0 ≤ iN. It seems appropriate before
embarking on this examination to provide some examples. Because the rationale of hashing is the time/space-trade-off, a hashing function must be easy to compute; this limits the possible choices.
We assume each record requires a unit cell in the hash table that contains space for N record entries. The hash table provides the connection between the m-bit key and the true address in memory of the record. The cell h(k) in hash table contains the pair (k, ADD[k]), where ADD[k] is the true address of the record with key k ∈ and h is a hashing function
(9.1)
is the key space and N = {0, 1, · · · , N − 1} identify the cells in the hash table. Often, ...
