In-Class Activity: HashMap

Recommended Steps

1. Download the following files:
   • hashmap.py
   • time_hashing.py
   Look over the code in the hashmap module. Several utility methods are already completed, including iterators and __repr__. However, none of the methods for inserting or searching in the map are written. There is a main function that runs several quick tests. If you try to run this module you should see a NotImplementedError.
2. Complete the implementation of the __contains__, __getitem__, and __setitem__ methods according to the provided docstrings. For now, don't worry about re-sizing the hash table when MAX_LOAD is exceeded. When these methods are correct, the module should produce the following output when executed:

   No assertions! Looks good.
   

   
   Hint:
   • Each of these methods will be easier to write if you first complete the _getNode helper method.
3. Modify your __setitem__ method so that rehashing occurs when the load factor exceeds LOAD_FACTOR. The new size should be a prime number around twice the size of the current table. When you have completed the code, rerun the module to make sure that it still passes the tests.
   Hints:
   • Rehashing should be handled by a new helper method.
   • You may use the _nextPrime function to find appropriate primes.
4. Read over time_hashing.py and then run it. Do the results make sense? What happens when you change the load factor from 1.0 to .1? 10? 100?
5. (If you have time.) Implement __delitem__ and pop. These are slightly more challenging. Recall that removing items from a linked list requires you to locate both the node to be removed, and the node that precedes it.