HashMap源码解析JDK1.8版本（二）

源代码及行注释如下：

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        // HashMap采用的是懒加载机制，第一次put，tab肯定为null，所以这个if包含初始化逻辑
        if ((tab = table) == null || (n = tab.length) == 0)
            // resize()方法进行初始化
            n = (tab = resize()).length;
        // (n - 1) & hash 和JDK1.7一样按位与获取到插入的数组索引
        // 因为这个if条件必定会执行，且对局部变量p进行了赋值，p表示插入槽位上原有的Node
        // 如果插入的槽位上没有值，则直接进行插入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            // 如果插入的槽位上已经存在值，则要形成链表或红黑树
            Node e; K k;
            // 如果插入的key和数组槽位上元素Node的key相同
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 这里的赋值将HashMap的数组中原先存在的Node赋值给局部变量e
                // 后续会对插入的key和HashMap已经存在的Node的key相同的这种情况做统一的判断逻辑
                e = p;
            // 如果原先数组槽位上的元素是红黑树的一个节点
            else if (p instanceof TreeNode)
                // 将调用put方法插入的元素添加到红黑树节点中
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 插入的key和原先数组槽位上元素Node的key不同，且数组槽位上的元素Node不是红黑                                
                // 树节点
                // 循环遍历链表中的每个Node节点
                for (int binCount = 0; ; ++binCount) {
                    // 如果遍历到末尾，就直接进行插入
                    if ((e = p.next) == null) {
                        // 新建节点，赋值给最后一个Node的next变量,即插入到链表的尾部
                        p.next = newNode(hash, key, value, null);
                        // 判断链表是否达到了转红黑树的条件
                        // 当我们插入第2个元素时，binCount在这个if判断中的值为0，而        
                        // TREEIFY_THRESHOLD等于8，所以在插入第9个元素时，这个if判断会等于 
                        // true，那么就会调用treeifyBin方法
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // e在这个for循环中，不断的被赋值为下一个节点，这里的if也就是判断链表中每个 
                    // 节点的key是否等于插入的key，如果相等，会跳出循环，e表示HashMap的数组中 
                    // 原先存在的Node
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 这里的赋值是为了遍历
                    p = e;
                }
            }
            // 这里是如果插入的key和HashMap已经存在的Node的key相同时的判断逻辑
            // e表示HashMap中原先存在的Node
            // 主要是将新的value覆盖原先存在的Node的value，然后返回原先存在的Node的value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 数组容量大于临界值就进行扩容（注意是大于）
        if (++size > threshold)
            // 扩容方法
            resize();
        // 节点插入后的处理，由子类去实现
        afterNodeInsertion(evict);
        return null;
    }

final void treeifyBin(Node[] tab, int hash) {
        int n, index; Node e;
        // 数组为空或数组的长度小于64就进行扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            // 转换成红黑树的逻辑
            TreeNode hd = null, tl = null;
            do {
                TreeNode p = replacementTreeNode(e, null);
                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);
        }
    }

  链表长度大于8且数组的长度大于或等于64，链表才会转换成红黑树

  数组长度要大于临界值才会进行扩容

源代码及行注释如下：

    final Node getNode(int hash, Object key) {
        Node[] tab; Node first, e; int n; K k;
        // 判断数组是否为空，查询的槽位上的节点是否为空，如果为空，直接返回null，如果不为空，根据key获取元素
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 判断槽位上第一个节点的key是否与查询的key相等
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 循环遍历槽位上的每个节点，如果是红黑树节点，
            if ((e = first.next) != null) {
                // 如果是红黑树节点，按红黑树节点的取值方法获取查询的元素
                if (first instanceof TreeNode)
                    return ((TreeNode)first).getTreeNode(hash, key);
                // 如果是普通链表，循环遍历，每个节点，返回key相等的元素
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

源代码及行注释如下：

    final Node[] resize() {
        // 原数组
        Node[] oldTab = table;
        // 原数组容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 原数组扩容临界值
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 原数组容量大于0
        if (oldCap > 0) {
            // 判断原数组容量是否大于等于最大容量
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            } // 扩容2倍后小于最大容量且原容量大于16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 新的临界值设置为原临界值的2倍
                newThr = oldThr << 1; // double threshold
        } // 原数组容量等于0且原临界值大于0，这种情况表示HashMap初始化且初始化容量未传或大于0
          // HashMap初始化时，将数组的容量赋值给了threshold
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        // 这里的else看起来是判断创建HashMap时，构造器传的初始化容量为0的情况
        // 但实际感觉不会走到else，因为你构造器传的初始化容量为0，经过tableSizeFor后就变成了1
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // newThr等于0表示HashMap初始化且初始化容量未传或大于0
        // newThr等于0也表示扩容2倍后容量大于等于最大容量或原容量小于16
        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数组
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        // 原数组不为空的情况下，需要进行节点转移
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                // 数组槽位上不为空
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 没有后续节点，直接插入到新数组中
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    // 如果是树节点，需要调用split方法处理
                    else if (e instanceof TreeNode)
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        // 链表循环插入到新数组中
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        do {
                            next = e.next;
                            // 与原数组长度按位与等于0，那么与新数组长度减1按位与的值和与原数                    
                            // 组长度减1按位与的值相等，即插入槽位索引不变
                            if ((e.hash & oldCap) == 0) {
                                // 数组元素的移动JDK1.8采用尾插法
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            } // 插入槽位索引改变，改变后插入的槽位索引等于原索引+原数组长度
                            else {
                                // 数组元素的移动JDK1.8采用尾插法
                                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;
    }

// 对每个槽位的红黑树节点进行处理
final void split(HashMap map, Node[] tab, int index, int bit) {
            // this表示调用split的对象，即槽位上的第一个红黑树节点
            TreeNode b = this;
            // Relink into lo and hi lists, preserving order
            TreeNode loHead = null, loTail = null;
            TreeNode hiHead = null, hiTail = null;
            int lc = 0, hc = 0;
            // 循环遍历红黑树
            for (TreeNode e = b, next; e != null; e = next) {
                next = (TreeNode)e.next;
                e.next = null;
                // 与原数组长度按位与等于0，那么与新数组长度减1按位与的值和与原数组                
                // 长度减1按位与的值相等，即插入槽位索引不变
                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) {
                // 槽位索引不变的节点个数小于等于6，就将原先的红黑树节点转换成链表
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else { // 槽位索引不变的节点个数大于6，仍然保持红黑树节点
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
            // 判断槽位索引改变的节点
            if (hiHead != null) {
                // 槽位索引改变的节点个数小于等于6，就将原先的红黑树节点转换成链表
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else { // 槽位索引改变的节点个数大于6，仍然保持红黑树节点
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }