当前位置：首页 > article >正文

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

article 2025/3/20 3:53:34

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

初始化桶数组：当创建一个std::unordered_map或std::unordered_set时，会初始化一定数量的桶（buckets）。这些桶实际上是用于存放键值对或者仅键（对于unordered_set）的数据结构。
计算哈希值：每当插入一个新的元素（键值对或键），首先通过该元素的键运行哈希函数来计算出一个哈希值。这个哈希值决定了该元素应该被放置在哪个桶中。
定位桶并处理冲突：
- 根据哈希值确定对应的桶。
- 如果目标桶当前为空，则直接将新元素插入到该桶中。
- 如果目标桶中已经存在其他元素，则说明发生了哈希冲突。此时，C++标准库通常使用**链地址法（Separate Chaining）**来解决冲突。这意味着每个桶实际上是一个链表，所有哈希到同一个桶的元素都会被添加到这个链表中。
负载因子监控与自动扩容：随着越来越多的元素被插入，哈希表的负载因子（即元素数量除以桶的数量）会逐渐增加。一旦负载因子超过某个阈值，哈希表会自动进行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号桶的链表中。