unordered_map是C++标准库提供的关联式容器，底层基于哈希表实现，核心目标是实现平均O(1)时间复杂度的插入、查询和删除操作。它的运行依赖两个核心组件：哈希函数和桶结构，二者配合完成数据的存储和定位。
哈希函数的作用
哈希函数是unordered_map定位数据的第一步，它的作用是将任意类型的键转换为一个整数哈希值。这个哈希值会进一步映射到对应的桶索引，从而快速定位数据应该存储的位置。
对于内置类型比如int、string，标准库已经提供了默认的哈希函数，我们也可以自定义哈希函数适配自定义类型。下面是一个自定义哈希函数的示例：
#include <unordered_map>
#include <string>
// 自定义类型
struct Person {
std::string name;
int age;
};
// 自定义哈希函数
struct PersonHash {
std::size_t operator()(const Person& p) const {
// 组合name和age的哈希值
return std::hash<std::string>()(p.name) ^ (std::hash<int>()(p.age) << 1);
}
};
// 自定义相等比较函数
struct PersonEqual {
bool operator()(const Person& a, const Person& b) const {
return a.name == b.name && a.age == b.age;
}
};
int main() {
// 使用自定义哈希和比较函数的unordered_map
std::unordered_map<Person, int, PersonHash, PersonEqual> person_score;
person_score[{"张三", 20}] = 90;
return 0;
}
桶的结构设计
unordered_map内部维护了一个桶数组，每个桶是一个存储键值对的数据结构，默认情况下桶是单向链表。当我们插入一个键值对时，会先通过哈希函数计算键的哈希值，再对桶的数量取模得到桶索引，最后把键值对放到对应索引的桶中。
桶的数量会随着元素数量的增加而动态调整，当元素数量超过桶数量乘以负载因子时，unordered_map会触发重哈希操作，扩大桶数组的容量，重新分配所有元素到新的桶中，保证操作效率。
哈希冲突的解决
哈希冲突是指不同的键经过哈希函数计算后，映射到同一个桶索引的情况。unordered_map采用链地址法解决哈希冲突，也就是同一个桶中的所有键值对以链表的形式存储，查询时先定位到桶，再遍历桶内的链表找到目标键。
我们可以通过下面的代码查看unordered_map的桶相关信息：
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_map<int, std::string> mp;
// 插入10个元素
for (int i = 0; i < 10; i++) {
mp[i] = "value" + std::to_string(i);
}
// 输出桶的数量
std::cout << "桶数量: " << mp.bucket_count() << std::endl;
// 输出负载因子
std::cout << "负载因子: " << mp.load_factor() << std::endl;
// 查看键0所在的桶索引
std::cout << "键0所在桶索引: " << mp.bucket(0) << std::endl;
// 遍历第0个桶的所有元素
std::cout << "第0个桶的元素: ";
for (auto it = mp.begin(0); it != mp.end(0); ++it) {
std::cout << it->first << ":" << it->second << " ";
}
std::cout << std::endl;
return 0;
}
核心操作的流程
插入操作
插入键值对时，先计算键的哈希值得到桶索引，检查桶内是否已经存在相同的键，如果不存在就把键值对插入到桶的链表中，然后检查负载因子是否超过阈值，超过则触发重哈希。
查询操作
查询键对应的值时，同样先计算桶索引，定位到对应的桶，然后遍历桶内的链表，比较键是否相等，找到则返回对应的值，否则表示键不存在。
删除操作
删除键时，先定位到对应的桶，再遍历桶内的链表找到目标节点，将其从链表中移除，元素数量减一。
注意事项
- 自定义类型作为unordered_map的键时，需要提供对应的哈希函数和相等比较函数，否则无法编译。
- 哈希函数的质量直接影响unordered_map的性能，差的哈希函数会导致大量哈希冲突，使得操作退化为O(n)时间复杂度。
- 重哈希操作会重新分配所有元素，成本较高，如果提前知道元素数量，可以通过
reserve方法提前预留足够的桶空间，减少重哈希次数。
unordered_map哈希函数桶哈希冲突哈希表修改时间：2026-06-15 18:03:30