能否让std::unordered_map使用vector而非链表作为桶容器？

当然可以聊聊这个问题！首先得明确核心结论：标准库的std::unordered_map并没有直接提供接口让你把默认的链表桶替换成std::vector，但我们可以通过其他方式实现类似的效果，或者理解背后的原因：

• 为什么默认是链表？
  标准并没有强制std::unordered_map的桶必须用链表，但主流编译器（GCC、Clang、MSVC）的实现都选择了链表——因为链表在处理哈希冲突时，插入、删除元素的时间复杂度是O(1)（只要找到位置），而std::vector在中间插入/删除元素需要移动后续元素，效率会低很多。

• 那有没有办法让桶用std::vector？
  如果你执着于用std::vector作为桶的存储容器，有两种思路：

  1. 自定义哈希容器：自己封装一个哈希表结构，把每个桶直接定义成std::vector<std::pair<const Key, T>>。这样你可以完全控制桶的类型，插入时直接push_back到对应桶的vector里，查找时线性遍历vector即可（如果需要优化查找，还可以给每个桶的vector排序后用二分查找）。
  2. 模拟类似行为：如果你想复用std::unordered_map的接口，可以提前调用reserve(n)预分配足够多的桶，让哈希冲突尽可能少，每个桶里的元素数量趋近于1。这时候虽然底层还是链表，但实际使用起来和每个桶是单元素vector的体验很接近。

• 补充：标准库的std::unordered_map的桶数组本身就是用std::vector实现的？
  对的，大多数实现里，桶的“数组”部分是用std::vector来存储指向链表节点的指针，但桶内的元素存储还是链表结构——这和你问的“用std::vector作为桶容器”不是一回事，后者指的是桶内的元素直接存在vector里，而非链表节点。

内容的提问来源于stack exchange，提问作者Raven