Setup

You MUST work solo on this project! You may not collaborate at all with anyone else! Please use the SSH link found at the picture after clicking the link in the registration email:

Bugfixing

Task 0. Bring over ll.c and fixed_size_hashtable.c into the library directory.

Additionally, in fixed_size_hashtable.c, rename hashtable_init to fixed_size_hashtable_init.

This week, we’ve added significantly more tests that exercise a variety of edge cases for dictionary implementations. Your code that passed the tests last week may not pass the new ones!

Task 1.

Fix any bugs that you may have in ll.c and fixed_size_hashtable.c so that make task0 passes.

Rehashing

It’s useful to have a hash table that can dynamically grow to store an arbitrary number of elements, not just a fixed initial capacity. When a hash table “becomes full”, it grows its backing array to be larger.

However, “becoming full” does not necessarily mean that the hash table is out of empty (or tombstone) slots. In our linear probing table, as we insert more and more elements, it becomes more likely that we have long probe sequences due to collisions and clustering. As a result, the hash table operations approach linear time, which defeats the point of a hash table!

To measure the fullness of a hash table, we use the load factor: the ratio of the number of key-value pairs in the dictionary to the length of the array. The maximum load factor for a linear probing hash table is 1, when every entry in the array is filled. However, performance significantly degrades as the load factor approaches 1. Thus, our hash tables should resize at a smaller load factor – we choose 0.5.

Task 2.

Copy your (debugged) functions from fixed_size_hashtable.c to hashtable.c.

Then, update your put implementation in hashtable.c so that the table size increases appropriately when necessary (load factor > 0.5). When you are done, run make task1 to check your implementation.