散列函数
概述
散列函数（Hash Function） 是 散列表 的核心组件，负责将全域 中的关键字 映射到散列表 的某个槽位。散列函数的质量直接决定了散列表的性能：好的散列函数能将关键字均匀分散到各槽位，最小化冲突；差的散列函数会导致大量元素聚集在少数槽位，使性能严重退化。本章介绍除法散列、乘法散列以及全域散列等经典方法。
定义
散列函数
一个散列函数 将全域 中的每个关键字 映射到散列表的一个槽位 。散列函数需要满足：
- 确定性：对同一关键字 ，每次计算 的结果相同
- 均匀性：理想情况下，每个关键字等概率地映射到任意槽位
- 高效性：计算 的时间为
核心性质
1. 除法散列（Division Method）
除法散列
即关键字 除以表大小 的余数。
特点：
- 实现最简单，只需一次取模运算
- 关键： 的选择至关重要
的选择原则：
- 不应接近 的幂（否则 仅由 的低 位决定）
- 不应接近 的幂（对十进制关键字同理）
- 推荐： 选择远离 2 的幂次的素数，例如当散列表大小约为 2000 时，选 或
示例： 若 ，则 。
2. 乘法散列（Multiplication Method）
乘法散列
其中 是一个常数，， 表示 的小数部分。
工作原理：
- 将关键字 乘以常数 ，得到一个 到 之间的值
- 取 的小数部分（即 ）
- 将小数部分乘以 并向下取整，得到槽位
特点：
- 对 的选择不如除法散列敏感， 可以取 的幂（便于位运算）
- 推荐的 值：Knuth 建议 （黄金比例的倒数）
示例： 设 ，，：
3. 全域散列（Universal Hashing）
全域散列
从一个精心设计的散列函数族 中随机选取散列函数 。全域散列保证：对于任意两个不同的关键字 ，它们发生冲突的概率不超过 ：
Carter-Wegman 全域散列类（1979）：
设全域 （ 为大于任何关键字的素数），散列函数族为：
其中 ，。
性质：
- ，从中均匀随机选取 和
- 对任意 ，恰好有 个散列函数使
- 因此 （精确等于 ，而非上界）
意义： 全域散列使得即使对手知道散列函数族，也无法构造一组关键字使性能最坏化，因为具体的散列函数是在运行时随机选取的。
4. d-独立散列（d-Universal Hashing）
d-独立散列
一个散列函数族 是d-独立的，如果从 中均匀随机选取 后，对于任意 个互不相同的关键字 和任意 个槽位 ：
- 2-独立 = 全域散列（Carter-Wegman 定义）
- 1-独立 = 每个关键字等概率映射到每个槽位（简单均匀散列）
- 越大，独立性越强，但构造和计算也越复杂
章节扩展
散列函数选择指南
| 场景 | 推荐方法 | 理由 |
|---|---|---|
| 通用场景 | 除法散列（ 选素数） | 简单高效 |
| 需为 2 的幂 | 乘法散列 | 对 不敏感 |
| 对抗性输入 | 全域散列 | 随机化防止最坏情况 |
| 理论分析 | d-独立散列 | 提供更强的概率保证 |
散列函数与冲突处理的关系
散列函数决定了元素的分布方式，而冲突处理方法（链地址法 或 开放寻址法）决定了冲突发生后的应对策略。两者共同决定了散列表的整体性能。一个好的散列函数可以减少冲突频率，但不能完全消除冲突。