答：哈希冲突的常用解决方案有以下 4 种：
 
开放定址法：当关键字的哈希地址 p=H（key）出现冲突时，以 p 为基础，产生另一个哈希地址 p1，如果 p1 仍然冲突，再以 p 为基础，产生另一个哈希地址 p2，循环此过程直到找出一个不冲突的哈希地址，将相应元素存入其中；
 
再哈希法：这种方法是同时构造多个不同的哈希函数，当哈希地址 Hi=RH1（key）发生冲突时，再计算 Hi=RH2（key），循环此过程直到找到一个不冲突的哈希地址，这种方法唯一的缺点就是增加了计算时间；
 
链地址法：这种方法的基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况；
 
建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

 
哈希冲突与解决哈希冲突的两种方法
 
1、哈希冲突
2、解决哈希冲突的方法
（1）链接法
（2）开放寻址法
①线性探查
②二次探查
③双重探查
  
 


 
注：本文注重对解决哈希冲突方法的介绍，而非对背后原理的介绍。
 
1、哈希冲突
 
当两个不同的数经过哈希函数计算后得到了同一个结果，即他们会被映射到哈希表的同一个位置时，即称为发生了哈希冲突。
 在此我们不对哈希冲突的危害进行过多的描述，本文的重点是通俗的介绍解决哈希冲突的几种方法。
 
2、解决哈希冲突的方法
 
解决哈希冲突的方法主要有链接法与开放寻址法。
 
（1）链接法
 
链接法的构思来源于链表的启发，将被哈希到哈希表同一位置的数通过链表进行连接，使得他们能够在哈希表中共存，从而解决了哈希冲突。
 如图所示，被哈希到同一位置的k1、k4；k5、k2、k7；k8、k6这三组数，被按照先后哈希的顺序，以双向链表的形式进行链接，从而共同被保存在哈希表中，解决了哈希冲突。
 
（2）开放寻址法
 
不同于链接法对哈希表的改变从而解决哈希冲突，开放寻址法的解决方法是通过对哈希函数的改变，从而将被可能发生哈希冲突的数按照一定规律哈希到另一个位置，从而保存在哈希表中。
 
需要注意的是，开放寻址法具有一个通用的位置计算公式，即
 hi(x)= ( Hash( x ) + F ( i ) ) % TableSize
 其中，hi(x)是第i次冲突的解决函数， Hash( x ) 是原哈希函数，F ( i )是不同的开放寻址法所定义的函数，TableSize是哈希表的大小。
 以下三种开放寻址法解决方式，所不同的仅是对F ( i )的不同定义而已。
 
①线性探查
 
根据上面所叙述的通用公式，在线性探查中，F ( i ) 为探查的次数，即发生哈希冲突后，依次将哈希函数值加一后对表大小取模，重新计算新的哈希位置。
 在具体实现中表现为，某个数x被哈希到i号位置，发现i号位置已经被占用，则查找(i+1)号位置，直到找到一个空的位置进行存放。
 hi(x)= ( Hash( x ) + i ) % TableSize
 
举例说明：
 
 将U中的数按顺序哈希到如图所示的TableSize=7的哈希表中，其中0、1、2、3由于不发生冲突，都按照 h0(x)= ( Hash( x ) + 0 ) % 7 进行哈希计算，被放入了0，1，2，3的位置。
 在进行7的哈希计算时发现 h0(7)= ( 7 + 0 ) % 7 = 0 ，而0号位置已经被占用，则进行冲突解决，尝试 h1(7)= ( 7 + 1 ) % 7 = 1 ，发现1号位置也被占用，继续探查，h2(7)= ( 7 + 2 ) % 7 = 2 ，h3(7)= ( 7 + 3 ) % 7 = 3 ， h4(7)= ( 7 + 4 ) % 7 = 4 ， 直到第三次探查，找到了4号位置是空的，则将7放入4号位置，解决了冲突。
 
②二次探查
 
在二次探查（也称平方探查）中，F ( i ) 是探查次数的平方。
 hi(x)= ( Hash( x ) + i^2 ) % TableSize
 同样举例说明：
 
 同样的，我们先将0、1哈希到表的0、1位置，且未发生冲突。
 接下来，我们对7进行哈希，发现 h0(7)= ( 7 + 0^2 ) % 7 = 0 ，且0号位置已被占用，则进行冲突解决，尝试 h1(7)= ( 7 + 1^2 ) % 7 = 1 ，发现1号位置同样被占用，继续探查， h2(7)= ( 7 + 2^2 ) % 7 = 4，此时4号位置未被占用，则将7放入4号位置，冲突解决。
 
③双重探查
 
双重探查也称二次再散列法，是指第一次散列产生哈希地址冲突，为了解决冲突，采用另外的散列函数或者对冲突结果进行处理的方法。
 在双重探查中，F ( i ) 是一个新的哈希函数的值的整数倍。
 通常情况下，我们有：
 hi(x)= ( Hash( x ) + i*Hash1( x ) ) % TableSize
 其中Hash1( x )是一个不同于Hash( x )的新的哈希函数。
 
举例说明：
 
 此例中，我们定义Hash1( x ) = x mod 5 。
 则有 hi(x)= ( Hash( x ) + i*(x mod 5) ) % 7 。
 在这里，0、1、2被哈希到0、1、2的位置，且未发生哈希冲突。
 对7进行哈希计算，发现 h0(7)= ( 7 + 0^2 ) % 7 = 0 ，0号位置已经被占用，发生哈希冲突，则进行解决，尝试 h1(7)= ( 7 + 1*(7 mod 5) ) % 7 = 2，发现2号位置同样被占用，则继续探查， h2(7)= ( 7 + 2*(7 mod 5) ) % 7 = 4，发现4号位置为空，则将7放入4号位置，解决冲突。

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
 


 
文章目录
 
一、什么是哈希冲突
二、如何解决哈希冲突

 
 
一、什么是哈希冲突
 
当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。
 哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。
 
二、如何解决哈希冲突
 
哈希冲突的解决方案有多种:开放地址法（发生冲突，继续寻找下一块未被占用的存储地址），二次散列函数法，链地址法。
 
在HashMap中就用到了二次散列的方法：
 
final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {//这里针对String优化了Hash函数，是否使用新的Hash函数和Hash因子有关  
            return sun.misc.Hashing.stringHash32((String) k);
        }
		//二次散列，没有直接用hashCode的值，解决hash冲突
        h ^= k.hashCode();
        
		//扰动函数，增加值的不确定性
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
 
还有链地址法数组+链表的方式
 什么是链地址法，简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
 HashMap做了一个Entry数组：
 
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;  // 键
    V value;  // 值
    Entry<K,V> next; // 指向下一个节点 ，也是一个Entry对象，从而形成解决hash冲突的单链表
    int hash;  // hash值
  
    /** 
     * 构造方法，创建一个Entry 
     * 参数：哈希值h，键值k，值v、下一个节点n 
     */  
    Entry(int h, K k, V v, Entry<K,V> n) {  
        value = v;  
        next = n;  
        key = k;  
        hash = h;  
    }  
  
    // 返回 与 此项 对应的键
    public final K getKey() {  
        return key;  
    }  

    // 返回 与 此项 对应的值
    public final V getValue() {  
        return value;  
    }  
  
    public final V setValue(V newValue) {  
        V oldValue = value;  
        value = newValue;  
        return oldValue;  
    }  
    
   /** 
     * equals（）
     * 作用：判断2个Entry是否相等，必须key和value都相等，才返回true  
     */ 
      public final boolean equals(Object o) {  
        if (!(o instanceof Map.Entry))  
            return false;  
        Map.Entry e = (Map.Entry)o;  
        Object k1 = getKey();  
        Object k2 = e.getKey();  
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
            Object v1 = getValue();  
            Object v2 = e.getValue();  
            if (v1 == v2 || (v1 != null && v1.equals(v2)))  
                return true;  
        }  
        return false;  
    } 
 
在put()方法中处理哈希冲突：
 
public V put(K key, V value) {
        //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），
        //入参为threshold，此时threshold为initialCapacity 默认是1<<4(=16)
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);//分配数组空间
        }
       	//对空值进行判断---允许空值null
        if (key == null)
            return putForNullKey(value);
        //获取哈希码
        int hash = hash(key);
        //得到对应数组下标位置
        int i = indexFor(hash, table.length);
        //如果放入的数组的位置上没有元素，那么直接添加，不用走这个for循环
        //e ！= null 满足的话就证明这个位置上有东西了
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //发生哈希冲突的时候，会先比较哈希值
            //比较是否是同一个对象，equals就不比
            //如果不是同一个对象，会比较equals方法
            //如果哈希值一样，equals方法的结果也一样，那么才会走这个if方法
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            	//获取老的value
                V oldValue = e.value;
                //新value替换老value----只替换value 不替换key
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        //新增一个entry
        addEntry(hash, key, value, i);
        return null;
    }

上篇博客我们说到了，什么是哈希冲突，其实就是再采用哈希函数对输入域进行映射到哈希表的时候，因为哈希表的位桶的数目远小于输入域的关键字的个数，所以，对于输入域的关键字来说，很可能会产生这样一种情况，也就是，一个关键字会映射到同一个位桶中的情况，这种情况就就叫做哈希冲突，解决哈希冲突的有三种方案，一种叫做拉链法（也叫作链接法、链地址法，一个意思），另外三种分别为开发地址法和再散列法。
 
一、拉链法
 
上篇博文我们举的例子，HashMap，HashSet其实都是采用的拉链法来解决哈希冲突的，就是在每个位桶实现的时候，我们采用链表（jdk1.8之后采用链表+红黑树）的数据结构来去存取发生哈希冲突的输入域的关键字（也就是被哈希函数映射到同一个位桶上的关键字）。首先来看使用拉链法解决哈希冲突的几个操作：
 
①插入操作：在发生哈希冲突的时候，我们输入域的关键字去映射到位桶（实际上是实现位桶的这个数据结构，链表或者红黑树）中去的时候，我们先检查带插入元素x是否出现在表中，很明显，这个查找所用的次数不会超过装载因子（n/m:n为输入域的关键字个数，m为位桶的数目），它是个常数，所以插入操作的最坏时间复杂度为O(1)的。
 
②查询操作：和①一样，在发生哈希冲突的时候，我们去检索的时间复杂度不会超过装载因子，也就是检索数据的时间复杂度也是O(1)的
 
③删除操作：如果在拉链法中我们想要使用链表这种数据结构来实现位桶，那么这个链表一定是双向链表，因为在删除一个元素x的时候，需要更改x的前驱元素的next指针的属性，把x从链表中删除。这个操作的时间复杂度也是O(1)的。
 
 
 
拉链法的优点
 
与开放定址法相比，拉链法有如下几个优点：
 
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
 
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
 
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
 
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
 
 
 
拉链法的缺点
 
指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
 
使用例子：
 
HashMap
 
二、开发地址法
 
开放地址法有个非常关键的特征，就是所有输入的元素全部存放在哈希表里，也就是说，位桶的实现是不需要任何的链表来实现的，换句话说，也就是这个哈希表的装载因子不会超过1。它的实现是在插入一个元素的时候，先通过哈希函数进行判断，若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法（探查序列），去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止。所以这种方法又称为再散列法。
 
有几种常用的探查序列的方法：
 
①线性探查
 
dii=1，2，3，…，m-1；这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
 
（使用例子：ThreadLocal里面的ThreadLocalMap）
 
②二次探查
 
di=12，-12，22，-22，…，k2，-k2    ( k<=m/2 )；这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
 
③ 伪随机探测
 
di=伪随机数序列；具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），生成一个位随机序列，并给定一个随机数做起点，每次去加上这个伪随机数++就可以了。
 
三、再哈希法
 
再哈希法其实很简单，就是再使用哈希函数去散列一个输入的时候，输出是同一个位置就再次哈希，直至不发生冲突位置
 
缺点：每次冲突都要重新哈希，计算时间增加。