Hash冲突就是，不同的数据元素关键字K，计算出的哈希值相同，此时两个或多个数据，对应同一个存储地址，即产生冲突。

Hash冲突解决办法：

  1. 开放定址法
  2. 再哈希法
  3. 链地址法
  4. 建立公共溢出区
  5. 开放定址法

使用某种探测算法在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。就是即使key产生hash冲突，也不会形成链表，而是将所有元素都存入哈希表里。发生hash冲突时，就以当前地址为基准，进行再寻址的方法去寻址下一个地址，直到找到一个为空的地址为止。

实现方式有：

1.线性探查：发生hash冲突时，顺序查找下一个位置，直到找到一个空位置（固定步长1探测）

2.二次探查：在发生hash冲突时，在表的左右位置进行按一定步长跳跃式探测（固定步长n探测）

3.伪随机探测：在发生hash冲突时，根据公式生成一个随机数，作为此次探测空位置的步长（随机步长n探测）。

再哈希法

这种方式是同时构造多个哈希函数，当产生冲突时，计算另一个哈希函数的值。

这种方法不易产生聚集，但增加了计算时间。

链地址法（拉链法）

jdk1.8 中HashMap，ConcurrentHashMap都是采用这个方法，使用链表来保存发生hash冲突的key，即不同的key有一样的hash值，将这些发生冲突的 value 组成一个单向链表（只有next指针，没有pre指针）

1
2
3
4
5
6

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

注意：最坏的就是hash值全都映射在同一个地址上，这样哈希表就会退化成链表

jdk1.8采用红黑树解决这种情况

建立公共溢出区

将哈希表分为基本表和溢出表两部分，为所有发生hash冲突的关键字记录一个公共的溢出区来存放。在查找的时候，先与哈希表的相应位置比较，如果查找成功，则返回。否则去公共溢出区按顺序一一查找。在冲突数据少时性能好，冲突数据多的时候耗时

优缺点比较：

开放散列（open hashing）/ 拉链法（针对桶链结构）

优点：

在总数频繁变动的时候可以节省开销，避免了动态调整；

记录存储在节点里，动态分布，避免了指针的开销

删除时候比较方便

缺点：

因为存储是动态的，所以在查询的时候跳转需要更多的时间的开销

在key-value可以预知，以及没有后续增改操作时候，封闭散列性能优于开放散列

不容易序列化

封闭散列（closed hashing）/ 开放定址法

优点：

容易序列化

如果可以预知数据总数，可以创建完美哈希数列

缺点：

存储的记录数目不能超过桶组数，在交互时候会非常麻烦

使用探测序列，计算时间成本过高

删除的时候比较麻烦