使用矢量矢量創建哈希表？

Question

我目前正在嘗試編寫一個程序，該程序創建一個哈希表，使用向量的矢量作爲我的衝突解決方法。

我面臨的問題是，在運行時，向量的矢量被創建，但所有的入口向量仍然大小爲0.我知道我的put函數有問題，但我不知道在哪裏/爲什麼。

這是我第一次創建一個哈希表，我會很感激任何問題的幫助。我的目標是創建一個入口向量的向量，並且每個入口都有其關聯的鍵和值。在找到新的Entry鍵的散列值後，它應該檢查Entry矢量的鍵值以查看鍵是否已經存在。如果是，則更新該密鑰的值。

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

這是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 */ 
}; 

和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

有各種各樣的問題你代碼，但你的問題的答案是這樣的：

在

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

看看循環。現在

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

，hashtable[hash]是一個載體。但最初它沒有任何元素。所以hashtable[hash].size()是0.所以你不要進入循環。

最重要的是，首先嚐試訪問hashtable[hash]會導致未定義的行爲，因爲hashtable未被正確調整爲Tsize。試試這個在您的構造函數（S）：

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

編輯：

這將是您更容易理解，如果你使用std::vector::at函數代替std::vector::operator[]。例如：

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

不調整hashtable，當你嘗試做hashtable.at(hash)第一次遇到這種代碼將拋出一個異常out_of_range。

P.S.這些都沒有經過測試。