This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
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.