c++ - 在 C++ 中为 HashMap 编写有效的复制构造函数

Question

我现在在为我的 HashMap 类创建复制构造函数时遇到了一些问题。目前，我了解如何通过将内容从原始数组复制到下一个来为数组执行复制构造函数。例如，这是对数组列表的处理:

ArrayList::ArrayList(const ArrayList& a)
    : items{new std::string[a.cap]}, sz{a.sz}, cap{a.cap}
{
    // arrayCopy is a for loop that does items[i] = a.items[i] on each iteration
    arrayCopy(items, a.items, sz);
}

我知道我们需要将值初始化为一个新的数组列表，并将它们复制到一个新的数组列表中。但是，我无法全神贯注地对单独链接的 HashMap 执行此操作。

在我的 HashMap.hpp 文件中，我有一个不可修改的结构，如下所示:

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

我需要帮助了解如何将每个节点放入我的复制构造函数中。这是我的复制构造函数，没有实际的“复制”代码:

HashMap::HashMap(const HashMap& hm)
   : hashTable{new Node*[hm.amountOfBuckets]}, amountOfBuckets{hm.amountOfBuckets}, sz{hm.sz}
{
}

我如何正确地遍历每个哈希表索引，并根据原始表中的节点数创建一个新节点？我是否必须创建四个节点，两个用于跟踪新表，两个用于跟踪原始表？

我尝试实现这一点，还尝试实现一种在 do while 循环中复制值的方法。这是我的代码(它不起作用并且完全糟透了:( )

  for(unsigned int i = 0; i < amountOfBuckets; i++) {
        // target
        Node* newHead = hashTable[i];
        Node* newCurrent = newHead;
        // source
        Node* head = hm.hashTable[i];
        Node* current = head;
        do{
            newCurrent = new Node();
            newCurrent->key = current->key;
            newCurrent->value = current->value;
            newCurrent->next = current->next;
            newCurrent = hashTable[i];
        } while(newCurrent != nullptr);

有了这个，我遇到了段错误。我真的不太确定如何正确地将每个值复制到新的哈希表中？或者我应该如何将它们链接在一起？

这是 HashMap.hpp 的声明

#ifndef HASHMAP_HPP
#define HASHMAP_HPP
#include <functional>
#include <string>
class HashMap
{
public:
    typedef std::function<unsigned int(const std::string&)> HashFunction;
    static constexpr unsigned int initialBucketCount = 10;
public:
    HashMap();

    // This constructor instead initializes the HashMap to use a particular
    // hash function instead of the default
    HashMap(HashFunction hasher);

    HashMap(const HashMap& hm);
    ~HashMap();
    HashMap& operator=(const HashMap& hm);

    void add(const std::string& key, const std::string& value);
    void remove(const std::string& key);
    bool contains(const std::string& key) const;
    std::string value(const std::string& key) const;

    unsigned int size() const;
    unsigned int bucketCount() const;
    double loadFactor() const;
    unsigned int maxBucketSize() const;


private:
    // This structure describes the nodes that make up the linked lists in
    // each of this HashMap's buckets.
    struct Node
    {
        std::string key;
        std::string value;
        Node* next;
    };
    // hash function gets stored in here
    HashFunction hasher;
private:
    Node** hashTable;
    unsigned int amountOfBuckets;
    unsigned int sz;

public:
    unsigned int getTableIndex(unsigned int hashVal) const;
};

这是我的(不完整的)HashMap.cpp 代码。此外，我不会使用命名空间中当前的哈希函数。我只是将它用作预测存储桶索引以测试我的添加/删除功能的简单方法。

#include <iostream>
#include "HashMap.hpp"

namespace {
    unsigned int easyHashFunc(const std::string& key) {
        unsigned int hashValue = 0;
        for(int i = 0; i < key.length(); i++) {
            int letterIndex = key.at(i);
            hashValue += letterIndex; // just add up the letters
        } // end for
        return hashValue;
    } // end easyHashFunc
}

HashMap::HashMap()
    : hasher{easyHashFunc}, hashTable{new Node*[initialBucketCount]()}, amountOfBuckets{initialBucketCount}, sz{0}
{
}

// constructor that initializes HashMap to use a different hash function other
// than the default
HashMap::HashMap(HashFunction hasher)
    : hasher{hasher}, hashTable{new Node*[initialBucketCount]()}, amountOfBuckets{initialBucketCount}, sz{0}
{
}

HashMap::HashMap(const HashMap& hm)
   : hashTable{new Node*[hm.amountOfBuckets]}, amountOfBuckets{hm.amountOfBuckets}, sz{hm.sz}
{
    for(unsigned int i = 0; i < amountOfBuckets; i++) {
        Node* newHead = hashTable[i];
        Node* newCurrent = newHead;
        // source
        Node* head = hm.hashTable[i];
        Node* current = head;
        do{
            newCurrent = new Node();
            newCurrent->key = current->key;
            newCurrent->value = current->value;
            newCurrent->next = current->next;
            newCurrent = hashTable[i];
        } while(newCurrent != nullptr);
    }
}


// destructor: deallocate the HashMap
HashMap::~HashMap()
{
    for(unsigned int i = 0; i < amountOfBuckets; i++) {
        Node* nextNode = hashTable[i]; // store each hashtable list in a bucket node
        while(nextNode != nullptr) {
            Node* deleteCurrent = nextNode; // set current to the bucket node (head)
            nextNode = nextNode->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

// Assignment operator that overloads equals
HashMap& HashMap::operator=(const HashMap& hm)
{
    // incomplete
    return *this;
}

void HashMap::add(const std::string& key, const std::string& value)
{
    // Check if key being stored matches key already in hashmap
    unsigned int hashedValue = hasher(key); // get hash value (unmodified by buckets)
    unsigned int tableIndex = getTableIndex(hashedValue); // get the table index
    // case 1, check to see if current is nullptr, meaning our first node
    // is the one we should use, ie. we don't need to traverse the list
    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];
        Node* current = head;
        if(current == nullptr) {
            // nothing in bucket
            // create a new node
            current = new Node();
            current->key = key; // set username
            current->value = value; // set pw
            current->next = nullptr;
            hashTable[tableIndex] = current;
            return; // exit
        } else {
            do {
                current = current->next; // advance to next node
            }while(current != nullptr);// 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 = head;
            hashTable[tableIndex] = current; // set next to point to nullptr
        } // end inner if-else (creates node)
    } // end outer if-else
} // end add

// takes in a key (username), removes it and the value (password) associated
// with it, otherwise, it has no effect
void HashMap::remove(const std::string& key)
{
    unsigned int hashedValue = hasher(key);
    unsigned int tableIndex = getTableIndex(hashedValue);
    if(contains(key) == false) { // could not find key in bucket
        return; // do nothing
    } else {
        Node* prevNode = hashTable[tableIndex];
        Node* delNode = prevNode;
        if(prevNode->key == key) { // first one is a match
            hashTable[tableIndex] = prevNode->next; // set the head of the hash table to point to the next node
            delete delNode;
            return; // exit
        } else { // otherwise, we must loop through and find the node we want to delete
            do{
                // check for match, if found, break out of do while
                if(delNode->key == key) {
                    break;
                }
                prevNode = delNode; // save current node in previous
                delNode = delNode->next; // point the searched node to the next node
            }while(delNode != nullptr); // end do while
            // set the previous node to point to delNodes next node
            prevNode->next = delNode->next;
        } // end inner if-else
        delete delNode; // de-allocate
    } // end outer if-else
} // end remove()

// returns true if given key is in hash map, otherwise returns false
// this acts as a find method
bool HashMap::contains(const std::string& key) const
{
    unsigned int hashedValue = hasher(key); // hash the key given to get an index
    unsigned int tableIndex = getTableIndex(hashedValue); // get the table index
    Node* current = hashTable[tableIndex];
    // iterate through each node in the linked list
    // start at first node (this is current)
    while(current != nullptr) {
        if(current->key == key) {
            return true; // found match, exit
        }
        current = current->next;
    } // end while
        return false; // we haven't found a match
}

// value() returns the value associated with the given key in this HashMap
// if the key is stored in this HashMap; if not, the empty string is returned.
std::string HashMap::value(const std::string& key) const
{
    if(contains(key) == true) { // found match
        unsigned int hashedValue = hasher(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
    }
}

unsigned int HashMap::size() const
{
    return sz;
}

unsigned int HashMap::bucketCount() const
{
    return amountOfBuckets;
}

double HashMap::loadFactor() const
{
    return sz / amountOfBuckets;
}

// return the table index for a given hashvalue
unsigned int HashMap::getTableIndex(unsigned int hashVal) const {
    return hashVal % amountOfBuckets;
}

Answer 1

HashMap::HashMap(const HashMap& hm)
{
    amountOfBuckets=hm.amountOfBuckets; 
    hashTable= new Node* [amountOfBuckets];

    for (int i=0; i<amountOfBuckets; i++)
    {
        Node* n = hm.hashTable[i];
        Node** p = &hashTable[i];
        *p = NULL;
        while (n)
        {
            Node* c = new Node(*n); // node copy constructor, should set n->next to null
            *p = c;
            p=&c->next;
            n=n->next;
        }
    }
}

如果您不想使用 Node 复制构造函数替换 Node* c = new Node(*n);与:

        Node* c = new Node;
        c->key = n->key;
        c->value = n->value;
        c->next = NULL;