hash冲突的四种解决办法
通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。
hash冲突的四种解决办法
哈希冲突
就是根据key即经过一个函数f(key)得到的结果的作为地址去存放当前的key value键值对(这个是hashmap的存值方式)，但是却发现算出来的地址上已经有人先来了。造成当前值无法存储的情况
一、开放定址法
1 | |
H(key)为哈希函数，m为哈希表表长，di为增量序列，i为已发生冲突的次数。其中，开放定址法根据步长不同可以分为3种：
1. 线性探查法
简单地说，就是以当前冲突位置为起点，步长为1循环查找，直到找到一个空的位置，如果循环完了都占不到位置，就说明容器已经满了。举个栗子，就像你在饭点去街上吃饭，挨家去看是否有位置一样。
2. 平方探测法
相对于线性探查法，这就相当于的步长为di = i2来循环查找，直到找到空的位置。以上面那个例子来看，现在你不是挨家去看有没有位置了，而是拿手机算去第i2家店，然后去问这家店有没有位置。
3. 伪随机探测法：di=伪随机序列
这个就是取随机数来作为步长。还是用上面的例子，这次就是完全按心情去选一家店问有没有位置了。
但开放定址法有这些缺点：
- 这种方法建立起来的哈希表，当冲突多的时候数据容易堆集在一起，这时候对查找不友好；
- 删除结点的时候不能简单将结点的空间置空，否则将截断在它填入散列表之后的同义词结点查找路径。因此如果要删除结点，只能在被删结点上添加删除标记，而不能真正删除结点；
- 如果哈希表的空间已经满了，还需要建立一个溢出表，来存入多出来的元素。
二、链地址法
将冲突位置的元素构造成链表。在添加数据的时候，如果哈希地址与哈希表上的元素冲突，就放在这个位置的链表上。
拉链法的优点：
- 处理冲突的方式简单，且无堆集现象，非同义词绝不会发生冲突，因此平均查找长度较短；
- 由于拉链法中各链表上的结点空间是动态申请的，所以它更适合造表前无法确定表长的情况；
- 删除结点操作易于实现，只要简单地删除链表上的相应的结点即可。
拉链法的缺点：需要额外的存储空间。
从HashMap的底层结构中我们可以看到，HashMap采用是数组+链表/红黑树的组合来作为底层结构，也就是开放地址法+链地址法的方式来实现HashMap。
三、再哈希法
1 | |
RHi()函数是不同于H()的哈希函数，用于同义词发生地址冲突时，计算出另一个哈希函数地址，直到不发生冲突位置。这种方法不容易产生堆集，但是会增加计算时间。
所以再哈希法的缺点是：增加了计算时间。
