《灵珠觉醒：从零到算法金仙的C++修炼》卷八·鸿蒙初判（76）山河社稷图展散列 - 设计哈希表（拉链法）

在这篇文章中，我们跟随小哪吒学习了如何使用拉链法设计高效的哈希表。通过暴力解法的尝试，哪吒意识到简单的线性探测虽然直观，但在处理冲突时效率低下。在太乙真人的指引下，他领悟了拉链法的精髓，通过在每个桶中维护链表，将冲突的键值对存储在链表中，大幅提高了哈希表的插入和查找效率。我们还详细介绍了C++中向量、字符串和配对的基本方法。通过这次修炼，哪吒不仅提升了算法能力，还对哈希表的应用有了更深刻的理解。

轻口味

1204人浏览 · 2025-03-19 14:00:00

轻口味 · 2025-03-19 14:00:00 发布

《灵珠觉醒：从零到算法金仙的C++修炼》卷八·鸿蒙初判（76）山河社稷图展散列 - 设计哈希表（拉链法）

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的山河社稷图领域，图中蕴含着散列的奥秘，代表着高效数据存储与检索的智慧。领域的入口处有一块巨大的石碑，上面刻着一行文字：“欲展此图，需以山河之力，设计哈希表，拉链法显真身。”

哪吒定睛一看，石碑上还有一行小字：“当存储键值对{“apple”: 1, “banana”: 2, “cherry”: 3}时，通过哈希函数计算键的哈希值，将冲突的键值对存储在链表中。”哪吒心中一动，他知道这是一道关于哈希表设计的难题，需要通过拉链法来解决。

暴力解法：山河社稷图的初次尝试

哪吒心想：“要设计哈希表，我可以尝试直接使用数组存储键值对，并在冲突时顺序查找空位。”他催动山河社稷图之力，通过简单的数组和线性探测，试图实现哈希表的基本功能。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int DEFAULT_CAPACITY = 10;

class HashTable {
private:
    vector<pair<string, int>> table;
    int size;

    int hash(const string& key) {
        int hashValue = 0;
        for (char c : key) {
            hashValue = hashValue * 31 + c;
        }
        return hashValue % table.size();
    }

public:
    HashTable() : size(0) {
        table.resize(DEFAULT_CAPACITY);
    }

    void put(const string& key, int value) {
        int index = hash(key);
        while (!table[index].first.empty()) {
            if (table[index].first == key) {
                table[index].second = value;
                return;
            }
            index = (index + 1) % table.size();
        }
        table[index] = {key, value};
        size++;
    }

    int get(const string& key) {
        int index = hash(key);
        while (!table[index].first.empty()) {
            if (table[index].first == key) {
                return table[index].second;
            }
            index = (index + 1) % table.size();
        }
        return -1;
    }
};

int main() {
    HashTable ht;
    ht.put("apple", 1);
    ht.put("banana", 2);
    ht.put("cherry", 3);
    cout << "apple的值为：" << ht.get("apple") << endl;
    return 0;
}

哪吒成功地实现了哈希表的基本功能，但山河社稷图领域的光芒却黯淡了下来。他意识到，这种方法在处理冲突时效率低下，尤其是当哈希表的负载因子较高时，线性探测会导致聚集问题，增加查找时间。

C++语法点

在C++中，哈希表的实现涉及到向量、字符串和配对。以下是一些重要特性：

向量操作：
- 使用vector类型存储哈希表的桶。
- 使用resize方法调整向量大小。
字符串哈希：
- 自定义哈希函数计算字符串的哈希值。
配对：
- 使用pair类型存储键值对。

高阶优化：拉链法的智慧

哪吒元神中突然浮现金色铭文——「山河社稷图展散列，拉链法显真身」。他意识到，可以通过拉链法优化哈希表的冲突处理，将冲突的键值对存储在链表中，从而减少查找时间。

哪吒决定使用拉链法，在每个桶中维护一个链表，将冲突的键值对存储在链表中。通过这种方式，他成功地优化了哈希表的插入和查找效率，灵力消耗也得到了大幅减少。

#include <iostream>
#include <vector>
#include <string>
#include <list>

using namespace std;

const int DEFAULT_CAPACITY = 10;

class HashTable {
private:
    vector<list<pair<string, int>>> table;
    int size;

    int hash(const string& key) {
        int hashValue = 0;
        for (char c : key) {
            hashValue = hashValue * 31 + c;
        }
        return hashValue % table.size();
    }

public:
    HashTable() : size(0) {
        table.resize(DEFAULT_CAPACITY);
    }

    void put(const string& key, int value) {
        int index = hash(key);
        for (auto& entry : table[index]) {
            if (entry.first == key) {
                entry.second = value;
                return;
            }
        }
        table[index].push_back({key, value});
        size++;
    }

    int get(const string& key) {
        int index = hash(key);
        for (const auto& entry : table[index]) {
            if (entry.first == key) {
                return entry.second;
            }
        }
        return -1;
    }

    void remove(const string& key) {
        int index = hash(key);
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (it->first == key) {
                table[index].erase(it);
                size--;
                return;
            }
        }
    }
};

int main() {
    HashTable ht;
    ht.put("apple", 1);
    ht.put("banana", 2);
    ht.put("cherry", 3);
    cout << "apple的值为：" << ht.get("apple") << endl;
    ht.remove("banana");
    cout << "banana的值为：" << ht.get("banana") << endl;
    return 0;
}