c++ - 在c++中实现hashmap的过程中发生了奇怪的事情

Question

我尝试用 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;

};

我使用初始化我的 map

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)，i从0到100。我发现我的buckets[i]并不是所有的都是空指针(我在put中添加了buckets[bucket] == null )!在我把对放在 map 上之前。有些是，但有些不是!怎么会发生这种事？因为我刚刚将它们全部初始化为 nullptr?

仅供引用，在构造函数内部，我检查了所有 bucket[i] 确实是 nullptr。这个错误让我发疯......有人可以帮我吗？谢谢!

Answer 1

您在构造函数中声明了另一个 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)
{ }

您还必须将 INIT_N_BUCKETS 移到类中更高的位置，因为在您初始化时顺序很重要。

示例代码: https://ideone.com/b8RN1Q