JDK8HashMap源码

一、红黑树 1.1 红黑树的定义

红黑树是一种自平衡的二叉查找树，它的节点的颜色为红色和黑色。它不严格控制左、右子树高度或节点数之差小于等于1。通过左旋、右旋、变色保证平衡

1.每个节点非红即黑；

2.根节点总是黑色的；

3.每个叶子节点都是黑色；

4.红节点的子节点一定是黑色的。

5.从任一节点到叶子节点必须包含相同数量的黑色节点。

AVL树是高度平衡的而红黑树不是高度平衡的，它只要求部分地达到平衡要求，结合变色，降低了对旋转的要求从而提高了性能。在最坏的情况下也可以保证O(logN)，二叉查找树最坏情况下O(N)。

树、红黑树

二、hashMap 2.1 HashMap结构

2.2 balanceInsertion 2.2.1 变量解释

红黑树调节平衡

 红黑树进行调整的几种情况

1.父结点是黑色，不用进行调整

2.父结点是红色

1.叔叔结点是空的，旋转+变色

2.叔叔结点是红色，父结点+叔叔结点变黑色，祖父结点变为红色

3.叔叔结点是黑色，旋转+变色

2.2.2 父结点为null

2.2.3 父结点为黑色

2.2.4 父节点为红色

1.叔叔结点是红色，父结点+叔叔结点变黑色，祖父结点变为红色

2.todo，博主已绕晕

2.3 hashMap的put方法

2.3.1 treeifyBin(tab,hash）

2.3.2 treeify

真正的树化逻辑

向红黑树里插入新结点之前，肯定要判断插入到哪个位置，确定好它的父结点，然后，判断，到底走左边，还是走右边。这就需要跟里面的值进行比较，这里比较主要用了下面几个参数进行比较

注意：这里同一个链表或者同一个树的数组下标一样，hashCode并不一定一样。

另外：hash冲突就是，不同的key经过hash计算，得到的数组下标都一样了，这就产生了hash冲突，所以用链表或红黑树来解决hash冲突。

2.3.3 putTreeVal

/**
         * 树版本的putVal。
         * 会在树中插入一个新节点，或者将原有节点返回，在putVal里面对它的value进行修改
         */
        final TreeNode putTreeVal(HashMap map, Node[] tab,
                                       int h, K k, V v) {
            Class kc = null;
            boolean searched = false;
            
            // p = tab[i = (n - 1) & hash]
            // ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            // p是这个hash对应tab里的桶，也就是自己this
            
            // root为自己这个节点的root节点
            TreeNode root = (parent != null) ? root() : this;
            // 将root赋值给p
            // 下面for的大循环的目的是，从root开始，根据hash和key，不断向下，遍历孩子，
            // 直到找到对应节点，或者对应节点没有，插入节点并维持红黑树平衡
            for (TreeNode p = root;;) {
                int dir, ph; K pk;
                
                // 下面的那个大if，是为了得到dir，确定下次迭代时，p=p.left/right
                // 大if中，如果hash和key相同，直接返回p
                // 如果hash相同，key无法比较，调用find方法，如果找到，返回q
                
                // 将p的hash赋值给ph
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                
                // 到这里ph与h相同
                // 将p的key赋值给pk
                // 如果找到key和hash对应的节点p，将p返回
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                // 如果hash相同，key不同
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                		 // dir为k与pk比较的结果
                         (dir = compareComparables(kc, k, pk)) == 0) {
                	
                	// 如果比较结果为0
                    if (!searched) {
                        TreeNode q, ch;
                        // 注意：由于searched的关系 直接调用find方法只会有一次！
                        searched = true;
                        // 对left和right调用find方法，如果找到了，返回对应节点
                        if (((ch = p.left) != null &&
                             (q = ch.find(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.find(h, k, kc)) != null))
                            return q;
                    }
                    // 如果hash相同，key不同，比较结果为0，find没找到，调用tieBreakOrder赋值给dir
                    // 即对两者的className和默认的hashcode进行依次比较
                    dir = tieBreakOrder(k, pk);
                }
                
                //上面的那个不断if else的语句结束，已经找到了节点或者得到了dir

                // p赋值给xp
                TreeNode xp = p;
                // 根据dir，p=p.left/right
                // 但是如果赋值后p为null，代表没有找到对应节点，新增一个节点，并维持平衡
                if ((p = (dir =TREEIFY_THRESHOLD=8
                        	// 原来的数目>=8，加入后，有9个节点，则树化桶，已经有8个元素了，再加一个就进行树化
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        break; // 如果e的数据正确，跳出
                    p = e; // 将e赋给p，就是p=p.next
                }
            }
            if (e != null) { // 这种情况不是新增节点，而是对已经存在节点进行修改
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //1.7hashmap扩容还判断了table[i]是否为null,如果不为null才进行扩容，jdk1.8去出了这个判断
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

    /**
     * 初始化或者倍化表的大小（*2）。
     * 如果表为null，使用字段threshold作为初始容量目标，分配空间。
     * 否则，因为我们使用2的幂的扩展，每个桶的元素，要么待在同一个index的桶，要么index+新表中2的幂。
     * 比如110+1000=1110，就是加了2的幂
     *
     * @return the table
     */
    final Node[] resize() {
    	// 将现在的table赋值给oldTab
        Node[] oldTab = table;
        // 如果现在的table，oldCap=0，否则为table.length
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 将threshold赋值给oldThr
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 下面的代码是得到新的容量和阀值，即newCap, newThr
        if (oldCap > 0) {
        	// 如果oldCap>0,说明是扩容（*2）的情况
            if (oldCap >= MAXIMUM_CAPACITY) {
            	// 如果oldCap超过限制，则设置threshold = Integer.MAX_VALUE，将现在的table直接返回
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 将oldCap MAXIMUM_CAPACITY，则newThr=Integer.MAX_VALUE
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 将newThr赋值给threshold
        // 将new Node[newCap]赋值给newTab
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node[] newTab = (Node[])new Node[newCap];
        // 将newTab赋值给table
        table = newTab;
        if (oldTab != null) {
        	// 如果oldTab != null，则是扩容状态，对旧表的数据向新表迁移
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                // 对oldTab进行遍历，将oldTab[j]赋值给e
                if ((e = oldTab[j]) != null) {
                	// 如果e不为null，则迁移
                	// 将旧表清空，oldTab[j] = null
                    oldTab[j] = null;
                    if (e.next == null)
                    	// 如果只有一个节点，新的index为  e.hash & (newCap - 1)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                    	// 如果e是TreeNode，调用e的split方法进行重新分配
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // 保持顺序
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        do {
                            next = e.next; // 将e.next赋值给next
                            // oldCap=1000，newCap=10000
                            // 本来要放入新桶的hash & (newCap-1) = hash & 1111
                            // 现在hash & oldCap = hash & 1000                                     hash= 1****
                            // 如果结果为0，hash为0xxx，说明 hash & 1111=hash & 0111，还是在原来的桶 & oldC= 10000 = 10000
                            // 如果结果不为0，hash为1xxx，
                            if ((e.hash & oldCap) == 0) {
                            	//(e.hash & oldCap) == 0，说明还是在原来的桶
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                                // 在lo中，形成一个链表，第一个为head，接下来不断放在tail的next
                                // newTab[j] = loHead;
                            }
                            else {
                            	// 说明在另一个桶
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                             // 在hi中，形成一个链表，第一个为head，接下来不断放在tail的next
                             // newTab[j + oldCap] = hiHead;   
                            }
                        } while ((e = next) != null);
                        //设置完两个链表后，将两个head赋值给新表中两个桶
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

 2.3.5 split

相当于把红黑树里面的两个元素，也拆成了两个链表。

/**
         * 将一个树桶的节点分割为低位和高位的树桶，或者如果当前的太小了，反树化。
         * 仅仅当resize时调用，看上面关于分割的位的讨论。
         *
         * @param map the map
         * @param tab the table for recording bin heads
         * @param index the index of the table being split
         * @param bit the bit of hash to split on
         */
        final void split(HashMap map, Node[] tab, int index, int bit) {
            //bit->oldCap
            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;
            // oldTab[j]赋值给e
            // ((TreeNode)e).split(this, newTab, j, oldCap);
            // 设置e为b，也就是this，也就是树桶的第一个节点
            // 从e开始，不断e.next进行循环
            for (TreeNode e = b, next; e != null; e = next) {
                next = (TreeNode)e.next;
                // 设置e.next为null
                e.next = null;
                // bit就是oldCap，二进制位10000
                // 如果hash&bit为0，放在lo的队尾,lc++
                if ((e.hash & bit) == 0) {
                    if ((e.prev = loTail) == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }
                // 如果hash&bit为1，放在hi的队尾,hc++
                else {
                    if ((e.prev = hiTail) == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }
            //把这个树拆成两个链表后，如果低位的链表元素个数，小于等于6
            if (loHead != null) {
                //UNTREEIFY_THRESHOLD=6,如果红黑树的个数小于等于6，就把它改为链表
                if (lc