# 散列查找
散列表 (Hash Table)，又称哈希表。是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关
若不同的关键字通过散列函数映射到同一个值，则称它们为同义词
通过散列函数确定的位置已经存放了其他元素，则称这种情况为冲突
处理冲突的方法 —— 拉链法：
用拉链法 (又称链接法、链地址法) 处理 "冲突"：把所有 "同义词" 存储在一个链表中
在插入新元素时，保持关键字有序，可微微提高查找效率
散列查找
查找长度 —— 在查找运算中，需要对比关键字的次数
最理想情况：散列查找时间复杂度可以达到 O (1)
装填因子 α= 表中记录数 / 散列表长度
装填因子大小会直接影响散列表的查找效率
常见的散列函数
除留余数法 ——H (key)=key% p
- 散列表长度为 m，取一个不大于 m 但是最接近或等于 m 的质数 p
- 用质数取模，分布更均匀，冲突更少。
直接定址法 ——H (key)=key 或 H (key)=a*key+b
- 其中，a 和 b 是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费
数字分析法
- 设关键字是 r 进制数 (如十进制数)，而 r 个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可以选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数
- 例如：手机后四位号码作为关键字设计散列函数
平方取中法 —— 取关键字的平方值的中间几位作为散列地址
- 具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取数都不够均匀或均小于散列地址所需的位数
- 例如：以身份证号作为关键字设计散列函数，取身份证号平方取中间 5 位作为关键字
散列查找是典型的 "用空间换时间" 的算法，只要散列函数设计的合理，则散列表示越长，冲突的概率越低
处理冲突的方法
- 开放定址法
- 指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其递推公式为：
- Hi=(H(key)+di)%m
- 其中 m 表示散列表表长；di 为增量序列；i 可理解为第 i 次发生冲突
- 线性探测法
- 即发生冲突时，每次往后探测相邻的下一个单元是否为空
- 线性探测法很容易造成同义词、非同义词的聚集 (堆积) 现象，严重影响查找效率
- 平方探测法
- 当 di 为 + k 为 - k，k 为正整数的平方时，称为平方探测法，又称二次探测法，其中 k<=m/2
- 比起线性探测法更不易产生 "聚集 (堆积)" 问题
- 伪随机序列法
- di 是一个伪随机序列
- 注意：采用 "开放地址法" 时，删除节点不能简单地将被删除节点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，可以做一个 "删除标记"，进行逻辑删除
- 小知识：散列表长度 m 必须是一个可以表示成 4j+3 的素数，才能探测到所有位置
- 指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其递推公式为：
- 再散列法
- 除了原始的散列函数 H (key) 之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止，Hi=RHi (key)
