什么是冲突？
尽管50000个单词，我们使用100000个位置来存储，并且通过一种比较好的哈希函数来完成，但是依然可能会发生冲突
- 比如melioration这个单词，通过哈希函数得到它数组的下标后，发现那个位置上已经存在一个单词demystify
- 因为它经过哈希化后和melioration得到的下标实现相同的
这种情况我们称为冲突
虽然我们不希望这种情况发生，当然更希望每个下标对应一个数据项，但是通常这时不可能的
冲突不可避免，我们只能解决冲突
就像之前0~199的数字选取5个放在长度为10的单元格中
- 如果我们随机选取出来的是33, 82, 11, 45, 90，那么最终的位置会是3-2-1-5-0，没有发生冲突
- 但是如果其中有一个33,还有一个73呢？还是发生了冲突
我们需要针对这种冲突提出一些解决方案 - 即使冲突的可能性比较小，你依然需要考虑到这种情况
- 以便发生的时候进行对应的处理代码
如何解决这种冲突呢？常见的情况有两种方案。- 链地址法
- 开放地址法
链地址法
链地址法是一种比较常见的解决冲突的方案。(也称为拉链法)
图片解析:
从图片中我们可以看出，链地址法解决冲突的办法是每个数组单元中的不在是单个数据，而是一个链条
这个链条使用什么数据结构呢？常见的是数组或者链表
比如是链表，也就是每个数组单元中存储着一个链表，一旦发现重复，将重复的元素插入到链表的首端或者末端即可
当查询时，先根据哈希化后的下标值找到对应的位置，在取出链表，依次查询找到寻找的的数据
数组还是链表呢？
数组或者链表在这里其实都可以，效率上也差不多
因为根据哈希化的Index找出这个数组或者链表时，通常就会使用线性查找，这个时候数组和链表的效率是差不多的
当然在某些实现中，会将新插入的数据放入数组或者链表的最前面，因为觉得新插入的数据用于取出的可能性更大
这种情况最好采用链表，因为数组在首位插入数据是需要所有其他项后移的，链表就没有这样的问题
当然，我觉得出于这个也看业务需求，不见得新的数据就访问次数会更多；比如我们微信新添加的好友，可能刚认识的，联系的频率不见得比我们的老朋友更多，甚至新加的只是聊一两句
所有，这里个人觉得选择数组或者链表都是可以的
开放地址法
开发地址法的主要工作方式是寻找空白的单元格来添加重复的数据
我们还是通过图片来了解开放地址法的工作方式
图片解析：
开放地址法其实就是要寻找空白的位置来放置冲突的数据项
但是探索这个位置(空白位置)的方式不同，有三种方法
- 线性探测
- 二次探测
- 再哈希法
线性探测非常好理解：线性的查找空白的单元格
插入的32：
经过哈希化的到的index=2,但是在插入的时候，发现该位置已经有了82，怎么办呢？
线性探测就是从index位置+1开始一点点查找合适的位置来放置32，什么是合适的位置呢？
空的位置就是合适的位置，在我们上面的例子中就是index=3的位置，这个时候32就会放在该位置
查询32呢？
查询32和插入32比较类似
首先经过哈希化的到index=2,比如2的位置结果和查询的数值是否相同，相同那么就直接返回
不相同呢？线性查找，从index位置+1开始查找和32一样的
这里有一个特别需要注意的地方：如果32的位置我们之前没有插入，是否将整个哈希表查询一遍来缺点32不存在吗？
- 当然不是，查询有一个约定，就是查询到空位置，就停止
因为查询到这里有空位置，32之前就不可能跳过空位置去其他的位置
删除32呢？
删除查找和插入和查询比较类似，但是也有一个特别注意点
注意：删除操作一个数据项时，不可以将这个位置下标的内容设置为null,为什么呢？
因为将它设置为null可能会影响我们之后查询其他操作，所有通常删除一个位置的数据项时，我们可以将它进行特殊处理（比如设置为-1）
当我们之后看到-1位置的数据项时，就知道查询时要继续查询，但是插入时这个位置可以放置数据
线性探测的问题：
线性探测有一个比较严重的问题，就是聚集，什么是聚集呢？
比如我在没有任何数据的时候，插入22-23-24-25-26,那么意味着下标值2-3-4-5-6的位置都有元素
这种一连串填充单位就叫做聚集
聚集会影响哈希表的性能，无论插入/查询/删除都会影响
比如我们插入一个32，会发现连续的单元都不允许我们放置数据，并且在这个过程中我们需要探索多次
二次探测可以解决一部分这个问题，我们一起来看看
线性探测存在的问题：如果之前的数据是连续插入的，那么新插入的一个数据可能需要探测很长的距离
二次探测主要优化的是探测的步长，什么意思呢？
线性探测，我们可以看成是步长为1的探测，比如从下标值x开始，那么线性探测就是x+1,x+2,x+3依次探测
二次探测，对步长做了优化，比如从下标值x开始，x+1^2, x+ 2^2, x+3^2
这样就可以一次性探测比较长的距离，以避免那些聚集带来的影响
二次探测的问题：
但是二次探测依然存在问题，比如我们连续插入的是32-112-82-2-192，那么它们依次累加的时候步长是相同的
也就是这种情况下或造成步长不一的一种聚集。还是会影响效率。(当然这种可能相对于连续的数字会小一些)
怎么根本解决这个问题呢？让每个人的步长不一样，一起来看看再哈希法吧.
再哈希法
为了消除线性探测和二次探测中无论步长+1还是步长+平方法中存在的问题，还有一种最常用的解决方案：再哈希法
二次探测的算法产生的探测次序步长是固定的：1，4，9，16，依次类推
现在需要一种方法：产生一种依赖关键字的探测序列，而不是每个关键字都一样
那么，不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列
再哈希法的做法就是：把关键字用另外一个哈希函数，再做依次哈希化，用这次哈希化的结果作为步长
对于指定的关键字，步长在整个探测中是不变的，不过不同的关键字使用不同的步长
第二次哈希化需要具备如下特点：
和第一个哈希函数不同。（不要再使用上一次的哈希函数了，不然结果还是原来的位置）
不能输出为0(否则，将没有步长。每次探测都是原地踏步，算法进入死循环)
其实，我们不用费脑细胞来设计了，计算机专家已经设计出一种工作很好的哈希函数：
stepSize = constant - (key % constant)
其中constant是质数，且小于数组的容量
例如:stepSize = 5 - (key % 5)满足需求，并且结果不可能为0