STL中的哈希表(unordered_map和unordered_set内部使用的数据结构)

在 std::unordered_map 和 std::unordered_set 中，数据的存储与管理主要依赖于哈希表这种数据结构。

哈希表的工作流程

1. 初始化桶数组 ：当创建一个 std::unordered_map 或 std::unordered_set 时，会初始化一定数量的桶（buckets）。这些桶实际上是用于存放键值对或者仅键（对于 unordered_set ）的数据结构。

2. 计算哈希值 ：每当插入一个新的元素（键值对或键），首先通过该元素的键运行哈希函数来计算出一个哈希值。这个哈希值决定了该元素应该被放置在哪个桶中。

3. 定位桶并处理冲突 ：

   • 根据哈希值确定对应的桶。
   • 如果目标桶当前为空，则直接将新元素插入到该桶中。
   • 如果目标桶中已经存在其他元素，则说明发生了哈希冲突。此时，C++标准库通常使用**链地址法（Separate Chaining）**来解决冲突。这意味着每个桶实际上是一个链表，所有哈希到同一个桶的元素都会被添加到这个链表中。

4. 负载因子监控与自动扩容 ：随着越来越多的元素被插入，哈希表的负载因子（即元素数量除以桶的数量）会逐渐增加。一旦负载因子超过某个阈值，哈希表会自动进行rehash操作，也就是增加桶的数量，并重新分配所有元素以保持较低的负载因子，从而确保查找、插入和删除操作的平均时间复杂度接近O(1)。

   

示例

假设我们有一个 std::unordered_map<int, std::string> ，并且插入了以下键值对：

• 插入 (1, "Apple")

  • 假设哈希函数为 h(k) = k % 8 （这里只是举例），则键 1 的哈希值为 1 % 8 = 1 。所以它会被放入第1号桶中。

• 接着插入 (9, "Banana")

  • 键 9 的哈希值同样为 9 % 8 = 1 。这导致了一个冲突，因为第1号桶已经有了一个元素。
  • 在这种情况下， "Banana" 会被添加到第1号桶的链表中。

这样，当需要查找键 9 对应的值 "Banana" 时，系统会先通过哈希函数找到第1号桶，然后遍历该桶中的链表找到对应的键值对。