一. 哈希概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( l o g 2 N log_2 N log 2 N)，搜索的效率取决于搜索过程中元素的比较次数
而理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系，那么在查找时通过该函数可以很快找到该元素
当向该结构中插入和删除时：
插入元素： 根据待插入元素的关键码，用此函数计算出该元素的存储位置，并将元素存放到此位置。
搜索元素： 对元素的关键码进行同样的计算，把求得的函数值当作元素的存储位置，在结构中按此位置取元素进行比较，若关键码相等，则搜索成功。
那么这种方式即为哈希（散列），哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
举个例子：
给定集合 {1, 7, 6, 4, 5000, 9000}，将哈希函数设置为：：hash(key) = key % capacity（取模），其中capacity为存储元素空间的总大小。
若我们将该集合存储在 capacity 为10的哈希表中，则各元素存储位置对应如下：
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？ 哈希冲突！
二. 哈希冲突
也叫哈希碰撞：不同关键字通过相同哈希哈数计算出相同的哈希地址，比如在上述的例子中再插入44就会产生哈希冲突，因为44模10后，也等于4
面对这种问题该怎么样处理呢？
三. 哈希函数
不合理的哈希函数就是引发哈希冲突的重要原因，哈希函数设计的越精妙，产生哈希冲突的可能性越低！
哈希函数的设计遵从三大原则：
哈希函数的定义域必须包括需要存储的全部关键码，且如果散列表允许有m个地址，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单
常见的哈希函数有：
直接定址法（常用）
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
除留余数法–(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
优点：使用广泛，不受限制
缺点：需要解决哈希冲突，冲突越多，效率越低
平方取中法–(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
折叠法–(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
随机数法–(了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数
通常应用于关键字长度不等时采用此法
数学分析法–(了解)
设有n个d位数，每一位可能有r种不同的符号，这r中不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，而在某些位上分布不均匀，只有几种符号经常出现。此时，我们可根据哈希表的大小，选择其中各种符号分布均匀的若干位作为哈希地址
例如：
假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为哈希地址。
数字分析法通常适合处理关键字位数比较大的情况，或事先知道关键字的分布且关键字的若干位分布较均匀的情况。
注意：哈希函数设计的越精妙，产生哈希冲突的可能性越低，但是无法避免哈希冲突。
四. 如何解决哈希冲突？
解决哈希冲突两种常见的方法是：闭散列和开散列
🌏闭散列 —— 开放定址法
也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？
线性探测
当发生哈希冲突时，从发生冲突的位置开始，依次向后探测，直到找到下一个空位置为止
Hi=(H0+i)%m ( i = 1 , 2 , 3 , . . . )
H0：通过哈希函数对元素的关键码进行计算得到的位置
Hi：冲突元素通过线性探测后得到的存放位置
m：表的大小
例如，我们用除留余数法将序列{1, 6, 10, 1000, 11, 18, 7, 40}插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的线性探测找到下一个空位置进行插入，插入过程如下：
通过上图可以看出：随着哈希表中数据的增多，产生哈希冲突的可能性也随着增加，最后在40进行插入的时候更是连续出现了四次哈希冲突（踩踏效应）
我们将数据插入到有限的空间中，随着数据的增多，冲突的概率越发越多，冲突多的时候插入的数据，在查找时候效率也会随之低下，为此引入了负载因子：
负载因子 = 表中有效数据个数 / 空间的大小
负载因子越大，产生的概率就越多，增删查改的效率越低
负载因子越小，产生的概率就越少，增删查改的效率越高，但是越小也意味着空间利用率越低，此时大量空间可能被浪费
如果我们把哈希表增大变成20，可以发现在插入相同数据时，产生的冲突会少
因此我们在闭散列（开放定址法）对负载因子的标准定在了 0.7~0.8，一旦大于 0.8 会导致查表时缓存未命中率呈曲线上升；这就是为什么有些哈希库都有规定的负载因子，Java 的系统库就将负载因子定成了 0.75，超过 0.75 就会自动扩容
😎作总结：
线性探测的优点：实现非常简单
线性探测的缺点：一旦发生冲突，所有的冲突连在一起，容易产生数据“堆积”，即不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要多次比较（踩踏效应），导致搜索效率降低。
二次探索
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：以2的i次方进行探测
Hi=(H0+i*i)%m ( i = 1 , 2 , 3 , . . . )
H0：通过哈希函数对元素的关键码进行计算得到的位置。
Hi：冲突元素通过二次探测后得到的存放位置。
m：表的大小
接下来举个例子：
但是二次探测没有从本质上解决问题，还是占用式的占用别人位置
🌏开散列——链地址法（拉链法）
开散列，又叫链地址法（拉链法），首先对关键码集合用哈希函数计算哈希地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
例如，我们用除留余数法将序列{1, 6, 15, 60, 88, 7, 40, 5, 10}插入到表长为10的哈希表中，当发生哈希冲突时我们采用开散列的形式，将哈希地址相同的元素都链接到同一个哈希桶下，插入过程如下：
相比于比散列的报复式占用其他人的位置（小仙女行为）来说，开散列就好得多了，用的是一种乐观的方式，我挂在这个节点的下面
与闭散列不同的是，这种将相同哈希地址的元素通过单链表链接起来，然后将链表的头结点存储在哈希表中的方式，不会影响与自己哈希地址不同的元素的增删查改的效率，因此开散列的负载因子相比闭散列而言，可以稍微大一点
开散列的哈希桶，负载因子可以超过1，一般建议控制在[0.0, 1.0]之间
为什么开散列在实际中，更加实用呢？
哈希桶的负载因子可以更大，空间利用率高
哈希桶在极端情况下还有可用的解决方案
哈希桶的极端情况就是：所以元素全部都挂在一个节点下面，此时的效率为O（N）
一个桶中如果元素过多的话，可以考虑用红黑树结构代替，并将红黑树的根结点存储在哈希表中
这样一来就算是有十亿个数，都只要在这个桶里查找30次，这就是桶里种树
五. 闭散列的实现
在闭散列的哈希表中，每个位置不仅仅要存放数据之外，还要存储当前节点的状态，三大状态如下：
EMPTY（空位置）
EXIST（已经存放数据了）
DELETE（原本有数据，但被删除）
对此我们可以用枚举实现：
//枚举出三种状态 enum State { EXIST, EMPTY, DELETE };
