Exercise 8: Open Addressing

Objectives

Assignment

The implementation of gmap used with the Chomp executable has been replaced with an implementation that uses open addressing to resolve collisions. Implement the gmap_remove function to remove a key and its associate value from the map. The gmap_remove function should run in $O(1)$ expected time, assuming that the distribution of keys and the hash function are such that the hash values of the keys are distributed randomly and uniformly across the range of size_t.

Code

The code given in /c/cs223/hw8/Optional/gmap.c implements a map using open addressing. You can combine it with your chomp_main.c from the previous exercise and the files in /c/cs223/hw8/Required to build the Chomp executable, which should then work as it did in the previous exercise.

The /c/cs223/hw8/Required/gmap.h specifies another function that has been added to the Map ADT: gmap_remove. To implement this function, you should find the slot containing the key and, if the key is actually present, free the key, set it to NULL, but leave the entry marked as used so the gmap functions can still find keys that collided with the one just removed that will be stored in later slots in the hash table. It will be helpful to keep track of the number of slots that have had keys removed from them but have not been reused yet.

Modify the other functions to account for slots that have had keys deleted from them. The loop in gmap_table_find_key that implements sequential search to find the slot containing a given key will have to skip over deleted slots.

The test in gmap_put that determines whether the key was already present will have to account for deleted slots. That function should also resize the hash table if the sum of the number of currently used slots plus the number of deleted slots gets too large.

The loops in gmap_embiggen, gmap_for_each, and gmap_destroy will also have to account for deleted slots.

Optional Enhancements

Modify gmap_put so that it reuses a deleted slot if it finds one when searching for the key to add and the key is not present.

Modify gmap_remove so that it resizes the hash table when the load factor gets too small.

Testing

Since the Chomp executable does not use gmap_remove, there is a suite of unit tests for gmap in /c/cs223/hw8/Required/gmap_unit.c from which you should build the GmapUnit executable.

Submissions

Submit your modified gmap.c files, your previous chomp_main.c, any other files you created, and your makefile with the Chomp executable as the default target and additional target GmapUnit as assignment number 8. You need not submit the other given files, and your makefile should assume they have been copied into the current directory rather than that they are in their original locations.