Hash Table Chaining using a Linked List

HashTable.h

//*****************************************************************
//  HashTable.h
//  This header file contains the Hash Table class declaration.
//  Hash Table array elements consist of Linked List objects.
//*****************************************************************

#ifndef HashTable_hpp
#define HashTable_hpp
#include "LinkedList.hpp"

//*****************************************************************
// Hash Table objects store a fixed number of Linked Lists.
//*****************************************************************
class HashTable
{
private:
    
    // Array is a reference to an array of Linked Lists.
    LinkedList * array;
    
    // Length is the size of the Hash Table array.
    int length;
    
    // Returns an array location for a given item key.
    int hash( string itemKey );
   
    
public:
    
    // Constructs the empty Hash Table object.
    // Array length is set to 13 by default.
    HashTable(int);
    
    // Adds an item to the Hash Table.
    void insertItem( Item * newItem );
    
    // Deletes an Item by key from the Hash Table.
    // Returns true if the operation is successful.
    bool removeItem( string itemKey );
    
    // Returns an item from the Hash Table by key.
    // If the item isn't found, a null pointer is returned.
    Item * getItemByKey( string itemKey );
    
    // Display the contents of the Hash Table to console window.
    void printTable();
    
    // Prints a histogram illustrating the Item distribution.
    void printHistogram();
    
    // Returns the number of locations in the Hash Table.
    int getLength();
    
    // Returns the number of Items in the Hash Table.
    int getNumberOfItems();
    
    // De-allocates all memory used for the Hash Table.
    ~HashTable();
};


#endif /* HashTable_hpp */

HashTable.cpp

// HashTable.cpp
#include "HashTable.hpp"

// Constructor for HashTable
HashTable::HashTable(int tableLength) {
    if (tableLength <= 0)
        tableLength = 13; // Default size is 13 if given length is non-positive
    array = new LinkedList[tableLength]; // Create an array of LinkedLists
    length = tableLength; // Set the length of the hash table
}

// Hash function to determine the index for a given item key
int HashTable::hash(string itemKey) {
    int value = 0;
    for (int i = 0; i < itemKey.length(); i++)
        value += itemKey[i]; // Sum ASCII values of characters in the key
    return (itemKey.length() * value) % length; // Compute index using sum and length
}

// Adds an item to the Hash Table
void HashTable::insertItem(Item * newItem) {
    int index = hash(newItem->key); // Get the hash index for the item
    array[index].insertItem(newItem); // Insert the item in the appropriate LinkedList
}

// Deletes an Item by key from the Hash Table
bool HashTable::removeItem(string itemKey) {
    int index = hash(itemKey); // Get the hash index for the item
    return array[index].removeItem(itemKey); // Remove the item from the appropriate LinkedList
}

// Returns an item from the Hash Table by key
Item * HashTable::getItemByKey(string itemKey) {
    int index = hash(itemKey); // Get the hash index for the item
    return array[index].getItem(itemKey); // Retrieve the item from the appropriate LinkedList
}

// Display the contents of the Hash Table to console window
void HashTable::printTable() {
    cout << "\nHash Table:\n";
    for (int i = 0; i < length; i++) {
        cout << "Bucket " << i + 1 << ": ";
        array[i].printList(); // Print each LinkedList in the table
    }
}

// Prints a histogram illustrating the Item distribution
void HashTable::printHistogram() {
    cout << "\n\nHash Table Contains ";
    cout << getNumberOfItems() << " Items total\n";
    for (int i = 0; i < length; i++) {
        cout << i + 1 << ":\t";
        for (int j = 0; j < array[i].getLength(); j++)
            cout << " X"; // Print an X for each item in the LinkedList
        cout << "\n";
    }
}

// Returns the number of locations in the Hash Table
int HashTable::getLength() {
    return length; // Return the length of the hash table
}

// Returns the number of Items in the Hash Table
int HashTable::getNumberOfItems() {
    int itemCount = 0;
    for (int i = 0; i < length; i++)
        itemCount += array[i].getLength(); // Sum lengths of all LinkedLists
    return itemCount; // Return total number of items
}

// Destructor for HashTable
HashTable::~HashTable() {
    delete[] array; // De-allocate the array of LinkedLists
}

LinkedList.h

//*****************************************************************
//  This header file contains the Linked List class declaration.
//  Hash Table array elements consist of Linked List objects.
//*****************************************************************

#ifndef LinkedList_hpp
#define LinkedList_hpp

#include <iostream>
#include <string>
using namespace std;

//*****************************************************************
// List items are keys with pointers to the next item.
//*****************************************************************
struct Item
{
    string key;
    Item * next;
};

//*****************************************************************
// Linked lists store a variable number of items.
//*****************************************************************
class LinkedList
{
private:
    // Head is a reference to a list of data nodes.
    Item * head;
    
    // Length is the number of data nodes.
    int length;
    
public:
    // Constructs the empty linked list object.
    // Creates the head node and sets length to zero.
    LinkedList();
    
    // Inserts an item at the end of the list.
    void insertItem( Item * newItem );
    
    // Removes an item from the list by item key.
    // Returns true if the operation is successful.
    bool removeItem( string itemKey );
    
    // Searches for an item by its key.
    // Returns a reference to first match.
    // Returns a NULL pointer if no match is found.
    Item * getItem( string itemKey );
    
    // Displays list contents to the console window.
    void printList();
    
    // Returns the length of the list.
    int getLength();
    
    // De-allocates list memory when the program terminates.
    ~LinkedList();
};


#endif /* LinkedList_hpp */

LinkedList.cpp

main.cpp