jdk8中的HashMap源码解析与理解

缺乏、安全感 2022-11-20 06:58 191阅读 0赞

## jdk8中的HashMap源码解析与理解 ##

### 一、预备知识 ###

**关于hash：**

有个非常关键的特点，不定长度的输入固定长度的输出，将一个对象经过一定的hash算法映射成相同长度的hash值。

**hash冲突的避免：**

hash冲突是无法完全避免的，只能通过各种方法手段尽量的减少hash冲突。

**关于hash碰撞的解决方案：**

1.  开放地址法：假设一个数组有四个长度此时存放了\[8,null,10,11,null\]两个为null的位置代表没有数据，此时如果有个15来了，15mod 4=3那么这个15应该放在下标为3的位置上，但是3号位置有了数据，所以我们需要用（15+1）mod 4=4此时就放在了4位置，此时恰好没有数据，如果4位置有数据那么我们应该继续向下探测，即（15+1+1）mod 4得到对应的索引位置，直到找到可以放置的位置。
2.  再hash法：再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数  
    计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。
3.  链地址法：这个就是利用链表来实现，当发生hash冲突的时候我们将冲突的数据继续放在该位置，只不过要形成链表连接在这个位置的元素的后边。我们的hashmap就是利用这种方式来实现的hash冲突的解决。
4.  建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

### 二、jdk8相对jdk7对于hashmap有哪些改进 ###

1.  jdk8采用了数组+链表+红黑树的数据结构进行数据的存储，而jdk7中采用了数组+链表的处理方式
2.  jdk8中将数据插入链表的时候采用的是尾插法，而jdk7采用的是头插法。
3.  jdk8中新增了一些新的特性，比如hashmap的foreach以及merge和replace方法
4.  jdk8中在扩容数据迁移的时候是采用的高低位链的形式进行，而jdk7则是采用的头尾倒置的方式进行迁移。

### 三、源码讲解 ###

**理解jdk8中的hashmap源码中几个重要的参数：**

1. 加载因子：在hashmap中这个值默认是0.75。
    2. map容量：map的容量并不一定等于实际创建时写入的map的容量，因为hashmap的容量一定是2的n次方，所以当我们申请一个大小为13的map的时候在实际创建的时候会申请一个大小为16的map，也就是说找到第一个大于或者等于申请大小的2的n次方的数据。**但是尤其重要的是这个容量是没有参数的，他一开始是存储在扩容阈值的那个参数中的**
    3. 扩容阈值：加载因子*map的容量，假如map的容量为16加载因子为0.75那么扩容的阈值就是 $16\ast0.75 =12$ ，也就是说当map中存放的元素如果大于了12那么就需要进行扩容。
    4. 树化的阈值：在jdk8中当链表的长度大于了8以后会转为红黑树，这个8就是转为红黑树的阈值。

**hashmap中的key的hashcode是直接利用hashcode方法生成的吗？**

这个地方不是直接用原生的hashcode方法生成的，而是随原生的hashcode方法进行搞16位异或低16位的扰动，举个例子，假设存放key=“nihao”，如图：

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

我们按照源码中的计算过程如下图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDIyNTYxMw_size_16_color_FFFFFF_t_70_pic_center 1]

通过这样得二次位扰动加工处理我们尽可能得避免了hash碰撞得发生，进一步降低hash冲突的几率。

我们可以通过另外一个例子分析一下是如何降低得，假设我们得数组长度是16那么我们在进行取模运算得时候则是通过hashcode&(16-1)这样得运算得到得索引值，如果我们得key为“abcabcabcabcabc”，我们得到如下:

<table> 
 <thead> 
  <tr> 
   <th>1954974080（HashCode）</th> 
   <th>111 0100 1000 0110 1000 1001 1000 0000</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>2^4-1=15（length-1）</td> 
   <td>000 0000 0000 0000 0000 0000 0000 1111</td> 
  </tr> 
  <tr> 
   <td>&amp;运算</td> 
   <td>000 0000 0000 0000 0000 0000 0000 0000</td> 
  </tr> 
 </tbody> 
</table>

而加上高16位异或低16位的“扰动函数”后，结果如下：

<table> 
 <thead> 
  <tr> 
   <th>原HashCode</th> 
   <th>1954974080</th> 
   <th>111 0100 1000 0110 1000 1001 1000 0000</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>(&gt;&gt;&gt;16)无符号右移16位</td> 
   <td>29830</td> 
   <td>000 0000 0000 0000 0111 0100 1000 0110</td> 
  </tr> 
  <tr> 
   <td>^（异或）运算</td> 
   <td>1955003654</td> 
   <td>111 0100 1000 0110 1111 1101 0000 0110</td> 
  </tr> 
  <tr> 
   <td>2^4-1=15（length-1）</td> 
   <td>15</td> 
   <td>000 0000 0000 0000 0000 0000 0000 1111</td> 
  </tr> 
  <tr> 
   <td>&amp;（与）运算</td> 
   <td>6</td> 
   <td>000 0000 0000 0000 0000 0000 0000 0110</td> 
  </tr> 
 </tbody> 
</table>

通过上边的例子我们可以得到，如果未进行扰动那么只要hashcode后四位为0那么无论前边28位如何变化得到的结果只会位0，但是进行扰动以后情况有所不同了，显然末尾变成了0110减少了碰撞几率。

**hashMap中数组的创建和初始化是一开始进行的吗？**

hashmap中的数组不是new的时候创建的，而是在第一次put的时候做的初始化使用懒加载的方式，节省了空间。如图：

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

第一次会走如图的红框部分，进去这个分支以后会执行resize()方法，在resize中会对数组进行初始化。

**链表转为红黑树需要什么条件：**

链表转为红黑树主要要满足两个条件，一个是链表的长度大于8，另外一个是数组的长度大于64这个我们可以看下源码中的表现：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDIyNTYxMw_size_16_color_FFFFFF_t_70_pic_center 3]

在上图的程序中binCount表示了链表的长度，我们可以看到当bitcount>=7的时候会执行treeifyBin()这个方法，既然是7为什么我们说大于8呢，这是因为bitCount等于7的时候我们其实已经循环了8次因为数组从0开始的，并且我们的p.next = newNode(hash, key, value, null);这段代码先执行也就是说先挂了一个node上去然后去判断的，所以此时除了根节点以外的长度是8而我们加上根节点，长度就变为了9，所以当大于8才会转为执行treeifyBin()这个方法，数组长度大于64又是从哪里体现呢，这个就在treeifyBin()方法中了，如图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDIyNTYxMw_size_16_color_FFFFFF_t_70_pic_center 4]

此时我们可以看出当数组的长度小于64的时候会执行resize()操作进行二倍扩容。

**为什么转为红黑树的链表长度要大于8？**

因为这是根据一个理论基础叫泊松分布，泊松分布用于描述单位时间（或空间）内随机事件发生的次数。我们可以看到jdk源码中有这么一段注释

>     Because TreeNodes are about twice the size of regular nodes, we
>     use them only when bins contain enough nodes to warrant use
>     (see TREEIFY_THRESHOLD). And when they become too small (due to
>     removal or resizing) they are converted back to plain bins.  In
>     usages with well-distributed user hashCodes, tree bins are
>     rarely used.  Ideally, under random hashCodes, the frequency of
>     nodes in bins follows a Poisson distribution
>     (http://en.wikipedia.org/wiki/Poisson_distribution) with a
>     parameter of about 0.5 on average for the default resizing
>     threshold of 0.75, although with a large variance because of
>     resizing granularity. Ignoring variance, the expected
>     occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
>     factorial(k)). The first values are:
>     0:    0.60653066
>     1:    0.30326533
>     2:    0.07581633
>     3:    0.01263606
>     4:    0.00157952
>     5:    0.00015795
>     6:    0.00001316
>     7:    0.00000094
>     8:    0.00000006
>     more: less than 1 in ten million

通过上面的讲述我们发现其实链表在加载因子位0.75的情况发生树化的概率仅为0.00000006这个概率是极为低下的，也就是说在大多数的情况下我们的链表都不会转为红黑树。

通常如果 hash 算法正常的话，那么链表的长度也不会很长，那么红黑树也不会带来明显的查询时间上的优势，反而会增加空间负担。所以通常情况下，并没有必要转为红黑树，所以就选择了概率非常小，小于千万分之一概率，也就是长度为 8 的概率，把长度 8 作为转化的默认阈值。

所以如果平时开发中发现 HashMap 或是 ConcurrentHashMap 内部出现了红黑树的结构，这个时候往往就说明我们的哈希算法出了问题，需要留意是不是我们实现了效果不好的 hashCode 方法，并对此进行改进，以便减少冲突。

**为什么要采用链表转为红黑树的方式进行存储？**

为了提高查询的性能，正常情况下如果我们要查询的数据在链表的最后边那么我们需要从前向后的依次进行遍历，直到找到对应元素，这样的话我们的时间复杂度便是o(n),但是我们如果采用了红黑树这种结果的话，他是一种近似平衡二叉树，也就是左节点要比根节点小，右子节点比根节点大，所以此时的查找的时间复杂度位O(logn)。

**分析hashmap的put操作流程**

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { 
    
        Node<K,V>[] tab;
        Node<K,V> p;
        int n, i;
    
        //第一次put的时候table为null
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //这个if分支代表当前的这个索引位置的元素为null 其实可以直接放入。
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //如果不为null则需要使用头插法放在链表中
        else { 
            Node<K,V> e; K k;
            //第一个分支意味着新增的key原先就存在，所以直接替换
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //这个分支意味着此时已经是一个红黑树的节点 也就是说链表长度已经大于了8
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //最后分支意味着普通情况的放入
            else { 
                for (int binCount = 0; ; ++binCount) { 
                    //如果当前的索引位置的节点的下一个节点为null证明可以直接放入到下一个节点
                    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) { 
                // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //这里就是判断是否需要扩容 看的是size是否大于扩容的容量
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

我们通过看源码不难看出put操作首先判断数组是不是null如果是null那么就进行初始化，初始化结束其实就分了四种情况，第一种就是需要放置的索引位置为null可以直接放置数据，第二种情况就是新增的key原先就存在需要直接替换，第三种情况就是他已经树化是一个红黑树，第四种情况就是正常的put操作，进行头插尾插法插入。

> 注意：jdk1.7的时候是头插法，jdk1.8以后是尾插法插入。

第一种直接放入元素即可，第二种情况就是判断hash值相同且key值相等，那么就是需要直接替换了，第四种情况就是在我们put的时候我们需要关注是否需要树化，即转为红黑树，我们在上边已经分析过转为红黑树的时机了，在遍历链表的时候同时也判断了是否需要替换相同的key。等到插入完成以后我们来判断是否达到了扩容的标准，即size是否大于threshold这个seize是个全局变量是实际放入到map中的数据量。

**hashmap的扩容（resize）解析**

当达到扩容阈值的时候会进行扩容操作，也就是执行resize()方法，代码如下：

final Node<K,V>[] resize() { 
    
        Node<K,V>[] oldTab = table;
        //旧的数组的长度 第一次put为0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //阈值
        int oldThr = threshold;
        //newThr代表了新的扩容阈值
        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)
                //oldThr*2 这就是真正扩容的大小每次扩容两倍
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0)
            //如果第一次执行会走入这个方法
            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进行初始化
        threshold = newThr;
        @SuppressWarnings({ "rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //才开始对数组进行初始化
        table = newTab;
        //这里这个分支意味着不是第一次执行put 因为当是第一次执行put的时候此时oldTab为null
        if (oldTab != null) { 
            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;
                            //索引位置没有变
                            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;
                        }
                    }
                }
            }
        }
        return newTab;
    }

扩容的时候一开始要计算新的map容量以及新的扩容阈值，在计算两者的时候分了两种情况，一种就是数组还没有进行初始化，第二种就是原先已经有数据了，如果没有进行初始化就让新的数组的容量等于扩容阈值， newCap = oldThr为什么会是这样呢，因为这里有个小细节那就是hashmap没有容量这个属性，一开始初始化之前是把容量大小计算以后赋值给了阈值这个字段，初始化第一次以后阈值字段存储的才是真正的阈值即执行了 newThr = (newCap < MAXIMUM\_CAPACITY && ft < (float)MAXIMUM\_CAPACITY ? (int)ft : Integer.MAX\_VALUE)。如果进行了初始化那就很明确了就是将原先的容量左移一位同时将阈值字段左移一位。采用位移的方式进行计算是因为乘法运算最终还是会转为位移运算。

第一步计算扩容后的容量以及阈值以后开始进行数据的迁移工作，即将老数组中的数据迁移到新数组中去。在迁移过程中又分为了四种情况，第一种情况就是当前的索引位置的数据为null这种情况我们可以就不做处理，第二种情况就是当前索引位置只有一个数据，没有形成链表，此时我们直接将这个数据迁移到新的数组的位置就可以了。第三种情况就是迁移的数据已经树化形成了红黑树。第四种情况就是普通没有树化的情况。

第四种情况是如何扩容的，如果是普通的链表没有树化的情况下是将链表分为了两部分（高位链、低位链），这个关于高位链和低位链我们来分析一下，假如我们一开始的数组大小为16后来扩容成32，并且我们又两个key（key1，key2）如图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDIyNTYxMw_size_16_color_FFFFFF_t_70_pic_center 5]

我们发现当我们在利用位运算取模进行索引值计算的时候如果是16我们会与15（1111）进行与运算这样另外的28位的高位无论是什么值都会是0，也就是索引只去取决于低四位。如果是32那么我们会与31（1 1111）进行与运算，此时的高27位无论是什么值都不有影响，我们发现从16到32其实就是多了一位的取决因素，多的这一位恰好就是十进制的16，所以我们不难想到我们将hash值与原有的容量进行与运算即key.hash&10000如果结果为0则意味着key.hash的第五位上是0不会因为扩容被干扰到所以就会放在低位链里边，但是如果不是0那么意味着会被扩容干扰到索引位置，需要放入到高位链中。通过这样区分了高位链和低位链以后我们将低位链放在新数组的原先位置，高位链放在新数组的原索引加上老数组的容量的位置，以此来摒弃了jdk7的倒置的扩容方式，有效的防止了环链的形成。

第三种情况如果是红黑树的情况下是如何扩容的，我们看下代码:

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { 
        TreeNode<K,V> b = this;
        // Relink into lo and hi lists, preserving order
        TreeNode<K,V> loHead = null, loTail = null;
        TreeNode<K,V> hiHead = null, hiTail = null;
        int lc = 0, hc = 0;
        for (TreeNode<K,V> e = b, next; e != null; e = next) { 
            next = (TreeNode<K,V>)e.next;
            e.next = null;
            if ((e.hash & bit) == 0) { 
                if ((e.prev = loTail) == null)
                    loHead = e;
                else
                    loTail.next = e;
                loTail = e;
                ++lc;
            }
            else { 
                if ((e.prev = hiTail) == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
                ++hc;
            }
        }
    
        if (loHead != null) { 
            if (lc <= UNTREEIFY_THRESHOLD)
                tab[index] = loHead.untreeify(map);
            else { 
                tab[index] = loHead;
                if (hiHead != null) // (else is already treeified)
                    loHead.treeify(tab);
            }
        }
        if (hiHead != null) { 
            if (hc <= UNTREEIFY_THRESHOLD)
                tab[index + bit] = hiHead.untreeify(map);
            else { 
                tab[index + bit] = hiHead;
                if (loHead != null)
                    hiHead.treeify(tab);
            }
        }
    }

我们可以看出其实在已经树化的链表中其实还是有一个链表存在的，这个链表是为了由树退化成链做出的重要操作，所以我们需要维护这个链表，这个链表的维护方式和上边提到的是一样的都是分为高位链和低位链然后进行迁移，迁移完成以后判断对应链表的长度，如果长度小于等于了6就退化成链表，否则继续重新树化链表形成红黑树。

**产生的并发问题分析：**

因为hashmap线程不安全所以会产生一系列的并发问题，它主要会产生以下的几个问题：

1.  get的时候死锁（形成了环链导致的 jdk8有效的避免了这个问题）。
2.  数据丢失问题：如果多个线程同时操作一个槽位那么就会出现数据覆盖丢失的问题。
3.  put非null的数据get为null：具体看jdk7中的transfer方法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDIyNTYxMw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/a4061fffcf814ff6bd529c6c523e9352.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDIyNTYxMw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/58318fa317974547bcae46a0e875ad50.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDIyNTYxMw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/ee2aa40ccac04b83bb854d288577650c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDIyNTYxMw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/01b39ec80b4941cf93ed8f08044bb9c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDIyNTYxMw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/093781a820b24d98953ed24d2cd5d829.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDIyNTYxMw_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/2626ae96001c412786143895cda9cfb5.png