MurmurHash3比std::hash更适合自定义哈希表，因其专为哈希表设计：具备雪崩效应、低碰撞率、高吞吐量（是std::hash<string>的3倍），支持128位输出扰动、短字符串优化及无锁并发，实测查找长度降低30%～50%。
为什么 MurmurHash 比 std::hash 更适合自定义哈希表
因为 std::hash 对自定义类型默认只做地址哈希或简单转发，碰撞率高、无雪崩效应；而 MurmurHash3 是为哈希表设计的非加密散列，能将微小输入差异扩散到整个输出位，显著降低冲突概率。实测在字符串键场景下，相同桶数时平均查找长度下降 30%～50%。
关键点：
-
MurmurHash3_x64_128输出 128 位，但哈希表通常只取低 64 位或 mod 桶数，高位信息仍参与扰动，比单纯截断更安全 - 它不依赖全局状态，可无锁并发调用，适合多线程插入场景
- 对短字符串（≤16 字节）有专门优化路径，避免循环展开开销
- 注意：
std::hash<std::string>在 GCC libstdc++ 中实际是 SipHash 变种（防 DoS），吞吐量约为 MurmurHash 的 1/3，且不可控
如何用 AVX2 加速 MurmurHash 的 16 字节批量处理
原版 MurmurHash3 对齐读取 8 字节后用 rotl64 + 异或 + 乘法组合，AVX2 可一次处理 16 字节（__m128i），把 4 轮标量计算压缩为 1 轮向量化操作。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 仅对长度 ≥ 32 字节的输入启用 AVX2 分支，短输入走标量路径更省指令周期
- 必须检查 CPU 支持：
__builtin_cpu_supports("avx2")，否则运行时 SIGILL - 避免跨缓存行读取：用
_mm_loadu_si128（非对齐）而非_mm_load_si128，但要确保内存已分配 16 字节对齐（aligned_alloc(32, size)） - 示例核心片段：
__m128i v = _mm_loadu_si128((__m128i const*)p); v = _mm_xor_si128(v, _mm_srli_epi64(v, 47)); v = _mm_mul_epu32(v, _mm_set1_epi64x(0xc6a4a7935bd1e995ULL));
开放寻址哈希表中探测序列选线性还是二次探测
线性探测（hash(key) + i）局部性好、CPU 预取友好，但容易产生“聚集”；二次探测（hash(key) + i*i）分散性好，但步长跳变导致 cache miss 率上升，在现代 DDR4 内存上反而更慢。
真实性能拐点：
- 负载因子 ≤ 0.7 时，线性探测平均访存次数比二次探测低 15%～20%
- 当发生长连续占用段（≥8 个桶），线性探测的删除操作需“墓碑标记”，否则破坏后续查找；二次探测无此问题但插入失败率更高
- 推荐方案：线性探测 + Robin Hood 重排（插入时把已有键往更接近其原始 hash 的位置挪），既保局部性又压平探测长度
- 禁用双哈希（
hash1 + i * hash2）：hash2若为偶数会导致永远跳过奇数桶，且分支预测失败率高
为什么哈希表 resize 时不能直接 memcpy 桶数组
因为新旧桶数不同，hash(key) % old_size 和 hash(key) % new_size 结果无映射关系，直接拷贝会把大量键放错桶，导致后续 find 永远找不到。
正确做法只有两种：
- 逐个 rehash：对每个非空桶，重新计算
hash(key) % new_size，再插入新表 —— 这是唯一安全方式 - 若新大小是旧大小的 2 倍（如 8→16），可用掩码优化：
new_hash = old_hash & (new_size - 1)，此时只需判断是否需要右移一格（old_hash >= old_size），但前提是 hash 函数输出均匀且桶数始终为 2 的幂 - 注意：resize 过程中若有并发读写，必须用原子指针切换
table_ptr，且旧表内存不能立即释放（需等待所有 reader 退出临界区）
最易被忽略的是：即使你用了 perfect hashing 或 static table，只要支持动态插入，就绕不开 rehash —— 所谓“零拷贝扩容”在通用哈希表里不存在。
