JDK1.8HashMap源码学习

我不是女神ヾ 2024-04-19 14:39 144阅读 0赞

此篇文章我们来学习一下HashMap的源码，这也是面试经常能问到的知识点，而之所以为什么面试会问到它，就是因为他的设计思想，是非常值得我们学习的，也是非常经典的。同时不同的JDK版本之间，HashMap源码也是不同的，此篇文章我们只是1.8的HashMap源码学习。

实现声明，看此篇文章之前，你需要大概对HashCode有一个基本的概念，例如是一个数据加链表的结构，是通过hashCode判断数组存放位置，出现hash冲突就会放入链表中等等；但是之前并没有自己去看过源码，所以呢，我也并不是直接从讲解理论，因为我也是边看源码边学习写的帖子，具体流程也就是个真正去看源码的流程，而不是生硬的告诉原理。

说完了，那就让我们开始看源码吧。

put

首先让我们来看看我们最常用的方法，put，当我们点击put方法进入之后，我们会看到这样一行代码

  1. public V put(K key, V value) {
  2.         return putVal(hash(key), key, value, false, true);
  3.     }

在这里，我们并没有做什么操作，但是对于这一个方法，hash(key)，让我非常奇怪，难道是获取hashcode值的？于是我又点了进入

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

看了一眼这行代码可以看出来，这个确实应该是计算hash值的代码，而且还能证明了一件事，就是HashMap确实是可以支持插入key值为null的。然后奇怪的东东又出现了

(h = key.hashCode()) ^ (h >>> 16)

这是在干嘛？？？

获取了hashCode值之后，为什么还要把获得的hashcode值与比他低十六位的值进行异或，得出一个新值呢？

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xqeTk1MDkxNA_size_16_color_FFFFFF_t_70

现在我们可能无法理解为什么这么做，所以留下这个疑问，接下来看下面的代码，点击进入putVal方法。

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  2.                    boolean evict) {
  3.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  4.         if ((tab = table) == null || (n = tab.length) == 0)
  5.             n = (tab = resize()).length;
  6.         if ((p = tab[i = (n - 1) & hash]) == null)
  7.             tab[i] = newNode(hash, key, value, null);
  8.         else {
  9.             ·········
  10.         }
  11.         ·········
  12.         return null;
  13.     }

这里出现了一个新的对象，Node

  1. static class Node<K,V> implements Map.Entry<K,V> {
  2.         final int hash;
  3.         final K key;
  4.         V value;
  5.         Node<K,V> next;
  7.         ······
  8.     }

省略一些暂时用不到的代码，我们发现这个内部类的里面，有着几个功能显而易见的属性

hash：hash值；K：key值；v：value值；next：下一个节点，也就相当于是下一个节点，同时证明了链表的存在

那么链表有了，数组呢

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xqeTk1MDkxNA_size_16_color_FFFFFF_t_70 1

经过搜索，我们确实也发现了node节点的数组。了解完了node之后，我们在回头看putVal方法

  1. if ((tab = table) == null || (n = tab.length) == 0)
  2.             n = (tab = resize()).length;

首先将全局Node数组赋值给局部变量tab，然后判断非空，再将获取数组长度=，同时判断是否长度为0，总的来说相当于Node数组如果为空，也就相当于第一次put值的时候（我们初始化HashMap的时候，是没有初始化数组的），我们就执行resize()方法，再获取数组长度。

如果机智的朋友，可能就会猜出来了，这个resize()方法，相当于初始化一个Node数组，所以我们在看看这个方法到底是怎么初始化的呢？

首先我们点进这个方法的时候，就可以先看这个注释：

  1. /**
  2.  * Initializes or doubles table size.  If null, allocates in
  3.  * accord with initial capacity target held in field threshold.
  4.  * Otherwise, because we are using power-of-two expansion, the
  5.  * elements from each bin must either stay at same index, or move
  6.  * with a power of two offset in the new table.
  7.  *
  8.  * @return the table
  9.  */

当然，我的英语非常菜，光看英语是不行的，只好求助翻译了。大家可以自行翻译。我这里只总结一下

他的这段注释的意思就是，这个方法的功能是初始化或者双倍Node数组的大小，如果table为空，我们就是用默认的初识大小，如果不是，我们则以2的幂展开这个数组。

好了，那我们可以确定了，这个绝对是有初始化数组的作用了，代码我们先不继续看，先回头把putVal方法看完的。

如果是第一次赋值，我们执行完resize方法就需要执行下面的方法了：

  1. if ((p = tab[i = (n - 1) & hash]) == null)
  2.             tab[i] = newNode(hash, key, value, null);
  3.     else {
  4.         ······
  5.     }

这里干了什么？？？（敲黑板）

(p = tab[i = (n - 1) & hash]) == null

判断是否为空？？？那个为空？ tab[i = (n - 1) & hash] 哦，是判断node数组的那个下面是否为空啊。

那么下面，为什么是这个？？？ (n - 1) & hash

首先，这个n，是数组的长度，那么初始化数组的长度是多少？

  1. /**
  2.      * The default initial capacity - MUST be a power of two.
  3.      */
  4.     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

先剧透一下，数组默认初识长度是这个 DEFAULT_INITIAL_CAPACITY = 1 << 4 也就相当于16。

好了，数组的初识大小是16，也就相当于n等于16了。那么 (n-1) & hash 这是在干嘛？

我们这时候需要思考一下，如果有这么一个十六个长度数组table在这里，我们想向里面插入node节点，我们是不是需要考虑，我们应该想那个位置插入呢，恰好，我们已经有了一个int类型的hash值了，是不是，我们既可以直接，用这个hash除以数组长度，然后取余呢，这样我们就知道了这个节点我们应该存入的下标了呢。

再看看 (n-1) & hash 这个操作

20190919151754511.png

& 操作，是一个只有两方全部为1，结果才会为1的运算，而放在我们这里，是不是刚刚好，由于我们的node数组长度默认16，即使扩容的情况下，也是按照2的幂来增加的，所以他们的二进制都是1开头剩下的都是0，减一之后，就是一个0带着剩下的都是1。这种情况，刚刚好，不就是hash除以数组长度取余的操作吗。同时由于是二进制取余，效率也会提高很多很多。

同时回想一下刚才的hash()方法中高十六位与低十六位异或的操作，对比一下这里取余的操作，是不是就是为了这里做准备，其实，那就是防止获取hashcode值之后取余的话，极容易出现hash碰撞，同时由于是通过 & 的方式来取余，只有低位数据才会对取余结果造成影响，而高位结果并没有太大影响，所以使用高十六位与低十六位进行异或，得到的数据，才能使得他们一起在取余的时候，都会尽可能的造成影响，才能减少hash碰撞的概率。

获取好了标之后，我们再来判断是否该下标已经有值，如果无值，则直接保存数据，如果有值，则进入else

  1. Node<K,V> e; K k;
  2.     if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
  3.         e = p;
  4.     else if (p instanceof TreeNode)
  5.         e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  6.     else {
  7.         ······
  8.     }

第一个判断很明显是判断是否key值相同，如果相同，则将临时节点e赋值

第二个判断啥意思？？？ 如果节点类型是 TreeNode ？ TreeNode 是啥？

是不是知道啥意思，那就先不管，咱们先去看最后一个else

  1. else {
  2.         for (int binCount = 0; ; ++binCount) {
  3.             if ((e = p.next) == null) {
  4.                 p.next = newNode(hash, key, value, null);
  5.                 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  6.                     treeifyBin(tab, hash);
  7.                 break;
  8.              }
  9.              if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
  10.                 break;
  11.              p = e;
  12.         }
  13.     }

刚开始就来了一个无限循环，然后给临时节点e赋值的同时判断链表的下一个是否为空，如果判断了下一位为空，则将这个节点作为他的下一个节点。

然后判断了我们循环的次数是否大于一个默认值？？？一旦大于，则执行 treeifyBin(tab, hash); 方法。

哦，原来是，1.8下的HashMap加入了红黑树，假如链表太长了，超过了默认值 

  1. /**
  2.      * The bin count threshold for using a tree rather than list for a
  3.      * bin.  Bins are converted to trees when adding an element to a
  4.      * bin with at least this many nodes. The value must be greater
  5.      * than 2 and should be at least 8 to mesh with assumptions in
  6.      * tree removal about conversion back to plain bins upon
  7.      * shrinkage.
  8.      */
  9.     static final int TREEIFY_THRESHOLD = 8; // 链表最大程度默认值
  11.     /**
  12.      * The bin count threshold for untreeifying a (split) bin during a
  13.      * resize operation. Should be less than TREEIFY_THRESHOLD, and at
  14.      * most 6 to mesh with shrinkage detection under removal.
  15.      */
  16.     static final int UNTREEIFY_THRESHOLD = 6; // treeNode最小数量

也就是 8 我们就把它转换为treeNode，而一旦treeNode小于默认值 6 我们就又会把他还为链表结果，而这个 treeifyBin(tab, hash); 就是执行将链表转换为treeNode的方法。

再回头看我们的putVal()，唉，回头的次数太对，感觉脖子都要扭断了。

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

这个if表示如果可以值在链表上面的这个节点上面已经相同了，我们直接结束循环。

当两个if条件都不满足的时候，我们就把p设置为当前节点的next节点，进行下一次循环判断。

直至循环结束。

当循环结束了之后：

  1. if (e != null) { // existing mapping for key
  2.                 V oldValue = e.value;
  3.                 if (!onlyIfAbsent || oldValue == null)
  4.                     e.value = value;
  5.                 afterNodeAccess(e);
  6.                 return oldValue;
  7.             }

这种情况会发生在key值已经存在的情况，那么我们的处理，理所应当的就是更换value值了。

而当这个值是新值，我们已经保存好了之后，我们又会执行

  1. ++modCount;
  2.         if (++size > threshold)
  3.             resize();
  4.         afterNodeInsertion(evict);
  5.         return null;

modCount 是啥？

  1. /**
  2.  * The number of times this HashMap has been structurally modified
  3.  * Structural modifications are those that change the number of mappings in
  4.  * the HashMap or otherwise modify its internal structure (e.g.,
  5.  * rehash).  This field is used to make iterators on Collection-views of
  6.  * the HashMap fail-fast.  (See ConcurrentModificationException).
  7.  */
  8. transient int modCount;

看了这个全局变量的注释，我们大概能理解：这个数字代表着修改次数，然后 用于在集合视图上生成迭代器 为啥叫删除线，因为我也不懂 0.0 尴尬，但是应该无伤大雅，继续看下面。

  1. /**
  2.      * The number of key-value mappings contained in this map.
  3.      */
  4.     transient int size;

哦 这个size就是HashMap中的键值映射的数目，那 threshold 呢？？？

  1. /**
  2.      * The next size value at which to resize (capacity * load factor).
  3.      *
  4.      * @serial
  5.      */
  6.     // (The javadoc description is true upon serialization.
  7.     // Additionally, if the table array has not been allocated, this
  8.     // field holds the initial array capacity, or zero signifying
  9.     // DEFAULT_INITIAL_CAPACITY.)
  10.     int threshold;

哦 大概理解了，如果这个长度多大，就将会扩容，而threshold这个值，就相当于临界值的存在。

到这里，我们就大概将基础的put给大致分析完了，但是 这其中的一个非常重要的方法 resize() 我们还没有看，接下来，我们再了解一下这个方法是怎么实现初始化以及扩容的。

初始化以及扩容

首先看这段代码：

  1. Node<K,V>[] oldTab = table;
  2.         int oldCap = (oldTab == null) ? 0 : oldTab.length;
  3.         int oldThr = threshold;
  4.         int newCap, newThr = 0;
  5.         if (oldCap > 0) { // 判断是否原table值大于0
  6.             if (oldCap >= MAXIMUM_CAPACITY) { // 判断是否大于等于最大容量
  7.                 threshold = Integer.MAX_VALUE;
  8.                 return oldTab;
  9.             } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
  10.                 // 如果未到达最大容量，则容量 * 2 并判断未到达最大容量，同时原table大小大于默认容量
  11.                 newThr = oldThr << 1; // double threshold 容量 * 2
  12.         } else if (oldThr > 0) // initial capacity was placed in threshold  
  13.             newCap = oldThr;
  14.         else { // zero initial threshold signifies using defaults 初始化
  15.             newCap = DEFAULT_INITIAL_CAPACITY;
  16.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  17.         }
  18.         if (newThr == 0) { // 什么时候会出现这种情况？？？ 没想出来
  19.             float ft = (float)newCap * loadFactor;
  20.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
  21.         }

我已经吧每个判断的逻辑都已经添加了注释了，我们只需要注意这两点

1、当时扩容的时候，我们会把新的容量直接 * 2

2、当是初始化的时候，我们的默认容量就是 16 这个默认值。同时设置容量阈值，是0.75*16，知道了这两点之后，我们继续向下看代码。

  1. Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  2.         table = newTab;
  3.         if (oldTab != null) {
  4.             for (int j = 0; j < oldCap; ++j) {
  5.                 Node<K,V> e;
  6.                 if ((e = oldTab[j]) != null) {
  7.                     oldTab[j] = null;
  8.                     if (e.next == null)
  9.                         newTab[e.hash & (newCap - 1)] = e;
  10.                     else if (e instanceof TreeNode)
  11.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  12.                     else { // preserve order
  13.                         ·········
  14.                     }
  15.                 }
  16.             }
  17.         }

我们获得新的容量大小之后，我们就用这个新的大小创建了一个新的数组，同时将其赋值给全局table

然后我们应该能猜出来接下来应该干什么了，那就是将原来的数组里面的值，重新放进我们新的数组里面，但是一个新的问题出现了，那就是下边该如何分配呢？？？我们之前的下标使用原来的数组大小hash值取余分配到对应的下标里面的，那么，新的也是必须符合这个规则的。

通过源码，我们发现，在我们的循环里面，第一个if判断

  1. if (e.next == null)
  2.     newTab[e.hash & (newCap - 1)] = e;

这不就是我们上面说的那个情况吗，但是由于链表中的hash值不同，除以一个新的数组大小获取的

第二个判断是如果是书节点我们会重新执行另一种分配方式

那么最后的else是什么情况呢，应该是就是数组下面还有链表的

  1. Node<K,V> loHead = null, loTail = null;
  2.     Node<K,V> hiHead = null, hiTail = null;
  3.     Node<K,V> next;
  4.     do {
  5.         next = e.next;
  6.         if ((e.hash & oldCap) == 0) {
  7.             if (loTail == null)
  8.                 loHead = e;
  9.             else
  10.                 loTail.next = e;
  11.             loTail = e;
  12.         } else {
  13.             if (hiTail == null)
  14.                 hiHead = e;
  15.             else
  16.                 hiTail.next = e;
  17.             hiTail = e;
  18.         }
  19.     } while ((e = next) != null);
  20.     if (loTail != null) {
  21.         loTail.next = null;
  22.         newTab[j] = loHead;
  23.     }
  24.     if (hiTail != null) {
  25.         hiTail.next = null;
  26.         newTab[j + oldCap] = hiHead;
  27.     }

这里在干嘛呢？想了想，就知道了，因为我们虽然说这个链表中是计算出来的相同的下标，但是当我们的数组大小发生改变的时候，我们的下标，可能就不同的，所以，我们要重新开始计算下标，那么，我们是怎么获得我们的新下标呢？

if ((e.hash & oldCap) == 0)

这个判断 我们是不是非常熟悉，和我们之前获取下标的方法很相似啊，只是，之前的我们是使用的长度减一与hash值与计算得到的下标，这个却是并没有减一。那么什么时候，e.hash & oldCap 才能等于0呢？

由于数组长度都是2的指数，所以，换为2进制，他不就是从1开始后面接的全是0，

例如 我们第一次开始扩容 原本长度是16 也就是10000

所以 当进行&运算的时候，只有hash的倒数第5位 是0 我们才可能得出0

但是呢，由于我们之前是通过hash与长度-1进行&运算，所以，倒数第五位的长度，并不能影响到我们获得下标。那么这个倒数第五位，到底有啥用？

举个例子 10011 与 00011 这两个值，第一次获取下标都是一直的，都是 3 但是其实这两个值的大小分别为 19和3。这两个值对于新的长度32来说，他们的下标，刚刚好又变成了 19 和 3 。所以倒数第五位值一旦为0，就代表着这个值是个小值切下标不变，不等于0，代表这个值较大，会有新的下标，且下标值刚好为原数组长度加上原本下标。

知道了原理之后，再看看代码，是不是就一目了然了呢。

  1. if (loTail != null) {
  2.     loTail.next = null;
  3.     newTab[j] = loHead;
  4. }
  5. if (hiTail != null) {
  6.     hiTail.next = null;
  7.     newTab[j + oldCap] = hiHead;
  8. }

这个 不就是刚刚好是我们原理的实现。

发表评论

表情：
评论列表 （有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

    相关 JDK1.8HashMap源码学习

    篇文章我们来学习一下HashMap的源码，这也是面试经常能问到的知识点，而之所以为什么面试会问到它，就是因为他的设计思想，是非常值得我们学习的，也是非常经典的。同时不同的...

    我不是女神ヾ我不是女神ヾ/ 0 赞/ 145 阅读

    相关 JDK8HashMap源码

    > 进入这篇文章之前，我想清楚的说一说怎么去理解`HashMap`源码。它先是使用的`hash`算法，那么哈希算法需要注意的那就是怎么`hash`，怎么减少冲突，怎么避免冲突。

    爱被打了一巴掌爱被打了一巴掌/ 0 赞/ 90 阅读

    相关 HashMap JDK8 源码分析

    概述 HashMap是基于哈希表(散列表)，实现Map接口的双列集合，数据结构是“链表散列”，也就是数组+链表 ，key唯一的value可以重复，允许存储null 键nu

    朱雀朱雀/ 0 赞/ 365 阅读