哈希表底层选数组因其支持O(1)随机访问，可直接通过哈希值定位；链表需O(n)遍历，不满足核心操作需求；底层数组配合冲突处理策略（如链地址法或开放寻址法）实现高效哈希。
哈希表底层为什么选数组而不是链表
因为数组支持 O(1) 随机访问，而哈希表的核心操作（插入、查找、删除）都依赖“通过哈希值直接定位位置”。链表做不到这点——哪怕你用 std::list，也得遍历才能找元素，退化成 O(n)。所以所有手写哈希表的底层容器，第一选择就是数组（或 vector），哪怕要处理冲突，也是在数组基础上加策略。
常见误区是以为“链地址法 = 用链表实现哈希表”，其实只是冲突处理方式；底层数组依然存在，bucket 数组里存的是链表头指针（或迭代器）。纯数组实现（开放寻址）更轻量，适合嵌入式或性能敏感场景。
开放寻址法中如何处理冲突和删除
开放寻址法把所有元素都塞进同一个数组，冲突时按规则探测下一个空位。关键难点不在插入，而在删除：不能简单把元素清空，否则后续查找会因“断链”失败（比如 probe sequence 中间缺了一环，后面元素就再也访问不到了）。
- 必须用特殊标记（如
DELETED）代替直接擦除，让查找继续往下探 -
DELETED位置可被新元素复用，但查找时不能停——只有遇到EMPTY才算真没找到 - 探测方式推荐线性探测（
hash + i）或二次探测（hash + i*i），避免聚集；别用伪随机数，难调试 - 负载因子超过 0.7 就该扩容，否则探测长度暴涨，性能崩塌
示例：插入键 k 时，计算 index = hash(k) % capacity，若 table[index] 非空且非 DELETED，则 index = (index + 1) % capacity 循环直到找到 EMPTY 或 DELETED 位置。
立即学习“C++免费学习笔记（深入）”；
哈希函数怎么写才不容易撞车
对整数键，别直接用 key % table_size——小范围连续 key（如 0,1,2,…）会全挤在开头。对字符串，别用 sum of chars，"ab" 和 "ba" 哈希值一样。
- 整数推荐
(key * 2654435761U) >> (32 - bits)（Knuth 黄金比例乘法，2654435761U是 2³²/φ 的近似） - 字符串用
std::hash<:string>{}(s)</:string>（C++11 起标准库已提供可靠实现），别自己手搓 - 自定义类型必须重载
operator==且提供专用std::hash特化，否则编译不过 - 哈希后务必
% table_size，但table_size最好是质数（减少周期性碰撞），或者用 2 的幂配合掩码（& (size-1)）提速
vector 能不能当哈希表的标记数组
不能。虽然 vector<bool></bool> 看起来节省空间，但它不是真正的容器——operator[] 返回的是代理对象 vector<bool>::reference</bool>，不是 bool&。这意味着你无法取地址、无法绑定到 bool*、甚至某些哈希表实现里用 memset 初始化都会出错。
更实际的问题是：它破坏了内存连续性和指针算术，导致 cache line 对齐混乱，反而拖慢探测速度。
- 用
vector<uint8_t></uint8_t>或vector<char></char>替代，语义清晰，性能更好 - 如果真抠内存，用
std::bitset（编译期确定大小）或手动位运算，但得自己管理位索引 -
vector<bool></bool>在 C++23 已被标记为 deprecated，早该弃用
哈希表的稳定性比省几个字节重要得多——一个错位的 vector<bool></bool> 可能让查找逻辑静默失效，debug 成本远高于内存开销。
