Task1: Chained Hash Table#

To begin, you need to build a hash table that resolves collisions with chaining in the hash_chaining.c file.

The hash_chaining struct requires the hash_parameters member, which should be generated by calling the generate_hash_parameters() function from the hash_parameters.c file.

Additionally, you should use the hash_func function defined in the hash_func.c file as your hash function. This function takes a key, hash parameters, and the size of the hash table (m) as input, and returns an integer x between 0 and m-1. The key should then be placed in the corresponding slot at index x in the hash table.

Task2: FKS Perfect Hash#

You are suggested to read https://www.cs.otago.ac.nz/cosc242/pdf/L11.pdf page 25-40 before you continue.

After building the chained hash table, you need to complete the FKS (Fredman, Komlós and Szemerédi) perfect hash (fks_level1.c fks_level2.c).

Instead of resolving collisions with linked lists, the perfect hash use small secondary hash tables that map each key in the hash table to a unique index in an array. The FKS perfect hash function guarantees that there are no collisions among the keys, resulting in constant-time lookups.

When implementing the fks_level1_build() function to build the Level 1 hash table for the FKS perfect hash, you should follow these steps:

• Use the same hash parameters and table size as the chained hash table: Since you’re leveraging the existing chained hash table as the Level 1 hash table for the FKS perfect hash, you should use the same hash function parameters and table size as the chained hash table.

• Create Level 2 hash tables for non-empty slots: Iterate through each slot (linked lists) in the chained hash table. For non-empty slots, create a small secondary hash table (fks_level2) to handle the collisions within that slot. Assume there are $n$ keys in that slot, its size should be $n^2$. For empty slots in fks_level2, their values should be FKS_LEVEL2_EMPTY. Its hash parameters should also be generated by calling the generate_hash_parameters() function. When there are collisions in Level 2 hash table, regenerate hash parameters and try again. For empty slots in the Level 1 hash table, its corresponding level2_tables[i] should be NULL.

Task3: Creating and linking with static/shared libraries#