This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 73

Perfect hashing example

Due: March 29
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 might keep choosing random hash functions at the top level until the number of collisions is \(O(n)\), and then go through and choose all the second-level hash functions after that. Well, for this small size that's not going to be very interesting. So just choose one random top-level hash function, and then do the repeated choices at the second level until every item ends up in its own bucket.