JDK11源码--HashMap源码分析

ゝ一纸荒年。 2022-03-16 04:50 398阅读 0赞

### 文章目录 ###

*  欢迎关注本人公众号
 *  概述
 *  hashmap数据结构
 *  基本参数
 *   *  \`MAXIMUM\_CAPACITY\`为什么设置成1 << 30
     *  为什么map的容量要限制为2的整数次方
     *  \`DEFAULT\_LOAD\_FACTOR\`负载因子为什么是0.75
     *   *  泊松分布（Poisson分布）
         *  hashmap中的泊松分布
 *  重要属性
 *  重要方法分析
 *   *  构造函数
     *  put() 及 hash 算法
     *  为什么重写equals方法时必须重写hashcode方法
     *  resize()
     *  treeifyBin() 链表转为红黑树
     *  get()

# 欢迎关注本人公众号 #

![在这里插入图片描述][20200515113638671.jpg_pic_center]

# 概述 #

本文介绍JDK11中HashMap的源码实现。

# hashmap数据结构 #

map中存储的是key,value键值对。众所周知，hashmap是采用的 数组 + 链表 + 红黑树 的数据结构存储数据的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pdDAwNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
上图中，左侧方形表示的是数组，初始化状态长度是16。数组中每个元素我们这里称之为桶，桶存储的是key的hash值，每个桶后面挂载着链表，链表中存储的是具体的数据value。

# 基本参数 #

/** * 默认的初始容量。 * 必须是2的整数次方 */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    /** * map的最大容量 * 也要是2的整数次方 */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    /** * 默认负载因子 * */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    /** * 链表长度大于8时，转换为红黑树结构 */
    static final int TREEIFY_THRESHOLD = 8;
    
    /** * 扩容时，如果发现树中节点数量小于6，则将树还原为链表 */
    static final int UNTREEIFY_THRESHOLD = 6;
    
    /** * map容器中某个箱子（bin）再有链表转为树之前还要满足键值对数量大于 64 才会发生转换。 * 目的是为了避免 resizing（扩容） 和 treeification（链表转树结构）之间的冲突 */
    static final int MIN_TREEIFY_CAPACITY = 64;

## `MAXIMUM_CAPACITY`为什么设置成1 << 30 ##

`MAXIMUM_CAPACITY`含义是map的最大容量。它是int类型，使用`<<`移位运算符的结果不能超过int可以表示的最大值。固最大只能左移30，再大就溢出了。

> java中的int占4个字节，每个字节8位，所以总共是占用32位。int是有符号的，其中第一位是符号位。所以还剩下31位。那么最多就是左移30了。  
> 1 << 2 = 4(十进制) = 100(二进制)

## 为什么map的容量要限制为2的整数次方 ##

上面已经提到map的数据结构是数组加链表的结构。  
那么如何才能快速定位某个键值对的位置呢？  
老版本的源码中有这么一个方法，获取元素的位置：

static int indexFor(int h, int length) { 
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
    }

上述代码在jdk11中已经删除。但是在其他代码段中依然是采用类似的方式寻找的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pdDAwNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]  
tab是数组，n是数组长度，hash是要查找的key的hash值。  
tab\[(n-1) & hash\] 含义就是根据hash值快速定位到数组的位置。  
由于数组长度是2的整数次方，n-1转为二进制就都是1111（初始化情况下）。这样进行 & 计算的结果就与hash一样，也就定位到了数组中的位置。  
那么为什么是2的整数次方呢。假如不是2的整数次方，length为15，则length-1为14，对应的二进制为1110，在于h与操作，最后一位都为0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。也就是说设置2的N次方，可以使得数据分布更加分散，减少碰撞

## `DEFAULT_LOAD_FACTOR`负载因子为什么是0.75 ##

### 泊松分布（Poisson分布） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pdDAwNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]

### hashmap中的泊松分布 ###

在hashmap的注释中也给出了泊松分布的公式及各参数作用的注释：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pdDAwNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]  
大体意思也就是说，treenode占用的空间是常规节点的两倍，所以只有当bin（指数组中的一个桶，这里也可以翻译为箱子）中元素数量超过TREEIFY\_THRESHOLD时才会使用treenode。  
在hash分布比较均匀的情况下，很少使用treenode。  
在随机hashCodes情况下，bin中节点出现的频率遵循`Poisson分布`。此时load factor（即DEFAULT\_LOAD\_FACTOR）=0.75f，λ=0.5。  
调整load factor，λ会出现比较大的偏差。

假如在长度为length=16的数组中放入0.75\*length=12个数据时，数组中某一个下标放入k个数据（即数组后面的链表的数据量）的概率：

<table> 
 <thead> 
  <tr> 
   <th>存储数据量</th> 
   <th>概率</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>0</td> 
   <td>0.60653066</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>0.30326533</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>0.07581633</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>0.01263606</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>0.00157952</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>0.00015795</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>0.00001316</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>0.00000094</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>0.00000006</td> 
  </tr> 
 </tbody> 
</table>

hashmap扩容到32或者64时，一个bin中存储8个数据量的概率都是0.00000006。  
所以，当某一个bin（链表）的节点数大于等于8个的时候，就可以从链表node转换为treenode，其性价比是值得的。

# 重要属性 #

/** * 存储hash的数组，首次使用时初始化 * 长度总是2的真实次方 */
    transient Node<K,V>[] table;
    
    /** * 存放实际的键值对 */
    transient Set<Map.Entry<K,V>> entrySet;
    
    /** * mao中元素总数量 */
    transient int size;
    
    /** * 每次扩容和更改map结构的计数器 */
    transient int modCount;
    
    /** * threshold = (capacity * load factor) * 该字段用于判断核实扩容 */
    int threshold;
    
    /** * 负载因子 */
    final float loadFactor;

# 重要方法分析 #

## 构造函数 ##

这里分析一下`HashMap<String, String> map = new HashMap<>();`中的实现。

hashmap中有三个构造方法，一般来说我们使用默认的无参构造就够了。当可以预估到容量时也可以指定容量大小。

public HashMap(int initialCapacity, float loadFactor) { 
           if (initialCapacity < 0)
               throw new IllegalArgumentException("Illegal initial capacity: " +
                                                  initialCapacity);
           if (initialCapacity > MAXIMUM_CAPACITY)
               initialCapacity = MAXIMUM_CAPACITY;
           if (loadFactor <= 0 || Float.isNaN(loadFactor))
               throw new IllegalArgumentException("Illegal load factor: " +
                                                  loadFactor);
           this.loadFactor = loadFactor;
           this.threshold = tableSizeFor(initialCapacity);
       }
    
    
       public HashMap(int initialCapacity) { 
           this(initialCapacity, DEFAULT_LOAD_FACTOR);
       }
    
    
       public HashMap() { 
           this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
       }

构造方法都是设置几个参数值，并没有实际初始化数组与链表。这样可以节省一点空间。  
在首次put时会调用`resize()`方法来初始化数组`tab`。

这里注意`tableSizeFor()`这个方法,该方法返回最近的不小于输入参数的2的整数次幂。比如10，则返回16：

static final int tableSizeFor(int cap) { 
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

先说`Integer.numberOfLeadingZeros`这个方法，他的作用是返回无符号整型i的最高非零位前面的0的个数，包括符号位在内。具体代码分析请参见 [jdk11源码–Integer.numberOfLeadingZeros][jdk11_Integer.numberOfLeadingZeros]。

假如cap=10 ，10的二进制表示是`00000000 00000000 00000000 00001010`。人工计算一下，大于10的最小2的n次方大于10且距离10最近的应该是16，二进制表示是`00000000 00000000 00000000 00010000`，也就是**从右往左找到最后一个1，这个1右边的值全部改为1，然后再加1就是我们想要的结果了**。  
上述代码可以快速计算出结果。详细计算步骤如下：

*  Integer.numberOfLeadingZeros(cap - 1) = 28，二进制表示是`00000000 00000000 00000000 00011100`
 *  n=-1>>>28=15
    
     *  \-1二进制原码是`10000000 00000000 00000000 00000001`
     *  \-1反码是`11111111 11111111 11111111 11111110`
     *  \-1补码是`11111111 11111111 11111111 11111111` (知识点：负数的补码 = \{原码符号位不变\} + \{数值位按位取反后+1\})
     *  所以-1带符号右移28位是`00000000 00000000 00000000 00001111`=15(十进制)
 *  最终结果是15+1=16.

hbase中是采用的先右移在左移的算法。具体参考 [Java对象占用堆内存大小计算][Java]

还是以上面的为例，则算法也可以写成，这样更加简单，但是java为什么没有这么写呢，是不是有坑没有发现？？

static final int tableSizeForByHbase(int cap) { 
        return 1 << (32 - Integer.numberOfLeadingZeros(cap - 1));
    }

## put() 及 hash 算法 ##

public V put(K key, V value) { 
        return putVal(hash(key), key, value, false, true);
    }
    
    //计算hash值。这里在获取了hash值以后，又进行了一次异或计算。目的是为了尽可能减少hash碰撞。
    static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) { 
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)//初始化时肯定为null
            n = (tab = resize()).length;//初始化时在这里调用resize()进行数组的初始化
        if ((p = tab[i = (n - 1) & hash]) == null)//数组中某个tab位是空的，也就是后面没有挂载链表 ，没有数据
            tab[i] = newNode(hash, key, value, null);//则直接创建node对象，挂载数据即可
        else { //数组中某个tab已经有数据存在了，则这里进行链表构建
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))//
                e = p;//key相同
            else if (p instanceof TreeNode)//是红黑树
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { //链表，且已经超过一个数据
                for (int binCount = 0; ; ++binCount) { 
                    if ((e = p.next) == null) { 
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) {  // key相同时更新value
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();//如果超过阈值，则扩充map大小
        afterNodeInsertion(evict);
        return null;
    }

我们首先来看一下上面的hash函数，jdk中没有直接使用hashcode()作为hash值，而是现将hashcode()值无符号右移16位得到新值，然后hashcode()与这个新值进行异或计算得到最终的hash值。

<table> 
 <thead> 
  <tr> 
   <th>描述</th> 
   <th>值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>key的hash值</td> 
   <td><code>00000101 00101101 10010100 01000010</code></td> 
  </tr> 
  <tr> 
   <td>无符号右移16位</td> 
   <td><code>00000000 00000000 00000101 00101101</code></td> 
  </tr> 
  <tr> 
   <td>两者异或结果</td> 
   <td><code>00000101 00101101 10010001 01101111</code></td> 
  </tr> 
 </tbody> 
</table>

这样做的墓地是避免hash碰撞。比如，在n - 1为15(0x1111)时，散列值真正生效的只是低4位。当新增的键的hashcode()是2，18，34这样恰好以16的倍数为差的等差数列，就产生了大量碰撞。  
因此，设计者综合考虑了速度、作用、质量，把高16bit和低16bit进行了异或。因为现在大多数的hashCode的分布已经很不错了，就算是发生了较多碰撞也用O(logn)的红黑树去优化了。仅仅异或一下，既减少了系统的开销，也不会造成因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。

## 为什么重写equals方法时必须重写hashcode方法 ##

上面put代码中有这么一句;

if (e.hash == hash &&
     ((k = e.key) == key || (key != null && key.equals(k))))
     break;

当根据key都hash值，定位到数组中某个位置以后，往后面链表添加元素时，判断元素是否完全一样，是首先判断了hash，然后再判断了equals。如果只重写了equals，那么仍然会按照不同的两个对象处理，所以重写equals方法时必须重写hashcode方法.

有人可能会奇怪，`if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))` 这个条件是不是有点复杂了，我感觉只使用 equals 方法就可以了啊，为什么要多此一举去判断 hashcode 呢?

因为在 HashMap 的链表结构中遍历判断的时候，特定情况下重写的 equals 方法比较对象是否相等的业务逻辑比较复杂，循环下来更是影响查找效率。所以这里把 hashcode 的判断放在前面，只要 hashcode 不相等就玩儿完，不用再去调用复杂的 equals 了。很大程度地提升 HashMap 的效率。

可能你又要问了，put都时候，是根据hash值定位到数组的 不同位置的，同一个数组位置后面都所有元素hash值都应该相同。其实这个问题上面hash函数都计算已经给出答案了，hashMap并没有直接使用hash值，而是进行了移位与异或计算。

## resize() ##

接下来看resize()方法。

final Node<K,V>[] resize() { 
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) { 
            if (oldCap >= MAXIMUM_CAPACITY) { //当数组容量达到最大值时不再扩容
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                     //将当前数组长度扩大一倍
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {                // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) { 
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;//设置新的阈值
        @SuppressWarnings({ "rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//第一次初始化会创建；扩容时会创建新的数组
        table = newTab;
        if (oldTab != null) { 
        //循环遍历老map中的所有数据，迁移到新数组中对应位置，进行扩容操作
            for (int j = 0; j < oldCap; ++j) { 
                Node<K,V> e;
                if ((e = oldTab[j]) != null) { 
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {  // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do { 
                            next = e.next;
                            //这里通过当前hash与数组长度进行逻辑与操作，判断是否为0，来区分该元素是不变位置还是需要重新更换位置
                            if ((e.hash & oldCap) == 0) { 
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else { 
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) { 
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) { 
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;//现有index+现有数组的长度就是新数组中的索引位置
                        }
                    }
                }
            }
        }
        return newTab;
    }

代码分析

*  当初始化hashmap时，按照threashold进行初始分配内存
 *  扩容时，数组会扩容两倍，采用左移一位算法
 *  扩容时，现有数据位置要么不动，要么是（当前索引+现有数组长度）
 *  扩容时不会重新计算hash值，key的hash值会保存在node元素中。
 *  上述代码中有个`(e.hash & oldCap) == 0`的计算，这一步的意思是判断这个元素是应该不动，还是应该迁移到新的位置。下面举例说明：

我们以`map.put("a1", "aa1")`为例，a1计算后的hash值是3056，初始化情况下，存储在数组中的位置是0：

00000000 00001111 【初始化数组长度是16，(16-1)对应二进制】  
00001011 11110000 【3056的二进制】  
&  
00000000 00000000 【逻辑与计算结果是0】

扩容时，数组长度增加一倍，变为32。计算a1是否应该迁移，迁移到什么位置。首先，将a1与16进行逻辑与计算，结果是1，所以要进行迁移：

00000000 00010000 【初始化数组长度是16，对应二进制】  
00001011 11110000 【3056的二进制】  
&  
00000000 000`1`0000 【逻辑与计算结果是1】

那么扩容后迁移的新位置的索引是：

00000000 00011111 【扩容后数组长度是32，（32-1）对应二进制】  
00001011 11110000 【3056的二进制】  
&  
00000000 000`1`0000 【逻辑与计算结果是16（正好是0+16）】

如果将aX与16进行逻辑与计算，结果是0，那么上述数组长度32的逻辑与计算的结果肯定与长度16的计算结果一致，因为高位结果是0.

## treeifyBin() 链表转为红黑树 ##

final void treeifyBin(Node<K,V>[] tab, int hash) { 
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();//为空或者容量小于MIN_TREEIFY_CAPACITY（默认64）则不进行转换，而是进行resize扩容
        else if ((e = tab[index = (n - 1) & hash]) != null) { 
            TreeNode<K,V> hd = null, tl = null;
            do { //循环遍历链表，切换为红黑树
                TreeNode<K,V> p = replacementTreeNode(e, null);//根据链表的node创建treenode
                if (tl == null)
                    hd = p;
                else { 
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

*  `(n = tab.length) < MIN_TREEIFY_CAPACITY`表示不仅仅是单个链表长度超过8，还要数组长度大于64才进行红黑树的转换，否则进行扩容。红黑树占用空间大，hashmap的设计是尽可能不用。

更多红黑树的内容参见：[红黑树详解][Link 1]

## get() ##

final Node<K,V> getNode(int hash, Object key) { 
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) { //map不是空的
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;//根据hash定位到数组中位置后，读取的第一个元素就是要找的元素
            if ((e = first.next) != null) { 
                if (first instanceof TreeNode)//在红黑树中查找
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do { //遍历链表，查询
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

*  红黑树查询时间复杂度 O(logn)
 *  链表查询时间复杂度 O(n)

[20200515113638671.jpg_pic_center]: /images/20220316/cb106247f4d349c8b841a82a77e8c5f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pdDAwNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20220316/1f4bda0a5b8d4d5fb8efd1ad83139897.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pdDAwNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20220316/3c02d728adde4fcebaa7f5c8b0c7b1da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pdDAwNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: /images/20220316/46e983101a0f49868ed0c3001b64f40f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9pdDAwNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]: /images/20220316/a5b783f0a2dc4bb38c9f30ced71c4d15.png
[jdk11_Integer.numberOfLeadingZeros]: https://it007.blog.csdn.net/article/details/87946142
[Java]: https://blog.csdn.net/liubenlong007/article/details/103278623
[Link 1]: https://www.cnblogs.com/yyxt/p/4983967.html