C++中執行hashmap時發生的奇怪事情

我嘗試在C++中實現我自己的hashmap。我的頭是 C++中執行hashmap時發生的奇怪事情

class MyMap 
{ 
public: 


    MyMap(); 
    ~MyMap(); 

    int get(int key) const; 
    void put(int key, int value); 
    bool containsKey(int key); 
    Vector<int> keys() const; 
    int size(); 

    void sanityCheck(); 
    MyMap(const MyMap &myMap); // copy constructor 
    MyMap& operator= (const MyMap &myMap); // assignment overload 
    friend ostream &operator<<(ostream &out, MyMap &myMap); 
    friend istream &operator>>(istream &in, MyMap &myMap); 
private: 

    struct key_val_pair { 
     int key; 
     int value; 
     key_val_pair* next; 
    }; 

    typedef key_val_pair** bucketArray; // just renaming the pointer to pointer. 

    bucketArray createBucketArray(int nBuckets); 
    int hashFunction(int input) const; 

    bucketArray buckets; 

    int nBuckets; 
    int nElems; 
    int INIT_N_BUCKETS = 128; 

};

我初始化使用

MyMap::MyMap() { 
    bucketArray buckets = createBucketArray(INIT_N_BUCKETS); 
    nBuckets = INIT_N_BUCKETS; 
    nElems = 0; 
} 
MyMap::bucketArray MyMap::createBucketArray(int nBuckets) { 
    bucketArray newBuckets = new key_val_pair*[nBuckets]; 
    for (int i = 0; i < nBuckets; i++) { 
     newBuckets[i] = nullptr; 
    } 
    return newBuckets;

}

，這裏是我的代碼把元素融入HashMap中

void MyMap::put(int key, int value) { 
    // compute hash; 
    int bucket = hashFunction(key) % nBuckets ; 
    key_val_pair *entry = buckets[bucket];  
    key_val_pair *prev = nullptr; 
    if(entry == nullptr) { 

     entry = new key_val_pair; 
     entry->key = key; 
     entry->value = value; 
     entry->next = nullptr; 
     buckets[bucket] = entry; 
     nElems++; 
    } 
    else{ 
     while(entry && entry->key != key){ 
      prev = entry; 
      entry = entry->next; 
     } 

     if(!entry){ 
      entry = new key_val_pair; 
      entry->key = key; 
      entry->value = value; 
      entry->next = nullptr; 
      if(!prev) buckets[bucket] = entry; 
      else prev->next = entry; 
      nElems++; 
     } 
     else{ 
      entry->value = value; 
     } 
    } 

}

現在我的地圖，這裏是奇怪的部分，即使在初始化之後。例如，我讓MyMap m = MyMap();。我輸入對（i，i），我從0到100.我發現並非我所有的桶[i]都是空指針（我在句子中添加了句子，如buckets[bucket] == null）！在我將地圖中的對之前。有些是，但有些不是！這個事情怎麼會發生？正如我剛將它們全部初始化爲nullptr？在構造函數中，我檢查了所有的桶[i]的確是nullptr。這個錯誤讓我瘋狂...... 有人可以幫助我嗎？謝謝！

來源

2017-08-30 jack

你確定你想這一點; 'new key_val_pair * [nBuckets];'？（*） – Stefan

@Stefan是的，我認爲是這樣，它只是一個由（鍵，值）對組成的鏈表。 – jack

這一行：'bucketArray buckets = createBucketArray（INIT_N_BUCKETS）;'？如果你從中刪除'bucketArray'，會發生什麼？ – pmaxim98

您聲明在構造另一個bucketarray但你不把它從類分配給您的會員：

bucketArray buckets = createBucketArray(INIT_N_BUCKETS);

應該是：

buckets = createBucketArray(INIT_N_BUCKETS);

甚至更好，初始化所有這樣的成員：

MyMap::MyMap() 
: 
INIT_N_BUCKETS(128), 
buckets(createBucketArray(INIT_N_BUCKETS)), 
nBuckets(INIT_N_BUCKETS), 
nElems(0) 
{ }

You ha由於初始化時順序很重要，因此我們也已經將類別中的INIT_N_BUCKETS更高。

示例代碼： https://ideone.com/b8RN1Q

來源

2017-08-30 10:04:15 pmaxim98

你是對的！這是一個非常不幸的錯字.....謝謝！ – jack

@jack沒問題:) – pmaxim98

C++中執行hashmap時發生的奇怪事情

回答

相關問題