HashMap源码剖析

简介
本文从jdk1.8源码层面介绍HashMap的元素插入和扩容的过程分析，树形化的部分比较复杂，本文此处跳过，同时也介绍了jdk1.8作为并发容器的可能存在的影响；
为了便于读者的阅读友好，已控制好了源码和注释代码的缩进格式避免水平滚动，注释部分已尽可能详尽，如果不懂的地方可以着重看下注释，熟悉的部分可直接跳过，全文阅读大概15分钟。

1. 基础属性介绍:

	// 默认容量，常量值16
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 	// 最大容量，常量值2^30次幂
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认负载因子，常量值0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 树化 阈值，常量值8
    static final int TREEIFY_THRESHOLD = 8;
    // 去树化 阈值，常量值6 即小于6时将去除树形态
    static final int UNTREEIFY_THRESHOLD = 6;
    //  最小树化容量 常量值64
    static final int MIN_TREEIFY_CAPACITY = 64;

2. 静态内部类介绍：
   下面只介绍本文涉及到的静态内部类，Node implements Map.Entry
   基础属性介绍：

 	// 保存节点的hash值
   	final int hash;
   	// 保存节点的key值
    final K key;
    // 保存节点的value值
    V value;
    // 保存下一个节点的引用
    Node<K,V> next;
    /*构造函数：
     每一个node节点都将保存当前节点的hash值，
     key,value值，以及下一个节点的引用next*/
     Node(int hash, K key, V value, Node<K,V> next) {
     this.hash = hash;
     this.key = key;
     this.value = value;
     this.next = next;
     }
     // 获取当前节点的key值
     public final K getKey() { return key; }
     // 获取当前节点的value值
     public final V getValue() { return value; }
     // 返回当前节点key,value信息
     public final String toString() { return key + "=" + value; }
     // 节点的key和value都参与hashcode计算，返回
     public final int hashCode() {
           return Objects.hashCode(key) ^ Objects.hashCode(value);
     }
     // 设置当前节点的value值
     public final V setValue(V newValue) {
           V oldValue = value;
           value = newValue;
           return oldValue;
     }
     // 判断节点是否相等
     public final boolean equals(Object o) {
            if (o == this)
                return true;
    // 如果属于entry结构，将同时判断key和value值与对照节点的一致性
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
     }

3. 在介绍前置部分之后，开始逐个看具体的方法实现过程。
   首先是hashmap的插入，然后再跟进resize()方法

	// 直接调用putVal插入相应的key,value
    public V put(K key, V value) {
          return putVal(hash(key), key, value, false, true);
    }
    	/* 放入值方法，onlyIfAbsent的值用来判断是否允许替换，
    		如果值存在且不允许替换，将不会覆盖原有的value值，
    		第四个参数用于linkedHashMap插入值是预留*/
        final V putVal(int hash, K key, 
        			    V value, 
        			    boolean onlyIfAbsent,
                   		boolean evict) {
     	/* tab数组为此方法内的局部hash表，作为成员属性hash表，
     	也就是table属性的方法内的副本，n用来标示tab数组的长度
     	  */             
        Node<K,V>[] tab; Node<K,V> p; int n, i;
     	/* 这里的table表示hashmap的hash表实例，如果hash表为null
     	或者表长度为0，那么将调用resize()扩容，
     	并且将n的长度置为新的hash表的长度*/
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
     	/* 将i的值置为tab数组长度减1，然后与入参hash作逻辑与运算，
     		计算出该hash值对应的在表中的索引值，
     		将该索引出的node节点的值赋给p，
        	如果为null代表该位置还没有占用，直接创建节点，
        	放在该索引即可 */ 
        if ((p = tab[i = (n - 1) & hash]) == null)
      		/* newNode()方法直接调用Node的构造方法返回node对象，
      		赋值给数组i这个位置 */
            tab[i] = newNode(hash, key, value, null);
        else {
      		/* 如果根据hash计算出来的位置已经有节点了，
      		那么将根据该位置节点形成的形状采取链表插入还是树形插入 */
            Node<K,V> e; K k;
      		/* 如果当前位置i的已经存在的首节点的hash值与入参hash值相等，
      		并且key值相等,那么将原先节点p赋值给e保存 */
            if (p.hash == hash &&
                ((k = p.key) == key || 
                (key != null && key.equals(k))))
                e = p;
       		/* 如果当前位置i的已经存在的首节点属于树节点TreeNode，
       		那么将通过树形插入，这部分比较复杂不在此处进行讨论展开 */   
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(
                this, tab, hash, key, value);
       		/* 如果当前位置i的已经存在的节点不等于首节点的hash值，
       		那么将继续向下遍历节点 */
            else {
       			/* 循环遍历位置i下挂载的所有节点，
       				每一轮循环binCount值加一，
       				记录遍历次数也即挂载的链表长度 */
                for (int binCount = 0; ; ++binCount) {
       				/* 首节点p的下一个节点赋值给e,如果为空，
       				则说明首节点p为最后一个节点，
       				也就是说p没有后继节点了，
       				是该位置i挂载的唯一节点 
       				此处，可看出jdk1.8采用尾部插入
       				直到遍历到当前节点后继引用为空时才执行插入*/
                    if ((e = p.next) == null) {
       					/* 根据入参的key,value构造一个新节点，
       					并将首节点p的后继节点指向新的创建的节点*/
                        p.next = newNode(hash, key,
                         value, null);
                        /* 如果当前的binCount的值大于了树形化的阈值，
                        binCount值为7时，代表循环进行了8次，长度为8，
                        此时有7>=7成立，此时长度达到了阈值 */
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            /* 那么将进行树化，树形化流程，下一篇详解，
                            此处跳过 */
                            treeifyBin(tab, hash);
                        break;
                    }
                    /* 此时e节点的值保存着首节点p的后继节点引用，
                    如果下一个节点的hash值与入参hash节点相同，
                    并且当前节点的key值相等，
                    那么直接跳出循环将p节点指向
                    当前节点e也就是尾节点了，此时p.next==null,
                    进行下一轮，此时满足if条件，
                    p.next为null,创建p的后继指向新创建节点*/
                    if (e.hash == hash &&
                        ((k = e.key) == key || 
                        (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 此处e保存在相同key的node节点，
            if (e != null) { // existing mapping for key
            // 当前节点的value将成为旧值
                V oldValue = e.value;
                /* onlyIfAbsent为false,此时允许更改，
                如果为true或者旧值为null的时候可以替换，
                也就是如果onlyIfAbsent为true,并且旧值不为null
                将不允许更改值*/
                if (!onlyIfAbsent || oldValue == null)
                // 重新将该key对应的value更改入参的value值
                    e.value = value;
                /* 空实现，用于linkedhashmap执行插入的后置处理，
                此处不对linkedhashmap的插入逻辑分析*/
                afterNodeAccess(e);
                /* 返回该节点的旧值，即hashmap插入值的时候，
                如果是覆盖，那么将返回被覆盖的value值 */
                return oldValue;
            }
        }
        // 将hashmap的更改次数加1
        ++modCount;
        // 将全局维护的容量大小加1，如果大于数组容量大小，
        将进行resize()扩容
        if (++size > threshold)
            resize();
        // linkedhashmap的优化，此处忽略暂不分析    
        afterNodeInsertion(evict);
        // 插入的新节点，将返回null
        return null;
    }

下面继续分析由resize()扩容分析的部分：

// resize() 扩容分析
    final Node<K,V>[] resize() {
        // 将table数组维护一份在方法内部，oldtable数组引用
        Node<K,V>[] oldTab = table;
        /* 如下oldTable此处称为旧数组，
        如果旧数组为null那么oldCap旧容量的值定为0，如果不为null，
        旧容量为旧数组的实际数组长度*/
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // oldThr 旧阈值， 将当前hashmap里维护的阈值赋给oldThr旧阈值
        int oldThr = threshold;
        // 定义新的容量和新阈值
        int newCap, newThr = 0;
        // 如果旧容量大于0
        if (oldCap > 0) {
            // 如果旧容量大于最大容量 1<<30
            if (oldCap >= MAXIMUM_CAPACITY) {
                // 那么将阈值设为最大整数值
                threshold = Integer.MAX_VALUE;
                /* 无法继续扩容，只是将阈值更改为最大整数2^31 -1 ，
                	并返回旧的数组oldTable */
                return oldTab;
            }
            /* 如果旧容量不大于最大容量，那么将就容量<<1左移一位即扩大一倍，
            	赋给新容量，新容量小于最大容量，
            	并且旧容量大于等于默认初始容量 */
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                     // 新阈值 同时也扩大一倍
                newThr = oldThr << 1; // double threshold
        }
        // 如果旧阈值大于0,此时没有走if表示此时旧容量为0
        else if (oldThr > 0) 
        // 那么将新容量的值 置为 旧的阈值
            newCap = oldThr;
        else {
        /* 如果旧容量和旧阈值都为0，那么将新容量置为默认初始容量，
        将旧阈值置为默认负载因子乘以默认初始容量*/
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * 
            		DEFAULT_INITIAL_CAPACITY);
        }
        // 若新阈值为0
        if (newThr == 0) {
            // 计算出新容量和负载因子的乘积
            float ft = (float)newCap * loadFactor;
            /* 如果新容量小于最大容量并且新容量和负载因子的乘积小于最大容量，
            	那么新阈值为此处的ft的值，否则，新阈值置为最大整数值*/
            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属性的指向改为新的数组
        table = newTab;
        // 下面开始旧数组的内容转移到新数组的转移处理
        // 如果旧数组不为null
        if (oldTab != null) {
            // 循环遍历旧数组，遍历次数取决旧数组容量，即数组长度
            for (int j = 0; j < oldCap; ++j) {
                // 声明临时变量e
                Node<K,V> e;
                // 将j位置的首节点赋值给e，如果不为null
                /* ***多线程访问下*** 
                假如线程1在此处因没争抢到时间片停留了，
                下一次从此处恢复执行，
                因线程2完成了该位置的转移，那么此时线程1认为该位置没有元素，
                因此线程1的执行结果将导致该位置的元素全部丢失，
                此处为java8 解决了死循环之后又以缺陷，不适合并发场景 */
                if ((e = oldTab[j]) != null) {
                    /* 将该位置置为空，该位置的节点信息都保存在了e节点上，
                    及其后继节点上
                    ***多线程访问下*** 
                    	此处在多线程环境下容易发生数据丢失情况，
                    	如果线程2执行到此处将j位置的清空 */
                    oldTab[j] = null;
                    // 如果e的next节点为空，那么该位置只有一个node节点
                    if (e.next == null)
                    /* 那么将该节点的hash值与新的数组长度减1，
                    作逻辑与运算计算出该节点在新的数组里的索引位置，
                    然后将新数组该位置的节点置为当前节点e */
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                    /* 如果当前节点是树形化节点，
                    此处不对树形化的节点转移进行分析*/
                        ((TreeNode<K,V>)e).split(
                        this, newTab, j, oldCap);
                    else { // 保证有序
                    /* 注意：
                    此处用高低位链来分表代表需要迁移和不需要迁移的链，
                    并且通过两个头尾双指针来保证每个元素的转移都是
                    保证转移之前的顺序声明四个节点，
                    分别为loHead低位头节点，loTail头节点尾节点；
                    hiHead高位头节点，hiTail高位尾节点，
                    来处理链表节点将旧数组里的链表分成两个链表来进行迁移，
                    如果rehash之后还是该位置，则放在一个链表里，
                    如果rehash之后位置加16了，放在高位链表里 */
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        // 下一节点指针
                        Node<K,V> next;
                        do {
                            /* 当前节点e的后继节点赋值给next节点存储，
                            持续向后遍历，
                            然后插在新链表尾部以保证原来的基础顺序*/
                            next = e.next;
                            /* 如果当前节点的hash值与旧容量的
                            逻辑与运算结果为0，
                            那么该节点e则为索引位置不变，
                            仍处于低位*/
                            if ((e.hash & oldCap) == 0) {
                                /* 如果尾节点为null,
                                将当前节点的值赋给头节点*/
                                if (loTail == null)
                                    loHead = e;
                                // 否则将当前节点放在尾节点的后继节点 
                                else
                                    loTail.next = e;
                                // 最后将尾继节点指向当前节点e
                                loTail = e;
                            }
                            /* 如果当前节点不是索引为0的位置，
                            则为高位链表，高位链的新位置为
                            原来的位置加上oldCap值*/
                            else {
                                // 如果高位尾节点为null
                                if (hiTail == null)
                                // 将e赋值给高位头节点
                                    hiHead = e;
                                else
                                /* 如果高位尾节点不为null，
                                	将当前节点放置在高位尾节点后面*/
                                    hiTail.next = e;
                                // 将高位尾节点指向当前节点e            
                                hiTail = e;
                            }
                            // 当前节点不为null的时候，遍历继续执行
                        } while ((e = next) != null);
                        // 如果低位尾节点不为null
                        if (loTail != null) {
                            // 将低位尾节点的后继节点指向null
                            loTail.next = null;
                            // 在新数组里j位置的节点指向低位头节点
                            newTab[j] = loHead;
                        }
                        // 再处理高位，如果高位尾节点不为null
                        if (hiTail != null) {
                            // 将高位尾节点指向null
                            hiTail.next = null;
                            /* 由于是高位链，高位链的位置将在
                            位置j的基础上加旧容量，
                            这里举例说明，
                            x,y两个节点的hashcode的值分别为1和17 
                            计算x的位置为：
                            方式一：1%16 = 1 方式二：1 & （16-1） = 1
                            同理，计算y的位置为：
                            17%16=1 在未扩容之前，
                            x,y的两个节点都挂载在table[1]这个位置，
                            一旦扩容成二倍即数组长度为32后
                            rehash x的位置为： 1%32 = 1 ，
                            此时 1&16=0 则x节点应该放在低位链
                            rehash y的位置为： 17%32 = 17，
                            此时17&16=16不为0 
                            则y节点应该放在高位链，
                            正好对应的新数组位置为1(j)+16(oldCap)的和
                            /* 此处为java8的rehash优化，
                            无需反复hash计算新位置，
                            直接采用这种高位链的特殊方式，来计算新位置 */
                            newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
        return newTab;
    }    

做完了源码的注释，下面结合图具体看resize()方法数据转移的代码执行流程：
初始状态：

迁移过程：

结束状态：

根据扩容后的结果，可以看到迁移之后，P1仍旧在P3节点前面，链表顺序没有反转

总结：

jdk1.8对于元素的插入是采用尾部插入的方式，在进行resize()扩容时，
做了如下优化：

• 元素转移采用两条链几高低位两条链来转移，且只转移高位链;
• 重新计算元素的索引位置时采用rehash时，简化计算是通过原位置加上oldCap值即为新位置；
• 元素转移后的顺序保持原有顺序，不会反转(jdk1.7元素迁移后顺序反转)

本文地址：https://blog.csdn.net/weixin_39719504/article/details/107334855