CHAPTER 15

Optimum Hashing

15.1 THE ULLMAN–YAO FRAMEWORK1

Ullman [Ullman 1972] conjectured that uniform hashing minimizes the expected SEARCH-cost in the class of open-addressing schema. A proof of his conjecture appeared 13 years later in Yao’s paper [Yao 1985], an exposition of which is the subject of this chapter.

15.1.1 The Ullman–Yao Hashing Functions

The hashing functions h in Chapters 10 to 13 were modeled as integer-valued mappings h: x1D4A6_EuclidMathOne_10n_000100 → x1D4B5_EuclidMathOne_10n_000100n from the set of keys x1D4A6_EuclidMathOne_10n_000100 to hash-table (HT) cells HTi with i ∈ x1D4B5_EuclidMathOne_10n_000100n. Double hashing (DH) (Chapter 14) extended the definition of a hashing function h → (h1, h2); the domain remained unchanged, but the range h(k) specified a probe sequence, which is a sequence of cells generated by an arithmetic progression. If (h1(k), h2(k)) = (i, c), then

c15ue001

  • The choice of the initial cell HTi into which an attempt to insert the k would be made.
  • In the event of a collision, the order that the cells should be probed thereafter.

Ullman made another extension in [Ullman 1972] ...

Get Hashing in Computer Science: Fifty Years of Slicing and Dicing now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial