导读

前面文章一、深入理解-Java集合初篇 中我们对Java的集合体系进行一个简单的分析介绍，上两篇文章二、Jdk1.7和1.8中HashMap数据结构及源码分析 、二、JDK1.7和1.8HashMap数据结构及源码分析-续 中我们分别对JDK1.7和JDK1.8中HashMap的数据结构、主要声明变量、构造函数、HashMap的put操作方法做了深入的讲解和源码分析。三、深入理解Java中的HashMap「网易面试快答」 文章中主要针对面试中常见的文件进行简单解答。

本篇文章我们将要对JDK1.7中HashMap的哈希冲突及减少哈希冲突的解决方案做详细的介绍，并通过源码加深大家的理解。

如果大家在面试中针对Java集合或者Java中的HashMap大家还有什么疑问或者其他问题，可以评论区告诉我。

简单介绍

JDK1.7---》哈希表，链表

JDK1.8---》哈希表，链表，红黑树--- JDK1.8之后，当链表长度超过8使用红黑树。

非线程安全

0.75的负载因子，扩容必须为原来的两倍。

默认大小为16，传入的初始大小必须为2的幂次方的值，如果不为也会变为2的幂次方的值。

根据HashCode存储数据。

JDK1.7的哈希冲突解决方案1.配置threshold：jdk.map.althashing.threshold（阀值-门槛）

配置改变hash冲突的门槛

源码：

/** * The default threshold of map capacity above which alternative hashing is * used for String keys. Alternative hashing reduces the incidence of * collisions due to weak hash code calculation for String keys. * <p/> * This value may be overridden by defining the system property * {@code jdk.map.althashing.threshold}. A property value of {@code 1} * forces alternative hashing to be used at all times whereas * {@code -1} value ensures that alternative hashing is never used. */static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

-Djdk.map.althashing.threshold = -1: 表示不做优化（不配置这个值作用一样）

-Djdk.map.althashing.threshold < 0: 报错

-Djdk.map.althashing.threshold = 1: 表示总是启用随机HashSeed

-Djdk.map.althashing.threshold >= 0 : 表示hashMap内部的数组长度超过该值了就使用随机HashSeed，降低碰撞

如果 配置该值为-1，表示不做hash冲突的优化；

如果 配置该值小于0，则报错；

如果 配置该值为1 则表示总是使用一个随机值（哈希因子hashseed）对hash冲突.

如果 配置该值大于等于0 表示当HashMap中数组长度超过该值的时候就使用随机值（哈希因子hashseed）来降低哈希冲突的可能性。

2使用一个私有的静态内部类Holder加载虚拟机引导之后才被初始化的值。

使用私有的静态内部类Holder加载上一步配置的Jdk.map.althashing.threshold。

源码：

/** * The default threshold of map capacity above which alternative hashing is * used for String keys. Alternative hashing reduces the incidence of * collisions due to weak hash code calculation for String keys. * <p/> * This value may be overridden by defining the system property * {@code jdk.map.althashing.threshold}. A property value of {@code 1} * forces alternative hashing to be used at all times whereas * {@code -1} value ensures that alternative hashing is never used. */static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;/** * holds values which can't be initialized until after VM is booted. */private static class Holder {    /**     * Table capacity above which to switch to use alternative hashing.     */    static final int ALTERNATIVE_HASHING_THRESHOLD;    static {        String altThreshold = java.security.AccessController.doPrivileged(            new sun.security.action.GetPropertyAction(                "jdk.map.althashing.threshold"));        int threshold;        try {            threshold = (null != altThreshold)                    ? Integer.parseInt(altThreshold)                    : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;            // disable alternative hashing if -1            if (threshold == -1) {                threshold = Integer.MAX_VALUE;            }            if (threshold < 0) {                throw new IllegalArgumentException("value must be positive integer.");            }        } catch(IllegalArgumentException failed) {            throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);        }        ALTERNATIVE_HASHING_THRESHOLD = threshold;    }}/** * A randomizing value associated with this instance that is applied to * hash code of keys to make hash collisions harder to find. If 0 then * alternative hashing is disabled. */transient int hashSeed = 0;

源码解读：

1、static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

如果在上一步中没有配置“jdk.map.althashing.threshold”,则使用该值表示是否对HashMap中的哈希冲突做干扰。该值的默认值是Integer的最大值。表示只有当HashMap中数组容量达到Integer的最大值时候才会做哈希冲突的干扰。设置这个值这么大，其实就是不做哈希冲突干扰。

2、在私有的静态内部类Holder中做判断判断。

①加载（jdk.map.althashing.threshold）配置的altThreshold;

String altThreshold = java.security.AccessController.doPrivileged(    new sun.security.action.GetPropertyAction(        "jdk.map.althashing.threshold"));

②如果从配置中加载到的altThreshold不为空，则把threshold赋值为加载到的altThreshold;

如果没有配置该altThreshold则使用默认的ALTERNATIVE_HASHING_THRESHOLD_DEFAULT，即Integer.MAX_VALUE;

threshold = (null != altThreshold)        ? Integer.parseInt(altThreshold)        : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;

③如果在JDK中配置的jdk.map.althashing.threshold为默认值-1，则把threshold设置为Integer.MAX_VALUE;

// disable alternative hashing if -1if (threshold == -1) {    threshold = Integer.MAX_VALUE;}

④．如果在JDK中配置的jdk.map.althashing.threshold值小于0，则报错，表示该值不是一个有效值。

if (threshold < 0) {    throw new IllegalArgumentException("value must be positive integer.");}

⑤．把经过计算的threshold的值赋值给“ALTERNATIVE_HASHING_THRESHOLD”.

也就是说最终是否对哈希冲突做干扰，或者在什么情况进行干扰是存储在“ALTERNATIVE_HASHING_THRESHOLD”中的。

ALTERNATIVE_HASHING_THRESHOLD = threshold;

⑥．解决哈希冲突的干扰因子。根据上一步中计算的配置“ALTERNATIVE_HASHING_THRESHOLD”判断是否启用该干扰因子。

/** * A randomizing value associated with this instance that is applied to * hash code of keys to make hash collisions harder to find. If 0 then * alternative hashing is disabled. */transient int hashSeed = 0;

从代码看出jdk.map.althashing.threshold这个变量设置的值最终会存放在静态常量ALTERNATIVE_HASHING_THRESHOLD

3.根据初始化的HashMap容量大小，决定干扰因子的值。

源码：

/**初始化哈希干扰的掩码值，我们把它的设置延迟到了真正使用它的时候。 * Initialize the hashing mask value. We defer initialization until we * really need it. */final boolean initHashSeedAsNeeded(int capacity) {   /**判断是否开启了hash干扰。如果hashseed 等于 0，则currentAltHashing = false;如果hashseed 不等于 0 ，则currentAltHashing = true;**/     boolean currentAltHashing = hashSeed != 0;/** 判断是否使用为干扰1.如果当前HashMap数组容量的大小等于jdk配置    中“jdk.map.althashing.threshold”的值时候，    且VM .isbooted 为true 时候，userAltHashing 为true;2.如果当前HashMap数组容量的小于jdk配置    中“jdk.map.althashing.threshold”的值时候，    且VM .isbooted 为true 时候，userAltHashing 为false;3. 如果当前HashMap数组容量的大小等于jdk配置    中“jdk.map.althashing.threshold”的值时候，    且VM .isbooted 为false 时候，userAltHashing 为false;4. 如果当前HashMap数组容量的小于jdk配置    中“jdk.map.althashing.threshold”的值时候，    且VM .isbooted 为false 时候，userAltHashing 为false;**/    boolean useAltHashing = sun.misc.VM.isBooted() &&            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);/** 对以上的两个值进行“异或”处理异或的结果为 两个值相同为0，两个值不同为1.也就是说 currentAltHashing 为true时且useAltHashing也为true时，或者 currentAltHashing 为false时且useAltHashing也为false时switching的结果为 true.其他情况时候，switching为false.**/    boolean switching = currentAltHashing ^ useAltHashing;    if (switching) {/**如果switching为true ，设置hashSeed(干扰因子)的值。如果useAltHashing的值为true，则随机一个干扰值给HashSeed。否则赋值为0.**/         hashSeed = useAltHashing            ? sun.misc.Hashing.randomHashSeed(this)            : 0;    }//返回是否启用干扰因子    return switching;}

源码解读：

当hashMap扩大容量时，都是调用该方法。从代码可以看出，当数组容量超过，我们设定的值ALTERNATIVE_HASHING_THRESHOLD且是vm booted，同时 hashSeed==0的时候，hashSeed的值就是用随机量，而不是固定的等于0。这样就能降低碰撞，就能降低演化成链表概率。

代码具体过程：

当 hashSeed==0 则 currentAltHashing=false当 capacity < Holder.ALTERNATIVE_HASHING_THRESHOLD 则currentAltHashing =false结果:switching=false 当 hashSeed==0 则 currentAltHashing=false当 capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD  则 currentAltHashing =true结果:switching=true  当 hashSeed !=0 则 currentAltHashing=true当 capacity < Holder.ALTERNATIVE_HASHING_THRESHOLD  则 currentAltHashing =false结果:当 switching=true 当 hashSeed !=0 则 currentAltHashing=true当 capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD  则 currentAltHashing =true结果:switching=false

回头再看代码，发现很巧妙

结论：

①.如果不配置“jdk.map.althashing.threshold”,则HashMap中的私有静态内部类中的’ALTERNATIVE_HASHING_THRESHOLD‘的值为Integer.MAX_VALUE，且HashSeed默认值为0，则switching的值永远为false，也就永远不会改变干扰因子（HashSeed）的值。

②．如果配置了“jdk.map.althashing.threshold”,则会根据当前HashMap中的数组容量动态的变更HashSeed的值，以便于引入HashSeed降低哈希冲突。

-Djdk.map.althashing.threshold=-1:表示不做优化（不配置这个值作用一样）

-Djdk.map.althashing.threshold<0:报错

-Djdk.map.althashing.threshold=1:表示总是启用随机HashSeed

-Djdk.map.althashing.threshold>=0:便是hashMap内部的数组长度超过该值了就使用随机HashSeed，降低碰撞

4.获取key的Hash值，位干扰。

源码：

/** * Retrieve object hash code and applies a supplemental hash function to the * result hash, which defends against poor quality hash functions.  This is * critical because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */final int hash(Object k) {/** 获取哈希干扰因子，该因子会跟根据HashMap的容量进行变更变更情况根据上一步的“final boolean initHashSeedAsNeeded(int capacity)”方法动态变更**/     int h = hashSeed;//如果为干扰因子不为0，且传入的key类型为String,则使用特定的算法（sun.misc.Hashing.stringHash32((String) k)）对该key进行hash计算。并返回    if (0 != h && k instanceof String) {        return sun.misc.Hashing.stringHash32((String) k);    }//如果哈希干扰因子为0 或者 k的类型不为String则使用异或操作变更key的hashcode    h ^= k.hashCode();//为了减少Hash冲突出现次数进行必要的位干扰，默认负载因子是8.    // This function ensures that hashCodes that differ only by    // constant multiples at each bit position have a bounded    // number of collisions (approximately 8 at default load factor).    h ^= (h >>> 20) ^ (h >>> 12);    return h ^ (h >>> 7) ^ (h >>> 4);}

源码解读：

可以看出生成的hash值和hashSeed 这个值有着紧密的关系，但是这个值默认是0。也就是说不管HashMap存多少数据，hashSeed 都是不会变的，可以看出随着hashMap 的容量增大，hash碰撞的概率增大的可能性也就增大。如果hash值，碰撞很高的话，那么hashMap逐渐演化成链表，性能就急剧下降。

在hash(Object k)中有这么一段位运算的代码：

h ^= k.hashCode();h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);

看起来既简单又深奥的样子，让我们来看看这段代码隐藏的东西吧。

k.hashCode()函数调用的是key键值类型自带的哈希函数，由于不同的对象其hashCode()有可能相同，所以需对hashCode()再次哈希，以降低相同率。

接下来的一串与运算和异或运算，称之为“扰动函数”，扰动的核心思想在于使计算出来的值在保留原有相关特性的基础上，增加其值的不确定性，从而降低冲突的概率。不同的版本实现的方式不一样，但其根本思想是一致的。

这里的具体实现方式是如何保证的呢？笔者功力浅薄，暂时还没有答案，如果有朋友知道的话可以交流。但是，“扰动函数”的核心思想一定要明白。

往期文章链接

Java集合

一、深入理解-Java集合初篇

二、Jdk1.7和1.8中HashMap数据结构及源码分析

二、JDK1.7和1.8HashMap数据结构及源码分析-续

三、深入理解Java中的HashMap「网易面试快答」

Java-IO体系

一、JAVA IO/NIO体系介绍

二、网络IO原理-创建ServerSocket-彻底弄懂IO

三、JAVA中ServerSocket调用Linux系统内核

四、「大厂职员教你」IO进化过程之BIO

五、「大厂职员教你」Java-IO进化过程之NIO

六、Selector实现Netty中Reactor单线程模型

七、Selector实现Netty中Reactor主从模型

八、Netty入门服务端代码

九、IO进化过程之EVENT（EPOLL-事件驱动异步模型）

如需了解更多更详细内容也可关注本人CSDN博客：不吃_花椒

Java集合还需要学习的内容