初始化哈希映射C++构造函数中节点的值

Question

我应该创建一个哈希映射来存储用户名和密码，它们存储为字符串。此哈希映射是单独链接的。在添加值或搜索值时，我应该在键上使用哈希函数，该键返回一个整数，然后该整数将为我提供需要使用函数的存储桶的索引。如果添加某些内容，我会将其存储在列表的末尾。

所以哈希图（在我看来）看起来像这样：

Bucket | List
[0] -> nullptr
[1] -> (key1/value1) -> (key2/value2)
[2] -> (key3/value3)

从技术上讲，每个键/值组合都是一个节点，在我的头文件中具有不可修改的结构，如下所示：

struct Node
{
    std::string key;
    std::string value;
    Node* next;
};

尽管我的添加和搜索函数在技术上有效，但我想在我的构造函数中正确初始化我的哈希映射，这样我就不会对未初始化的值进行比较。这就是我的构造函数现在的样子：

HashMap::HashMap()
    : hashTable{new Node*[initialBucketCount]}, amountOfBuckets{initialBucketCount}, sz{0}
{
    for(int i = 0; i < amountOfBuckets; i++) {
        hashTable[i] = nullptr;
    }
}

问题是，当我必须比较某些东西时，例如在我的 add 函数中，我收到 valgrind 的错误，说我正在执行条件跳转或移动未初始化的值。例如，在 add：

Node* current = hashTable[tableIndex];
if(current == nullptr)
    return false;

会说if(current == nullptr)引用了一个未初始化的值。

我将如何正确初始化哈希映射构造函数中的值？特别是如果我想在一个函数中做一些事情，我将列表的开头与 nullptr 之类的值进行比较，以便我可以确定我需要将列表中的下一个节点放在何处。

编辑：这是浓缩到一个文件中的所有内容。

/* HashMap.cpp */
namespace {
    unsigned int hashFunc(const std::string& key)
    {
        unsigned int hashValue = 0; // what we end up returning
        for(int i = 0; i < key.length(); i++) { // iterate through string
            int letterIndex = key.at(i) - 96; // create an index for each ASCII char
            hashValue = hashValue * 27 + letterIndex;
        }
        return hashValue;
    } // end hashFunc
}
class HashMap
{
public:
    typedef std::function<unsigned int(const std::string&)> HashFunction;
    static constexpr unsigned int initialBucketCount = 10;
private:
    struct Node
    {
        std::string key;
        std::string value;
        Node* next;
    };
    HashFunction hasher;
    Node** hashTable;
    unsigned int amountOfBuckets;
    unsigned int sz;
public:
    HashMap()
    : hashTable{new Node*[initialBucketCount]}, amountOfBuckets{initialBucketCount}, sz{0}
    {
    for(int i = 0; i < amountOfBuckets; i++) {
        hashTable[i] = nullptr;
    }
    }
    HashMap(HashFunction hasher)
    : hasher{hashFunc}, hashTable{new Node*[initialBucketCount]()}, amountOfBuckets{initialBucketCount}, sz{0}
    {
    for(int i = 0; i < amountOfBuckets; i++) {
        hashTable[i] = nullptr;
    }
    }
    HashMap(const HashMap& hm)
    : hashTable{new Node*[hm.amountOfBuckets]}, amountOfBuckets{hm.amountOfBuckets}, sz{hm.sz}
    {
        for(unsigned int i = 0; i < sz; i++) {
            hashTable[i] = hm.hashTable[i];
        } // end for
    }
    ~HashMap()
    {
    for(unsigned int i = 0; i < amountOfBuckets; i++) {
        Node* bucketNode = hashTable[i]; // store each hashtable list in a bucket node
        while(bucketNode != nullptr) {
            Node* deleteCurrent = bucketNode; // set current to the bucket node (head)
            bucketNode = bucketNode->next; // delete current is on the first node, update head to second node
            delete deleteCurrent;
        } // end while
    } // end for
    // once done, delete hash table
    delete[] hashTable;
    } // end destructor
    void add(const std::string& key, const std::string& value)
    {
    unsigned int hashedValue = hashFunc(key); // get hash value (unmodified by buckets)
    unsigned int tableIndex = getTableIndex(hashedValue); // get the table index
    if(contains(key) == true) { // if key is already in the hashtable
        return; // exit program
    } else { // otherwise, key is not in the hash table
        Node* head = hashTable[tableIndex]; // head of the hash table, represents
        Node* current = head; // set current to first node
        if(current == nullptr) { // no nodes yet
            // nothing in bucket
            current = new Node(); // construct single node
            current->key = key; // set key (username)
            current->value = value; // set value (password)
            current->next = head; // add value to head of list
            hashTable[tableIndex] = current; // update current to point to front of list
            return; // exit
        } else {
            while(current->next != nullptr) {
                current = current->next; // advance to next node
            } // end while
            // currently at node we want to insert key/value at
            current = new Node();
            current->key = key; // set key(username)
            current->value = value; // set value (pw)
            current->next = nullptr; // set next to point to nullptr
        } // end inner if-else (creates node)
    } // end outer if-else
    } // end add
    bool contains(const std::string& key) const
    {
    unsigned int hashedValue = hashFunc(key); // hash the key given to get an index
    unsigned int tableIndex = getTableIndex(hashedValue); // get the table index
    Node* current = hashTable[tableIndex];
    if(current == nullptr) { // if there are no nodes at given index
        return false;
    } else { // there are some nodes in the hash table
        while(current != nullptr && current->key != key) {
            current = current->next;
        } // end while
        if(current == nullptr) { // we reached the end of our linked list
            return false; // couldn't find a value
        } else { // we found the key provided
            return true;
        }
    } // end if-else
    }
    std::string value(const std::string& key) const
    {
        if(contains(key) == true) { // found match
            unsigned int hashedValue = hashFunc(key); // hash the key given to get an index
            unsigned int tableIndex = getTableIndex(hashedValue); // get the table index
            Node* current = hashTable[tableIndex];
            while(current != nullptr && current->key != key) {
                current = current->next;
            }
            return current->value; // return value after traversal
        } else {
            return ""; // no match, return empty string
        }
    }
}; // end class
/* main.cpp */
int main()
{
    // initialize test
    HashMap test1;
    std::cout << "TEST 1 HASHMAP OBJECT CREATED" << std::endl;
    // add some values
    std::string key1 = "Alex";
    std::string value1 = "password1";
    std::string key2 = "Danielle";
    std::string value2 = "password2";
    std::cout << "strings have been created" << std::endl;
    // add to hash map
    test1.add(key1, value1);
    test1.add(key2, value2);
    std::cout << "Keys and values have been added to hash map" << std::endl;
    // does key1 contain the word "hi"? no, should return false (0)
    std::cout << "Hash map contains word hi?: " << test1.contains("hi") << std::endl;
    // does key2 contain word "Danielle"? yes, should return true (1)
    std::cout << "Hash map contains word Danielle?: " << test1.contains("Danielle") << std::endl;
    // copy constructor test
    HashMap test2{test1};
    test2.add("Chicken", "lizard1");
    std::cout << "Password for user Chicken: " << test2.value("Chicken") << std::endl;
    HashMap test3 = test2;
    // pw should stay lizard1 (doesn't work rn)
    std::cout << "Password for user Chicken after copy: " << test3.value("Chicken") << std::endl;
    // check to see if we get value
    std::cout << "Password for user " << key1 << ": " << test1.value(key1) << std::endl;
    std::cout << "Password for user " << key2 << ": " << test1.value(key2) << std::endl;
    // should return empty string
    std::cout << "Test of incorrect password for invalid user INVALID: " << test1.value("lol") << std::endl;
    return 0;
}

Answer 1

您在默认 ctor 中写注释

// initialize each node to nullptr from the array of buckets to nullptr

然后继续做其他完全不同的事情。另一件事是完全错误的。初始化所有节点 ptrs 以指向同一节点。这意味着在销毁时，您将多次删除同一节点，然后崩溃和刻录。

还要修复该警告。

更新 新版本的代码在修复明显错误后，具有损坏的复制构造函数和赋值运算符。

hashTable[i] = hm.hashTable[i];

将使两个哈希表共享数据元素。你想要复制，而不是共享。而且您想复制所有存储桶，而不是sz存储桶（您永远不会更新sz但这是另一个问题）。