Erstellen einer Hashtable mit Vektoren von Vektoren?

Question

Ich versuche gerade, ein Programm zu schreiben, das eine Hash-Tabelle erstellt, Vektoren von Vektoren für meine Kollisionsauflösungsmethode verwendend. Das Problem, dem ich gegenüberstehe, ist, dass während der Laufzeit ein Vektor von Vektoren erzeugt wird, aber alle Eingabevektoren innerhalb der Größe bleiben. Ich weiß, dass meine Put-Funktionen fehlerhaft sind, aber ich weiß nicht wo/warum.

Dies ist das erste Mal, dass ich eine Hash-Tabelle erstelle und ich würde mich über jede Hilfe bei dem Problem freuen. Mein Ziel ist es, einen Vektor von Eintragsvektoren zu erstellen, und jedem Eintrag sind Schlüssel und Wert zugeordnet. Nachdem der Hash-Wert für einen neuen Entry-Schlüssel gefunden wurde, sollte er die Schlüsselwerte der Entry-Vektoren prüfen, um zu sehen, ob der Schlüssel bereits existiert. Wenn dies der Fall ist, aktualisiert es den Wert dieses Schlüssels.

Dies ist ein Segment von 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 
     } 
    } 
} 

Dies ist 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 */ 
}; 

und 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

Es gibt verschiedene Probleme mit Ihrem Code, aber die Antwort für Ihre Frage wäre dies:

In

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

Werfen Sie einen Blick auf die Schleife.

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

Nun ist hashtable[hash] ein Vektor. Aber anfangs hat es keine Elemente. Also ist hashtable[hash].size() 0. Also kommst du nicht in die Schleife.

Darüber hinaus führt der Versuch, zuerst auf hashtable[hash] zuzugreifen, zu undefiniertem Verhalten, da hashtable nicht korrekt auf Tsize geändert wird. Versuchen Sie dies in Ihrem Konstruktor (e):

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

EDIT:

Es wäre einfacher für Sie zu verstehen, wenn Sie std::vector::at Funktion anstelle von std::vector::operator[] verwenden. Zum Beispiel:

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 
     } 
    } 
} 

Ohne hashtable Ändern der Größe, würde dieser Code eine out_of_range Ausnahme auslösen, wenn Sie versuchen, hashtable.at(hash) das erste Mal zu tun.

P.S. Nichts davon ist getestet.