《别看了，你学不会的》——HashMap底层源码解析

• HashMap在1.8之后使用了红黑树。红黑树是一种自平衡的二叉树，它可以避免二分搜索树在极端情况下蜕变成链表的情况。在学习红黑树之前，首先要了解2-3树
• 2-3树是一种绝对平衡的多叉树，在这颗树中，任意一个节点，它的左右子树的高度树相同的。
  
• 2-3树分为两种节点，分别是2-节点，和3-节点。其中，2-节点表示节点中保存一个元素，3-节点则表示节点中保存两个元素。
• 如何生成一个2-3树
• • 向2-3树中插入30和25
    
• • 当插入39的时候，一个节点就容纳了3个元素了，那么就要进行分裂操作
    
• • 然后再插入20和33，可以正常的容纳这两个插入的元素
    
• • 再继续插入17和43时，有两个节点都出现了容纳3个元素，那么这两个节点都需要进行分裂操作
    
• • 插入27和35，两个节点都可以容纳这两个新插入的元素
    
• • 那么再最后插入22，结果发现，一个节点容纳了3个元素，要进行分裂，但是分裂后，叶子节点的高度不一致，那么就要再进行聚合操作
    
• 在了解完2-3树之后，回过头来看一下红黑树，也就是说，2-3树怎么转变成红黑树？方式很多，此处可以采用左倾红黑树的方式，来将2-3转换为红黑树，转换规则如下：
  
  如上规则进行转换上面的2-3树时，构造的红黑树如下
  

• 每个节点要么是红色，要么是黑色
• 根节点一定是黑色
• 每个叶子节点一定是黑色
• 如果一个节点上红色，那么它的左右子节点一定都是黑色的
• 从任意一个节点到叶子节点，所经过的黑色节点的数量一样多

也许你会发现上面的2-3树转换成红黑树之后33节点是红色的，这并不满足所有叶子节点都是黑色这一条件
其实，那是因为没有画上空的叶子节点，完整的红黑树如下

当我们使用HashMap的时候，首先会通过HashMap的构造方法创建HashMap，然后通过put方法向HashMap对象赋值

    
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

上面代码做的操作是给loadFactor赋值
loadFactor是什么？它是HashMap的加载因子，也就是说，元素所占的空间达到加载因子的规定值的时候，那么就会执行扩容

DEFAULT_LOAD_FACTOR的值为0.75f

    
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

0.75的含义就是：如果数组中存储的元素长度达到了原长度的75%，那么就需要执行扩容操作

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

put方法里面只是调用了putVal方法

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node[] tab;
        Node p;
        int n, i;
        if ((tab = table) == null || (n = tab.length) == 0) {//如果是空的table，那么默认初始化一个长度为16的Node数组
            n = (tab = resize()).length;
        }
        if ((p = tab[i = (n - 1) & hash]) == null) {//如果计算后的下标i，在tab数组中没有数据，那么则新增Node节点
            tab[i] = newNode(hash, key, value, null);
            //判断是否有哈希冲突，如果没有，直接向数组赋值
        } else {
            Node e;
            K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {//如果与已存在的Node是相同的key值
                e = p;
            }
            else if (p instanceof TreeNode) { //如果与已存在的Node是相同的key值，并且是树节点
                e = ((TreeNode) p).putTreeVal(this, tab, hash, key, value);
            } else { //如果与已存在的Node是相同的key值，并且是普通节点，则循环遍历链式Node，并对比hash和key，如果都不相同，则将新的Node拼装到链表的末尾。如果相同，则进行更新
                for (int binCount = 0; ; ++binCount) {
                //获得p节点的后置节点，赋值给e。直到遍历到横向链表的最后一个节点，即：该节点的next后置指针为null
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // binCount从0开始，横向链表中第2个node对应binCount=0，如果Node链表大于8个Node，那么试图变为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) {
                            treeifyBin(tab, hash);
                        }
                        break;
                    }
                    //针对链表中的每个节点，都来判断一下，是否待插入的key与已存在的链表节点相同，如果相同，则跳出循环，并在后续的操作中，将该节点内容更新为最新的插入值 
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        break;
                    }
                    p = e;
                }
            }

            if (e != null) {
            //如果存在相同的key值
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null) {
                    e.value = value;//对value值进行更新
                }
                afterNodeAccess(e); 
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold) {
            resize();//超过阈值，进行扩容操作
        }
        afterNodeInsertion(evict); 
        return null;
    }

putVal方法中hash是key的哈希值，key的键，value是值，onlyIfAbsent控制对value值进行更新(允许覆盖的话就是false)， evict如果为False，则表处于创建模式

1. 创建table数组
2. 向table数组中赋值（有哈希冲突和哈希不冲突两种情况）
3. 超过阈值则进行扩容

扰动函数：(h = key.hashCode()) ^ (h >>> 16)
将key的哈希code一分为二

• 高半区16位：数据不变
• 低半区16位：数据与高半区16位数据进行异或操作，以此来加大低位的随机性

如果key的哈希code小于等于16位，那么是没有任何影响的。只有大于16位，才会触发扰动函数的执行效果。

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

扰动函数是为了让数据更加平整， 让每个节点存储的数据都差不多多；只用哈希的话，会出现每个节点有些存储的数据很多，有些存储的数据很少

如果table数组（底层存储HashMap元素的数组）等于null或者table数组的长度为0，则执行resize()方法进行扩容

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

resize()方法

    final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap = 0;
        int newThr = 0;
        //table数组为null，所以old Tab=null，因为oldTab=null，所以oldCap=0
        //threshold默认等于0，所以oldThr=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) {
                newThr = oldThr << 1;
            }
        } else if (oldThr > 0) {
            newCap = oldThr;
        } else {
        //oldThr=0，所以执行下面内容
            newCap = DEFAULT_INITIAL_CAPACITY; //默认表容量为16（1<<4）
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //默认值为12
        }
        if (newThr == 0) {
            float ft = (float) newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        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;//没有后置节点，说明e是最后一个节点
                    } else if (e instanceof TreeNode) { //e是树节点
                        ((TreeNode) e).split(this, newTab, j, oldCap);
                    } else {
                        Node loHead = null;
                        Node loTail = null;
                        Node hiHead = null;
                        Node hiTail = null;
                        Node next;
                        do {
                            next = e.next;//获得oldTab数组下标的Node列表的下一个节点
                            if ((e.hash & oldCap) == 0) {//计算e在老表oldTab的下标，如果是第一个Node，即：下标index==0
                                if (loTail == null) {
                                    loHead = e;//将loHead指向oldTab数组第一个下标的第一个元素
                                } else {
                                    loTail.next = e;//建立新的链表
                                }
                                loTail = e;//将loTail指向oldTab数组第一个下标的最后一个元素e
                            } else {//如果不是oldTab中的第一个下标Node
                                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;
    }

resize()方法会根据旧的数组来确定新扩容的数组的容量、阈值，然后创建新的table数组

全局变量
table：当前使用的table数组
threshold：当前所使用的table数组的阈值
loadFactor：当前所使用的table数组的加载因子

局部变量
oldTab：表示旧的table数组
oldThr：表示旧的table数组的阈值
oldCap：表示旧的table数组的容量/长度
newTab：表示新的table数组
newThr：表示新的table数组的阈值
newCap：表示新的table数组的容量/长度

当数组的长度大于等于64，并且横向链表大于8的时候，链表才是转成红黑树

    final void treeifyBin(Node[] tab, int hash) {
        int n;
        int index;
        Node e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) { //当表tab的长度小于64时，只扩展数组大小，不转换为红黑树
            resize();
        } else if ((e = tab[index = (n - 1) & hash]) != null) { //如果新增的node要插入的数组位置已经有node存在了，取出该位置的node节点
            
             //遍历链表中每个节点，将Node转化为TreeNode
            TreeNode hd = null; //指向头节点
            TreeNode tl = null; //指向尾节点
            do {
                TreeNode p = replacementTreeNode(e, null);
                //将每个Node转换为TreeNode，以hd为头节点，每个TreeNode用prev和next连接成新的TreeNode链表
                if (tl == null) {
                    hd = p;
                } else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);

            //步骤二：如果头节点hd不为null，则TreeNode链表进行树型化操作
            if ((tab[index] = hd) != null) {
                hd.treeify(tab);
            }
        }
    }

遍历整个链表，构建红黑树

final void treeify(Node[] tab) {
            TreeNode root = null;
            for (TreeNode x = this, next; x != null; x = next) {
                next = (TreeNode) x.next;
                x.left = x.right = null; //清空x的左右子节点
                if (root == null) { //构建根节点：如果是第一个节点，则将其置为根节点 
                    x.parent = null;
                    x.red = false;
                    root = x;//根节点为黑色
                }
                //构建非根节点
                else {/
                    K k = x.key;    // k：待插入节点的key值
                    int h = x.hash; //h：待插入节点的hash值
                    Class kc = null;
                    for (TreeNode p = root; ; ) {
                        int dir;        //dir：大于0表示右侧节点，否则表示左侧节点
                        int ph;         // ph：parent节点的hash值
                        K pk = p.key;   //pk：parent节点的key值
                        if ((ph = p.hash) > h) {
                            dir = -1;
                        } else if (ph < h) {
                            dir = 1;
                        } else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                                (dir = compareComparables(kc, k, pk)) == 0) {
                            dir = tieBreakOrder(k, pk);
                        }
                        TreeNode xp = p;
                        //试图将x放到p的左子节点或右子节点
                        if ((p = (dir <= 0) ? p.left : p.right) == null) { //p默认是指向root节点的，然后通过这段代码，p会向下（子节点）移动 
                            x.parent = xp;
                            if (dir <= 0) {
                                xp.left = x;
                            } else {
                                xp.right = x;
                            }
                            root = balanceInsertion(root, x);
                            break;
                        }
                    }
                }
            }
            moveRootToFront(tab, root);
        }

平衡插入数据

        static  TreeNode balanceInsertion(TreeNode root, TreeNode x) {
            x.red = true; // 新增的TreeNode默认设置为红色
            for (TreeNode xp, xpp, xppl, xppr; ; ) {
            //xp：父节点
            //xpp：祖父节点
            //xppl：祖父节点的左节点
            //xppr：祖父节点的右节点
                //没有父节点
                if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                //父节点是黑色或没有爷节点
                else if (!xp.red || (xpp = xp.parent) == null) {
                    return root;
                }//只有满足【父节点红色】并且【爷节点不为空】，才满足需要做树节点平衡操作的条件
                //如果x的父节点是爷节点的左侧子节点
                if (xp == (xppl = xpp.left)) {
                    //如果x的爷节点存在右侧子节点并且这个右侧子节点是红色
                    if ((xppr = xpp.right) != null && xppr.red) {
                        xppr.red = false;   // 爷节点的右侧子节点变为黑色
                        xp.red = false;     // 父节点变为黑色
                        xpp.red = true;     // 爷节点变为红色
                        x = xpp;
                    } else {
                        // x在父节点的右侧
                        if (x == xp.right) {
                            root = rotateLeft(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        //x存在父节点,在父节点左侧
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateRight(root, xpp) ;
                            }
                        }
                    }
                }
                //如果x的父节点是爷节点的右侧子节点
                else {
                    if (xppl != null && xppl.red) {
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    } else {
                        if (x == xp.left) {
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }