哈希表的核心
计算位置：构造散列函数确定关键词存储位置；
解决冲突：应用某种策略解决多个关键词位置相同的问题
计算位置
数字关键词
直接定址法：取关键词的线性函数值为散列地址，即 key + b a = h(key) (a、b为常数)
除留余数法：散列函数为：h(key) = key mod p；p 取素数
数字分析法：分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址
折叠法：把关键词分割成位数相同的几个部分，然后叠加
平方取中法
字符关键词
核心思想：将字符串编码为数字，然后在调用数字关键字的构造方法
编码方法：ASCII码*32的字节次方，累加
解决冲突
开放定址法（Open Addressing）
线性探测：往后找空位填
平方探测 ：两侧平方增量找空位填（当表大小为4k+3平方探测可探查整个空间）
双散列：
di 为i*h2 (key)，h2 (key)是另一个散列函数，h2 (key) ≠ 0
为了所有的散列存储单元都能够被探测。选择以下形式有 h2 (key) = p - (key mod p) p < TabeSize，p、TabeSize都是素数。再散列
- 当散列表元素太多（即装填因子 α太大）时，查找效率会下降；
实用最大装填因子一般取 0.5 <= α<= 0.85
当装填因子过大时，加倍扩大散列表，这个过程叫做“再散列”
链地址法：将相应位置上冲突的所有关键词存储在同一个单链表中
性能分析
衡量标准
平均查找长度（ASL）用来度量散列表查找效率：成功、不成功
关键词的比较次数，取决于产生冲突的多少，影响产生冲突有以下三个因素
散列函数是否均匀；
处理冲突的方法；
散列表的装填因子α
结论
哈希表的优缺点
选择合适的 h(key)，散列法的查找效率期望是常数O(1)，它几乎与关键字的空间的大小 *无关！也适合于关键字直接比较计算量大的问题
它是以较小的α为前提。因此，散列方法是一个以空间换时间
散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适合于范围查找，或最大值最小值查找。
开放地址法
散列表是一个数组，存储效率高，随机查找
散列表有“聚集”现象
分离链法：
散列表是顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低。
关键字删除不需要“懒惰删除”法，从而没有存储“垃圾”。
太小的α可能导致空间浪费，大的α又将付出更多的时间代价。 不均匀的链表长度导致时间效率的严重下降。