哈希表二次探测再散列法
1. 概述
二次探测再散列法是一种解决哈希冲突的开放地址法。当哈希表中发生冲突时，它使用二次函数来计算下一个可能的位置，有效减少了数据聚集现象。
2. 基本原理
当计算出的哈希地址已被占用时，按照二次函数的规律查找下一个可用位置。
3. 探测序列
假设初始位置是 h，哈希表大小为 m，探测序列为：
h, (h+1²) % m, (h+2²) % m, (h+3²) % m, ..., (h+k²) % m
其中 k 是探测次数。
4. 优点
- 比线性探测法更少地产生聚集现象
- 可以更均匀地分布数据
5. 缺点
- 计算复杂度略高于线性探测
- 不能探测到哈希表中的所有位置（除非表的大小是某个质数的平方）
6. 实现步骤
- 计算初始哈希值 h = H(key)
- 如果位置 h 被占用，则计算 (h+1²) % m
- 如果新位置仍被占用，则计算 (h+2²) % m
- 重复这个过程，直到找到空位置或探测完整个表
7. 示例
假设哈希表大小为 11，要插入关键字 49：
- 初始哈希值：H(49) = 49 % 11 = 5
- 如果位置 5 被占用，下一个尝试的位置将是：
- (5+1²) % 11 = 6
- (5+2²) % 11 = 9
- (5+3²) % 11 = 3
- ...以此类推
8. 注意事项
- 选择合适的表大小很重要，通常选择质数可以获得更好的分布
- 在实际应用中，可能需要结合其他方法（如再哈希）来处理极端情况
- 二次探测法在负载因子不太高的情况下效果较好
9. 应用场景
- 数据库索引
- 缓存系统
- 符号表实现
- 某些编程语言的内置哈希表实现
10. 结论
二次探测再散列法是一种在实践中比较有效的解决哈希冲突的方法，特别适用于中等规模的哈希表和较低的负载因子情况。