散列表：散列函数的构造方法、处理散列冲突的方法、散列表的查找性能分析
散列表，也叫哈希表。这东西我刚开始学的时候觉得挺玄乎，后来在项目中做缓存系统，才发现它简直是性能救星。说白了，散列表就是通过一个函数，把关键字直接映射到存储位置。理想情况下，查找时间复杂度能到 O(1)。
但现实没那么完美。你想想看，如果两个不同的关键字映射到了同一个位置，怎么办？这就是散列冲突。今天我们就来聊聊散列函数怎么设计、冲突怎么处理、以及散列表的查找性能到底怎么样。
一、散列函数的构造方法
散列函数的目标很简单：计算快、分布均匀。我见过不少新手一上来就写个取模完事，结果数据一分布不均匀，性能直接崩了。
1. 直接定址法
取关键字本身或它的线性函数作为散列地址。比如 H(key) = a * key + b。这种方法简单，但只适合关键字分布连续的情况。我在做学号管理系统时用过，因为学号是连续的，效果不错。
2. 除留余数法
最常用的方法。公式：H(key) = key % p。这里的 p 一般选一个不大于表长的质数。为什么？因为质数能减少冲突。我曾经踩过坑，选了 p = 100，结果所有 key 都是 10 的倍数，全挤到 0、10、20... 这几个位置上了。
3. 数字分析法
分析关键字的各位数字分布，选取分布较均匀的几位作为散列地址。比如电话号码，后四位往往分布更随机。我在做用户 ID 映射时用过这招，效果比直接取模好不少。
4. 平方取中法
先计算关键字的平方，然后取中间几位。为什么取中间？因为平方的中间几位受关键字各位的影响，分布更均匀。适合关键字位数不多的情况。
5. 折叠法
把关键字分成几段，然后叠加求和。比如关键字 123456789，分成 123、456、789 三段，加起来得到 1368，再取后几位。这种方法适合关键字位数很长的情况。
二、处理散列冲突的方法
冲突是散列表绕不开的问题。我刚开始做项目时，天真地以为选个好函数就万事大吉，结果数据量一上来，冲突还是啪啪打脸。下面说两种主流方法。
1. 开放定址法
冲突了？那就再找个空位。具体有几种探测方式：
- 线性探测法： 冲突后依次往后找。简单，但容易产生「堆积」现象——冲突的数据挤成一团。
- 二次探测法： 探测序列是 1²、-1²、2²、-2²... 能缓解堆积，但可能找不到空位。
- 伪随机探测法： 用随机数决定步长。嗯，这个我实际用得少，因为随机数生成也有开销。
2. 链地址法
每个散列位置挂一个链表。冲突的元素直接链在后面。这是我最喜欢的方法，实现简单，删除也方便。
// 链地址法节点定义
typedef struct Node {
int key;
struct Node *next;
} Node;
// 散列表
typedef struct {
Node **heads; // 每个槽位一个链表头
int size;
} HashTable;链地址法的缺点是，如果某个槽位链表太长，查找就退化成 O(n)。所以一般会设定一个负载因子，超过阈值就扩容。
三、散列表的查找性能分析
散列表的查找性能，主要看三个因素：散列函数、冲突处理方法、负载因子。负载因子 α = 表中元素个数 / 表长。α 越大，冲突概率越高，查找越慢。
1. 平均查找长度（ASL）
对于链地址法，成功查找的 ASL 大约是 1 + α/2。不成功查找的 ASL 大约是 α。对于开放定址法，情况复杂一些，但大致趋势是 α 越大，ASL 增长越快。
2. 查找性能对比
| 方法 | 成功查找 ASL | 不成功查找 ASL | 适用场景 |
|---|---|---|---|
| 线性探测 | 约 (1 + 1/(1-α))/2 | 约 (1 + 1/(1-α)²)/2 | 表长较大，α 较小 |
| 二次探测 | 略优于线性探测 | 略优于线性探测 | 需要避免堆积 |
| 链地址法 | 约 1 + α/2 | 约 α | 插入删除频繁 |
3. 性能优化建议
- 选择合适的表长： 最好是质数，或者 2 的幂（配合位运算）。我习惯用质数，因为分布更均匀。
- 动态扩容： 当负载因子超过阈值时，重新分配一个更大的表，重新散列所有元素。这个过程开销大，但能保证长期性能。
- 避免退化： 如果发现某个槽位链表特别长，可以考虑换散列函数，或者用红黑树代替链表（Java 8 的 HashMap 就是这么干的）。
四、知识体系图
下面这张图总结了散列表的核心知识点，方便你快速回顾。
散列表这东西，用好了是神器，用不好就是灾难。我见过有人把负载因子设到 0.95，结果查找比链表还慢。记住一句话：散列函数要均匀，冲突处理要得当，负载因子要控制。做到这三点，你的散列表基本就稳了。
公众号:蓝海资料掘金营，微信deep3321