# 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.