Class Notes: Data Structures and Algorithms

Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344

Instructor: M.S. Schmalz -- TAs: TA Mailing List

Homework #9 -- Due Fri 30 July 1999 : 09.30am

Note: The detailed analysis required in Questions 4-6 will not be on the final exam, due to time constraints.

• Question 1. Short answer questions (1 point each):
  (a) Why are hash tables useful?

  (b) What are the limitations of hash tables?

  (c) Explain the collision problem in closed hashing.

  (d) Given N data stored in a hash table with B buckets, explain why N/B represents the average number of data per bucket.

• Question 2. Short answer questions:
  (a) [2 points] Compare and contrast open and closed hashing.

  (b) [1 point] List the disadvantages of closed hashing in detail.

  (c) [1 point] What is rehashing and how is it used?

• Question 3. Given a linear rehash h_i(x) = (h(x) + (c · i)) mod B, applied to a hash table that has N data and B buckets:
  (a) [2 points] What are bad choices for the constant c? Express your answer in terms of N and B.

  (b) [2 points] What are two successful strategies for choosing c? Illustrate each choice with a diagram of the hash table that shows both successful and unsuccessful probes.

• Question 4. Given the cost analysis of hashing discussed in class, apply this to a two-level closed hashing scheme, where the first level has B₁ buckets and each hash table in the second level has B₂ buckets. The entire hash scheme is designed to store N data.
  (a) [2 points] What are reasonable constraints on B₁ and B₂ with respect to N, to achieve < 2 probes per successful table access? You must state your assumptions to receive full credit.

  (b) [2 points] How full should the first and second level tables be to generate two or fewer probes per access at each level of the hashing scheme?

• Question 5. Given the assumptions in Question 4:
  (a) [2 points] Formulate an equation for the efficiency of a two-level closed hashing scheme.

  (b) [2 points] Graph the number of probes as a function of the fill factor a_i = N_i/B_i, where i = 1..2. Here, N_i denotes the number of data stored at level i of the hashing scheme. List 5-8 data points (as pairs), so their values can be checked.

  Hint: Recall the hash table efficiency graphs that we discussed in class.

• Question 6. Given the assumptions in Question 4 and the equations for the number of probes as a function of N and B, which we discussed in class:
  (a) [2 points] Generalize the equations for an M-level table, using N_i and B_i, where i = 1..M . The result of this effort should be an expression for number of probes per level as a function of fill factor.

  (b) [2 points] Graph the number of probes as a function of the fill factor a_i for each level, where M = 4. List 5-8 data points (as pairs), so they can be checked.

Copyright © 1999 by Mark S. Schmalz.