C++链式哈希表详解（手把手教你用链地址法实现哈希表）

这种方式简单、高效，而且能很好地处理任意数量的冲突。这也是我们今天要实现的核心——链地址法哈希表。

C++实现链式哈希表

我们将使用 C++ 标准库中的 vector 作为桶数组，每个桶是一个 list（或 forward_list），用来存储键值对。

1. 定义节点结构

首先，我们需要一个结构体来保存键值对：

struct KeyValuePair {    int key;    std::string value;    KeyValuePair(int k, const std::string& v) : key(k), value(v) {}};

2. 实现哈希函数

为了简化，我们使用取模运算作为哈希函数：

size_t hashFunction(int key, size_t tableSize) {    return key % tableSize;}

3. 完整的链式哈希表类

现在，我们把所有部分组合成一个完整的类：

#include <iostream>#include <vector>#include <list>#include <string>class ChainedHashTable {private:    std::vector<std::list<KeyValuePair>> buckets;    size_t tableSize;    size_t hashFunction(int key) {        return key % tableSize;    }public:    // 构造函数    ChainedHashTable(size_t size = 10) : tableSize(size) {        buckets.resize(tableSize);    }    // 插入键值对    void insert(int key, const std::string& value) {        size_t index = hashfunction(key);        for (auto& pair : buckets[index]) {            if (pair.key == key) {                pair.value = value; // 更新已有键                return;            }        }        buckets[index].emplace_back(key, value);    }    // 查找值    std::string search(int key) {        size_t index = hashfunction(key);        for (const auto& pair : buckets[index]) {            if (pair.key == key) {                return pair.value;            }        }        return "Key not found";    }    // 删除键    bool remove(int key) {        size_t index = hashfunction(key);        auto& bucket = buckets[index];        for (auto it = bucket.begin(); it != bucket.end(); ++it) {            if (it->key == key) {                bucket.erase(it);                return true;            }        }        return false;    }};

注意：上面代码中的 hashfunction 应为 hashFunction（大小写敏感），这是为了演示常见错误。实际使用时请确保函数名一致。

4. 使用示例

int main() {    ChainedHashTable ht(7); // 创建大小为7的哈希表    ht.insert(10, "Alice");    ht.insert(20, "Bob");    ht.insert(17, "Charlie"); // 17 % 7 = 3，与10不同桶    ht.insert(3, "David");    // 3 % 7 = 3，与17同桶 → 链表    std::cout << ht.search(10) << std::endl;  // 输出: Alice    std::cout << ht.search(3) << std::endl;   // 输出: David    std::cout << ht.search(99) << std::endl;  // 输出: Key not found    ht.remove(3);    std::cout << ht.search(3) << std::endl;   // 输出: Key not found    return 0;}

性能分析

在理想情况下（哈希函数均匀分布），每个桶的链表长度很短，操作接近 O(1)。最坏情况下（所有键都哈希到同一桶），退化为链表，时间复杂度为 O(n)。因此，选择合适的哈希函数和负载因子（元素数 / 桶数）非常重要。

总结

通过本教程，你已经学会了如何用 C++ 实现一个基于链地址法的哈希表。这种 C++链式哈希表结构灵活、易于扩展，是解决哈希冲突的经典方法。无论你是准备面试，还是开发高性能应用，掌握 链地址法哈希表 和 C++哈希表实现 都是非常有价值的技能。

动手试试吧！修改哈希函数、添加动态扩容功能，或者用模板让它支持任意类型键值——你的哈希表，由你掌控！