讲座主题：C++中实现一个高效率的哈希表——让我们一起“哈希”到底！

大家好！今天我们要聊一聊如何在C++中实现一个高效、优雅且性能卓越的哈希表。哈希表是计算机科学中最常用的抽象数据结构之一，它就像一位默默无闻但极其可靠的助手，帮助我们快速查找、插入和删除数据。那么，如何用C++来打造这样一个高性能的工具呢？让我们一起深入探讨吧！

---

第一幕：哈希表的基本原理

首先，我们需要明确哈希表的核心思想：通过一个哈希函数将键（key）映射到一个数组的索引位置，从而实现快速访问。听起来很简单对吧？但实际上，要让这个过程既快又稳定，还需要考虑很多细节。

哈希表的关键要素

1. 哈希函数：将键转换为数组索引。
2. 冲突解决策略：当两个键被映射到同一个索引时怎么办？
3. 动态扩容：当表变得太满时，如何扩展以保持性能？

---

第二幕：设计选择与取舍

在C++中实现哈希表时，我们需要做出一些关键的设计决策。以下是几个重要方向：

1. 哈希函数的选择

一个好的哈希函数应该满足以下条件：

• 均匀分布：尽量减少碰撞（collision）。
• 快速计算：哈希函数的执行速度直接影响整体性能。

常见的哈希函数有FNV、MurmurHash和DJB2等。这里我们选择DJB2作为例子，因为它简单且性能不错。

size_t djb2_hash(const std::string& key) {
    size_t hash = 5381;
    for (char c : key) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}

2. 冲突解决策略

冲突不可避免，因此我们需要一种有效的解决方案。常见的方法有两种：

• 链地址法（Chaining）：每个桶存储一个链表。
• 开放寻址法（Open Addressing）：在表内寻找下一个空闲位置。

链地址法 vs 开放寻址法

特性	链地址法	开放寻址法
空间利用率	较低（需要额外的指针）	较高
插入/查找性能	在小负载因子下表现优异	对负载因子敏感
删除操作	简单	复杂（可能需要标记删除）

在这里，我们选择链地址法，因为它更易于实现且适合大多数场景。

---

第三幕：代码实现

接下来，我们用C++实现一个简单的哈希表。为了便于理解，我们将逐步构建。

1. 定义哈希表的基本结构

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

template <typename Key, typename Value>
class HashTable {
private:
    struct Entry {
        Key key;
        Value value;
        Entry(const Key& k, const Value& v) : key(k), value(v) {}
    };

    std::vector<std::list<Entry>> table; // 使用链地址法
    size_t size;

    size_t hash_function(const Key& key) const {
        return std::hash<Key>{}(key) % table.size();
    }

public:
    HashTable(size_t initial_size = 10) : table(initial_size), size(0) {}

    void insert(const Key& key, const Value& value);
    Value* find(const Key& key);
    void remove(const Key& key);
};

2. 实现插入操作

template <typename Key, typename Value>
void HashTable<Key, Value>::insert(const Key& key, const Value& value) {
    size_t index = hash_function(key);
    for (auto& entry : table[index]) {
        if (entry.key == key) { // 如果键已存在，更新值
            entry.value = value;
            return;
        }
    }
    table[index].emplace_back(key, value); // 否则插入新条目
    ++size;
}

3. 实现查找操作

template <typename Key, typename Value>
Value* HashTable<Key, Value>::find(const Key& key) {
    size_t index = hash_function(key);
    for (const auto& entry : table[index]) {
        if (entry.key == key) {
            return &entry.value;
        }
    }
    return nullptr; // 如果未找到，返回空指针
}

4. 实现删除操作

template <typename Key, typename Value>
void HashTable<Key, Value>::remove(const Key& key) {
    size_t index = hash_function(key);
    for (auto it = table[index].begin(); it != table[index].end(); ++it) {
        if (it->key == key) {
            table[index].erase(it);
            --size;
            return;
        }
    }
}

---

第四幕：性能优化与动态扩容

为了让我们的哈希表更加高效，我们需要引入动态扩容机制。当负载因子（size / table.size()）超过某个阈值时，我们可以重新分配更大的表并重新哈希所有元素。

template <typename Key, typename Value>
void HashTable<Key, Value>::rehash() {
    std::vector<std::list<Entry>> old_table = table;
    table = std::vector<std::list<Entry>>(table.size() * 2);
    size = 0;

    for (const auto& bucket : old_table) {
        for (const auto& entry : bucket) {
            insert(entry.key, entry.value); // 重新插入
        }
    }
}

// 修改插入函数，检查是否需要扩容
template <typename Key, typename Value>
void HashTable<Key, Value>::insert(const Key& key, const Value& value) {
    if (size >= table.size() * 0.75) { // 负载因子达到75%
        rehash();
    }
    // 原始插入逻辑
    size_t index = hash_function(key);
    for (auto& entry : table[index]) {
        if (entry.key == key) {
            entry.value = value;
            return;
        }
    }
    table[index].emplace_back(key, value);
    ++size;
}

---

第五幕：总结与展望

通过今天的讲座，我们学会了如何在C++中实现一个高效的哈希表。从哈希函数的选择到冲突解决策略，再到动态扩容机制，每一步都至关重要。当然，这只是一个基础版本，实际应用中可能还需要考虑更多的细节，比如线程安全、内存管理等。

希望这篇文章能激发你对哈希表的兴趣！如果你有任何问题或想法，欢迎随时交流。下次见啦！