用C ++编写散列映射的有效拷贝构造函数 [英] Writing a valid copy constructor for a hash map in C++
问题描述
我现在在为我的哈希映射类创建一个拷贝构造函数时遇到了一些麻烦。目前，我知道如何通过将数组的拷贝构造函数从原始数组拷贝到下一个拷贝构造函数。例如，这里是一个数组列表：
ArrayList :: ArrayList（const ArrayList& a）
：items {new std :: string [a.cap]}，sz {a.sz}，cap {a.cap}
{
// arrayCopy是一个for循环， i] = a.items [i]每次迭代
arrayCopy（items，a.items，sz）;
$ b我知道我们需要将值初始化为一个新的数组列表，他们到一个新的阵列列表。然而，我在绕过我的脑海时想把它做成单独链接的哈希映射。
在我的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的声明
p>
#ifndef HASHMAP_HPP
#define HASHMAP_HPP
#include< functional>
#include< string>
class HashMap
{
public：
typedef std :: function< unsigned int（const std :: string&）>散列函数;
static constexpr unsigned int initialBucketCount = 10;
public：
HashMap（）;
//此构造函数将初始化HashMap以使用特定的
//散列函数，而不是默认的
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：
//这个结构描述了构成
//这个HashMap桶中每一个的链表的节点。
struct Node
{
std :: string key;
std :: string value;
Node * next;
};
//散列函数存储在这里
HashFunction hasher;
private：
节点** hashTable;
unsigned int amountOfBuckets;
unsigned int sz;
public：
unsigned int getTableIndex（unsigned int hashVal）const;
};
这里是我的HashMap.cpp（不完整）代码。另外，我不会使用当前在命名空间中的散列函数。我只是用它作为预测桶索引来测试我的添加/删除功能的简单方法。
#includeHashMap.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; //只需加上字母
} //结束
返回hashValue;
} // end easyHashFunc
}
HashMap :: HashMap（）
：hasher {easyHashFunc}，hashTable {new Node * [initialBucketCount]（）}， amountOfBuckets {initialBucketCount}，sz {0}
{
}
//构造函数初始化HashMap使用不同的哈希函数other
//比默认
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）;
$ b //析构函数：取消分配HashMap
HashMap ::〜HashMap（）
{
for （unsigned int i = 0; i< amountOfBuckets; i ++）{
Node * nextNode = hashTable [i]; //将每个哈希表列表存储在一个桶节点中
while（nextNode！= nullptr）{
Node * deleteCurrent = nextNode; //设置当前节点的节点（head）
nextNode = nextNode-> next; //删除当前位于第一个节点上，更新头到第二个节点
delete deleteCurrent;
} // end while
} // end for
//完成后，删除哈希表
delete [] hashTable;
} //结束析构函数
//赋值运算符，重载等于
HashMap& HashMap :: operator =（const HashMap& hm）
{
//不完整
return * this;
void HashMap :: add（const std :: string& key，const std :: string& value）
{
//检查键是否存在存储的匹配键已经在hashmap中
unsigned int hashedValue = hasher（key）; //获取哈希值（未由桶修改）
unsigned int tableIndex = getTableIndex（hashedValue）; //获取表索引
// case 1，检查current是否为nullptr，这意味着我们的第一个节点
//是我们应该使用的节点，即。我们不需要遍历列表
if（contains（key）== true）{//如果key已经在散列表
return; //退出程序
} else {//否则，key不在散列表中
Node * head = hashTable [tableIndex];
Node * current = head;
if（current == nullptr）{
// bucket中没有任何内容
//创建一个新节点
current = new Node（）;
current-> key = key; //设置用户名
current-> value = value; // set pw
current-> next = nullptr;
hashTable [tableIndex] = current;
return; // exit
} else {
do {
current = current-> next; //前进到下一个节点
} while（current！= nullptr）; // end while while
//当前在节点处我们想要在
current = new Node（） ;
current-> key = key; //设置密钥（用户名）
current-> value = value; //设定值（pw）
current-> next = head;
hashTable [tableIndex] = current; //设置为指向nullptr
} // end end if-else（创建节点）
} //结束外部if-else
} //结束添加
//接收一个密钥（用户名），将其除去，并将值（密码）与
相关联，否则它不起作用
void HashMap :: remove（const std： ：string& key）
{
unsigned int hashedValue = hasher（key）;
unsigned int tableIndex = getTableIndex（hashedValue）;
if（contains（key）== false）{//无法在桶中找到键
return; // do nothing
} else {
Node * prevNode = hashTable [tableIndex];
Node * delNode = prevNode;
if（prevNode-> key == key）{//第一个是匹配
hashTable [tableIndex] = prevNode->下一个; //设置散列表头指向下一个节点
delete delNode;
return; //退出
} else {//否则，我们必须遍历并找到我们想要删除的节点
do {
//检查匹配，如果找到，跳出do while
if（delNode-> key == key）{
break;
}
prevNode = delNode; //保存当前节点在前
delNode = delNode->下; //将搜索到的节点指向下一个节点
} while（delNode！= nullptr）; // end do while
//设置前一个节点指向delNodes下一个节点
prevNode-> next = delNode-> next;
} // end if-else
delete delNode; //取消分配
} //结束外部if-else
} //结束remove（）
//如果给定键位于哈希映射中则返回true，否则返回false
//这是一个find方法
bool HashMap :: contains（const std :: string& key）const
{
unsigned int hashedValue = hasher（key）; //散列给出的键以获得索引
unsigned int tableIndex = getTableIndex（hashedValue）; //获取表索引
Node * current = hashTable [tableIndex];
//遍历链表中的每个节点
//从第一个节点开始（这是当前的）
while（current！= nullptr）{
if（current-> ; key == key）{
return true; //找到匹配项，退出
}
current = current-> next;
} //结束而
返回false; //我们还没有找到匹配
}
// value（）返回与此HashMap中给定键相关的值
//如果键存储在这个HashMap;如果不是，则返回空字符串。
std :: string HashMap :: value（const std :: string& key）const
{
if（contains（key）== true）{//发现匹配
unsigned int hashedValue = hasher（key）; //散列给出的键以获得索引
unsigned int tableIndex = getTableIndex（hashedValue）; //获取表索引
Node * current = hashTable [tableIndex]; （current！= nullptr&& current-> key！= key）{
current = current-> next;
}
返回current->值; //遍历后的返回值
} else {
return; //不匹配，返回空字符串
}
}
unsigned int HashMap :: size（）const
{
return sz;
}
unsigned int HashMap :: bucketCount（）const
{
return amountOfBuckets;
}
double HashMap :: loadFactor（）const
{
return sz / amountOfBuckets;
}
//返回给定散列值的表索引
unsigned int HashMap :: getTableIndex（unsigned int hashVal）const {
return hashVal％amountOfBuckets;
}
HashMap :: HashMap（const HashMap& hm）
{
amountOfBuckets = hm.amountOfBuckets;
hashTable =新节点* [amountOfBuckets];
for（int i = 0; i< amountOfBuckets; i ++）
{
Node * n = hm.hashTable [i];
节点** p =&hashTable [i];
* p = NULL;
while（n）
{
Node * c = new Node（* n）; //节点拷贝构造函数，应该在空值旁边设置n->
* p = c;
p =& c->下;
n = n-> next;
$ b如果你不想要节点拷贝构造函数替换Node * c = new Node（* n）; with：
Node * c = new Node;
c-> key = n-> key;
c-> value = n-> value;
c-> next = NULL;
I'm having some trouble creating a copy constructor for my hash map class right now. Currently, I understand how to do a copy constructor for arrays, by copying things over from the original array to the next. For example, here is what would be done for an array list:
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);
}
I understand that we need to initialize values to a new array list, and copy them over to a new list of arrays. However, I'm having trouble wrapping my mind around doing this to a separately chained hash map.
In my HashMap.hpp file, I have an unmodifiable structure, like this:
struct Node
{
std::string key;
std::string value;
Node* next;
};
I need help understanding how to put each node into my copy constructor. This is my copy constructor, without the actual "copying" code:
HashMap::HashMap(const HashMap& hm)
: hashTable{new Node*[hm.amountOfBuckets]}, amountOfBuckets{hm.amountOfBuckets}, sz{hm.sz}
{
}
How would I accomplish properly iterating through each hash table index, and creating a new node depending on how many there are in the original table? Would I have to create four Nodes, two to keep track of the new table, and two to keep track of the original table?
I tried to implement this and also tried to implement a way to copy over values within a do while loop. This is my code (that doesn't work and completely sucks :( )
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);
With this I run into segmentation faults. I'm really not quite sure how to properly copy over each value into the new hash table? Or how I should go about linking it all together?
Here is the declarations for 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;
};
And here is my (incomplete) code for HashMap.cpp. Also, I will not be using the hash function currently in the namespace. I just used it as an easy way to predict bucket indices to test my add/remove functions.
#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;
}
解决方案 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;
}
}
}
If you don't want Node copy constructor replace Node* c = new Node(*n); with:
Node* c = new Node;
c->key = n->key;
c->value = n->value;
c->next = NULL;
这篇关于用C ++编写散列映射的有效拷贝构造函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
