JDK8：HashMap源码解析：hash方法

た入场券 2024-04-20 08:15 64阅读 0赞

一、概述

我们知道在HashMap中，一个键值对存储在HashMap内部数据的哪个位置上和K的hashCode值有关，这也是因为HashMap的hash算法要基于hashCode值来进行。

这里要注意区分三个概念：hashCode值、hash值、hash方法、数组下标

hashCode值：是KV对中的K对象的hashCode方法的返回值（若没有重写则默认用Object类的hashCode方法的生成值）

hash值：是在hashCode值的基础上又进行了一步运算后的结果，这个运算过程就是hash方法。

数组下标：根据该hash值和数组长度计算出数组下标，计算公式：hash值  &（数组长度-1）= 下标。

我们要讨论的就是上面提到的hash方法，首先他是HashMap类中的一个静态方法，该方法的代码特别简单，只有两行，语法很容易懂，可以其中具体用意确值得好好深入研究下。

我们首先讨论下数组下标计算过程，这个有助于我们理解hash方法的设计思想

二、数组下标计算

hash：hash值
    length：数组长度
    计算公式：hash  &（length-1）
     
    若length=16，hash=1,那么下标值计算过程如下：
        0000 0000 0000 0000 0000 0000 0000 1111    16-1 = 15，15对应的二进制值为1111
        0000 0000 0000 0000 0000 0000 0000 0001    1的二进制
        0000 0000 0000 0000 0000 0000 0000 0001    上两行进行与运算，最终结果是1
     
    若length=16，hash=17,那么下标值计算过程如下：
        0000 0000 0000 0000 0000 0000 0000 1111    16-1 = 15，15对应的二进制值为1111
        0000 0000 0000 0000 0000 0000 0001 0001    17的二进制
        0000 0000 0000 0000 0000 0000 0000 0001    上两行进行与运算，最终结果是1
     
    若length=16，hash=33,那么下标值计算过程如下：
        0000 0000 0000 0000 0000 0000 0000 1111    16-1 = 15，15对应的二进制值为1111
        0000 0000 0000 0000 0000 0000 0010 0001    33的二进制
        0000 0000 0000 0000 0000 0000 0000 0001    上两行进行与运算，最终结果是1
     
    若length=32，hash=1,那么下标值计算过程如下：
        0000 0000 0000 0000 0000 0000 0001 1111    32-1 = 31，31对应的二进制值为11111
        0000 0000 0000 0000 0000 0000 0000 0001    1的二进制
        0000 0000 0000 0000 0000 0000 0000 0001    上两行进行与运算，最终结果是1
     
    若length=32，hash=17,那么下标值计算过程如下：
        0000 0000 0000 0000 0000 0000 0001 1111    32-1 = 31，31对应的二进制值为11111
        0000 0000 0000 0000 0000 0000 0001 0001    17的二进制
        0000 0000 0000 0000 0000 0000 0001 0001    上两行进行与运算，最终结果是17
     
    若length=32，hash=33,那么下标值计算过程如下：
        0000 0000 0000 0000 0000 0000 0001 1111    32-1 = 31，31对应的二进制值为11111
        0000 0000 0000 0000 0000 0000 0010 0001    33的二进制
        0000 0000 0000 0000 0000 0000 0000 0001    上两行进行与运算，最终结果是1
     
     
    (1,16)->1、(17,16)->1、(33,16)->1
    (1,32)->1、(17,32)->17、(33,32)->1
    总结：
    hash  &（length-1）的运算效果等同于 hash%length。
    我们知道hashMap的扩容规则是2倍扩容、数组长度一定是2的N次方。假设数组长度不是2的N次方，那么再重复以上的计算过程，就达不到求模的效果了。

讨论完hashMap数组下标寻址过程后，我们可以得知

在put(K,V)的时候，会根据K的hash值和当前数组长度求模，得到该键值对应该存储在数组的哪个位置。

在get(K)的时候，同样会根据K的hash值和当前数组长度求模，定位到应该去数组的哪个位置寻找V。

按照上面举得例子，put(K,V)，多个hash值和数组长度求模之后的结果相同时，大家都存储在数据的同一位置，这种情况也叫hash碰撞，发生了这种碰撞时，大家会以先来后到的方式以链表的方式组织起来，那么也就意味着我在get(K)的时候，虽然能够定位到数组位置，还需要遍历链表，通过equals逐个对比之后才能确定需要返回的V。

假设hash值都不相同，那么hashMap数组的长度越大，碰撞的机率越小。

在数组长度为16时，当hash值为1、17、33时，大家都定位到下标1，那么此时我们也可以这么想一下，当我的hashMap数组的长度不变或者不会再变得时候，大于数组长度的hash值（17、33）对我hashMap来讲和hash值1的效果是等同的。

在数组长度为65535时，当hash值为1、131071、262143时，大家都定位到下标1，那么此时我们也可以这么想一下，当我的hashMap数组的长度不变或者不会再变得时候，大于数组长度的hash值（131071、262143）对我hashMap来讲和hash值1的效果是等同的。

以上两种场景，如果假设：hash值 = hashCode值，就意味着无论是我们自己定义的hashCode还是默认的hashCode生成方式，大于数组长度的值并没有产生我们想要达到的理想效果（我们希望，不同的hashCode能够让他分布到一个不会碰撞的位置），因为取模之后，他的位置可能至少会和某个小于数组长度的值碰撞。

什么场景下可以避免碰撞：hashMap数组最大长度可知（要存储的数据不超过数组最大长度），创建时就指定初始容量为最大长度，每个K的hash值各不同，且每个hash值都小于数组最大长度。这种场景有么？有，但是我们大部分的应用场景都不会如此巧合或如此故意而为之。

再看下我们可能最常用的场景：

Map<String,Object> user = new HashMap<String,Object>(); // 默认内部数据长度为16
    user.put("name", "kevin");
    user.put("sex", 1);
    user.put("level", 1);
    user.put("phone", "13000000000");
    user.put("address", "beijing fengtai");

以字符串作为key应该是比较常用的情况了，那么这些K对应的hashCode是什么呢？如果根据hashCode来定位下标的话又是什么？

System.out.println("\"name\".hashCode()	: " +"name".hashCode());
    System.out.println("\"sex\".hashCode()	: " +"sex".hashCode());
    System.out.println("\"level\".hashCode()	: " +"level".hashCode());
    System.out.println("\"phone\".hashCode()	: " +"phone".hashCode());
    System.out.println("\"address\".hashCode()	: " +"address".hashCode());
     
    System.out.println("--------*****---------");
     
    System.out.println("\"name\".hashCode() & (16 - 1) 	:" + ("name".hashCode() & (16 - 1)));
    System.out.println("\"sex\".hashCode() & (16 - 1) 	:" + ("sex".hashCode() & (16 - 1)));
    System.out.println("\"level\".hashCode() & (16 - 1)	:" + ("level".hashCode() & (16 - 1)));
    System.out.println("\"phone\".hashCode() & (16 - 1) 	:" + ("phone".hashCode() & (16 - 1)));
    System.out.println("\"address\".hashCode() & (16 - 1) :" + ("address".hashCode() & (16 - 1)));
     
    输出结果：
     
    "name".hashCode()	: 3373707
    "sex".hashCode()	: 113766
    "level".hashCode()	: 102865796
    "phone".hashCode()	: 106642798
    "address".hashCode()	: -1147692044
    --------*****---------
    "name".hashCode() & (16 - 1) 	:11
    "sex".hashCode() & (16 - 1) 	:6
    "level".hashCode() & (16 - 1)	:4
    "phone".hashCode() & (16 - 1) 	:14
    "address".hashCode() & (16 - 1) :4

如上输出结果，我们向hashMap里put了5个键值对，每个K的hashCode值均不相同，但是根据hashCode计算出来的下标却存在碰撞（有两个4），虽然hashCode的值很随机，但是限于我们数组长度，即便是很少的几个数据，也是有很高机率碰撞的，这也就说明了这些看起来（绝对值）很大hashCode值和【0-15】范围内的值对于长度为16的初始数组容量来讲效果等同。

但是在数据量很少的情况下，即便发生了碰撞，性能上的劣势也几乎可以忽略不计。

但是我们上面的下标求值是一种假设，假设直接根据K的hashCode和数组长度求模，但是实际上是根据K的hash值和数组长度求模

那么K的hash值是什么，如何计算出来的呢，接下来就来讨论hash值的计算过程，hash方法。

三、hash方法解析

static final int hash(Object key) {
         int h;
         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

1、如果key为空，那么hash值置为0。HashMap允许null作为键，虽然这样，因为null的hash值一定是0，而且null==null为真，所以HashMap里面最多只会有一个null键。而且这个null键一定是放在数组的第一个位置上。但是如果存在hash碰撞，该位置上形成链表了，那么null键对应的节点就不确定在链表中的哪个位置了（取决于插入顺序，并且每次扩容其在链表中的位置都可能会改变）。

2、如果key是个不为空的对象，那么将key的hashCode值h和h无符号右移16位后的值做异或运算，得到最终的hash值。

从代码中目前我们可确定的信息是：hashCode值（h）是计算基础，在h的基础上进行了两次位运算（无符号右移、异或）

我们还针对前面的user的key来重新进行一下测试

System.out.println("hash(\"name\")	: " + hash("name"));
    System.out.println("hash(\"sex\")	: " + hash("sex"));
    System.out.println("hash(\"level\")	: " + hash("level"));
    System.out.println("hash(\"phone\")	: " + hash("phone"));
    System.out.println("hash(\"address\")	: " + hash("address"));
     
    System.out.println("--------*****---------");
     
    System.out.println("hash(\"name\") & (16 - 1) 	:" + (hash("name") & (16 - 1)));
    System.out.println("hash(\"sex\") & (16 - 1) 		:" + (hash("sex") & (16 - 1)));
    System.out.println("hash(\"level\") & (16 - 1)	:" + (hash("level") & (16 - 1)));
    System.out.println("hash(\"phone\") & (16 - 1) 	:" + (hash("phone") & (16 - 1)));
    System.out.println("hash(\"address\") & (16 - 1) 	:" + (hash("address") & (16 - 1)));
     
    输出结果：
     
    hash("name")	: 3373752
    hash("sex")	: 113767
    hash("level")	: 102866341
    hash("phone")	: 106642229
    hash("address")	: -1147723677
    --------*****---------
    hash("name") & (16 - 1) 	:8
    hash("sex") & (16 - 1) 		:7
    hash("level") & (16 - 1)	:5
    hash("phone") & (16 - 1) 	:5
    hash("address") & (16 - 1) 	:3

我们对比一下两次的输出结果

"name".hashCode()	    : 3373707               hash("name")	: 3373752
    "sex".hashCode()	    : 113766                hash("sex")	        : 113767
    "level".hashCode()	    : 102865796             hash("level")	: 102866341
    "phone".hashCode()	    : 106642798             hash("phone")	: 106642229
    "address".hashCode()	    : -1147692044           hash("address")	: -1147723677
    --------*****---------
    "name".hashCode() & (16 - 1) 	:11                 hash("name") & (16 - 1) 	:8
    "sex".hashCode() & (16 - 1) 	:6                  hash("sex") & (16 - 1) 	:7
    "level".hashCode() & (16 - 1)	:4                  hash("level") & (16 - 1)	:5
    "phone".hashCode() & (16 - 1) 	:14                 hash("phone") & (16 - 1) 	:5
    "address".hashCode() & (16 - 1) :4                  hash("address") & (16 - 1) 	:3

虽然经过hash算法之后与直接使用hashCode的输出不同，但是数组下标还是出现了碰撞的情况（有两个5）。所以hash方法也不能解决碰撞的问题（实际上碰撞不算是问题，我们只是想尽可能的少发生）。那么为什么不直接用hashCode而非要经过这么一种位运算来产生一个hash值呢。

我们先通过几个例子来看下 h ^ (h >>> 16)  的计算过程

若h=17，那么h ^ (h >>> 16)的计算可体现为如下过程：
        0000 0000 0000 0000 0000 0000 0001 0001    此时就是：h（17）的二进制。【高位是16个0】
        0000 0000 0000 0000 0000 0000 0000 0000    h（17）的二进制无符号右移16位后，此时就是：（h >>> 16）的二进制
        0000 0000 0000 0000 0000 0000 0001 0001    上两行进行异或运算，此时就是：h ^ (h >>> 16)的二进制
    最终可知（当h=17时）：h ^ (h >>> 16) = 17，并没有发生变化。
     
    若h=65535，那么h ^ (h >>> 16)的计算可体现为如下过程：
        0000 0000 0000 0000 1111 1111 1111 1111    h【高位还是16个0】
        0000 0000 0000 0000 0000 0000 0000 0000    h >>> 16
        0000 0000 0000 0000 1111 1111 1111 1111    h ^ (h >>> 16)
    最终可知（当h=65535时）：h ^ (h >>> 16) = 65535，并没有发生变化。
     
    若h=65536，那么h ^ (h >>> 16)的计算可体现为如下过程：
        0000 0000 0000 0001 0000 0000 0000 0000     h【高位含有一个1】
        0000 0000 0000 0000 0000 0000 0000 0001     h >>> 16
        0000 0000 0000 0001 0000 0000 0000 0001     h ^ (h >>> 16)
    最终可知（当h=65536时）：h ^ (h >>> 16) = 65537，hash后的值和原值不同。
     
    若h=1147904，那么h ^ (h >>> 16)的计算可体现为如下过程：
        0000 0000 0001 0001 1000 0100 0000 0000     h【高位含有两个1，并不连续】
        0000 0000 0000 0000 0000 0000 0001 0001     h >>> 16
        0000 0000 0001 0001 1000 0100 0001 0001     h ^ (h >>> 16)
    最终可知（当h=1147904时）：h ^ (h >>> 16) = 1147921，hash后的值和原值不同。
     
    再来看个负数的情况，负数的情况稍微复杂些，主要因为负数的二进制和十进制之间的转换会有【加|减|取反】等操作。
    若h=-5，那么h ^ (h >>> 16)的计算可体现为如下过程：
        0000 0000 0000 0000 0000 0000 0000 0101    先得到5的二进制
        1111 1111 1111 1111 1111 1111 1111 1010    5的二进制取反
     
        1111 1111 1111 1111 1111 1111 1111 1011    5的二进制取反后加1，此时就是：h（-5）的二进制。
        0000 0000 0000 0000 1111 1111 1111 1111    h（-5）的二进制无符号右移16位后，此时就是：（h >>> 16）的二进制
        1111 1111 1111 1111 0000 0000 0000 0100    上两行进行异或运算，此时就是：h ^ (h >>> 16)的二进制
                                                   接下来求一下这个二进制对应的10进制数值
        1111 1111 1111 1111 0000 0000 0000 0011    上一个二进制值减1
        0000 0000 0000 0000 1111 1111 1111 1100    再取反，此时十进制值为65532，但是需要加个负号
    最终可知（当h=-5时）：h ^ (h >>> 16) = -65532，hash后的值和原值相差比较悬殊

1）上面的例子只考虑了正数的情况，但可以得出以下结论  
当h（hashCode值）在【0-65535】时，位运算后的结果仍然是h  
当h（hashCode值）在【65535-N】时，位运算后的结果和h不同

当h（hashCode值）为负数时，位运算后的结果和h也不尽相同

2）我们上面user对象里的key的hashCode值都没有在【0-65535】范围内，所以计算出来的结果与hashCode值存在差异。

为什么【0-65535】范围内的数值h，h ^ (h >>> 16) = h ？

从例子中的二进制的运算描述我们可以发现，【0-65535】范围内的数值的二进制的高16位都是0，在进行无符号右移16位后，原来的高16位变成了现在的低16位，现在的高16位补了16个0，这种操作之后当前值就是32个0，以32个0去和任何整数值N做异或运算结果都还是N。而不再【0-65535】范围内的数值的高16位都包含有1数字位，在无符号右移16位后，虽然高位仍然补了16个0，但是当前的低位任然包含有1数字位，所以最终的运算结果会发生变化。

而我们use对象里的key的hashCode要么大于65535、要么小于0所以最终的hash值和hashCode都不相同，因为在异或运算中hashCode的高位中的非0数字位参与到了运算中。

四、hash方法的作用

前文通过实例已经印证了hash方法并不能杜绝碰撞。

而且通过对比观察，hash后的值和hashCode值虽然不尽相同，而对于正数的hashCode的产生的hash值即便和原值不同，差别也不是很大。为什么不直接使用hashCode作为hash值呢？为什么非要经过 h ^ (h >>> 16)  这一步运算呢？

在hash方法的注释是这样描述的：

/**
    * Computes key.hashCode() and spreads (XORs) higher bits of hash
    * to lower.  Because the table uses power-of-two masking, sets of
    * hashes that vary only in bits above the current mask will
    * always collide. (Among known examples are sets of Float keys
    * holding consecutive whole numbers in small tables.)  So we
    * apply a transform that spreads the impact of higher bits
    * downward. There is a tradeoff between speed, utility, and
    * quality of bit-spreading. Because many common sets of hashes
    * are already reasonably distributed (so don't benefit from
    * spreading), and because we use trees to handle large sets of
    * collisions in bins, we just XOR some shifted bits in the
    * cheapest possible way to reduce systematic lossage, as well as
    * to incorporate impact of the highest bits that would otherwise
    * never be used in index calculations because of table bounds.
    */

大概意思就是：

寻址计算时，能够参与到计算的有效二进制位仅仅是右侧和数组长度值对应的那几位，意味着发生碰撞的几率会高。

通过移位和异或运算让hashCode的高位能够参与到寻址计算中。

采用这种方式是为了在性能、实用性、分布质量上取得一个平衡。

有很多hashCode算法都已经是分布合理的了，并且大量碰撞时，还可以通过树结构来解决查询性能问题。

所以用了性能比较高的位运算来让高位参与到寻址运算中，位运算对于系统损耗相对低廉。

还提到了Float keys，个人认为说的应该是浮点数类型的对象作为key的时候，也顺便测试了下

System.out.println("Float.valueOf(0.1f).hashCode()		:" + Float.valueOf(0.1f).hashCode());
    System.out.println("Float.valueOf(1.3f).hashCode()		:" + Float.valueOf(1.3f).hashCode());
    System.out.println("Float.valueOf(100.4f).hashCode()	:" + Float.valueOf(1.4f).hashCode());
    System.out.println("Float.valueOf(987607.3f).hashCode()	:" + Float.valueOf(100000.3f).hashCode());
    System.out.println("Float.valueOf(2809764.4f).hashCode()	:" + Float.valueOf(100000.4f).hashCode());
    System.out.println("Float.valueOf(-100.3f).hashCode()	:" + Float.valueOf(-100.3f).hashCode());
    System.out.println("Float.valueOf(-100.4f).hashCode()	:" + Float.valueOf(-100.4f).hashCode());
     
    System.out.println("--------*****---------");
     
    System.out.println("hash(0.1f)		:" + hash(0.1f));
    System.out.println("hash(1.3f)		:" + hash(1.3f));
    System.out.println("hash(1.4f)	:" + hash(1.4f));
    System.out.println("hash(100000.3f)	:" + hash(100000.3f));
    System.out.println("hash(100000.4f)	:" + hash(100000.4f));
    System.out.println("hash(-100.3f)	:" + hash(-100.3f));
    System.out.println("hash(-100.4f)	:" + hash(-100.4f));
     
    输出结果：
     
    Float.valueOf(0.1f).hashCode()		:1036831949
    Float.valueOf(1.3f).hashCode()		:1067869798
    Float.valueOf(100.4f).hashCode()	:1068708659
    Float.valueOf(987607.3f).hashCode()	:1203982374
    Float.valueOf(2809764.4f).hashCode()	:1203982387
    Float.valueOf(-100.3f).hashCode()	:-1027040870
    Float.valueOf(-100.4f).hashCode()	:-1027027763
    --------*****---------
    hash(0.1f)	:1036841217
    hash(1.3f)	:1067866560
    hash(1.4f)	:1068698752
    hash(100000.3f)	:1203967973
    hash(100000.4f)	:1203967984
    hash(-100.3f)	:-1027056814
    hash(-100.4f)	:-1027076603

示例中的浮点数数值大小跨度还是比较大的，但是生成hashCode相差都不大，因为hashCode相差不大，所以最终的hash值相差也不大。那么要怎么证明hash之后就会减少碰撞呢？这个不太理解，看来还得看看大神们的分析。