CSCE 2014 - Laboratory Assignment 11

    This laboratory assignment focuses on hash tables. As we will see, well designed hash tables can provide constant time access to data, which is significantly better than the O(logN) time access that binary trees provide. The remainder of this lab goes into the the implementation and use of hash tables in more detail.

  1. Introduction to Hash Tables
  2. The basic idea behind hash tables is to use the data value itself to decide where to store and retrieve data records. We do this by using a hash function that maps between data values and table locations. For example, if hash function for the string "hello" is equal to 42, we would store the string "hello" in position 42 in the table. This makes it very easy to add "hello" to the hash table, and also very easy to look up this data record at a later time.

    Hash functions can be created for a wide variety of data types (strings, integers, floats, etc.) by any combination of arithmetic operations that yields a value between [0..SIZE-1] where SIZE is the size of the hash table. Hash functions are typically "many to one", meaning that there are many data values that could produce the same hash value. For example, "elephant" could also have a hash value of 42. If this happens, there is a collision in the hash table when we try to insert both strings in the table. We must design hash table implementations to deal with this situation.

  3. The HashTable Class
  4. Consider the following declaration of the HashTable class. You will see that the class has four public operations: Insert, Search, delete, and Print. You will also see that there are two private methods Hash and Hash2. The private data for the hash table is stored in two dynamically allocated arrays of integers called "Value" and "Key". The size of the hash table is in the private integer "Size".

    //-----------------------------------------------------------
    //  Purpose:    Header file for the HashTable class.
    //  Author:     John Gauch
    //-----------------------------------------------------------
    
    #include < iostream >
    using namespace std;
    const int NONE = 0;
    const int EMPTY = -1;
    const int DELETED = -2;
    
    //-----------------------------------------------------------
    // Define the HashTable class interface
    //-----------------------------------------------------------
    class HashTable
    {
    public:
       // Constructors
       HashTable(int size);
       HashTable(const HashTable & ht);
       ~HashTable();
    
       // Methods
       bool Insert(int key, int value);
       bool Search(int key, int &value);
       bool Delete(int key);
       void Print();
    
    private:
       // Private methods
       int Hash(int key);
       int Hash2(int index);
    
       // Private data
       int Size;
       int *Value;
       int *Key;
    };
    

  5. HashTable Implementation
  6. Consider the implementation of the HashTable class below. The constructor function allocates two arrays of integers of length "Size" and initializes these arrays to EMPTY. The destructor function releases this memory when you are finished using your HashTable objects.

    The "Insert" method calls the private method "Hash" to determine where to store the (key, value) pair. If this array location is already occupied, the method calls "Hash2" to search for an empty location. This collision handling technique is called linear probing.

    The "Search" method also calls "Hash" and "Hash2" to locate the requested (key, value) pair. The Search method returns true if the key is found in the hash table, and false otherwise.

    The "Delete" method first calls "Hash" and "Hash2" to locate the requested key in the hash table. If found, the key is changed to DELETED to indicate that this (key, value) pair has been removed from the table. This method also returns true if the key is found in the hash table, and false otherwise.

    //-----------------------------------------------------------
    //  Purpose:    Implementation of HashTable class.
    //  Author:     John Gauch
    //-----------------------------------------------------------
    #include "hash.h"
    
    //-----------------------------------------------------------
    // Constructor
    //-----------------------------------------------------------
    HashTable::HashTable(int size)
    {
       Size = size;
       Value = new int[Size];
       Key = new int[Size];
    
       for (int index=0; index < Size; index++)
       {
          Value[index] = NONE;
          Key[index] = EMPTY;
       }
    }
    
    //-----------------------------------------------------------
    // Copy constructor
    //-----------------------------------------------------------
    HashTable::HashTable(const HashTable & ht)
    {
       Size = ht.Size;
       Value = new int[Size];
       Key = new int[Size];
    
       for (int index=0; index < Size; index++)
       {
          Value[index] = ht.Value[index];
          Key[index] = ht.Key[index];
       }
    }
    
    //-----------------------------------------------------------
    // Destructor
    //-----------------------------------------------------------
    HashTable::~HashTable()
    {
       delete []Value;
       delete []Key;
    }
    
    //-----------------------------------------------------------
    // Insert method
    //-----------------------------------------------------------
    bool HashTable::Insert(int key, int value)
    {
       // Find desired key
       int index = Hash(key);
       while ((Key[index] != key) && (Key[index] != EMPTY))
          index = Hash2(index); 
    
       // Insert value into hash table
       Value[index] = value;
       Key[index] = key;
       return true;
    }
    
    //-----------------------------------------------------------
    // Search method
    //-----------------------------------------------------------
    bool HashTable::Search(int key, int &value)
    {
       // Find desired key
       int index = Hash(key);
       while ((Key[index] != key) && (Key[index] != EMPTY))
          index = Hash2(index); 
    
       // Return value from hash table
       if (Key[index] == key)
          value = Value[index];
       return (Key[index] == key);
    }
    
    //-----------------------------------------------------------
    // Delete method
    //-----------------------------------------------------------
    bool HashTable::Delete(int key)
    {
       // Find desired key
       int index = Hash(key);
       while ((Key[index] != key) && (Key[index] != EMPTY))
          index = Hash2(index); 
    
       // Delete value from hash table
       if (Key[index] == key)
       {
          Value[index] = NONE;
          Key[index] = DELETED;
          return true;
       }
       return false;
    }
    
    //-----------------------------------------------------------
    // Primary hash function
    //-----------------------------------------------------------
    int HashTable::Hash(int key)
    {
       return key % Size;
    }
    
    //-----------------------------------------------------------
    // Secondary hash function
    //-----------------------------------------------------------
    int HashTable::Hash2(int index)
    {
       return (index+1) % Size;
    }
    
    //-----------------------------------------------------------
    // Print function for debugging
    //-----------------------------------------------------------
    void HashTable::Print()
    {
       cout << "Index\t" << "Value\t" << "Key\n";
       for (int index=0; index < Size; index++)
          cout << index << "\t"
               << Value[index] << "\t" 
               << Key[index] << "\n";
    }
    
    //-----------------------------------------------------------
    // Main program.
    //-----------------------------------------------------------
    int main()
    {
       // ADD HERE
    }
    

  7. Testing the HashTable Class
  8. Copy and paste the class declaration above into a file called "heap.h" and the class implementation into a file called "heap.cpp" and compile and run this program in NetBeans.

    Now extend the main function to create a HashTable object of SIZE=20. Then write a loop to insert COUNT=10 (key, value) pairs into the hash table with random values between [0..MAX-1] where MAX=100. Call the "Print" method to see what your hash table looks like.

    Cut and paste your new main function below:

    Cut and paste your program output below:

  9. Detecting Collisions
  10. Edit your program to prompt the user for three input values: SIZE, COUNT, and SIZE and use these values in your main function. Repeat the experiment with SIZE=20, COUNT=15, and MAX=100. You should see several (key, value) pairs with the same last digit in consecutive hash table locations. These are the result of collisions.

    Go into your code and edit the "Hash2" function to print out a message every time it is called to handle a collision. Run an experiment with SIZE=40, COUNT=15, and MAX=100. There should be fewer collisions than you had above. Run another experiment with SIZE=40, COUNT=30, and MAX=100. You should see an increase in the number of collisions.

    Run a series of experiments with SIZE=40 and MAX=100 to fill in the table below. Be careful to keep COUNT < SIZE, in your experiments or your program may go into an infinite loop. If you do end up with an infinite loop, kill your program quickly to save CPU cycles.

  11. Fixing the Insert Method
  12. As noted above, it is possible for the "Insert" method to go into an infinite loop if the table runs out of empty locations. There are several ways to fix this problem.

    Choose one of the methods above, and go into your code to fix the infinite loop problem. When you think you have it working, test your code with SIZE=40 and COUNT=50 to verify that it works properly. If you do end up with an infinite loop, kill your program quickly to save CPU cycles.

    Cut and paste your new "Insert" method below:

    Cut and paste your new program output below:

  13. Submit Work
  14. This lab assignment will be submitted electronically to the TAs once you fill in the fields below and click on the "submit" button. You do NOT need to print a copy of this document to hand in.

    Your UAID number:
    Your website PASSWORD: