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时发生的奇怪事情

回答

相关问题