哈希表unordered_map的底层实现与哈希冲突处理
std::unordered_map的底层数据结构是如何实现的？它如何处理哈希冲突？什么是负载因子和rehash？为什么C++标准使用链地址法而非开放地址法？
回答
古法程序员
底层结构：哈希表(桶数组)+链地址法(Chaining)解决冲突。每个桶是一个单向链表(或forward_list)。
关键组件：
- 哈希函数：
std::hash<Key>，将key映射到size_t - 桶数组：
vector<forward_list<Node>>或类似实现 - 负载因子：
size() / bucket_count()，默认max_load_factor=1.0 - rehash：实时元素数超过
bucket_count()*max_load_factor时，扩大桶数组并重新哈希所有元素
哈希冲突处理：链地址法——冲突的元素挂在同一个桶的链表上。插入O(1)+冲突处理O(k)，查找O(1)+链表遍历O(k)，其中k是桶内元素数。
为什么不能用开放地址法(如线性探测)：
- 开放地址法删除困难(需要延迟删除标记)
- 迭代器稳定性——开放地址法rehash时所有元素移动，而链地址法可复用节点
- C++标准要求引用/迭代器在插入其他元素时不失效(除非rehash)，链地址法更易实现
- 异常安全——链地址法逐个构造，异常时易回滚
C++11 vs C++14/17：C++11起unordered容器保证插入后引用/指针不失效(除非rehash)。迭代器可能因rehash失效。rehash保证是O(n)的。
性能优化：可自定义哈希函数(减少冲突)，控制max_load_factor(降低链表长度)，预reserve减少rehash次数。