JDK1.8HashMap源码学习

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

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

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

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

# put #

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

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

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

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

看了一眼这行代码可以看出来，这个确实应该是计算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方法。

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)
                n = (tab = resize()).length;
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                ·········
            }
            ·········
            return null;
        }

这里出现了一个新的对象，**Node<K, V>**

static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    
            ······
        }

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

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

那么链表有了，数组呢

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xqeTk1MDkxNA_size_16_color_FFFFFF_t_70 1][]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

/**
         * The default initial capacity - MUST be a power of two.
         */
        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

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

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

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

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

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;
            }
        }

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

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

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

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

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

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

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

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

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

直至循环结束。

当循环结束了之后：

if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }

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

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

++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;

modCount 是啥？

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

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

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

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

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

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

--------------------

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

# 初始化以及扩容 #

首先看这段代码：

Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) { // 判断是否原table值大于0
                if (oldCap >= MAXIMUM_CAPACITY) { // 判断是否大于等于最大容量
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
                    // 如果未到达最大容量，则容量 * 2 并判断未到达最大容量，同时原table大小大于默认容量
                    newThr = oldThr << 1; // double threshold 容量 * 2
            } 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);
            }

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

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

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

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            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
                            ·········
                        }
                    }
                }
            }

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

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

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

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

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

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

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

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;
    	}

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

**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，代表这个值较大，会有新的下标，且下标值刚好为原数组长度加上原本下标。

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

>     if (loTail != null) {
>         loTail.next = null;
>         newTab[j] = loHead;
>     }
>     if (hiTail != null) {
>         hiTail.next = null;
>         newTab[j + oldCap] = hiHead;
>     }

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xqeTk1MDkxNA_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/66bd803a3e4c4141b15117276261607a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xqeTk1MDkxNA_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ee378a7aa2fa42cfbb4f5446a976108e.png
[20190919151754511.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/6d8436d33f184a8f837d873992857683.png