前言

由于hash函数是将大范围的输入，映射到一个小范围的存储区，所以，依据抽屉原理，必然会出现冲突；

常见的解决冲突方案有这几种：开放定址、链地址、增加溢出区、再hash；

开放地址法

• 线性探测法
• 如果hash到地址发现已经有数据存储了，基于该地址进行线性探测，比如+1探测等，直至可以放下数据；
• 再平方探测
• 伪随机探测
• 以上两种探测其实思想和线性探测基本一致，都是基于首次hash到的地址，进行一定修正，直至不发生冲突为止；

链地址法

• 链地址法的原理是存储节点为一个链表，每个地址均表现为一个链表，然后将数据存储在hash到的地址尾端，无需进行地址修正；
• 升级方案为，当冲突的地址节点数达到某一阈值，可以将链表升级为map类结构，提升查询效率；

公共溢出区法

• 核心思想是，当方式冲突了，就将该键值对存储到一块公共的溢出区，由于溢出区的数据量相对会比较少，可以择优选择数据结构；

再Hash法

• 核心思想和开放定址类似；
• 当冲突发生时，可以对首次hash结果再次进行hash，直至找到不发生冲突的地址放入；

几种方案比较

• 个人理解，以上四种方案，按照是否修正首次hash的地址，可以分为2类；
• 一类为修正类：开放定址、公共溢出区、再Hash
• 优点：
• 存储区可以初始化为数组，按照需要存储的大小事先开辟好数组空间，效率较高；
• 并且可以做共享内存映射，提高数据可靠性；
• 缺点：
• 单纯根据key无法精准确定地址，如果当前数据里已经占用了这个地址，就需要修正地址，增加了寻址的性能开销；
• 同时，在删除节点时，并不能直接移除数据，而是需要将这个存储区标记为已删除，这样才能不影响到后继数据块的查找；
• 还有一类就是链地址法了（也叫开链）
• 优点
• 键地址的唯一映射，一次Hash即可，寻址效率高；
• 在删除某一个数据块时，直接移除节点即可，效率比修正类要高；
• 缺点
• 链表的数据块需要动态申请和释放，无法预分配，存在一定的开销；
• 无法进行共享内存映射；

选择哪种方案，就看你实际的场景需求了。

最后，撒泼打滚求关注；