Problem 83

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# Perfect hashing example

Due: April 19
Points: 3

Use the FKS "perfect hashing" data structure, along with Carter & Wegman universal hash functions, to construct a data structure to store the following set of 7 three-digit numbers:

[535, 71, 168, 353, 950, 883, 618]

Show the top-level hash function and table, and then show each of the second-level hash tables, along with each of the second-level hash functions.

Note: In real perfect hashing, you would keep choosing random hash functions at the top level until the size of each bucket is less than $$(\log n)/(\log\log n)$$. Well this works out to less than 2 for $$n=7$$, so that wouldn't be very interesting. So just pick a random top-level hash function and stick with it, even if there are some large buckets. Of course, you do still need to choose the second-level hash functions so that there are no collisions.