HashMap源码解析

注意：所有文章除特别说明外，转载请注明出处.

HashMap源码解析

[TOC]

1. 默认属性

　　static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  //默认初始容量 16

static final int MAXIMUM_CAPACITY = 1 << 30; //最大值 2^30

static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认扩容因子

static final int TREEIFY_THRESHOLD = 8; //转为红黑树的值

static final int UNTREEIFY_THRESHOLD = 6;//由树转换为链表的值

static final int MIN_TREEIFY_CAPACITY = 64;//默认的树存在的最小数组长度 此长度最少是TREEIFY_THRESHOLD的四倍（注释之中说的很清楚）

2. put方法

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

hash方法

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
//hashcode是32位的，无符号右移16位，那生成的就是16位0加原高位的16位值， 就是对半了，异或计算也就变成
//了高16位和低16位进行异或，原高16位不变。这么干主要用于当hashmap 数组比较小的时候所有二进制都参与运
//算了，防止hash冲突太大，

==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;
        // 如果存储元素的table为空，则进行初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            ///这里的resize  是初始化的时候调用 后面会讲
            n = (tab = resize()).length;    // 获取默认长度（16）
    	//p = tab[i = (n - 1) & hash] 获取要插入的元素在hash桶中的位置
        // 如果根据hash值获取的结点为空（这个位置没有节点）
        if ((p = tab[i = (n - 1) & hash]) == null)      // 此处 & 代替了 %（效率更高）
            tab[i] = newNode(hash, key, value, null);//则直接新建一个结点
        // 这里的p结点是根据hash值算出来对应在数组中的元素
        else {//如果有节点
            Node<K,V> e; K k;
            // 如果新插入的结点和table中p结点的hash值，key值相同的话
            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 {//定位到这个hash桶了 但是这里面是链表（没有进行过树化）
                for (int binCount = 0; ; ++binCount) {
                    // 如果p节点的next为空 直接在后面插入(代表这个单链表只有一个头部结点)
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);//插入完成之后再次判断是否要转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);//转换为红黑树
                        break;
                    }
                    ////如果下一个节点e 不为null 并且这个链表中的节点就是你要找的节点 终止循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 及时更新p 保证p是最后一个
                    p = e;
                }
            }
            // 如果存在这个映射就覆盖
            if (e != null) { 
                V oldValue = e.value;
                // 判断是否允许覆盖，并且value是否为空、
                //onlyIfAbsent 如果为true，不更改现有值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);     // 回调以允许LinkedHashMap后置操作
                return oldValue;
            }
        }
    // 执行到这里，说明是增加了新的元素，而不是替换了老的元素，所以相关计数需要累加
        ++modCount;     // 更改操作次数
        if (++size > threshold)     // 大于临界值
            // 将数组大小设置为原来的2倍，并将原先的数组中的元素放到新数组中
            // 因为有链表，红黑树之类，因此还要调整他们
            resize();  
        // 回调以允许LinkedHashMap后置操作
        afterNodeInsertion(evict);
        return null;// 返回空
    }

==PUT方法的流程：==

• 1、如果未被初始化，则初始化
• 2、根据KEY求Hash值，然后计算下标。
• 3、如果没有碰撞直接放入bucket中。
• 4、如果碰撞了，则以链表的方式连接到后面。
• 5、如果链表长度大于 8，则调转换为红黑树的方法
• 6、如果树节点个数低于 6，则调转换链表的方法
• 7、如果节点已经存在则直接替换
• 8、如果超过了阈值，则进行扩容

resize(扩容)方法

//初始化或者扩容之后元素调整
final Node<K,V>[] resize() {
        // 获取旧元素数组的各种信息
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;//如果你是新创建的话 表的大小就是0 否则就是原来的大小
        //第一次是为0的 代表 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;就是16
        // 老的扩容阀值设置
        int oldThr = threshold;
        // 定义新数组的长度及扩容的临界值（都初始化为0）
        int newCap, newThr = 0;
        if (oldCap > 0) {   // 如果原table不为空
            // 如果数组元素个数大于等于限定的最大容量（2的30次方）
            if (oldCap >= MAXIMUM_CAPACITY) {
                // 扩容阀值设置为int最大值（2的31次方 -1 ），因为oldCap再乘2就溢出了
                threshold = Integer.MAX_VALUE;
                //直接返回
                return oldTab;
            }
            // 下面就是扩容操作（2倍）newCap = oldCap << 1 相当于*2
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)//并且旧的容量大于默认的初始化大小16
                // 新的扩容阈值 = 旧的扩容阈值 * 2 
                newThr = oldThr << 1;
        }
        else if (oldThr > 0)
            newCap = oldThr;//如果旧的扩容本来就大于0，那么新的容量就是旧的扩容
        else { // threshold（旧的扩容）为0，则使用默认值
            // 能运行到这里的话，说明是调用无参构造函数创建的该map，并且第一次添加元素
            newCap = DEFAULT_INITIAL_CAPACITY; //16 
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//0.75*16=12
        }
        if (newThr == 0) {  // 如果阈值值还为0，则设置临界值
            //计算得到新的阙值
            float ft = (float)newCap * loadFactor;
            //新的阙值 =  如果新的容量<最大的容量 并且 新的阈值<最大的容量 ，那么新的阙值 = 计算的             //否则=最大int
            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 = newTab;
        if (oldTab != null) {   // 调整数组大小之后，需要调整红黑树或者链表的指向
            //遍历旧的hash桶
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //如果旧的hash桶的元素不为null  e为旧的hash桶的元素
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;//旧的hash桶设置为null(主要为了使得数组可被回收)
                    if (e.next == null)//如果你是一个元素
                        //那么在新的hash桶中给你安排一个位置  
                        //位置是你的hash值 & 新的桶的容量-1（再次分配位置） 
                        newTab[e.hash & (newCap - 1)] = e;
                 	//如果你不只一个元素并且是TreeNode
                    else if (e instanceof TreeNode)
                        //调用split方法
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { //如果你是普通的链表
                        // 链表调整
                        // 按命名来翻译的话，应该叫低位首尾节点
                        Node<K,V> loHead = null, loTail = null;
                        // 按命名来翻译的话，应该叫高位首尾节点
                        Node<K,V> hiHead = null, hiTail = null;
             //以上的低位指的是新数组的 0 到 oldCap-1 、高位指定的是oldCap 到 newCap - 1
                        Node<K,V> next;
                        do {
                            next = e.next;
                            
                            //看是否需要进行位置变化 新增位的值 不需要变化就放在原来的位置
                            //如果hash值和老的长度做与运算，结果为0，那么该hash值再和新数组的长度取摸的话值也不会放生变化，所以该元素的在新数组的位置和在老数组的位置是相同的，所以该元素可以放置在低位链表中。
                            if ((e.hash & oldCap) == 0) { 
                                if (loTail == null) // 如果没有尾，说明链表为空
                                    loHead = e;// 链表为空时，头节点指向该元素
                                else
                                    // 如果有尾，那么链表不为空，把该元素挂到链表的最后。
                                    loTail.next = e; 
                                loTail = e;// 把尾节点设置为当前元素
                            }
                            // 如果与运算结果不为0，说明hash值大于老数组长度（例如hash值为17）
                            // 此时该元素应该放置到新数组的高位位置上
                            //例：老数组长度16，那么新数组长度为32，hash为17的应该放置在数组的第17个位置上，也就是下标为16，那么下标为16已经属于高位了，低位是[0-15]，高位是[16-31]
                            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) {
                             // 销毁实例，等待GC回收
                            hiTail.next = null;
                            // 例：hash为 17 在老数组放置在0下标，在新数组放置在16下标；                                   //hash为 18 在老数组放置在1下标，在新数组放置在17下标； 
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        //返回新的数组
        return newTab;
    }
/** 总结一下
 *  1、如果你是新创建的话 旧的表的大小就是0 否则就是原来的大小
 *  2、 如果原table不为空且数组元素个数大于等于限定的最大容量（2的30次方），扩容阀值设置为int最大值
 *    直接返回。
 *  3、新的表的大小等于旧的乘2,如果其大小小于最大容量，并且旧的容量大于默认的初始化大小16，
 *     新的扩容阈值 = 旧的扩容阈值 * 2 
 *  4、如果是是调用无参构造函数创建的该map，并且第一次添加元素，给附上初始值16
 *  5、如果阈值值还为0，则设置临界值：新的阙值 =  如果新的容量<最大的容量 并且 新的阈值<最大的容量
 *     那么新的阙值 = 计算的  否则=最大int
 *  6、创建一个新的哈希数组桶 大小为新的容量，然后遍历旧的哈希桶
 *  7、如果旧的hash桶的元素不为null，旧的hash桶设置为null(主要为了使得数组可被回收)这里已经用e接收了
 *  8、如果你是一个元素，那么在新的hash桶中给你安排一个位置，
 *	   位置是你的hash值 & 新的桶的容量-1（再次分配位置）
 *  9、如果你不只一个元素并且是TreeNode,那么调用split方法，进行树的修剪
 *  10、如果你是一个普通链表，且(e.hash & oldCap) == 0，则挂到低位链，否则挂到高位链
 *  11、如果链表上存在元素，则尾插。
 *  12、把老数组赋空，便于GC回收。
 *  13、高位的元素组成的链表放置的位置只是在原有位置上偏移了老数组的长度个位置
 		例：hash为 17 在老数组放置在0下标，在新数组放置在16下标；                                   	//hash为 18 在老数组放置在1下标，在新数组放置在17下标； 
 */

split(红黑树修剪)方法

上述方法在resize()过程中被调用 
和链表的修剪差不多（再次操作看看是否要再次保留红黑树）
目的是将树的数据重新散列到数组中
//被调用的代码 split(当前hash表，新的哈希桶，要分割的元素的下标，旧的容量) 
        final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this;//这里的this :    e = oldTab[j] 上下文中的代码
            
            TreeNode<K,V> loHead = null, loTail = null;//低位的头和低位的尾
            TreeNode<K,V> hiHead = null, hiTail = null;//高位的头和高位的尾
            int lc = 0, hc = 0; //地位和高位的2个计数器
            for (TreeNode<K,V> e = b, next; e != null; e = next) {
                next = (TreeNode<K,V>)e.next;//获取下一个节点
                e.next = null;//设置为null
                if ((e.hash & bit) == 0) {
                //如果 e.hash 与 原来旧的容量 & 为 0 说明不需要进行移动位置  
                    if ((e.prev = loTail) == null)
                        loHead = e;//将e 复制给头
                    else
                    //如果尾巴不为null 尾巴的next 为 e
                        loTail.next = e;
                    loTail = e;//将e 作为新的尾巴
                    ++lc;//次数 + 1 
                }
                else {
                    if ((e.prev = hiTail) == null)//否则需要移动位置
                        hiHead = e;//高位的链表和低位一样
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }

            if (loHead != null) { //如果有链表
                if (lc <= UNTREEIFY_THRESHOLD)//如果长度 <= 6  
                //取消树化 将这个树里面的链表结构变成普通的链表结构
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead; //否则将地位复制给原来的下标
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);//进行树化
                }
            }
            if (hiHead != null) {
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);//进行了移位 位置偏移 下标 + 原来的容器大小
                else {
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }

untreeify(非树化)方法

如果链表的长度 <= UNTREEIFY_THRESHOLD(6) 就进行非树化，否则就进行树化。
这里的非树化就是将TreeNode转换成Node
		final Node<K,V> untreeify(HashMap<K,V> map) {
            Node<K,V> hd = null, tl = null;
            for (Node<K,V> q = this; q != null; q = q.next) {
            //将q转换成普通的Nod return new Node<>(p.hash, p.key, p.value, next);
                Node<K,V> p = map.replacementNode(q, null);
                if (tl == null)
                    hd = p; //头为p
                else
                    tl.next = p;
                tl = p;
            }
            return hd;//返回这个链表
        }

treeifyBin(树化)方法

treeifyBin方法，应该可以解释为：把容器里的元素变成树结构   

/**
 * tab：元素数组，
 * hash：hash值（要增加的键值对的key的hash值）
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
 
    int n, index; Node<K,V> e;
    /*
     * 如果元素数组为空 或者 数组长度小于 树结构化的最小限制
     * MIN_TREEIFY_CAPACITY 默认值64，对于这个值可以理解为：如果元素数组长度小于这个值，没有必要去进行结构转换
     * 当一个数组位置上集中了多个键值对，那是因为这些key的hash值和数组长度取模之后结果相同。（并不是因为这些key的hash值相同）
     * 因为hash值相同的概率不高，所以可以通过扩容的方式，来使得最终这些key的hash值在和新的数组长度取模之后，拆分到多个数组位置上。
     */
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // 扩容，可参见resize方法解析
        
    // 如果元素数组长度已经大于等于了 MIN_TREEIFY_CAPACITY，那么就有必要进行结构转换了
    // 根据hash值和数组长度进行取模运算后，得到链表的首节点
    else if ((e = tab[index = (n - 1) & hash]) != null) { 
        TreeNode<K,V> hd = null, tl = null; // 定义首、尾节点
        do { 
            TreeNode<K,V> p = replacementTreeNode(e, null); // 将该节点转换为 树节点
            if (tl == null) // 如果尾节点为空，说明还没有根节点
                hd = p; // 首节点（根节点）指向 当前节点
            else { // 尾节点不为空，以下两行是一个双向链表结构
                p.prev = tl; // 当前树节点的 前一个节点指向 尾节点
                tl.next = p; // 尾节点的 后一个节点指向 当前节点
            }
            tl = p; // 把当前节点设为尾节点
        } while ((e = e.next) != null); // 继续遍历链表
        // 到目前为止 也只是把Node对象转换成了TreeNode对象，把单向链表转换成了双向链表
        // 把转换后的双向链表，替换原来位置上的单向链表
        if ((tab[index] = hd) != null)
            hd.treeify(tab);//此处单独解析
    }
}

treeify(打头树化)方法

/**
 * 参数为HashMap的元素数组,
 * treeify方法是TreeNode类的一个实例方法，通过TreeNode对象调用，实现该对象打头的链表转换为树结构。
 */
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null; // 定义树的根节点
    for (TreeNode<K,V> x = this, next; x != null; x = next) { // 遍历链表，x指向当前节点、next指向下一个节点
        next = (TreeNode<K,V>)x.next; // 下一个节点
        x.left = x.right = null; // 设置当前节点的左右节点为空
        if (root == null) { // 如果还没有根节点
            x.parent = null; // 当前节点的父节点设为空
            x.red = false; // 当前节点的红色属性设为false（把当前节点设为黑色）
            root = x; // 根节点指向到当前节点
        }
        else { // 如果已经存在根节点了
            K k = x.key; // 取得当前链表节点的key
            int h = x.hash; // 取得当前链表节点的hash值
            Class<?> kc = null; // 定义key所属的Class
            for (TreeNode<K,V> p = root;;) { // 从根节点开始遍历，此遍历没有设置边界，只能从内部跳出
                // GOTO1
                int dir, ph; // dir 标识方向（左右）、ph标识当前树节点的hash值
                K pk = p.key; // 当前树节点的key
                if ((ph = p.hash) > h) // 如果当前树节点hash值 大于 当前链表节点的hash值
                    dir = -1; // 标识当前链表节点会放到当前树节点的左侧
                else if (ph < h)
                    dir = 1; // 右侧
 
                /*
                 * 如果两个节点的key的hash值相等，那么还要通过其他方式再进行比较
                 * 如果当前链表节点的key实现了comparable接口，并且当前树节点和链表节点是相同Class的实例，那么通过comparable的方式再比较两者。
                 * 如果还是相等，最后再通过tieBreakOrder比较一次
                 */
                else if ((kc == null &&
                            (kc = comparableClassFor(k)) == null) ||
                            (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
 
                TreeNode<K,V> xp = p; // 保存当前树节点
 
                /*
                 * 如果dir 小于等于0 ： 当前链表节点一定放置在当前树节点的左侧，但不一定是该树节点的左孩子，也可能是左孩子的右孩子 或者 更深层次的节点。
                 * 如果dir 大于0 ： 当前链表节点一定放置在当前树节点的右侧，但不一定是该树节点的右孩子，也可能是右孩子的左孩子 或者 更深层次的节点。
                 * 如果当前树节点不是叶子节点，那么最终会以当前树节点的左孩子或者右孩子 为 起始节点  再从GOTO1 处开始 重新寻找自己（当前链表节点）的位置
                 * 如果当前树节点就是叶子节点，那么根据dir的值，就可以把当前链表节点挂载到当前树节点的左或者右侧了。
                 * 挂载之后，还需要重新把树进行平衡。平衡之后，就可以针对下一个链表节点进行处理了。
                 */
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp; // 当前链表节点 作为 当前树节点的子节点
                    if (dir <= 0)
                        xp.left = x; // 作为左孩子
                    else
                        xp.right = x; // 作为右孩子
                    root = balanceInsertion(root, x); // 重新平衡
                    break;
                }
            }
        }
    }
 
    // 把所有的链表节点都遍历完之后，最终构造出来的树可能经历多个平衡操作，根节点目前到底是链表的哪一个节点是不确定的
    // 因为我们要基于树来做查找，所以就应该把 tab[N] 得到的对象一定根节点对象，而目前只是链表的第一个节点对象，所以要做相应的处理。
    moveRootToFront(tab, root); // 单独解析
}

moveRootToFront(保证根节点)方法

/**
 * 把红黑树的根节点设为  其所在的数组槽 的第一个元素
 * 首先明确：TreeNode既是一个红黑树结构，也是一个双链表结构
 * 这个方法里做的事情，就是保证树的根节点一定也要成为链表的首节点
 */
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) { // 根节点不为空 并且 HashMap的元素数组不为空
        int index = (n - 1) & root.hash; // 根据根节点的Hash值 和 HashMap的元素数组长度  取得根节点在数组中的位置
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; // 首先取得该位置上的第一个节点对象
        if (root != first) { // 如果该节点对象 与 根节点对象 不同
            Node<K,V> rn; // 定义根节点的后一个节点
            tab[index] = root; // 把元素数组index位置的元素替换为根节点对象
            TreeNode<K,V> rp = root.prev; // 获取根节点对象的前一个节点
            if ((rn = root.next) != null) // 如果后节点不为空 
                ((TreeNode<K,V>)rn).prev = rp; // root后节点的前节点  指向到 root的前节点，相当于把root从链表中摘除
            if (rp != null) // 如果root的前节点不为空
                rp.next = rn; // root前节点的后节点 指向到 root的后节点
            if (first != null) // 如果数组该位置上原来的元素不为空
                first.prev = root; // 这个原有的元素的 前节点 指向到 root，相当于root目前位于链表的首位
            root.next = first; // 原来的第一个节点现在作为root的下一个节点，变成了第二个节点
            root.prev = null; // 首节点没有前节点
        }
 
        /*
         * 这一步是防御性的编程
         * 校验TreeNode对象是否满足红黑树和双链表的特性
         * 如果这个方法校验不通过：可能是因为用户编程失误，破坏了结构（例如：并发场景下）；也可能是TreeNode的实现有问题（这个是理论上的以防万一）；
         */ 
        assert checkInvariants(root); 
    }
}

putTreeVal(树的添加节点)方法

​ 当同一个位置上链表中的元素达到8个的时候，就会再将这些元素构建成一个红黑树（参见：treeifyBin方法分析），同时把==原来的单链表结构变成了双链表结构==，也就是这些==元素即维持着红黑树的结构又维持着双链表的结构==。当第9个相同hash值的键值对put过来时，发现该位置已经是一个树节点了，那么就会调用putTreeVal方法，将这个新的值设置到指定的key上。

    
/**
 * 当存在hash碰撞的时候，且元素数量大于8个时候，就会以红黑树的方式将这些元素组织起来
 * map 当前节点所在的HashMap对象
 * tab 当前HashMap对象的元素数组
 * h   指定key的hash值
 * k   指定key
 * v   指定key上要写入的值
 * 返回：指定key所匹配到的节点对象，针对这个对象去修改V（返回空说明创建了一个新节点）
 */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                int h, K k, V v) {
    Class<?> kc = null; // 定义k的Class对象
    boolean searched = false; // 标识是否已经遍历过一次树，未必是从根节点遍历的，但是遍历路径上一定已经包含了后续需要比对的所有节点。
    TreeNode<K,V> root = (parent != null) ? root() : this; // 父节点不为空那么查找根节点，为空那么自身就是根节点
    for (TreeNode<K,V> p = root;;) { // 从根节点开始遍历，没有终止条件，只能从内部退出
        int dir, ph; K pk; // 声明方向、当前节点hash值、当前节点的键对象
        if ((ph = p.hash) > h) // 如果当前节点hash 大于 指定key的hash值
            dir = -1; // 要添加的元素应该放置在当前节点的左侧
        else if (ph < h) // 如果当前节点hash 小于 指定key的hash值
            dir = 1; // 要添加的元素应该放置在当前节点的右侧
        else if ((pk = p.key) == k || (k != null && k.equals(pk))) // 如果当前节点的键对象 和 指定key对象相同
            return p; // 那么就返回当前节点对象，在外层方法会对v进行写入
 
        // 走到这一步说明 当前节点的hash值  和 指定key的hash值  是相等的，但是equals不等
        else if ((kc == null &&
                    (kc = comparableClassFor(k)) == null) ||
                    (dir = compareComparables(kc, k, pk)) == 0) {
 
            // 走到这里说明：指定key没有实现comparable接口   或者   实现了comparable接口并且和当前节点的键对象比较之后相等（仅限第一次循环）
        
 
            /*
             * searched 标识是否已经对比过当前节点的左右子节点了
             * 如果还没有遍历过，那么就递归遍历对比，看是否能够得到那个键对象equals相等的的节点
             * 如果得到了键的equals相等的的节点就返回
             * 如果还是没有键的equals相等的节点，那说明应该创建一个新节点了
             */
            if (!searched) { // 如果还没有比对过当前节点的所有子节点
                TreeNode<K,V> q, ch; // 定义要返回的节点、和子节点
                searched = true; // 标识已经遍历过一次了
                /*
                 * 红黑树也是二叉树，所以只要沿着左右两侧遍历寻找就可以了
                 * 这是个短路运算，如果先从左侧就已经找到了，右侧就不需要遍历了
                 * find 方法内部还会有递归调用。参见：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; // 找到了指定key键对应的
            }
 
            // 走到这里就说明，遍历了所有子节点也没有找到和当前键equals相等的节点
            dir = tieBreakOrder(k, pk); // 再比较一下当前节点键和指定key键的大小
        }
 
        TreeNode<K,V> xp = p; // 定义xp指向当前节点
        /*
        * 如果dir小于等于0，那么看当前节点的左节点是否为空，如果为空，就可以把要添加的元素作为当前节点的左节点，如果不为空，还需要下一轮继续比较
        * 如果dir大于等于0，那么看当前节点的右节点是否为空，如果为空，就可以把要添加的元素作为当前节点的右节点，如果不为空，还需要下一轮继续比较
        * 如果以上两条当中有一个子节点不为空，这个if中还做了一件事，那就是把p已经指向了对应的不为空的子节点，开始下一轮的比较
        */
        if ((p = (dir <= 0) ? p.left : p.right) == null) {  
            // 如果恰好要添加的方向上的子节点为空，此时节点p已经指向了这个空的子节点
            Node<K,V> xpn = xp.next; // 获取当前节点的next节点
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); // 创建一个新的树节点
            if (dir <= 0)
                xp.left = x;  // 左孩子指向到这个新的树节点
            else
                xp.right = x; // 右孩子指向到这个新的树节点
            xp.next = x; // 链表中的next节点指向到这个新的树节点
            x.parent = x.prev = xp; // 这个新的树节点的父节点、前节点均设置为 当前的树节点
            if (xpn != null) // 如果原来的next节点不为空
                ((TreeNode<K,V>)xpn).prev = x; // 那么原来的next节点的前节点指向到新的树节点
            moveRootToFront(tab, balanceInsertion(root, x));// 重新平衡，以及新的根节点置顶
            return null; // 返回空，意味着产生了一个新节点
        }
    }
}

balanceInsertion(树的平衡)方法

红黑树插入节点后，需要重新平衡
 root 当前根节点
 x 新插入的节点
 返回重新平衡后的根节点

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
    x.red = true; // 新插入的节点标为红色
 
    /*
     * 这一步即定义了变量，又开起了循环，循环没有控制条件，只能从内部跳出
     * xp：当前节点的父节点、xpp：爷爷节点、xppl：左叔叔节点、xppr：右叔叔节点
     */
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { 
 
        // 如果父节点为空、说明当前节点就是根节点，那么把当前节点标为黑色，返回当前节点
        if ((xp = x.parent) == null) { // L1
            x.red = false;
            return x;
        }
 
        // 父节点不为空
        // 如果父节点为黑色 或者 【（父节点为红色 但是 爷爷节点为空） -> 这种情况何时出现？】
        else if (!xp.red || (xpp = xp.parent) == null) // L2
            return root;
        if (xp == (xppl = xpp.left)) { // 如果父节点是爷爷节点的左孩子  // L3
            if ((xppr = xpp.right) != null && xppr.red) { // 如果右叔叔不为空 并且 为红色  // L3_1
                xppr.red = false; // 右叔叔置为黑色
                xp.red = false; // 父节点置为黑色
                xpp.red = true; // 爷爷节点置为红色
                x = xpp; // 运行到这里之后，就又会进行下一轮的循环了，将爷爷节点当做处理的起始节点 
            }
            else { // 如果右叔叔为空 或者 为黑色 // L3_2
                if (x == xp.right) { // 如果当前节点是父节点的右孩子 // L3_2_1
                    root = rotateLeft(root, x = xp); // 父节点左旋，见下文左旋方法解析
                    xpp = (xp = x.parent) == null ? null : xp.parent; // 获取爷爷节点
                }
                if (xp != null) { // 如果父节点不为空 // L3_2_2
                    xp.red = false; // 父节点 置为黑色
                    if (xpp != null) { // 爷爷节点不为空
                        xpp.red = true; // 爷爷节点置为 红色
                        root = rotateRight(root, xpp);  //爷爷节点右旋，见下文右旋方法解析
                    }
                }
            }
        }
        else { // 如果父节点是爷爷节点的右孩子 // L4
            if (xppl != null && xppl.red) { // 如果左叔叔是红色 // L4_1
                xppl.red = false; // 左叔叔置为 黑色
                xp.red = false; // 父节点置为黑色
                xpp.red = true; // 爷爷置为红色
                x = xpp; // 运行到这里之后，就又会进行下一轮的循环了，将爷爷节点当做处理的起始节点 
            }
            else { // 如果左叔叔为空或者是黑色 // L4_2
                if (x == xp.left) { // 如果当前节点是个左孩子 // L4_2_1
                    root = rotateRight(root, x = xp); // 针对父节点做右旋，见下文右旋方法解析
                    xpp = (xp = x.parent) == null ? null : xp.parent; // 获取爷爷节点
                }
                if (xp != null) { // 如果父节点不为空 // L4_2_4
                    xp.red = false; // 父节点置为黑色
                    if (xpp != null) { //如果爷爷节点不为空
                        xpp.red = true; // 爷爷节点置为红色
                        root = rotateLeft(root, xpp); // 针对爷爷节点做左旋
                    }
                }
            }
        }
    }
}
 
 
/**
 * 节点左旋
 * root 根节点
 * p 要左旋的节点
 */
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
    TreeNode<K,V> r, pp, rl;
    if (p != null && (r = p.right) != null) { // 要左旋的节点以及要左旋的节点的右孩子不为空
        if ((rl = p.right = r.left) != null) // 要左旋的节点的右孩子的左节点 赋给 要左旋的节点的右孩子 节点为：rl
            rl.parent = p; // 设置rl和要左旋的节点的父子关系【之前只是爹认了孩子，孩子还没有答应，这一步孩子也认了爹】
 
        // 将要左旋的节点的右孩子的父节点  指向 要左旋的节点的父节点，相当于右孩子提升了一层，
        // 此时如果父节点为空， 说明r 已经是顶层节点了，应该作为root 并且标为黑色
        if ((pp = r.parent = p.parent) == null) 
            (root = r).red = false;
        else if (pp.left == p) // 如果父节点不为空 并且 要左旋的节点是个左孩子
            pp.left = r; // 设置r和父节点的父子关系【之前只是孩子认了爹，爹还没有答应，这一步爹也认了孩子】
        else // 要左旋的节点是个右孩子
            pp.right = r; 
        r.left = p; // 要左旋的节点  作为 他的右孩子的左节点
        p.parent = r; // 要左旋的节点的右孩子  作为  他的父节点
    }
    return root; // 返回根节点
}
 
/**
 * 节点右旋
 * root 根节点
 * p 要右旋的节点
 */
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
    TreeNode<K,V> l, pp, lr;
    if (p != null && (l = p.left) != null) { // 要右旋的节点不为空以及要右旋的节点的左孩子不为空
        if ((lr = p.left = l.right) != null) // 要右旋的节点的左孩子的右节点 赋给 要右旋节点的左孩子 节点为：lr
            lr.parent = p; // 设置lr和要右旋的节点的父子关系【之前只是爹认了孩子，孩子还没有答应，这一步孩子也认了爹】
 
        // 将要右旋的节点的左孩子的父节点  指向 要右旋的节点的父节点，相当于左孩子提升了一层，
        // 此时如果父节点为空， 说明l 已经是顶层节点了，应该作为root 并且标为黑色
        if ((pp = l.parent = p.parent) == null) 
            (root = l).red = false;
        else if (pp.right == p) // 如果父节点不为空 并且 要右旋的节点是个右孩子
            pp.right = l; // 设置l和父节点的父子关系【之前只是孩子认了爹，爹还没有答应，这一步爹也认了孩子】
        else // 要右旋的节点是个左孩子
            pp.left = l; // 同上
        l.right = p; // 要右旋的节点 作为 他左孩子的右节点
        p.parent = l; // 要右旋的节点的父节点 指向 他的左孩子
    }
    return root;
}

ConcurrentHashMap

1、简介

​ ConcurrentHashMap是Java并发包中提供的一个线程安全且高效的HashMap实现。==ConcurrentHashMap不允许key或value为null值==。

2.为什么HashMap用于多线程会出错？：

​ JDK1.7 的 HashMap在高并发环境下会形成环状链表，导致get操作时，进入死循环，所以，在并发环境中使用HashMap是非常危险的。

3.为什么不用Hashtable？

​ HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

4、ConcurrentHashMap java7 中的实现方式

HashTable性能差主要是由于所有操作需要竞争同一把锁，而如果容器中有多把锁，每一把锁锁一段数据，这样在多线程访问时不同段的数据时，就不会存在锁竞争了，这样便可以有效地提高并发效率。这就是ConcurrentHashMap所采用的==”分段锁”==思想。

4.1 java7中的优缺点

​ ConcurrentHashMap采用了非常精妙的”分段锁”策略，ConcurrentHashMap的主干是个==Segment==数组。每个段其实==就是一个小的Hashtable==，它们有自己的锁。==只要多个修改操作发生在不同的段上，它们就可以并发进行。（JDK7中是这样实现的）==

​ ==但是！！！==有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里“按顺序”是很重要的，否则极有可能出现死锁.

​ 所以，对于同一个Segment的操作才需考虑线程同步，不同的Segment则无需考虑。

ConcurrentHashMap java8 中的实现

1、简介

​ JDK8：ConcurrentHashMap在JDK8中进行了巨大改动，它摒弃了Segment（锁段）的概念，而是启用了一种全新的方式实现,利用==CAS==算法。

2、什么是volatille关键字？

volatile是一种轻量级的同步机制，它主要有两个特性：

一是保证共享变量对所有线程的可见性；（==内存可见性==）

二是禁止指令重排序优化。同时需要注意的是，volatile对于单个的共享变量的读/写具有原子性，但是像num++这种复合操作（读写存），volatile无法保证其原子性。

==3、重要属性==

3.1 sizeCtl

​ 可以说它是ConcurrentHashMap中出镜率很高的一个属性，因为它是一个==控制标识符==，在不同的地方有不同用途，而且它的取值不同，也代表不同的含义。

• 负数代表正在进行初始化或扩容操作
• -1代表正在初始化
• -N 表示有N-1个线程正在进行扩容操作
• 正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小，==这一点类似于扩容阈值的概念==。还后面可以看到，它的值始终是当前ConcurrentHashMap容量的0.75倍，这与loadfactor是对应的

3.2初始化数组 initTable

​ 初始化方法主要应用了关键属性sizeCtl 如果这个值〈0，表示其他线程正在进行初始化，就放弃这个操作。在这也可以看出ConcurrentHashMap的==初始化只能由一个线程完成==。如果获得了初始化权限，就用CAS方法将sizeCtl置为-1，防止其他线程进入。初始化数组后，将sizeCtl的值改为0.75*n。

3.3 核心内容

• forword （(transfer)扩容时标记，碰到这个标记直接跳过），==类似于大家一起搭积木==
• Moved （在put时候碰到Moved ，则帮助其扩容 helptransfer）
• sizeCtl
• CAS
• Volatile（val 和 next 都用了）
• 以上五点保证了 ConcurrentHashMap 的高并发情况下的线程安全问题
• java7中只有1000多行代码，而在Java8中重新编写了现在有6000多行代码

==PUT流程：==

• 1、判断是否初始化过，没有则进行初始化。
• 2、通过Hash定位到数组的索引坐标，判断是否有Node 节点，
  • 如果没有则使用 CAS 进行添加，添加失败进入下次循环
• 3、检查到内部在扩容，就帮助他一块扩容（Moved ）
• 4、如果 Node 节点存在，则使用 synchronized 锁住头结点，
  • 如果是链表结构就进行链表的添加操作
    • 如果是红黑树结构就进行红黑树的添加操作
    • 5、判断链表的长度是否大于 8，如果大于就去转为树结构