Hashing in Computer Science: Fifty Years of Slicing and Dicing

Exercises and Solutions

PART II, CHAPTER 7

Exercise 7.1. (Model for performance evaluation of simple storage).

Assume the following:

• m records R₀, R₁, · · · , R_m−1, each requiring for storage a single cell (1 unit), have been stored in a block of n contiguous cells with starting address A.
• If an existing record is selected for access, then each of the m records is chosen with equal probability.

The procedure SEARCH(k) to locate the record with key k = KEY requires a C comparison.

7.1a) Calculate the probability distribution and average number of C needed to execute SEARCH(k) if such the record with key k = KEY is currently in storage.

7.1b) Assuming that no record with key k = KEY has been stored, calculate the average number of comparisons needed to execute SEARCH(k).

Solution.

Let C he number of comparisons used by SEARCH(k) to locate the record with key k = KEY assuming it has already been stored. Since this record may be any of the m records in the single chain with equal probability

(Ex7.1a)

and

(Ex7.1b)

In 7.1b, C = m + 1 comparisons are needed by SEARCH(k) since all of the keys in the records in the chain need to be tested.

PART II, CHAPTER 8

Exercise 8.1.

Assume the following: ...