我正在练习C ++中哈希映射的实现。我的目标是最终将单词映射到一对与文本文件中的行和列相对应的整数。我从here中获取了哈希映射实现,并以此为基础。当我传递只有一个字母的单词时,代码可以正常工作。但是,当我有一个单词包含多个字母时,代码将在Visual Studio上编译,但在运行时通过此行的读取访问冲突:
HashNode<K,V> *entry = table[hashValue];
(在insert成员函数内)。我认为在寺庙结构中使用琴弦时,可能会有一些我应该不知道的调整;但是,经过数小时的网上搜索,我才真正找不到它。任何解决此问题的想法都将受到赞赏。
#include <string>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;
#define TABLE_SIZE 1028
template <typename K,typename V>
class HashNode {
public:
HashNode(const K &key,const V &value) :
key(key),value(value),next(NULL) {
}
K getKey() const {
return key;
}
V getvalue() const {
return value;
}
void setvalue(V value) {
HashNode::value = value;
}
HashNode *getNext() const {
return next;
}
void setNext(HashNode *next) {
HashNode::next = next;
}
private:
// key-value pair
K key;
V value;
// next bucket with the same key
HashNode *next;
};
template <typename K,typename V,typename F = KeyHash<K>>
class HashMap {
public:
HashMap() {
// construct zero initialized hash table of size
table = new HashNode<K,V> * [TABLE_SIZE]();
}
~HashMap() {
// destroy all buckets one by one
for (int i = 0; i < TABLE_SIZE; ++i) {
HashNode<K,V> *entry = table[i];
while (entry != NULL) {
HashNode<K,V> *prev = entry;
entry = entry->getNext();
delete prev;
}
table[i] = NULL;
}
// destroy the hash table
delete[] table;
}
void get(const K &key,vector<V> &value) {
unsigned long hashValue = hashFunc(key);
HashNode<K,V> *entry = table[hashValue];
while (entry != NULL) {
if (entry->getKey() == key) {
value.push_back(entry->getvalue());
//return true;
}
entry = entry->getNext();
}
//return false;
}
void insert(const K &key,const V &value) {
unsigned long hashValue = hashFunc(key);
HashNode<K,V> *prev = NULL;
HashNode<K,V> *entry = table[hashValue];
while (entry != NULL && entry->getKey() == key) {
prev = entry;
entry = entry->getNext();
}
if (entry == NULL) {
entry = new HashNode<K,V>(key,value);
if (prev == NULL) {
// insert as first bucket
table[hashValue] = entry;
}
else {
prev->setNext(entry);
}
}
else {
// just update the value
entry->setvalue(value);
}
}
void remove(const K &key) {
unsigned long hashValue = hashFunc(key);
HashNode<K,V> *entry = table[hashValue];
while (entry != NULL && entry->getKey() != key) {
prev = entry;
entry = entry->getNext();
}
if (entry == NULL) {
// key not found
return;
}
else {
if (prev == NULL) {
// remove first bucket of the list
table[hashValue] = entry->getNext();
}
else {
prev->setNext(entry->getNext());
}
delete entry;
}
}
private:
// hash table
HashNode<K,V> **table;
F hashFunc;
};
int main()
{
struct MyKeyHash
{
unsigned long operator()(const string & s) const
{
int hash = 7;
for (int i = 0; i < s.length(); i++)
{
hash = hash * 31 + s[i];
}
return hash;
}
};
HashMap<string,tuple<int,int>,MyKeyHash> hmap;
hmap.insert("BB",make_pair(3,3));
hmap.insert("A",make_pair(1,2));
hmap.insert("A",make_pair(4,2));
vector<tuple<int,int>> value;
hmap.get("B",value);
for (auto it : value)
{
cout << get<0>(it) << "," << get<1>(it) << endl;
}
}