哈希冲突的解决方法

开放定址法

使用某种探测算法在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。

实现方式有：
1. 线性探查再散列：发生hash冲突时，顺序查找下一个位置，直到找到一个空位置。d_i=+1,+2,+3,…
2. 二次/平方探查再散列：在发生hash冲突时，在表的左右位置进行按一定步长跳跃式探测。d_i=+1^2,-1^2,+2^2,-2^2,…
3. 伪随机探测再散列：有一个固定的随机数序列，在发生hash冲突时，将要存储的数据加上下一个随机数再散列，直到找到一个空位置。

再哈希法

构造多个哈希函数，当产生冲突时，计算另一个哈希函数的值。
这种方法不易产生聚集，但增加了计算时间。

链地址法 / 拉链法

链地址法又称为拉链法。
将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。
链地址法适合经常进行插入和删除的情况。
Java的HashMap和HashSet采用这种方式解决哈希冲突，同时对同义词链使用红黑树，提高查找和修改的效率。

建立公共溢出区

将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

参考资料

Hash冲突及解决办法 – 51CTO
解决hash冲突的三个方法 – 博客园
解决哈希冲突的常用方法分析