哈希表在C++中的具体实现（unordered_map）

哈希表在C++标准库中的主要实现是std::unordered_map，它是一个关联容器，存储的是键值对（key-value pairs），并且提供平均常数时间复杂度的查找、插入和删除操作。

1. 基本结构与模板参数

std::unordered_map是一个类模板，其声明大致如下：

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class unordered_map;

• Key: 键的类型。
• T: 值的类型。
• Hash: 哈希函数对象类型，用于计算键的哈希值。默认是std::hash<Key>，对于基本数据类型（如int, string）标准库已提供特化版本。
• KeyEqual: 键比较函数对象类型，用于在哈希冲突时比较键是否相等。默认是std::equal_to<Key>（即使用operator==）。
• Allocator: 内存分配器。

3. 内部数据结构：桶数组与链表

unordered_map的典型实现结合了动态数组（桶数组）和单向链表。

• 桶数组（Bucket Array）：一个动态分配的指针数组，每个数组元素称为一个“桶”（bucket）。桶数组的大小通常是一个质数，这有助于哈希值更均匀地分布。
• 链表节点：每个桶并不直接存储键值对，而是指向一个链表的头节点。这个链表用于存储所有哈希到同一个桶的键值对。在C++标准库的常见实现（如GCC的libstdc++和LLVM的libc++）中，这个链表是单向链表。

一个简化的节点结构可能像这样：

struct node {
    std::pair<const Key, T> data; // 存储键值对，键是const的
    node* next;                   // 指向下一个节点的指针
    // ... 可能还有其他实现相关的元数据
};

整个结构可以想象成一个“数组+链表”的形式：

桶数组: [0] -> nullptr
        [1] -> node{K1,V1} -> node{K2,V2} -> nullptr
        [2] -> nullptr
        ...
        [n] -> node{K3,V3} -> nullptr

4. 核心操作过程

插入操作（insert/emplace/operator[]）

1. 计算哈希值：对于给定的键key，使用哈希函数对象Hash计算其哈希值：hash_value = Hash{}(key)。
2. 映射到桶索引：通过取模运算（或其他压缩函数）将哈希值映射到桶数组的索引：bucket_index = hash_value % bucket_count。这个索引决定了键值对应该放入哪个桶对应的链表中。
3. 处理冲突与查找重复键：
   • 遍历指定桶索引对应的链表。
   • 对于链表中的每个节点，使用KeyEqual比较函数检查节点的键是否与要插入的键相等。
   • 如果找到相等的键：根据插入策略（例如insert会失败并返回已有元素迭代器，而operator[]会修改其值），操作结束。
   • 如果未找到相等的键：创建一个新的节点来存储键值对，然后将这个新节点插入到链表的头部（或尾部，取决于实现，头部插入更常见因为速度快）。这是一个常数时间操作。

查找操作（find）

1. 计算哈希值与桶索引：与插入操作的前两步完全相同。
2. 遍历链表：在计算得到的桶索引对应的链表中，逐个节点比较键是否相等。
3. 返回结果：如果找到相等的键，返回指向该键值对的迭代器；如果遍历完整个链表都没找到，返回end()迭代器。

删除操作（erase）

1. 定位节点：首先执行类似查找的步骤，找到要删除的节点及其前驱节点（因为是单向链表，需要前驱节点来修改next指针）。
2. 修改链表：将前驱节点的next指针指向要删除节点的下一个节点。
3. 释放内存：删除节点并释放其占用的内存。

5. 动态扩容（Rehashing）

为了维持操作的效率，当元素数量过多导致链表过长时，unordered_map需要进行扩容。

• 触发条件：当负载因子（load factor）（即size() / bucket_count()，元素数量除以桶的数量）超过最大负载因子（max_load_factor）（默认约为1.0）时，会自动触发扩容。也可以手动调用rehash。
• 扩容过程：
  1. 分配一个新的、更大的桶数组（新的大小通常是一个比当前桶数大的质数）。
  2. 遍历旧桶数组中的所有桶，以及每个桶对应的链表上的所有节点。
  3. 对于每个节点中的键值对，根据新的桶数组大小重新计算其桶索引（new_index = hash_value % new_bucket_count）。
  4. 将每个节点从旧链表中取出，并插入到新桶数组对应链表的新位置。
• 性能影响：扩容是一个O(n)操作（n是元素数量），因此单个插入操作在最坏情况下是O(n)。但使用均摊分析，多次插入操作的平均时间复杂度仍然是O(1)。

6. 迭代器

unordered_map的迭代器需要能够遍历所有元素。它内部需要维护两个指针：

• 一个指向当前节点（在某个链表中）。
• 一个指向当前桶在桶数组中的位置。
  当迭代完当前链表后，迭代器需要移动到桶数组中下一个非空的桶的链表头部。因此，遍历unordered_map的顺序是不可预测的，与键的哈希值分布和桶数组大小有关。

总结
std::unordered_map在C++中通过“桶数组+单向链表”解决哈希冲突，提供了高效的键值对存储。其核心在于通过哈希函数快速定位桶，再在短链表中进行精确操作。动态扩容机制确保了性能的稳定。理解其内部结构有助于在C++中更有效地使用该容器。