散列表(Hash Table)

定义

散列表是一种以平均O(1)时间插入、删除和查找的数据结构，可是类似于findMax，findMin等操作则需要以O(N)的时间才能完成

散列函数

散列函数是将关键字计算成Hash值的一个函数 散列函数的选择是非常重要的，它的复杂度影响着影响着插入、删除、查找的速度：

1. 散列值的计算时间
   • 每次操作前需要根据关键字进行散列，寻找关键字存储位置
2. 散列值的重合度
   • 根据散列冲突（Hash Conflict）的解决方案，从冲突的存储数据中找到真正的数据位置

解决Hash冲突

方案1：分离链接法

将关键字的Hash值相同的节点以链表的方式进行存储，以解决Hash冲突

新插入的节点都会放在第一个，因为往往新插入的节点元素最有可能被访问，所以插入效率很高。 而当需要删除/查找节点的时候，如果散列函数的计算出来的值重合度非常高，那么最坏的情况会将O(1)的常数时间变成O(N)的线性时间，因为需要把整个链表进行遍历。也可以用变种的二叉树进行存储，也只是将O(N)的时间变成了O(logN)而已。

所以散列函数的选择是非常非常重要的，尽量对关键字所计算的时间要短，并且重合度低才能保证Hash的效率

分离链接法

方案2：开放寻址法-线性探测

根据关键字散列后，找到关键字散列位置，查找散列表中离冲突单元最近的空闲单元，并且把新的键插入这个空闲单元。当插入节点满了的话，则需要进行扩容。 如下图： John Smith和Sandra Dee（都被杂凑映射到了单元873）的冲突，借由把后者放在下一个空闲单元（单元874）而解决

线性探测法

当查找节点的时候，找到Hash位置，然后一个个往下找，直到找到节点或者空节点才返回。

当删除节点的时候，单纯地清空对应的单元是不够的。这会影响到对于储存时间早于该单元、但储存位置在该单元之后的其他键，从而对查找产生影响。 相较于直接清空对应单元i，更好的做法是先清空，然后把它之后所有会造成问题的单元向前移动，来避免搜索出错。重复直到出现空单元，则删除动作安全完成。如下图：

当一对键值对被删除，可能会有必要将其他的键值对放回到它的单元中，来防止搜索时搜索到空的单元

方案3：开放寻址法-平方探测

与线性探测差不多，只是插入的间隔从1变成了冲突间隔的平方，如A与B冲突了，而C与AB都冲突了，那么C就会插入到距离A的2*2的空闲位置处。

荷载因子

散列表的载荷因子定义为：A = 填入表中的元素个数 / 散列表的长度

A越大，表明填入表中的元素越多，产生冲突的可能性就越大，A越小，标明填入表中的元素越少，产生冲突的可能性就越小

对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表