Perfect hashing exampleDue: March 29
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.