Hash tables - Data Structures and Problem Solving Using Java - page 805

statement. The statement numbers in the input might be as large as a 32-
bit integer, and you may assume that the renumbered statement numbers
fit in a 32-bit integer. Your program must run in linear time.

references

Despite the apparent simplicity of hashing, much of the analysis is quite dif-
ficult and many questions remain unresolved. Also there are many interesting
ideas that generally attempt to make it unlikely that worst-case possibilities of
hashing arise.
An early paper on hashing is [11]. A wealth of information on the subject,
including an analysis of hashing with linear probing, is presented in [6]. Dou-
ble hashing is analyzed in [5] and [7]. Yet another collision resolution scheme,
coalesced hashing, is described in [12]. An excellent survey on the subject
is [8], and [9] contains suggestions for and pitfalls in choosing hash functions.
Precise analytic and simulation results for all the methods described in this
chapter are available in [4]. Uniform hashing, in which no clustering exists, is
optimal with respect to the cost of a successful search [13].
If the input keys are known in advance, perfect hash functions, which do
not allow collisions, exist [1]. Some more complicated hashing schemes, for
which the worst case depends not on the particular input but on random num-
bers chosen by the algorithm, appear in [2] and [3]. These schemes guarantee
that only a constant number of collisions occur in the worst case (although
construction of a hash function can take a long time in the unlikely case of
bad random numbers). They are useful for implementing tables in hardware.
One method of implementing Exercise 20.7 is described in [10].

1.

J. L. Carter and M. N. Wegman, “Universal Classes of Hash Func-
tions,” Journal of Computer and System Sciences 18 (1979), 143-154.

2.

M. Dietzfelbinger, A. R. Karlin, K. Melhorn, F. Meyer auf def Heide, H.
Rohnert, and R. E. Tarjan, “Dynamic Perfect Hashing: Upper and Lower
Bounds,” SIAM Journal on Computing 23 (1994), 738-761.

R. J. Enbody and H. C. Du, “Dynamic Hashing Schemes,” Computing
Surveys 20 (1988), 85-113.

3.

G. H. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data
Structures, 2d ed., Addison-Wesley, Reading, MA, 1991.

4.

L. J. Guibas and E. Szemeredi, “The Analysis of Double Hashing,” Jour-
nal of Computer and System Sciences 16 (1978), 226-274.

5.

D. E. Knuth, The Art of Computer Programming, Vol 3: Sorting and
Searching, 2d ed., Addison-Wesley, Reading, MA, 1998.

6.