22、哈希表的优化技巧：预分配策略、哈希函数选择、冲突优化、CPU缓存行对齐
哈希表这东西，用起来简单，想用好却不容易。我见过太多人直接拿个库函数一调就完事，结果数据量一上来，性能直接崩了。今天咱们聊聊哈希表的几个核心优化点，都是我在实际项目中踩过坑之后总结出来的。
预分配策略：别让哈希表频繁扩容
哈希表底层通常是个数组。你往里面插数据，数组不够用了怎么办？扩容。扩容要重新分配内存，还要把旧数据全部重新哈希一遍。这个操作，说白了就是一次全量搬迁，代价极高。
我建议你这么做：
- 提前估算数据量：如果你知道大概要存多少元素，直接初始化时就分配好容量。比如你知道要存100万条记录，那就别让哈希表从16开始慢慢扩。
- 负载因子要留余量：一般负载因子设为0.75比较合理。也就是说，如果你要存100万条，容量至少分配100万 / 0.75 ≈ 134万。
- 避免频繁resize：每次扩容都是O(n)操作。如果你在循环里不断插入，突然来一次扩容，那一下就会卡住。
核心原则：预分配容量 = 预期元素数量 / 负载因子 + 一个安全余量。别省这点内存，省出来的性能是实打实的。
哈希函数选择：均匀分布才是王道
哈希函数的好坏，直接决定了你的哈希表会不会退化成链表。你想想看，如果所有key都哈希到同一个桶里，那查找复杂度就变成O(n)了，跟没优化一样。
我个人习惯用这么几种哈希函数：
| 哈希函数 | 特点 | 适用场景 |
|---|---|---|
| MurmurHash | 速度快，分布均匀 | 通用场景，我最常用 |
| CityHash | 针对短字符串优化 | 字符串key较多时 |
| FNV-1a | 实现简单，适合小数据 | 嵌入式或简单场景 |
| 自定义位运算 | 针对特定数据分布 | 你知道key的规律时 |
我在项目中遇到过一个问题：用了一个很简单的取模哈希，结果key都是2的倍数，哈希表直接废了。后来换成MurmurHash，分布立刻均匀了。
小技巧：如果你的key是整数，而且分布比较随机，可以试试用黄金分割法：hash = (key * 2654435761) >> 32。这个数是个神奇的数字，能让分布更均匀。
冲突优化：别让链表太长
哈希冲突是不可避免的。关键是怎么处理冲突。常见的方案有链地址法和开放地址法。我重点说说链地址法的优化。
链地址法的问题在于：如果某个桶的链表太长，查找就慢。怎么优化？
- 链表转红黑树：Java的HashMap就是这么干的。当链表长度超过8时，转成红黑树，查找从O(n)降到O(log n)。
- 使用跳表：有些场景下跳表比红黑树更友好，实现也简单。
- 二次哈希：如果第一次哈希冲突了，再用另一个哈希函数算一次。这样可以减少冲突概率。
我曾经在一个高并发服务里，发现某个桶的链表长度达到了几百。查了半天，原来是哈希函数对某些特殊key分布不均匀。后来加了一层二次哈希，问题就解决了。
注意：不要为了优化而过度设计。如果你的数据量不大，链表就够用了。红黑树和跳表都有额外开销，小数据量反而更慢。
CPU缓存行对齐：让数据更亲近CPU
这个优化点，很多人容易忽略。CPU读取内存不是按字节读的，而是按缓存行读的。一个缓存行通常是64字节。如果你的哈希表节点刚好跨了两个缓存行，那CPU就要读两次，性能直接打折扣。
怎么做缓存行对齐？
- 结构体对齐：用
__attribute__((aligned(64)))让结构体按64字节对齐。 - 分离热点数据：把经常访问的字段放在同一个缓存行里。比如key和hash值放一起，value放另一边。
- 避免伪共享：多线程场景下，两个线程修改同一个缓存行的不同变量，会导致缓存行频繁失效。可以用填充字节来隔离。
// 缓存行对齐示例
struct hash_node {
uint64_t key; // 热点数据
uint32_t hash; // 热点数据
char padding[48]; // 填充到64字节
void *value; // 非热点数据
} __attribute__((aligned(64)));嗯，这里要注意：缓存行对齐会浪费一些内存。但如果你追求极致性能，这点浪费是值得的。我在做数据库索引时，用了缓存行对齐，查询性能提升了将近20%。
知识体系总览
下面这张图，把哈希表优化的几个维度串起来了。你可以对照着看，哪个环节是你的瓶颈。
这四个优化点，说白了就是：让数据少搬家、让哈希更均匀、让冲突更少、让CPU更快访问。你不需要一次性全用上，先找到你的瓶颈在哪，再针对性地优化。
我记得有一次，一个同事问我：为什么他的哈希表插入100万条数据要好几秒？我一看代码，每次插入前都没预分配，哈希函数也是个简单的取模。改完之后，同样的数据，0.3秒就搞定了。你看，优化就是这么立竿见影。