有时候哈希表⽆论选择什么哈希函数都⽆法避免冲突，那么插⼊数据时，如何解决冲突呢？主要两种⽅法，线性探测法和链地址法，这篇先做原理描述，下篇实现代码模拟

一、线性探测

发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。

案例:

第一个元素19计算的哈希值为8，所以找到标的位置8，把19塞到这里面，第二个元素30的哈希值也是8，但下标9里面已经有19了，此时出现哈西冲突，用线性探测法解决这个哈希冲突就是依次向后寻找一个没有存储数据的位置，也就是放到下标9的位置，接着5放到下标5，36放到下标3，3放到下标2，20放到下标9，9里面已经有30了，便放到下一个位置10，21放到下标10，下标10已经有20了且走到表尾，没关系，从表头开始依次向后找，我们可以把哈希表看成环的形式，走到表尾之后再继续走到前21放到下标0，12放到下标1，这样就把所有的数据利用线性探测的方式全都存到哈希表里了，如果我想确定一下21这个数有没有存到表中，根我们存储的形式是一样的，首先计算出来它的哈希值为10，从10位置依次向后找看有没有21这个数就可以了

但是有一个致命问题，假设给数组添加一个数据8，8%11=8，存到下标8的这个位置出现哈西冲突，所以要向后探测，发现9 10 0 1 2 3下标都存着数据，直到4的时候才找到空位置，并把8存了进去，因此线性探测是有它的弊端的，如果哈希表里面存的数很密集，有可能要线性探测很多次，这样的哈希表想O(1)来查找以及存储每一个数据是做不到的，其实也有方法解决这个弊端，创建个大一点的数组，比如题目里面有八个数据，可以创建一个是它两倍大小的数组，并且把哈希函数的模数在原有的数值上×2，在它的附近找一个质数去模

二、链地址法

链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面。

案例:

给定数组 a={19,30,5,36,13,20,21,12,24,96}，哈希函数为 hash(key)= key % 11；h(19)= 8.h(30)=8.h(5)=5.h(36)=3.h(13)=2h(20)=9.h(21)=10，h(12)=1.h(24)=2.h(96)=8

如上图12的哈希值为1，就会把12以链表的形式挂在下标1上，24和13挂在下标2的哈希表中，以此类推，解释一下，下面8挂着的链表96 30 19，明明是19先插入的，为什么他会在最后，因为这个链表的插入操作是头插

当然它也有弊端，如果所有的数全都冲突挂在下标8，这个链表就会特别长，往后查找一个数的时候，他的时间复杂就变成O(N)了，这个解决方式是不用链表挂，而是用红黑树，这时候时间复杂会变成logN级别