C++哈希表详解（链地址法实现哈希冲突解决的完整教程）

C++实现链地址法哈希表

下面我们将一步步用C++实现一个基于链地址法的哈希表。我们将使用标准库中的 vector 作为桶数组，每个桶是一个 list（链表）来存储键值对。

1. 包含必要的头文件

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

2. 定义哈希表类

我们定义一个模板类 HashMap，支持任意类型的键和值。

template<typename K, typename V>class HashMap {private:    // 桶的数量    static const int TABLE_SIZE = 10;        // 使用 vector 存储链表（每个桶是一个 list）    std::vector<std::list<std::pair<K, V>>> table;        // 简单的哈希函数（仅适用于整数键）    int hash(const K& key) {        return key % TABLE_SIZE;    }public:    HashMap() : table(TABLE_SIZE) {}        void insert(const K& key, const V& value);    bool search(const K& key, V& value);    void remove(const K& key);    void display();};

3. 实现插入操作

插入时，先计算哈希值，找到对应桶，然后遍历链表检查是否已存在该键。如果存在则更新值，否则插入新节点。

template<typename K, typename V>void HashMap<K, V>::insert(const K& key, const V& value) {    int index = hash(key);        // 遍历链表，检查键是否已存在    for (auto& pair : table[index]) {        if (pair.first == key) {            pair.second = value; // 更新值            return;        }    }        // 键不存在，插入新键值对    table[index].push_back(std::make_pair(key, value));}

4. 实现查找操作

template<typename K, typename V>bool HashMap<K, V>::search(const K& key, V& value) {    int index = hash(key);        for (const auto& pair : table[index]) {        if (pair.first == key) {            value = pair.second;            return true;        }    }    return false; // 未找到}

5. 实现删除操作

template<typename K, typename V>void HashMap<K, V>::remove(const K& key) {    int index = hash(key);        auto& bucket = table[index];    for (auto it = bucket.begin(); it != bucket.end(); ++it) {        if (it->first == key) {            bucket.erase(it);            return;        }    }}

6. 显示哈希表内容（用于调试）

template<typename K, typename V>void HashMap<K, V>::display() {    for (int i = 0; i < TABLE_SIZE; ++i) {        std::cout << "Bucket " << i << ": ";        for (const auto& pair : table[i]) {            std::cout << "[" << pair.first << ", " << pair.second << "] ";        }        std::cout << std::endl;    }}

7. 主函数测试

int main() {    HashMap<int, std::string> map;        // 插入数据    map.insert(1, "Apple");    map.insert(11, "Banana"); // 与1冲突（11 % 10 = 1）    map.insert(2, "Cherry");    map.insert(22, "Date");  // 与2冲突        // 显示哈希表    std::cout << "哈希表内容：\n";    map.display();        // 查找    std::string value;    if (map.search(11, value)) {        std::cout << "\n键 11 对应的值是: " << value << std::endl;    }        // 删除    map.remove(1);    std::cout << "\n删除键 1 后：\n";    map.display();        return 0;}

总结

通过本教程，你已经学会了如何在C++中使用链地址法实现哈希表。这种方法简单有效，能够很好地处理哈希冲突问题。对于初学者来说，理解这种数据结构的实现有助于深入掌握C++编程和算法设计。

记住，实际项目中可能需要更复杂的哈希函数（尤其是处理字符串键时），以及动态扩容机制来保证性能。但本教程提供的基础框架已经涵盖了C++哈希表的核心思想。

希望这篇哈希表编程教程对你有所帮助！动手实践是掌握编程的关键，建议你复制代码并尝试修改参数，观察不同输入下的行为。