我们知道，哈希表的底层是由 数组 构成的，而数组是一个 连续且有限的 空间，因此从本质上来讲，在有限的空间中存放无限的元素，那么一定就会出现 冲突，本文就准备聊聊如何解决这种冲突，废话不多说，开搞！
冲突的定义
给出一个对于 哈希冲突 的官方定义：对 不同的 关键字可能得到 同一散列地址，即k1≠k2，而f(k1)==f(k2) ，这种现象称为 哈希冲突，具有相同函数值的关键字对该散列函数来说称作 同义词
冲突的解决方案
目前主流的解决方案有三种
- 开放寻址法
- 再散列法
- 链地址法（拉链法）
下面分别做下介绍
开放寻址法
公式为 loc = H（key）+ di，i=1,2，…，k（k≤m-1），其中H（key）为散列函数，m为散列表长，di为增量序列
它又分为三个子类别
- 如果di=1,2,3，…，m-1，则称为 线性探测再散列
- 如果di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k）^2,则称为 二次探测再散列
- 如果di是 伪随机数序列，则称为 伪随机探测再散列
再散列法
即在同义词产生地址冲突时，使用另一个散列函数再计算新的地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间
链地址法（拉链法）
这种方式结合了 链表 来实现，具体来说，就是数组存放的 不是 关键字，而是指向第一个关键字节点的地址，也就是说关键字被包装成了关键字节点，包含了关键字本身与指向下一个节点的指针
而当同义词产生时，将当前已存在的关键字节点的next指针指向同义词节点，这样就可以在数组的同一位置存放多个关键字，从而解决了冲突，从理论上说，这种形式的哈希表是可以存放无限个关键字的
结语
了解哈希冲突如何处理对于我们更深刻地理解哈希表是非常有用的，因此对于不同的冲突处理方式一定要有了解，好啦，就写到这啦，over！
