c++ - 自定义哈希表实现 - 将字符串映射到整数时出现内存错误

Question

我正在练习用 C++ 实现 HashMap 。我的目标是最终将单词映射到一对整数，这对整数对应于文本文件中的行和列。我从 here 中获取了 HashMap 实现并以此为基础。当我只用一个字母传递单词时，代码工作正常。但是，当我有一个包含多个字母的单词时，代码会在 Visual Studio 上编译，但在运行时会在这一行发生读取访问冲突:

HashNode<K, V> *entry = table[hashValue];

(在插入成员函数内)。我认为在寺庙结构中使用琴弦时可能需要考虑一些我可能没有意识到的调整；但是，在网上搜索了几个小时后，我还是找不到它。非常感谢任何有关如何解决此问题的想法。

#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> *prev = NULL;
        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;
    }
}

Answer 1

unsigned long hashValue = hashFunc(key);
//...
table[hashValue]

函数返回hashValue

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;
}

可以返回任意大的值(在int范围内)。但是 table 是一个长度为 TABLE_SIZE (1028) 的数组。如果输出恰好大于该值，则说明您正在越界访问它。

函数的编写方式，对于较长的输入字符串更有可能发生这种情况。

你可能是说

unsigned long hashValue = hashFunc(key)%TABLE_SIZE;

另请注意，如果字符串足够长，您的哈希函数会溢出，导致未定义的行为(因为您使用的是带符号的整数)。您应该使用 unsigned long 而不是 int，匹配返回类型并且是无符号的。