C++ Hashtable issues with rehash

Question

As for my school assigment I have to update my hashtable size when it hits %70-90 load. I am having issues with rehashing the hash table. I cannot modify tableSize (because I created it with const static. I had to because it wouldn't let me otherwise). Also I cant modify HashTable as it's not modifiable value. I think my constructor is wrong but i can't figure out by my self.

Any help is appreciated.

hash_table.cpp

#include <iostream>
#include <cstdlib>
#include <string>

#include "hash_table.h"

using namespace std;


hash_table::hash_table()
{
    for (int i = 0; i < tableSize; i++) {
        HashTable[i] = new item;
        HashTable[i]->name = "";
        HashTable[i]->info.documentName = "";
        HashTable[i]->info.count = 1;
        HashTable[i]->info.next = NULL;
        HashTable[i]->next = NULL;
    }
}

int hash_table::Hash(string key)
{
    int hash = 0;
    int index;

    for (int i = 0; i < key.length(); i++) {
        hash = (hash + (int)key[i]) * 17;
    }

    index = hash % tableSize;

    return index;
}

void hash_table::AddItem(string name,string document)
{
    int index = Hash(name);
    int check = size / tableSize;

    if(check > 0.78){
        reHash();
    }

    if (HashTable[index]->name == "") {
        HashTable[index]->name = name;
        HashTable[index]->info.documentName = document;
        HashTable[index]->info.count = 1;
        size++;
    }
    else if (HashTable[index]->name == name) {
        if (HashTable[index]->info.documentName == document) {
            HashTable[index]->info.count++;
        }
        else if (HashTable[index]->info.next != NULL) {
            Document* checkPtr = &HashTable[index]->info;
            while (HashTable[index]->info.next != NULL) {
                checkPtr = checkPtr->next;
                if (checkPtr != NULL) {
                    if (checkPtr->documentName == document) {
                        checkPtr->count++;
                    }
                }
                else {
                    break;
                }
            }
        }
        else {
            Document* tempPtr = &HashTable[index]->info;
            Document* t = new Document;
            t->documentName = document;
            t->count = 1;
            t->next = NULL;
            while (tempPtr->next != NULL) {
                tempPtr = tempPtr->next;
            }
            tempPtr->next = t;
        }
    }
    else {
        item* Ptr = HashTable[index];
        item* n = new item;
        n->name = name;
        n->next = NULL;
        while (Ptr->next != NULL) {
            Ptr = Ptr->next;
        }
        Ptr->next = n;
    }
}

int hash_table::NumberOfItemsInIndex(int index)
{
    int count = 0;

    if (HashTable[index]->name == "") {
        return count;
    }
    else {
        count++;
        item* Ptr = HashTable[index];
        while (Ptr->next != NULL) {
            count++;
            Ptr = Ptr->next;
        }
    }
    return count;
}

void hash_table::PrintTable() // CAN USE AS CALCULATING TOTAL NUMBER
{
    int number;
    for (int i = 0; i < tableSize; i++) {
        number = NumberOfItemsInIndex(i);
        cout << "----------------" << endl;
        cout << "index = " << i << endl;
        cout << HashTable[i]->name << endl;
        cout << HashTable[i]->info.count << endl;
        cout << "# of items = " << number << endl;
        cout << "----------------" << endl;
    }
}

void hash_table::PrintItemsInIndex(int index)
{
    item* Ptr = HashTable[index];

    if (Ptr->name == "empty") {
        cout << "index = " << index << " is empty" << endl;
    }
    else {
        cout << "index " << index << "countains the following item" << endl;

        while (Ptr != NULL) {
            cout << "--------------" << endl;
            cout << Ptr->name << endl;
            cout << Ptr->info.count << endl;
            cout << "--------------" << endl;
            Ptr = Ptr->next;
        }
    }
}

void hash_table::FindString(string name)
{
    int index = Hash(name);
    bool foundQuery = false;
    item *Ptr = HashTable[index];
    Document* checkPtr = NULL;

    while (Ptr != NULL) {
        if (Ptr->name == name) {
            foundQuery = true;
            checkPtr = &Ptr->info;
        }
        Ptr = Ptr->next;
    }
    if (foundQuery == true) {
        while (checkPtr != NULL) {
            cout << "in document " << checkPtr->documentName << ", " << name << " found " << checkPtr->count << " times." << endl;
            checkPtr = checkPtr->next;
        }
    }
    else {
        cout << "No document contains the given query" << endl;
    }
}

void hash_table::reHash()
{
    int oldCapacity = tableSize;
    tableSize = tableSize * 2 + 1;

    item** newHashTable = new item*[tableSize];

    for (int i = 0; i < oldCapacity; i++) {
        item *n = HashTable[i];
        while (n != NULL) {
            item *tmp = n;
            n = n->next;

            item*& bucket = newHashTable[hash_table::Hash(tmp->name) % tableSize];
            tmp->next = bucket;
            bucket = tmp;
        }
    }

    delete[] HashTable;
    HashTable = newHashTable;
}

hash_table.h

#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

#ifndef HASH_H
#define HASH_H

struct Document {
    string documentName;
    int count;
    Document* next;
};

struct item {
    string name;
    item* next;
    struct Document info;
};




class hash_table{
private:
    const static int tableSize = 26;
    item* HashTable[tableSize];

public:
    hash_table();
    int Hash(string key);
    void AddItem(string name, string document);
    int NumberOfItemsInIndex(int index);
    void PrintTable();
    void PrintItemsInIndex(int index);
    void FindString(string name);
    void reHash();
    int size = 0;

};

#endif  // !HASH_H

Answer 1

Generally, to make an array bigger, you need to make a bigger array and copy the contents of the old array to the new. You figured this out!

You are locked in to fixed array size by making table_size a constant and then declaring a fixed sized array here.

const static int tableSize = 26;
item* HashTable[tableSize];

If you make tableSize a variable above, and make the initial array more like this

item** newHashTable = new item*[tableSize];

then you have a better chance of succeeding! Since this is a school exercise, its not right to do the code for you...

Generally though, in the situation where you need to change the array size during program execution, its much better to use vectors. These can be extended at will during execution, and well worth reading up and doing some examples.