哈希表
使用哈希函数确定下标以插入数据的数组叫哈希表
哈希化
通过哈希函数把一个数字从大的范围转化为小范围的数字叫哈希化
把关键字转化为数组下标
1、关键字不需要转换，比如员工编号从0到1000，关键字员工编号可以直接做为数组下标
2、关键字需要转换，把一部英文字典装入哈希表，a是1，b是2，c是3，依此类推，z是26，还有空格是0
1）数字相加 cats=3+1+20+19=43
假设单词最长有10个字母组成a的编码是1，zzzzzzzzzz是26*10=260，这样单词编码的范围是从1到260。不幸的是，字典中一共有50000个单词。数组下标太少，每个数组元素大概要存储50000/260=192个单词。
2）幂的连乘
7564= 7*103 + 5*102 + 6*101 + 4*100
cats= 3*273 + 1*102 + 20*101+ 19*100
这样每个单词对应独一无二的一个数字
最长的10个字母的单词zzzzzzzzzz，将转化成26*279+26*278+26*277+26*276+26*275+26*274+26*273+26*272+26*271+26*270
仅279就超过7000000000000，结果非常巨大，内存中的数组根本不可能有这么多的单元，产生的数组下标太多
3）哈希函数
取余法：index = x / arrayLength
哈希化后的冲突
1、开放地址法
期望的数组平均起来，每两个数组单元，有一个单词；有些单元没有单词，而有些单元有多个单词。所以设计数组大小应该两倍于需要存储的数据量，这样可能一半的单元是空的，冲突后，找到数组的一个空位并填入。
1）线性探测：+1，+2，+3，+4
装填因子是二分之一或三分之二时，哈希表的性能最好；装填因子接近1时，哈希表效率非常低。一连串已填充的单元越来越长，叫聚集，大块的聚集降低了哈希表的效率。
2）二次探测：+1，+4，+9，+16
3）再哈希法
二次探测的问题，产生的步长总是固定的1、4、9、16...，再哈希法不同的关键字使用不同的步长
再哈希法函数必须具备的特点：1、和第一个哈希函数不同。2、不能得到0，否则总是原地踏步
一个再哈希函数：stepSize = constant - ( key % constant )，constant是质数且小于数组容量
装填因子是9/10或更大，大多数数据项还是能一次哈希函数找到
再哈希法和二次探测要求数组容量是一个质数，否则会造成死循环
2、链地址法
当装填因子是1时，大约三分之一的单元是空白单元，三分之一的单元有一个数据项，三分之一的单元有两个或更多的数据项。
链地址法装填因子可以达到1以上，对性能影响并不大；找到初始单元需要O(1)的时间级，搜索链表的时间与链表的平均数据项成正比。
表容量不像在再哈希法和二次探测中显得那么重要，链地址法不需要探测，不会出现死循环；但当表容量不是质数时，还是能够导致聚集
哈希表优缺点
优点：
哈希表的速度明显比树快。插入、查找、删除时间复杂度接近O(1)。
缺点：
基于数组，难于扩展。哈希函数根据数组大小计算数据项的位置，所以在扩展哈希表时，不能简单地从一个数组向另一个数组拷贝数据；需要顺序遍历旧数组，重新计算数据项的下标，再插入新数组
不能以任何一种顺序遍历数据
某些哈希表被基本填满时，性能下降得非常严重