一、散列查找
（一）散列表（Hash Table）
- 散列表（Hash Table），又称哈希表。是?种数据结构，特点是：数据元素的关键字与其存储地址直接相关
 - 若不同的关键字通过散列函数映射到同?个值，则称它们为“同义词”
- 通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”
（二）处理冲突的方法——拉链法
- 用拉链法（又称链接法、链地址法）处理“冲突”：把所有“同义词”存储在一个链表中
1. 散列查找
（1）查找目标：27、20
（2）查找目标：21
（3）查找目标：66
2. 散列查找效率
（1）查找成功效率
- 最理想情况：散列查找时间复杂度可到达O(1)
（2）查找失败效率
（三）常见的散列函数
1. 除留余数法
- 设计目标——让不同关键字的冲突尽可能地少
- 除留余数法 —— H(key) = key % p
- 散列表表长为m，取一个不大于m但最接近或等于m的质数p
2. 直接定址法
- 直接定址法 —— H(key) = key 或 H(key) = a*key + b
- 其中，a和b是常数。这种?法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。
3. 数字分析法
- 数字分析法 —— 选取数码分布较为均匀的若?位作为散列地址
- 设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不?定相同，可能在某些位上分布均匀?些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。
4. 平方取中法
- 平方取中法——取关键字的平?值的中间?位作为散列地址。
- 具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
 - 散列查找是典型的“用空间换时间”的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。
|