CP164 Lab 9 : Hash Sets

Week of

The Hash_Set

Hash_Sets were discussed in detail in lecture. In lab you will complete the Hash_Set ADT. The file Hash_Set_array.py contains the array-based implementation of the Hash_Set ADT. You also need your List implementation List_array.py, and Food code and data.

  1. Add the following method to your Movie class implementation. (Replace any existing method if necessary.)

        def __hash__(self):
            """
            -------------------------------------------------------
            Generates a hash value from a movie name.
            Use: h = hash(movie)
            -------------------------------------------------------
            Returns:
                returns
                value - the total of the characters in the name string
                    multiplied by the year (int > 0)
            -------------------------------------------------------
            """
            value = 0
    
            for c in self.title:
                value = value + ord(c)
            value *= self.year
            return value
    

    Write and test the following function:

    def hash_table(slots, values):
        """
        -------------------------------------------------------
        Print a hash table of a set of values. The format is:
    Hash     Slot Key
    -------- ---- --------------------
     1652346    3 Dark City, 1998
      848448    6 Zulu, 1964
        Do not create an actual Hash_Set.
        -------------------------------------------------------
        Parameters:
           slots - the number of slots available (int > 0)
           values - the values to hash (list of ?)
        Returns:
           None
        -------------------------------------------------------
        """
    

    Add this function to the PyDev module functions.py .

    Use this function to print out a list of all the Movie keys and the resulting hash values and slots - assuming that there are seven slots to choose from - in the following format:

    Hashes
    Hash     Slot Key
    -------- ---- --------------------
     1652346    3 Dark City, 1998
      848448    6 Zulu, 1964
     1810314    2 I Am Legend, 2007
     2306070    4 Omega Man, The, 1971
    ...
    

    Test functions.py:


  2. Implement and test the Hash_Set insert and remove methods.

    Test Hash_Set_array.py:


  3. Implement and test the Hash_Set debug method. It must print out the contents of a Hash_Set clearly indicating what slot a List of values belongs to, something like the following:

    7 slots
    
    ----------------------------------------
    Slot 0
    
    Title:    Broken Flowers
    Year:     2005
    Director: Jim Jarmusch
    Rating:   7.2
    Genres:   romance, comedy
    
    ----------------------------------------
    Slot 1
    
    ----------------------------------------
    Slot 2
    
    Title:    Juno
    Year:     2007
    Director: Jason Reitman
    Rating:   7.7
    Genres:   romance, comedy
    
    ...
    

    Test Hash_Set_array.py:


  4. Implement and test the Hash_Set rehash method. Use a change factor of 2 ×— current slots + 1 . Use debug to display the new slots.

    Test Hash_Set_array.py: