CMSC 341 — Data Structures — Fall 2013

Homework 6

Due Dates:

• Sections 1 & 3: Thursday, November 21, in class.
• Sections 2 & 4: Monday, November 25, in class.

1. Hash the values 23, 25, 36, 54, 15, 43, 65 and 34 (in that order) into a hash table with 11 slots indexed from 0 to 10 (inclusive) using the hash function h( x ) = x mod 11 and each of the following collision resolution methods. For each collision resolution method, draw the resulting hash table after all the items have been inserted.

   1. Separate chaining.
   2. Linear probing.
   3. Quadratic probing.
   4. Double hashing using h₂( x ) = 5 − ( x mod 5 ).

2. Consider the sample output given with Project 4:

   Primary hash table statistics: Number of cities: 15937 Table size: 16000 Max collisions = 6 # of primary slots with 0 cities = 5958 # of primary slots with 1 cities = 5801 # of primary slots with 2 cities = 2965 # of primary slots with 3 cities = 963 # of primary slots with 4 cities = 260 # of primary slots with 5 cities = 41 # of primary slots with 6 cities = 12 # of primary slots with 7 cities = 0 # of primary slots with 8 cities = 0 # of primary slots with 9 cities = 0 # of primary slots with 10 cities = 0 ...

   The data indicates that 5,958 of the 16,000 slots in the primary hash table (or about 37% of the slots) are empty. Let's consider if this is reasonable. Suppose that a hash function h( ) had equal probability of hashing an item x into any of the 16,000 slots. (This assumption is called "simple uniform hashing" and is considered ideal behavior for hash functions.)

   1. For a given slot in the primary hash table, what is the probability that the slot remains empty after all 15,937 cities have been inserted in the hash table using h( )? Show your work.
   2. What is the expected number of slots that would remain empty after all 15,937 cities have been inserted in the hash table using h( )? Show your work.
   3. What is the expected number of slots that have exactly 1 city? Show your work.
   4. What is the expected number of slots that have exactly 2 cities? Show your work.

3. Again, consider the sample output given with Project 4, shown above. What is the total number of slots used by all of the secondary hash tables for a hash table constructed using the perfect hashing scheme described in Section 5.7.1 of the textbook (and in the project description)? How does this compare with the expected value predicted in the textbook?