时间戳

首页 > 解决方案 > 自定义哈希表实现 - 将字符串映射到整数时出现内存错误

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

问题描述

我正在练习 C++ 中哈希映射的实现。我的目标是最终将单词映射到一对整数，这些整数对应于文本文件中的行和列。我从这里获取了哈希映射实现并以此为基础。当我只用一个字母传递单词时，代码可以正常工作。但是，当我有一个包含多个字母的单词时，代码会在 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;
    }
}

标签： c++hashmaphashtable

解决方案

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）。但是是一个长度为（1028）table的数组。TABLE_SIZE如果输出恰好大于此值，则您正在越界访问它。

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

你可能是说

unsigned long hashValue = hashFunc(key)%TABLE_SIZE;

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

推荐阅读