Assignment 6: Implementing a Map with a Hash Table

Objectives

• to implement a hash table

Assignment

Complete the implementation of the functions described in smap.h from the /c/cs223/hw6/Required/ directory. The functions define an Map ADT where the keys are strings and the values are pointers to ints. The functions should run in the following time bounds:

• smap_create: $O(1)$
• smap_size: $O(1)$ (worst case)
• smap_contains_key: $O(1)$
• smap_get: $O(1)$
• smap_put: $O(1)$
• smap_remove: $O(1)$
• smap_for_each: $O(n)$ (worst case, assuming f runs in $O(1)$ time)
• smap_destroy: $O(n)$ (worst case)

Where $n$ is the number of (key, value) pairs in the map and, unless otherwise noted, the running times are expected running times under the assumption that there is a bound on the length of the keys and 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 an int, and that malloc, free, etc. run in $O(1)$ time.

Additionally, smap_default_hash should run in $O(n)$ time where $n$ is the length of the string passed to it.

Your implementation should work with the main function in smap_unit.c also found in /c/cs223/hw6/Required/ along with the supporting smap_test_functions library and a makefile that builds an executable called Unit. The Unit executable runs a number of different unit tests and you can select one by passing its index on the command line. See the code for the unit tests for more details about each one.

Examples

[jrg94@lion ~]$ for N in 1 2 3 4 5 6 7 8 9 10 11 12 13 14; do echo $N; ./Unit $N; done
1
PASSED
2
PASSED
3
PASSED
4
PASSED
5
PASSED
6
PASSED
7
PASSED
8
PASSED
9
PASSED
10
PASSED
11
PASSED
12
PASSED
13
PASSED
14
PASSED

Submissions

Submit your source code necessary to build the executable using the provided makefile and supporting code. There is no need to submit the provided makefile, smap_unit.c or smap_test_functions files. Your makefile can assume that the supporting files have been copied into the current directory, but should not assume they are still in their original locations.