CS110 Homework [3]

发表于 更新于 分类于 ,
本文字数: 3.7k 阅读时长 ≈ 23 分钟

Fetch the homework here on Github classroom, you will use Github for version control and Gradescope for submission.

Homework 3

Computer Architecture I @ ShanghaiTech University

FKS Perfect Hash

In this homework, you are going to implement a FKS perfect hash.

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 nn keys in that slot, its size should be n2n^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

3.1 Static Library

In the Makefile, complete the rules $(STATIC_LIB): $(STATIC_OBJS) and test_fks_static: test_fks.c $(STATIC_LIB).

For $(STATIC_LIB): $(STATIC_OBJS), a $(STATIC_LIB) (./build/libhash.a) should be created from $(STATIC_OBJS).

For test_fks_static: test_fks.c $(STATIC_LIB), a static linked binary $(STATIC_BIN)(/build/test_fks_static) should be create from test_fks.c and the $(STATIC_LIB)

Make sure that $(STATIC_BIN) does not have any shared objects dependencies. That is, ldd ./build/test_fks_static should return not a dynamic executable.

3.2 Shared Library

In the Makefile, complete the rules $(SHARED_LIB): $(SHARED_OBJS) and test_fks_shared: test_fks.c $(SHARED_LIB).

For $(SHARED_LIB): $(SHARED_OBJS), a $(SHARED_LIB) (./build/libhash.so) should be create from $(SHARED_OBJS).

For test_fks_shared: test_fks.c $(SHARED_LIB), a dynamic linked binary $(SHARED_BIN)(/build/test_fks_shared) should be created from test_fks.c and the $(SHARED_LIB)

Make sure that $(SHARED_BIN) have shared object dependency to $(SHARED_LIB). That is, the output of ldd ./build/test_fks_dynamic should include libhash.so => ./build/libhash.so.