Lab 7: Hash Tables (100 pts)
Due Tuesday, May 24 as a soft copy at 1:00pm on Catalyst and as a hard copy at 1:30 in class.


Complete The Following Hash Table Functions, Testing Each One as You Go Along:

#ifndef HASHTABLE_H_
#define HASHTABLE_H_
#include <string>
#include <iostream>
#include <cstdlib>
using namespace std;

class HashTable {

public:
    HashTable();

    //~HashTable();
    //Will write as part of Lab 6

    int hash(string key);
    //returns the hash value for the given key
    //the hash value is the sum of
    //the ASCII values of each character % the table size
   
    void addItem(string title, string author, int isbn);
    //inserts a new item into the table
    // calls the hash function on the key title to determine the correct bucket
   
    //void removeItem(string key);
    //removes the item with the given key

    int numItemsAtIndex(int index);
    //Helper function to printTable
    //Counts the number of items in each bucket
   
    void printTable();
    //prints the first item of each bucket
    //includes the number of items stored at that bucket

    void printBucket(int index);
    //Prints all items stored at a single bucket
  
    int findAuthor(string title);
    //Searches for an author in the table using the key
    //returns the index under which the author is stored
    //returns -1 if the author is not found

private:

    struct Node
    {
        string title;
        string author;
        int isbn;
        Node* next;
        Node(): title(""), author(""), isbn(0), next(NULL){}
        Node(string ntitle, string nauthor, int nisbn): title(ntitle), author(nauthor), isbn(nisbn), next(NULL) {}
    };

    typedef struct Node* Nodeptr;

    static const int TABLE_SIZE = 10;
    Nodeptr Table[TABLE_SIZE];

};

#endif /* HASHTABLE_H_ */


Hash Table Constructor
  • The purpose of this constructor is to assign an initial value to each bucket in the Table[].
  • Table array is an array of Node pointers.
  • Therefore, we will want to assign each index of the Table array to be an empty Node, by calling the default Node constructor at each index of the array.

HashTable::HashTable()
{
    for each index i of the Table array
    {
        assign Table[i] to be a new, empty Node
    }
}

  • When you are finished writing the constructor, open up a new C++ file called HashTest.cpp.
  • Add a main function inside of HashTest.cpp and instantiate a new HashTable.


Adding Values to the Hash Table

  • The next step in the process is to be able to add a value to the hash table.
  • Since we are using the separate chaining approach to collisions, we will need to consider two cases:
  1. The key to add will be the first inserted at that index.
  2. The key is not the first, and will need to be added onto the back of the chain.
  • We will also need to determine at which index to insert our key, meaning that we will need to have written a hash function.
  • For the purposes of this assignment, we will be using the algorithm defined in class which sums the ASCII values of all the characters in a string and scales the result to fit in the table.
    • You are welcome to use this or an alternate hash algorithm for your project.
  • Since my Node contains several fields that store information about a Book, I must also decide which of these to use as my key to pass to the hash function.
  • Because an author could have written more than one book that is being stored in the table, I will select the title of the book to be the key.
    • Do you think that this is the best choice for a key?
    • Note that I could have also selected isbn or a combination of the author and title fields to be my key.
  • Below is the pseudocode for the addItem function:


Pseudocode for addItem(string title, string author, int isbn)

  1. Call the Node constructor to create a new Node, passing it the title, author and isbn. We will insert this Node in the table.
  2. Call the hash function on the title to determine the index at which to insert.
  3. Case 1: the index holds no values (title == "")//adapt for your project
    1. Set the Node at that index to be our new Node.
  4. Case 2: the index holds one or more values
    1. Create a temp Node to point to the first node at the index
    2. Scroll through the Nodes at that index until you find one whose next pointer is NULL
    3. Set the new Node equal to the temp Node's next pointer


Test Values for addItem

  • You can test your addItem function by making the following function calls in HashTest.cpp:

      table.addItem("Pride and Prejudice", "Jane Austen", 12345678);
    table.addItem("Contact", "Carl Sagan", 9999333939);
    table.addItem("The Hunger Games", "Suzanne Collins", 12388888);
    table.addItem("Harry Potter", "J.K. Rowlings", 55555678);
    table.addItem("The Man in the High Castle", "Philip K Dick", 9595959595);
    table.addItem("Bleak House", "Charles Dickens", 47389023849);


Printing the Hash Table Using PrintTable

  • To properly test our Hash Table, we will need to be able to print the values contained in it.
  • Therefore, our next step is to write a print function.
  • There are two print functions that I may want to write, depending on my purposes.
  • If you are following along with my example, we want our printTable function to print the following to the console given the values we have already inserted:

Book Hash Table:

-------------------------------------------
Index 0:
Title:
Author:
ISBN: 0
Number Values at this Index: 0
-------------------------------------------
Index 1:
Title:
Author:
ISBN: 0
Number Values at this Index: 0
-------------------------------------------
Index 2:
Title:
Author:
ISBN: 0
Number Values at this Index: 0
-------------------------------------------
Index 3:
Title: The Hunger Games
Author: Suzanne Collins
ISBN: 12388888
Number Values at this Index: 1
-------------------------------------------
Index 4:
Title: Pride and Prejudice
Author: Jane Austen
ISBN: 12345678
Number Values at this Index: 1
-------------------------------------------
Index 5:
Title:
Author:
ISBN: 0
Number Values at this Index: 0
-------------------------------------------
Index 6:
Title: Contact
Author: Carl Sagan
ISBN: 1409399347
Number Values at this Index: 1
-------------------------------------------
Index 7:
Title: The Man in the High Castle
Author: Philip K Dick
ISBN: 1006025003
Number Values at this Index: 2
-------------------------------------------
Index 8:
Title: Harry Potter
Author: J.K. Rowlings
ISBN: 55555678
Number Values at this Index: 1
-------------------------------------------
Index 9:
Title:
Author:
ISBN: 0
Number Values at this Index: 0

  • In other words, for each bucket in the table, we are going to output the following to the console:

--------------------------------------------

Index <#>:

Title: <Title Stored in First Node>

Author: <Author Stored in First Node>

ISBN: <ISBN Stored in First Node>

Number of Values at this Index: <#>


  • For this function we are going to need a simple for loop to scroll through each bucket in our table, printing the first values at each index.
  • However, we are also going to need a helper function: numItemsAtIndex, like the following

Pseudocode for numItemsAtIndex:

  1. Create a temp Node to point to the first Node in the index
  2. Initialize a counter variable to 0
  3. If the title value at temp is the empty string
    1. Return counter variable
  4. Otherwise, while temp is not NULL
    1. Increment counter variable
    2. Set temp to be temp->next
  5. Return counter variable


Printing the Table Using PrintBucket:
  • PrintBucket is used to display all of the values at a single bucket.
  • Because printTable will only display the first value stored at each index, printBucket will allow us to dig more deeply into what is contained at a particular bucket.
  • You can think of printTable as providing a vertical cross section of values whereas printBucket gives us a horizontal cross section.
  • For example, a call to printBucket(7); should display the following
Values Stored at Bucket 7:

Title: Contact
Author: Carl Sagan
ISBN: 1409399347

Title: Pride and Prejudice
Author: Jane Austen
ISBN: 12345678

Searching the Table

  • There are various possible search functions that I could write depending upon the purposes of my table.
  • Here I am going to suppose that my users are interested in finding out the author of a book given its title.
  • Thus, given a title, the findAuthor function will return the author of the book.
  • The findAuthor function is fairly straight-forward to implement.

Pseudocode for int findAuthor(string title)

  1. Call hash function on the title (key)
  2. Go to the index returned by the hash function
  3. Using a loop, scroll through the Nodes stored at that index
    1. If title is found,
      1. print author information
      2. return index.
  4. If title is not found at that index
    1. Print a message to my users that the title was not stored in my table.
    2. Return -1 to indicate author not found




What to Submit
  • Once you are certain all of your functions are working, upload your files to Catalyst under Lab 7
  • Submit your complete HashTable, including HashTable.h, HashTable.cpp, and HashTest.cpp
  • Note that you will lose 10 points per function for any missing function
  • You will lose 15 points for not testing your functions