Creating a hashtable using vectors of vectors?

Question

I'm currently trying to write a program that creates a hash table, using vectors of vectors for my collision resolution method.

The problem I am facing is that during runtime, a vector of vectors is created, but all of the Entry vectors inside remain of size 0. I know my put functions are faulty but I don't know where/why.

This is my first time creating a hash table and I'd appreciate any assistance in what the problem might be. My goal is to create a vector of Entry vectors, and each Entry has its associated key and value. After finding the hash value for a new Entry key, it should check the Entry vectors' key values to see if the key already exists. If it does, it updates that key's value.

This is a segment of table.cpp:

Table::Table(unsigned int maximumEntries) : maxEntries(100){
    this->maxEntries = maximumEntries;
    this->Tsize = 2*maxEntries;

}

Table::Table(unsigned int entries, std::istream& input){ //do not input more than the specified number of entries.

    this->maxEntries = entries;
    this->Tsize = 2*maxEntries;

    std::string line = "";

    int numEntries = 0;


    getline(input, line);
    while(numEntries<maxEntries || input.eof()){ // reads to entries or end of file
        int key;
        std::string strData = "";

        convertToValues(key, strData, line);

        put(key, strData); // adds each of the values to the tab;e

        numEntries++;

        getline(input,line);

    }

}



void Table::put(unsigned int key, std::string data){ 
    Entry newEntryObj(key,data); //create a new Entry obj
    put(newEntryObj);
}


void Table::put(Entry e){ // creating the hash table

    assert(currNumEntries < maxEntries);

    int hash = (e.get_key() % Tsize);

    Entry newEntry = Entry(e.get_key(), e.get_data()); 

    for(int i = 0; i < hashtable[hash].size(); i++){
        if (e.get_key() == hashtable[hash][i].get_key()){ 
            hashtable[hash][i].set_data(e.get_data());
        }
        else{
            hashtable[hash].push_back(newEntry);  // IF KEY DOESNT EXIST, ADD TO THE VECTOR
        }
    }
}

This is Table.h

#ifndef table_h
#define table_h

#include "entry.h"
#include <string>
#include <istream>
#include <fstream>
#include <iostream>
#include <vector>


class Table{

  public: 

    Table(unsigned int max_entries = 100); //Builds empty table with maxEntry value
    Table(unsigned int entries, std::istream& input); //Builds table designed to hold number of entires


    void put(unsigned int key, std::string data); //creates a new Entry to put in
    void put(Entry e);  //puts COPY of entry into the table
    std::string get(unsigned int key) const; //returns string associated w/ param, "" if no entry exists
    bool remove(unsigned int key); //removes Entry containing the given key

    friend std::ostream& operator<< (std::ostream& out, const Table& t); //overloads << operator to PRINT the table.

    int getSize();

    std::vector<std::vector<Entry>> getHashtable(); 


  private:
    std::vector<std::vector<Entry>> hashtable; //vector of vectors
    int Tsize; //size of table equal to twice the max number of entries
    int maxEntries;
    int currNumEntries;

#endif /* table_h */
};

and Entry.h:

#include <string>
#include <iosfwd>

class Entry {

public:
    // constructor
    Entry(unsigned int key = 0, std::string data = "");

    // access and mutator functions
    unsigned int get_key() const;
    std::string get_data() const;
    static unsigned int access_count();
    void set_key(unsigned int k);
    void set_data(std::string d);

    // operator conversion function simplifies comparisons
    operator unsigned int () const;

    // input and output friends
    friend std::istream& operator>>
    (std::istream& inp, Entry &e);
    friend std::ostream& operator<<
    (std::ostream& out, Entry &e);

private:
    unsigned int key;
    std::string data;
    static unsigned int accesses;

};

Answer 1

There are various problems with your code, but the answer for your question would be this:

In

void Table::put(Entry e){ // creating the hash table

Have a look at the loop.

for(int i = 0; i < hashtable[hash].size(); i++){

Now, hashtable[hash] is a vector. But initially it doesn't have any elements. So hashtable[hash].size() is 0. So you don't enter the loop.

On top of this, trying to access hashtable[hash] in the first place results in undefined behaviour due to hashtable not being properly resized to Tsize. Try this in your constructor(s):

this->maxEntries = maximumEntries;
this->Tsize = 2*maxEntries;
this->hashtable.resize(this->Tsize);

EDIT:

It would be easier for you to understand if you use std::vector::at function instead of std::vector::operator[]. For example:

void Table::put(Entry e){ // creating the hash table

    assert(currNumEntries < maxEntries);

    int hash = (e.get_key() % Tsize);

    Entry newEntry = Entry(e.get_key(), e.get_data()); 

    for(int i = 0; i < hashtabl.at(hash).size(); i++){
        if (e.get_key() == hashtable.at(hash).at(i).get_key()){ 
            hashtable.at(hash).at(i).set_data(e.get_data());
        }
        else{
            hashtable.at(hash).push_back(newEntry);  // IF KEY DOESNT EXIST, ADD TO THE VECTOR
        }
    }
}

Without resizing hashtable, this code would throw an out_of_range exception when you try to do hashtable.at(hash) the first time.

P.S. None of this is tested.