IT评测·应用市场-qidao123.com

标题: STL中的哈希表(unordered_map和unordered_set内部使用的数据结构) [打印本页]

作者: 天津储鑫盛钢材现货供应商 时间: 2025-3-16 12:03
标题: STL中的哈希表(unordered_map和unordered_set内部使用的数据结构)
在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号桶的链表中。

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)