如何在 C++ 中正确实现哈希插入函数？

Question

我需要读取一个文件，然后将每个单词存储到带有链表冲突处理的散列table，并计算每个单词出现的次数（节点的值）。当我运行我的代码带有小文本（如 30 行）时它可以工作，但从大约 100 开始它崩溃（分段错误：11）。我知道我的 hashCode 功能不好，但它不应该崩溃。我认为问题在于我如何增加价值。

using namespace std;

class HashNode
{
public:
    string key;
    string value;

public:
    HashNode(string key, int value)
    {
        this->key = key;
        this->value = value;
    }
    friend class HashTable;
};

class HashTable {
    private:
        list<HashNode> *buckets; 
        int size;               
        int capacity;           
        int collisions;

    public:
        HashTable(int capacity){
            buckets = new list<HashNode>[capacity];
            this->capacity = capacity;
            this->size = 0;
            this->collisions = 0;
        }
        ~HashTable()
        {
            for (int i = 0; i < capacity; i++)
                buckets[i].clear();

            delete[] this->buckets;
        }
        int hashCode(string key)
        {
            int sum = 0;
            for (int k = 0; k < key.length(); k++)
                sum = sum + int(key[k]);
            return sum % capacity;
        }
        void insert(string key)
        {
            int value=0;
            int index = hashCode(key) % this->capacity; 

            for (list<HashNode>::iterator it = buckets[index].begin(); it != buckets[index].end(); ++it)
                if (it->key == key)
                {
                    it->value+=1; 
                    return;
                }
            if (buckets[index].size() > 0)
                collisions++;

            buckets[index].push_back(HashNode(key, value)); 
            this->size++;                                   
        }

        int getCollisions()
        {
            return this->collisions;
        }

};

int main() {
    string user_input;
    string word;
    ifstream inFile;
    string parameter;
    string command;
    HashTable object(80000);
    inFile.open("file.txt");
    cout << "Welcome " << endl;
    if (!inFile)
    {
        cout << "Unable to open the file";
        exit(1); 
    }
    listOfCommand();
    while (inFile >> word)
    {   
        object.insert(word);
    }
}

什么会导致此崩溃？任何帮助将不胜感激！

Answer 1

很可能 char 在您的系统中已签名，因此在行 sum = sum + int(key[k]); 中将其转换为整数会导致负值，然后在尝试使用负索引获取 buckets[index] 时出现分段错误。

一个快速的修复方法是首先将 key[k] 转换为 unsigned char，然后才转换为 int:

for (int k = 0; k < key.length(); k++) {
    unsigned char c = static_cast<unsigned_char>(key[k]);
    sum = sum + static_cast<int>(c);
}

如何在 C++ 中正确实现哈希插入函数？

How to correctly implement hash insert function in c++?

c++

hash-function

linked-list

hashmap