目录
一、概念
我们在初学数据结构时，接触了许多的搜索方式，但是搜索效率最高的也只有O(logN),比如说二分查找。有时我就不经幻想，是否有一种方法，可以让搜索效率达到恐怖的O（1）呢？我以为在白日做梦，唉，没想到还真有，没错就是今天要讲的哈希表！
既然它那么厉害，说明它的搜索方式就不走寻常路，举个例子，来大致理解一下它的原理，以数据集合{1,7,6,4,5,9}为例：
首先要把待搜索元素集合，放到哈希表（一种特别的“数组”）中：
红色的是数字数据集合中的6个元素，看起来，这6个元素放的很乱，但实际上，他们是按照一个特定的规则去存放的。
每个待存放元素的值，我们称为关键码，关键码通过哈希函数的计算得到一个哈希表的存放位置下标（就是数组的下标）。
For example:元素“6”，把6带入哈希函数，返回的值是6，那么就把元素6放到哈希表的数组中的6下标位置。
在所有元素存完后，如果要搜索某一个元素，只需要获取改元素的关键码，通过哈希函数，计算出哈希表相应位置，判断是否有此元素即可。
比如我要查询元素“3”是否存在：
假设元素“3”(元素值就是关键码)通过哈希函数计算，哈希函数返回了2下标，我们就去2下标，寻找，发现2下标没有元素存放，所以没有找到。
注意：
有时候，我们要查询的元素，不一定是简单类型int，这时候需要用到java中hashCode()方法获取一个关键码，然后再用哈希函数计算下标值。
关于哈希函数：
一般哈希函数：hash(key) = key % capacity
hash就是底层数组的下标了
key是元素的关键码
capacity是储存底层元素的空间容量大小
如图：
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度非常快。
当然这也是有代价的，属于使用空间效率换取时间效率，毕竟世界上很难有十全十美的东西。
按照上述的思考逻辑，来思考一下，如果往这个集合中插入元素“66”，会怎么样？
二、哈希冲突
如果插入元素“66”，我们发现这个哈希表（数组），就出现问题了，因为通过哈希函数计算，下下标应该是6，但是下标为6的位置已经存储了一个元素了。
这实际上就叫做哈希冲突
此时，我们在用关键码，借助哈希函数计算出下标的位置，就可能出错了，因为同一个下标，不同的元素，计算出来的下标可能会出现一样的情况，无法做到11对应，就无法正确的搜索。
减少哈希冲突的办法：
首先先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一 个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率
有些同学可能会想，那一定会冲突，冲突了怎么办？
这个问题等一下会有解决办法，我们先不急，等一下会讲，先把降低冲突率的方法讲完。
1、设计合理的哈希函数
哈希函数设计原则：
第一点：哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1 之间
第二点：哈希函数计算出来的地址能均匀分布在整个空间中（这是为什么叫散列表的原因）
第三点：哈希函数应该比较简单
常用的哈希函数：
第一个方法----直接定制法--(常用)：
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀 缺点：需要事先知道关 键字的分布情况
使用场景：适合查找比较小且连续的情况
第二个方法----除留余数法--(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数： Hash(key) = key% p(p<=m),将关键码转换成哈希地址
2、降低负载因子（必须重点掌握）
负载因子和冲突率的粗略关系：
从公式中我们直到，要降低负载因子，就只能去扩大散列表的长度了（因为表中的元素不可更改，你不能让别人不存东西吧）
也就是说，在负载因子达到某个值时，就要考虑给数组扩容了。
哈希冲突的解决
第一类：闭散列
也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以 把key存放到冲突位置中的“下一个” 空位置中去。
方式有线性探测和二次探测，不用重点掌握。
比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
因为他要把冲突的元素放到另一个位置，而这个位置又要尽可能分散。因此，时不时需要扩容。
第二类：开散列/哈希桶（重点掌握）
如图，若我们还想放一个“44”，将会出现哈希冲突：
闭散列想的是，把44放到空的位置。
而开散列，将计就计，也把他放到，下标为4的位置。
怎么放呢很简单。
先前这个数组，只是一个简单的数组，每个元素，存放的都是int型。
现在我们不储存int型元素，而是储存链表的头结点：
此时，想要存“44”就简单了，直接在4下标出，把val=44的节点，头插或者尾插（jdk1.8之后底层使用的尾插法）进链表即可。
有些同学可能会有疑问，不是说哈希表的搜索效率是O（1）吗？
如果要找到相应的元素，最终不是还要遍历链表？
回答：
首先，在哈希表中，当负载因子达到某个值时，会自动扩容，降低冲突概率，冲突概率本身就很低，绝大部分情况下链表长度并不大。
其次，当链表的长度的确变得很大时，哈希表还会对这个链表进行优化--（把链表转化为一个红黑树（（底层就是搜索树））
实际上，这才是真正的哈希表，（由多个哈希桶组成的--哈希桶就是上面所说的链表，或者红黑树）
哈希表是一个很重要的数据结构，不论是Map还是Set实际上底层都是哈希表实现的。
完