Hashing Lab

Objectives

The goal of this lab is to gain experience with hashing and to implement a basic Map ADT based on a hash table.

Introduction

Download the following files:

Look over the code in the hash_map 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 tests. If you run this module without modification it should produce a NotImplementedError.

Exercises

  1. 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 _get_node helper method.
  2. Modify your __setitem__ method so that rehashing occurs when the load factor exceeds LOAD_FACTOR. Rehashing should be implemented in the provided _rehash helper method. 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.

    Hint:
    • You should use the _next_prime function to find appropriate primes.
  3. 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 0.1? 10? 100?
  4. (Optional) Implement __delitem__ and pop. These are slightly more challenging. However, their behavior is nearly identical; the only difference is that pop returns the value associated with the key it removes while __delitem__ does not. Recall that removing items from a linked list requires you to locate both the node to be removed, and the node that precedes it.

Submission

This lab will serve as the basis for part of a homework assignment. Make sure you keep a copy of your code for future reference and submission. If you would like to discuss your solution or any problems you encounter while working on this lab, please come to office hours or make an appointment.