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 Movie code and data.

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

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

    Print out a list of all the Food keys and the resulting hash values and slots (for the slot assume there are seven slots to choose from) in the following format:

    Hashes
    Hash     Slot Key
    ======== ==== ====================
         695    2 Lasagna, 7
        1355    4 Butter Chicken, 2
        1284    3 Moo Goo Guy Pan, 1
        1521    2 Vegetable Alicha, 3
    ...
    

    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
    
    Name:       Spring Rolls
    Origin:     Chinese
    Vegetarian: True
    Calories:   200
    
    Name:       Chicken Kabob
    Origin:     Indian
    Vegetarian: False
    Calories:   167
    
    ...
    

    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: