Java集合 HashMap 源码分析

HashMap 介绍

1. HashMap是Map接口使用频率最高的实现类
2. HashMap是以key-val对的方式来存储数据（HashMap$Node)
3. key不能重复，但是值可以重复，允许使用null键和null值
4. 如果添加相同的key，则会覆盖原来的key-val，等同于修改（key不会替换，val会替换）
5. 与HashSet一样不保证映射的顺序，因为底层是以hash表的方式来存储的(jdk8 数组+链表+红黑树)
6. HashMap没有实现同步，线程不安全（线程安全的是ConcurrentHashMap）
7. 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
8. 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。

扩容机制

1. HashMap底层维护了Node类型的数组table，默认为null

2. 当创建对象时，将加载因子（loadfactor）初始化为0.75

3. 当添加key-val时，通过key的哈希值得到在table的索引，然后判断该索引处是否有元素，如果没有元素则直接添加，如果有元素，继续判断该元素的key是否和准备加入的key相等，如果相等则直接替换val，如果不相等则需要判断是树结构还是链表结果，做出相应处理，如果添加时发现容量不够，则需要扩容

4. 第一次添加，则需要扩容table容量为16，临界值（threshold）为12；(16*0.75=12)

5. 以后的扩容，则需要扩容table的容量为原来的2倍，临界值为原来的2倍，依次类推

6. 在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认8)，并且table大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化(红黑树)

   Node e; K k;
   if (p.hash == hash &&//这里判断了链表的头节点
       ((k = p.key) == key || (key != null && key.equals(k))))
       e = p;
   else if (p instanceof TreeNode)
       e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
   else {
       //binCount从0开始 然而之前已经比较过头结点 所以实际从第二个节点开始比较
       //binCount=0->第2个 
       //binCount >= TREEIFY_THRESHOLD - 1 即 binCount >= 7   [TREEIFY_THRESHOLD默认为8]
       //当binCount = 7 时 此时为第9个 才调用 treeifyBin()
       //结论 一条链表长度超过8个 才会调用treeifyBin()
       for (int binCount = 0; ; ++binCount) {
           if ((e = p.next) == null) {
               p.next = newNode(hash, key, value, null);
               if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                   treeifyBin(tab, hash);
               break;
           }
           if (e.hash == hash &&
               ((k = e.key) == key || (key != null && key.equals(k))))
               break;
           p = e;
       }
   }
   if (e != null) { // existing mapping for key
       V oldValue = e.value;
       if (!onlyIfAbsent || oldValue == null)
           e.value = value;
       afterNodeAccess(e);
       return oldValue;
   }
   

7. treefiBin()当table容量达到64才会树化 否则调用 resize()扩容

   final void treeifyBin(Node[] tab, int hash) {
       int n, index; Node e;
       //如果table为空或者容量小于64 [MIN_TREEIFY_CAOACITY默认为64]
       //则调用resize()扩容
       //否则进行树化（红黑树）
       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. untreeify()解除树化变回链表 节点数小于等于6则变回链表

   //lc 树的节点个数 UNTREEIFY_THRESHOLD（默认6）
   //节点数 <= 6 则变回链表
   if (lc <= UNTREEIFY_THRESHOLD)
       tab[index] = loHead.untreeify(map);
   

构造方法

HashMap() 构造一个空的 HashMap ，默认初始容量（16）和默认负载系数（0.75）。
HashMap(int initialCapacity) 构造一个空的 HashMap具有指定的初始容量和默认负载因子（0.75）。
HashMap(int initialCapacity, float loadFactor) 构造一个空的 HashMap具有指定的初始容量和负载因子。
HashMap(Map m) 构造一个新的 HashMap与指定的相同的映射 Map 。

方法

void	clear() 从这张Map中删除所有的映射。
Object	clone() 返回此 HashMap实例的浅拷贝：键和值本身不被克隆。
V	compute(K key, BiFunction remappingFunction) 尝试计算用于指定键和其当前映射的值的映射（或 null如果没有当前映射）。
V	computeIfAbsent(K key, Function mappingFunction) 如果指定的键尚未与值相关联（或映射到 null ），则尝试使用给定的映射函数计算其值，并将其输入到此映射中，除非 null 。
V	computeIfPresent(K key, BiFunction remappingFunction) 如果指定的密钥的值存在且非空，则尝试计算给定密钥及其当前映射值的新映射。
boolean	containsKey(Object key) 如果此映射包含指定键的映射，则返回 true 。
boolean	containsValue(Object value) 如果此Map将一个或多个键映射到指定值，则返回 true 。
Set>	entrySet() 返回此Map中包含的映射的Set视图。
void	forEach(BiConsumer action) 对此映射中的每个条目执行给定的操作，直到所有条目都被处理或操作引发异常。
V	get(Object key) 返回到指定键所映射的值，或 null如果此映射包含该键的映射。
V	getOrDefault(Object key, V defaultValue) 返回到指定键所映射的值，或 defaultValue如果此映射包含该键的映射。
boolean	isEmpty() 如果此Map不包含键值映射，则返回 true 。
Set	keySet() 返回此Map中包含的键的Set视图。
V	merge(K key, V value, BiFunction remappingFunction) 如果指定的键尚未与值相关联或与null相关联，则将其与给定的非空值相关联。
V	put(K key, V value) 将指定的值与此映射中的指定键相关联。
void	putAll(Map m) 将指定Map的所有映射复制到此Map。
V	putIfAbsent(K key, V value) 如果指定的键尚未与某个值相关联（或映射到 null ），则将其与给定值相关联并返回 null ，否则返回当前值。
V	remove(Object key) 从该Map中删除指定键的映射（如果存在）。
boolean	remove(Object key, Object value) 仅当指定的密钥当前映射到指定的值时删除该条目。
V	replace(K key, V value) 只有当目标映射到某个值时，才能替换指定键的条目。
boolean	replace(K key, V oldValue, V newValue) 仅当当前映射到指定的值时，才能替换指定键的条目。
void	replaceAll(BiFunction function) 将每个条目的值替换为对该条目调用给定函数的结果，直到所有条目都被处理或该函数抛出异常。
int	size() 返回此Map中键值映射的数量。
Collection	values() 返回此Map中包含的值的Collection视图。

内部基本属性常量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16：


static final int MAXIMUM_CAPACITY = 1 << 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;



transient Node[] table;


transient Set> entrySet;


transient int size;


transient int modCount;


int threshold;


final float loadFactor;

hash计算:

1、通过hashCode()的高16位异或低16位实现的：( h=k.hashCode())^(h>>>16))，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

2、计算组数下标：h&(table.length-1)，HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优。当length总是2的n次方时，h&(length-1)运算等价于对length取模，也就是h%length，但是&比％具有更高的效率。

put

如果已经存在则覆盖且返回原value，否则返回null
put过程:

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

// 第三个参数 onlyIfAbsent 如果是 true，那么只有在不存在该 key 时才会进行 put 操作
// 第四个参数 evict 我们这里不关心
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    // 第一次 put 值的时候，会触发下面的 resize()，类似 java7 的第一次 put 也要初始化数组长度
    // 第一次 resize 和后续的扩容有些不一样，因为这次是数组从 null 初始化到默认的 16 或自定义的初始容量
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 找到具体的数组下标，如果此位置没有值，那么直接初始化一下 Node 并放置在这个位置就可以了
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    else {// 数组该位置有数据
        Node e; K k;
        // 首先，判断该位置的第一个数据和我们要插入的数据，key 是不是"相等"，如果是，取出这个节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果该节点是代表红黑树的节点，调用红黑树的插值方法，本文不展开说红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
        else {
            // 到这里，说明数组该位置上是一个链表
            for (int binCount = 0; ; ++binCount) {
                // 插入到链表的最后面(Java7 是插入到链表的最前面)
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // TREEIFY_THRESHOLD 为 8，所以，如果新插入的值是链表中的第 8 个
                    // 会触发下面的 treeifyBin，也就是将链表转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果在该链表中找到了"相等"的 key(== 或 equals)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 此时 break，那么 e 为链表中[与要插入的新值的 key "相等"]的 node
                    break;
                p = e;
            }
        }
        // e!=null 说明存在旧值的key与要插入的key"相等"
        // 对于我们分析的put操作，下面这个 if 其实就是进行 "值覆盖"，然后返回旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值，需要进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

get

1、计算 key 的 hash 值，根据 hash 值找到对应数组下标: hash & (length-1)

2、判断数组该位置处的元素是否刚好就是我们要找的，如果不是，走第三步

3、判断该元素类型是否是 TreeNode，如果是，用红黑树的方法取数据，如果不是，走第四步

4、遍历链表，直到找到相等(==或equals)的 key

public V get(Object key) {
    //当前节点
    Node e;
    //获取当前节点，并返回节点的值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node getNode(int hash, Object key) {
    //当前表
    Node[] tab;
    Node first, e;
    int n;
    K k;
    //如果当前表不为null,且表长度大于0.并且找到桶的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //如果第一个就和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);
            //迭代链表，获取匹配的节点
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //没找到，返回null
    return null;
}

thresold、loadFactor

当 HashMap 中的 size >= threshold 时，HashMap 就要扩容。

• size：HashMap表中包含的键值映射的数目。
• threshold：要调整大小的下一个大小的阈值，等于(capacity * loadFactor)。
• capacity：HashMap容量
• loadFactor：哈希表的加载因子。

其中有一个tableSizeFor()方法的作用是： 找到>=这个值的一个2的次方数。

这个方法是在计算阈值thresold的时候调用的 (初始计算threshold的时候):

举例:

public class Main {
    public static void main(String[] args) {
        for(int i = 0; i < 35; i++){
            System.out.println(i + " -> " + tableSizeFor(i));
        }
    }

    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
}

输出:

0 -> 1
1 -> 1
2 -> 2
3 -> 4
4 -> 4
5 -> 8
6 -> 8
7 -> 8
8 -> 8
9 -> 16
10 -> 16
11 -> 16
12 -> 16
13 -> 16
14 -> 16
15 -> 16
16 -> 16
17 -> 32
18 -> 32
19 -> 32
20 -> 32
21 -> 32
22 -> 32
23 -> 32
24 -> 32
25 -> 32
26 -> 32
27 -> 32
28 -> 32
29 -> 32
30 -> 32
31 -> 32
32 -> 32
33 -> 64
34 -> 64

添加第一个元素时，默认分配的大小为16，不过，并不是size大于16时再进行扩展，下次什么时候扩展与threshold有关。

threshold表示阈值，当键值对个数size大于等于threshold时考虑进行扩展。threshold是怎么算出来的呢？初始阈值就是上面的tableSizeFor()方法计算得到，也就是和initCapity有关。

后面一般而言，threshold等于table.length乘以loadFactor，比如，如果table.length为16，loadFactor为0.75，则threshold为12，看下面的源码。

loadFactor是负载因子，表示整体上table被占用的程度，是一个浮点数，默认为0.75，可以通过构造方法进行修改。

HashMap 红黑树

原博客：https://www.cnblogs.com/mfrank/p/9227097.html

红黑树介绍

什么是红黑树？嗯，首先，它是一颗树，所谓的树，便是长的像这样的东西

不像树？emmmm，你把它想象成一颗倒过来的树就好了，A~H都是树的节点，每个节点有零个或者多个子节点，或者说多个孩子，但除了根节点以外，每个节点都只有一个父节点，也称只有一个父亲拿出来，则又是一颗树，称为树的子树。

好了，知道树是什么东西了，那么红黑树是什么样的呢？

红黑树，本质上来说是一颗二叉搜索树。嗯，还是先说说这个二叉搜索树吧。二叉代表它的节点最多有两个子节点，而且左右有顺序，不能颠倒，分别叫左孩子和右孩子，这两个节点互为兄弟节点，嗯，其实叫法根现实里的叫法差不多，以下图为例，4、9互为兄弟，7是他们的父亲，9是2的叔叔，8是2的堂兄弟，很简单吧。说完了称谓，再来说说用途，既然叫做搜索树表示它的用途是为了更快的搜索和查找而设计的，所以这棵树本身满足一定的排序规则，即树中的任何节点的值大于它的左孩子，且小于它的右孩子。 任意节点的左、右子树也分别为二叉查找树。嗯，结合下图意会一下：

而红黑树，就跟它的名字一样，又红又黑，红黑并进，理实交融，节点是非红即黑的，看起来就像这样

红黑树的主要特性:
　　（1）每个节点要么是黑色，要么是红色。（节点非黑即红）
　　（2）根节点是黑色。
　　（3）每个叶子节点（NIL）是黑色。
　　（4）如果一个节点是红色的，则它的子节点必须是黑色的。（也就是说父子节点不能同时为红色）
　　（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。（这一点是平衡的关键）

说简单也简单，其实就是一颗比较平衡的又红又黑的二叉树嘛。

TreeNode结构

既然我们已经知道红黑树长什么样了，那么我们再来看看HashMap中的TreeNode代码里是如何表示的：

    
    static final class TreeNode extends linkedHashMap.Entry {
        TreeNode parent;  // 红黑树父节点
        TreeNode left;
        TreeNode right;
        TreeNode prev;    // 删除后需要取消链接
        boolean red;
        TreeNode(int hash, K key, V val, Node next) {
            super(hash, key, val, next);
        }　　　　 //省略后续代码

TreeNode继承自linkedHashMap中的内部类——linkedHashMap.Entry，而这个内部类又继承自Node，所以算是Node的孙子辈了。我们再来看看它的几个属性，parent用来指向它的父节点，left指向左孩子，right指向右孩子，prev则指向前一个节点（原链表中的前一个节点），注意，这些字段跟Entry，Node中的字段一样，是使用默认访问权限的，所以子类可以直接使用父类的属性。

树化的过程

在前几篇中已经有所介绍，当HashMap桶中的元素个数超过一定数量时，就会树化，也就是将链表转化为红黑树的结构。

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

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        ...省略部分代码...
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //当桶中元素个数超过阈值（8）时就进行树化
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            treeifyBin(tab, hash);
                        break;
                    }
         ...省略部分代码...
    }

    final void treeifyBin(Node[] tab, int hash) {
        int n, index; Node e;
        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
                TreeNode p = replacementTreeNode(e, null);
                if (tl == null)　　　　　　　　　　　　//hd指向头结点
                    hd = p;
                else {
                    //这里其实是将单链表转化成了双向链表，tl是p的前驱，每次循环更新指向双链表的最后一个元素，用来和p相连，p是当前节点
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                //将链表进行树化
                hd.treeify(tab);
        }
    }  

从代码中可以看到，在treeifyBin函数中，先将所有节点替换为TreeNode，然后再将单链表转为双链表，方便之后的遍历和移动操作。而最终的操作，实际上是调用TreeNode的方法treeify进行的。

final void treeify(Node[] tab) {
            //树的根节点
            TreeNode root = null;
            //x是当前节点，next是后继
            for (TreeNode x = this, next; x != null; x = next) {
                next = (TreeNode)x.next;
                x.left = x.right = null;
                //如果根节点为null，把当前节点设置为根节点
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                }
                else {
                    K k = x.key;
                    int h = x.hash;
                    Class kc = null;
                    //这里循环遍历，进行二叉搜索树的插入
                    for (TreeNode p = root;;) {
                        //p指向遍历中的当前节点，x为待插入节点，k是x的key，h是x的hash值，ph是p的hash值，dir用来指示x节点与p的比较，-1表示比p小，1表示比p大，不存在相等情况，因为HashMap中是不存在两个key完全一致的情况。
                        int dir, ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        //如果hash值相等，那么判断k是否实现了comparable接口，如果实现了comparable接口就使用compareTo进行进行比较，如果仍旧相等或者没有实现comparable接口，则在tieBreakOrder中比较
                        else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);

                        TreeNode xp = p;
                        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;
                        }
                    }
                }
            }　　　　　　　//确保给定节点是桶中的第一个元素
            moveRootToFront(tab, root);
        }    
     //这里不是为了整体排序，而是为了在插入中保持一致的顺序
     static int tieBreakOrder(Object a, Object b) {
            int d;
            //用两者的类名进行比较，如果相同则使用对象默认的hashcode进行比较
            if (a == null || b == null ||
                (d = a.getClass().getName().
                 compareTo(b.getClass().getName())) == 0)
                d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                     -1 : 1);
            return d;
        }  

这里的逻辑其实不复杂，仅仅是循环遍历当前树，然后找到可以该节点可以插入的位置，依次和遍历节点比较，比它大则跟其右孩子比较，小则与其左孩子比较，依次遍历，直到找到左孩子或者右孩子为null的位置进行插入。

真正复杂一点的地方在于balanceInsertion函数，这个函数中，将红黑树进行插入平衡处理，保证插入节点后仍保持红黑树的性质。这个函数稍后在TreeNode的插入中进行介绍，这里先看看moveRootToFront，这个函数是将root节点移动到桶中的第一个元素，也就是链表的首节点，这样做是因为在判断桶中元素类型的时候会对链表进行遍历，将根节点移动到链表前端可以确保类型判断时不会出现错误。

        
    static  void moveRootToFront(Node[] tab, TreeNode root) {
            int n;
            if (root != null && tab != null && (n = tab.length) > 0) {
                int index = (n - 1) & root.hash;
                //first指向链表第一个节点
                TreeNode first = (TreeNode)tab[index];
                if (root != first) {
                    //如果root不是第一个节点，则将root放到第一个首节点位置
                    Node rn;
                    tab[index] = root;
                    TreeNode rp = root.prev;
                    if ((rn = root.next) != null)
                        ((TreeNode)rn).prev = rp;
                    if (rp != null)
                        rp.next = rn;
                    if (first != null)
                        first.prev = root;
                    root.next = first;
                    root.prev = null;
                }
                //这里是防御性编程，校验更改后的结构是否满足红黑树和双链表的特性
                //因为HashMap并没有做并发安全处理，可能在并发场景中意外破坏了结构
                assert checkInvariants(root);
            }
        }    

红黑树的左旋和右旋

左旋和右旋，顾名思义嘛，就是将节点以某个节点为中心向左或者向右进行旋转操作以保持二叉树的平衡，让我们看图说话

图画的有点大。将就着看一下吧，左旋相当于以要旋转的节点为中心，将子树整体向左旋转，该节点变成子树的根节点，原来的父节点A变成了左孩子，如果右孩子C有左孩子D，则将其变为A的右孩子。说起来好像有点绕，可以联系图进行形象化的理解，当节点A向左旋转之后，C的左孩子D可以理解为因为重力作用掉到A的右孩子位置，嗯，就是这样。右旋也是类似理解即可。

TreeNode的左旋和右旋

了解了左旋和右旋，让我们看看代码里是怎样实现的：

        
        static  TreeNode rotateLeft(TreeNode root,
                                              TreeNode p) {
            //这里的p即上图的A节点，r指向右孩子即C，rl指向右孩子的左孩子即D，pp为p的父节点
            TreeNode r, pp, rl;
            if (p != null && (r = p.right) != null) {
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                //将p的父节点的孩子节点指向r
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                //将p置为r的左节点
                r.left = p;
                p.parent = r;
            }
            return root;
        }

        
        static  TreeNode rotateRight(TreeNode root,
                                               TreeNode p) {
             //这里的p即上图的A节点，l指向左孩子即C，lr指向左孩子的右孩子即E，pp为p的父节点
            TreeNode l, pp, lr;
            if (p != null && (l = p.left) != null) {
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
        }

红黑树的插入

现在来看看一个比较麻烦一点的操作，红黑树的插入，首先找到这个节点要插入的位置，即一层一层比较，大的放右边，小的放左边，直到找到为null的节点放入即可，但是如何在插入的过程保持红黑树的特性呢，想想好像比较头疼，但是再仔细想想其实就会发现，其实只有这么几种情况：

1.插入的为根节点，则直接把颜色改成黑色即可。

2.插入的节点的父节点是黑色节点，则不需要调整，因为插入的节点会初始化为红色节点，红色节点是不会影响树的平衡的。

3.插入的节点的祖父节点为null，即插入的节点的父节点是根节点，直接插入即可（因为根节点肯定是黑色）。

4.插入的节点父节点和祖父节点都存在，并且其父节点是祖父节点的左节点。这种情况稍微麻烦一点，又分两种子情况：

i.插入节点的叔叔节点是红色，则将父亲节点和叔叔节点都改成黑色，然后祖父节点改成红色即可。

ii.插入节点的叔叔节点是黑色或不存在：

a.若插入节点是其父节点的右孩子，则将其父节点左旋，

b.若为左孩子，则将其父节点变成黑色节点，将其祖父节点变成红色节点，然后将其祖父节点右旋。

5.插入的节点父节点和祖父节点都存在，并且其父节点是祖父节点的右节点。这种情况跟上面是类似的，分两种子情况：

i.插入节点的叔叔节点是红色，则将父亲节点和叔叔节点都改成黑色，然后祖父节点改成红色即可。

ii.插入节点的叔叔节点是黑色或不存在：

a.若插入节点是其父节点的左孩子，则将其父节点右旋

b.若为右孩子，则将其父节点变成黑色节点，将其祖父节点变成红色节点，然后将其祖父节点左旋。

然后重复进行上述操作，直到变成1或2情况时则结束变换。说半天，可能还是云里雾里，一图胜千言，让我们从无到有构建一颗红黑树，假设插入的顺序为：10，5，9，3，6，7，19，32，24，17（数字是我拍脑袋瞎想的。）

先来插个10，为情景1，直接改成黑色即可，再插入5，为情景2，比10小，放到10的左孩子位置，插入9，比10小，但是比5大，放到5的右孩子位置，此时，为情景4iia，左旋后变成了情景4iib，变色右旋即可完成转化。插入3后为情景4i，将父节点和叔叔节点同时变色即可，插入6不需要调整，插入7后为情景5i，变色即可。插入19不需要调整，插入32，变成了5iib，左旋变色即可，插入24，变成5iia，右旋后变成5i，变色即可，最后插入17，完美。

TreeNode的插入

了解了红黑树的删除之后，我们再来看下TreeNode中是怎样用代码实现的：

      static  TreeNode balanceInsertion(TreeNode root,
                                                    TreeNode x) {
            x.red = true;
            for (TreeNode xp, xpp, xppl, xppr;;) {                //情景1：父节点为null
                if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }　　　　　　　　　 //情景2，3：父节点是黑色节点或者祖父节点为null
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;　　　　　　　　　　//情景4：插入的节点父节点和祖父节点都存在，并且其父节点是祖父节点的左节点
                if (xp == (xppl = xpp.left)) {　　　　　　　　　　　　//情景4i：插入节点的叔叔节点是红色
                    if ((xppr = xpp.right) != null && xppr.red) {
                        xppr.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }　　　　　　　　　　　　//情景4ii：插入节点的叔叔节点是黑色或不存在
                    else {　　　　　　　　　　　　　　//情景4iia：插入节点是其父节点的右孩子
                        if (x == xp.right) {
                            root = rotateLeft(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }　　　　　　　　　　　　　　//情景4iib：插入节点是其父节点的左孩子
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateRight(root, xpp);
                            }
                        }
                    }
                }　　　　　　　　　 //情景5：插入的节点父节点和祖父节点都存在，并且其父节点是祖父节点的右节点
                else {　　　　　　　　　　　　//情景5i：插入节点的叔叔节点是红色
                    if (xppl != null && xppl.red) {
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }　　　　　　　　　　　　//情景5ii：插入节点的叔叔节点是黑色或不存在
                    else {·　　　　　　　　　　　　　　//情景5iia：插入节点是其父节点的左孩子　
                        if (x == xp.left) {
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }　　　　　　　　　　　　　　//情景5iib：插入节点是其父节点的右孩子
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }

其实就是一毛一样的，对号入座即可。

红黑树的删除

讲完插入，接下来我们来说说删除，删除的话，比插入还要复杂一点，请各位看官先深呼吸，做好阅读准备。

之前已经说过，红黑树是一颗特殊的二叉搜索树，所以进行删除操作时，其实是先进行二叉搜索树的删除，然后再进行调整。所以，其实这里分为两部分内容：1.二叉搜索树的删除，2.红黑树的删除调整。

二叉搜索树的删除主要有这么几种情景：

情景1：待删除的节点无左右孩子。

情景2：待删除的节点只有左孩子或者右孩子。

情景3：待删除的节点既有左孩子又有右孩子。

对于情景1，直接删除即可，情景2，则直接把该节点的父节点指向它的左孩子或者右孩子即可，情景3稍微复杂一点，需要先找到其右子树的最左孩子（或者左子树的最右孩子），即左（右）子树中序遍历时的第一个节点，然后将其与待删除的节点互换，最后再删除该节点（如果有右子树，则右子树上位）。总之，就是先找到它的替代者，找到之后替换这个要删除的节点，然后再把这个节点真正删除掉。

其实二叉搜索树的删除总体来说还是比较简单的，删除完之后，如果替代者是红色节点，则不需要调整，如果是黑色节点，则会导致左子树和右子树路径中黑色节点数量不一致，需要进行红黑树的调整，跟上面一样，替代节点为其父节点的左孩子与右孩子的情况类似，所以这里只说其为左孩子的情景（PS:上一步的寻找替换节点使用的是右子树的最左节点，所以该节点如果有孩子，只能是右孩子）：

情景1：只有右孩子且为红色，直接用右孩子替换该节点然后变成黑色即可。

（D代表替代节点，即要被删除的节点，之前在经过二叉搜索树的删除后，D节点其实已经被删除了，这里为了方便理解这个变化过程，所以把这个节点也画出来了，所以当前的初始状态是待删除节点与其替换节点互换位置与颜色之后的状态）

情景2：只有右孩子且为黑色，那么删除该节点会导致父节点的左子树路径上黑色节点减一，此时只能去借助右子树，从右子树中借一个红色节点过来即可，具体取决于右子树的情况，这里又分成两种：

i.兄弟节点是红色，则此时父节点是黑色，且兄弟节点肯定有两个孩子，且兄弟节点的左右子树路径上均有两个黑色节点，此时只需将兄弟节点与父节点颜色互换，然后将父节点左旋，左旋后，兄弟节点的左子树SL挂到了父节点p的右孩子位置，这时会导致p的右子树路径上的黑色节点比左子树多一，此时再SL置为红色即可。

ii.兄弟节点是黑色，那么就只能打它孩子的主意了，这里主要关注远侄子（兄弟节点的右孩子，即SR）的颜色情况，这里分成两种情况：

a.远侄子SR是黑色，近侄子任意（白色代表颜色可为任意颜色），则先将S转为红色，然后右旋，再将SL换成P节点颜色，P涂成黑色，S也涂成黑色，再进行左旋即可。其实简单说就是SL上位，替换父节点位置。

b.远侄子SR为红色，近侄子任意（该子树路径中有且仅有一个黑色节点），则先将兄弟节点与父节点颜色互换，将SR涂成黑色，再将父节点左旋即可。

TreeNode的删除节点

TreeNode删除节点其实也是两步走，先进行二叉搜索树的删除，然后再进行红黑树的调整，跟之前的情况分析是一致的。

final void removeTreeNode(HashMap map, Node[] tab, boolean movable) {

     ......

     //p是待删除节点，replacement用于后续的红黑树调整，指向的是p或者p的继承者。
     //如果p是叶子节点，p==replacement，否则replacement为p的右子树中最左节点
     if (replacement != p) {
        //若p不是叶子节点，则让replacement的父节点指向p的父节点
        TreeNode pp = replacement.parent = p.parent;
        if (pp == null)
            root = replacement;
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;
        p.left = p.right = p.parent = null;
    }

    //若待删除的节点p时红色的，则树平衡未被破坏，无需进行调整。
    //否则删除节点后需要进行调整
    TreeNode r = p.red ? root : balanceDeletion(root, replacement);

    //p为叶子节点，则直接将p从树中清除
    if (replacement == p) {  // detach
        TreeNode pp = p.parent;
        p.parent = null;
        if (pp != null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }
}

麻烦的地方就在删除节点后的调整了，所有逻辑都在balanceDeletion函数里，两个参数分别表示根节点和删除节点的继承者，来看看它的具体实现：

static  TreeNode balanceDeletion(TreeNode root, TreeNode x) {
    for (TreeNode xp, xpl, xpr;;)  {
        //x为空或x为根节点，直接返回
        if (x == null || x == root)
            return root; 
        //x为根节点，染成黑色，直接返回（因为调整过后，root并不一定指向删除操作过后的根节点，如果之前删除的是root节点，则x将成为新的根节点）
        else if ((xp = x.parent) == null) {
            x.red = false; 
            return x;
        }
        //如果x为红色，则无需调整，返回
        else if (x.red) {
            x.red = false;
            return root; 
        }
        //x为其父节点的左孩子
        else if ((xpl = xp.left) == x) {
            //如果它有红色的兄弟节点xpr，那么它的父亲节点xp一定是黑色节点
            if ((xpr = xp.right) != null && xpr.red) { 
                xpr.red = false;
                xp.red = true; 
                //对父节点xp做左旋转
                root = rotateLeft(root, xp); 
                //重新将xp指向x的父节点，xpr指向xp新的右孩子
                xpr = (xp = x.parent) == null ? null : xp.right; 
            }
            //如果xpr为空，则向上继续调整，将x的父节点xp作为新的x继续循环
            if (xpr == null)
                x = xp; 
            else {
                //sl和sr分别为其近侄子和远侄子
                TreeNode sl = xpr.left, sr = xpr.right;　　　　　　　　　　　　
                if ((sr == null || !sr.red) &&
                    (sl == null || !sl.red)) {
                    xpr.red = true; //若sl和sr都为黑色或者不存在，即xpr没有红色孩子，则将xpr染红
                    x = xp; //本轮结束，继续向上循环
                }
                else {
                    //否则的话，就需要进一步调整
                    if (sr == null || !sr.red) { 
                        if (sl != null) //若左孩子为红，右孩子不存在或为黑
                            sl.red = false; //左孩子染黑
                        xpr.red = true; //将xpr染红
                        root = rotateRight(root, xpr); //右旋
                        xpr = (xp = x.parent) == null ?
                            null : xp.right;  //右旋后，xpr指向xp的新右孩子，即上一步中的sl
                    }
                    if (xpr != null) {
                        xpr.red = (xp == null) ? false : xp.red; //xpr染成跟父节点一致的颜色，为后面父节点xp的左旋做准备
                        if ((sr = xpr.right) != null)
                            sr.red = false; //xpr新的右孩子染黑，防止出现两个红色相连
                    }
                    if (xp != null) {
                        xp.red = false; //将xp染黑，并对其左旋，这样就能保证被删除的X所在的路径又多了一个黑色节点，从而达到恢复平衡的目的
                        root = rotateLeft(root, xp);
                    }
                    //到此调整已经完毕，进入下一次循环后将直接退出
                    x = root;
                }
            }
        }
        //x为其父节点的右孩子，跟上面类似
        else { // symmetric
            if (xpl != null && xpl.red) {
                xpl.red = false;
                xp.red = true;
                root = rotateRight(root, xp);
                xpl = (xp = x.parent) == null ? null : xp.left;
            }
            if (xpl == null)
                x = xp;
            else {
                TreeNode sl = xpl.left, sr = xpl.right;
                if ((sl == null || !sl.red) &&
                    (sr == null || !sr.red)) {
                    xpl.red = true;
                    x = xp;

基础部分源码

public class HashMap extends AbstractMap
        implements Map, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;

    

    
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16：

    
    static final int MAXIMUM_CAPACITY = 1 << 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;

    
    static class Node implements Entry {
        // 哈希值
        final int hash;
        // 键
        final K key;
        // 值
        V value;
        // 写一个Node节点的引用
        Node next;

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final String toString() {
            return key + "=" + value;
        }

        public final int hashCode() {
            // 位异或运算（^）：两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1
            return Objects.hashCode(key) ^ Objects.hashCode(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;
            if (o instanceof Map.Entry) {
                Entry e = (Entry) o;
                if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

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

    
    static Class comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class c;
            Type[] ts, as;
            Type t;
            ParameterizedType p;
            //如果是String类型，直接返回String.class
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;
            //获取所有的实现接口，迭代
            if ((ts = c.getGenericInterfaces()) != null) {
                for (int i = 0; i < ts.length; ++i) {
                    //如果为参数化类型，且为Comparable
                    if (((t = ts[i]) instanceof ParameterizedType) &&
                            ((p = (ParameterizedType) t).getRawType() ==
                                    Comparable.class) &&
                            (as = p.getActualTypeArguments()) != null &&
                            as.length == 1 && as[0] == c) // type arg is c
                        return c;
                }
            }
        }
        return null;
    }

    
    @SuppressWarnings({"rawtypes", "unchecked"}) // for cast to Comparable
    static int compareComparables(Class kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable) k).compareTo(x));
    }

    
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    

    
    transient Node[] table;

    
    transient Set> entrySet;

    
    transient int size;

    
    transient int modCount;

    
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

    
    final float loadFactor;

    

    
    public HashMap(int initialCapacity, float loadFactor) {
        //初始容量不能小于0
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        //初始容量最大为2^30
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //加载因子不能小于等于0
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);
        this.loadFactor = loadFactor;
        //扩容阈值，2的n次幂
        this.threshold = tableSizeFor(initialCapacity);
    }

    
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

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

    
    public HashMap(Map m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    
    final void putMapEntries(Map m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            //如果第一次初始化
            if (table == null) { // pre-size
                float ft = ((float) s / loadFactor) + 1.0F;
                int t = ((ft < (float) MAXIMUM_CAPACITY) ?
                        (int) ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    // 算出阈值
                    threshold = tableSizeFor(t);
            } else if (s > threshold)
                // 需要扩容
                resize();
            for (Entry e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                //元素入map
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

    
    public int size() {
        return size;
    }

    
    public boolean isEmpty() {
        return size == 0;
    }

    
    public V get(Object key) {
        //当前节点
        Node e;
        //获取当前节点，并返回节点的值
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    
    final Node getNode(int hash, Object key) {
        //当前表
        Node[] tab;
        Node first, e;
        int n;
        K k;
        //如果当前表不为null,且表长度大于0.并且找到桶的位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
            //如果第一个就和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);
                //迭代链表，获取匹配的节点
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        //没找到，返回null
        return null;
    }

    
    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

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

    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //当前表
        Node[] tab;
        //桶
        Node p;
        //n:表长度
        //i:桶在表中的索引
        int n, i;
        //如果当前表为null或者表长度为0
        if ((tab = table) == null || (n = tab.length) == 0)
            //扩容操作,初始化
            n = (tab = resize()).length;
        //如果 键所在的桶 为null
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 新建桶
            tab[i] = newNode(hash, key, value, null);

            //如果 键所在的桶 不为null
        else {
            //当前key节点
            Node e;
            K k;
            //确认桶的位置
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
                //如果是红黑树
            else if (p instanceof TreeNode)
                //红黑树新增节点 后期分析
                e = ((TreeNode) p).putTreeval(this, tab, hash, key, value);
            else {
                //循环
                for (int binCount = 0; ; ++binCount) {
                    //如果桶的下一个节点为null
                    if ((e = p.next) == null) {
                        //创建节点
                        p.next = newNode(hash, key, value, null);
                        //如果大于树化阈值
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //将链表转为红黑树，后期分析
                            treeifyBin(tab, hash);
                        //跳出循环
                        break;
                    }
                    //在链表中找到了key
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        //跳出循环
                        break;
                    p = e;
                }
            }
            //存在key节点
            if (e != null) { // existing mapping for key
                //老的值
                V oldValue = e.value;
                // onlyIfAbsent如果为真，则不要更改现有值
                if (!onlyIfAbsent || oldValue == null)
                    //更改现有值
                    e.value = value;
                //回调
                afterNodeAccess(e);
                //返回旧的值
                return oldValue;
            }
        }
        //修改计数器加一
        ++modCount;
        //判断是否需要扩容
        if (++size > threshold)
            //扩容操作
            resize();
        //回调
        afterNodeInsertion(evict);
        //返回null
        return null;
    }

    
    final Node[] resize() {
        //老的表，有可能为null
        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;
            } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 新的表长度变为以前老表长度的2倍
                newThr = oldThr << 1; // double threshold
        } else if (oldThr > 0) // initial capacity was placed in threshold
            //如果老的阈值大于0，且老的表长度为0，则新表容量设置为老阈值
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            //初始阈值为零表示使用默认值：16
            newCap = DEFAULT_INITIAL_CAPACITY;
            //扩容阈值：16*0.75
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //如果新的阈值为0，则根据新的表容量计算出。
        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[] newTab = (Node[]) new Node[newCap];
        // 使用新表
        table = newTab;
        //如果老表内有数据，则取出来，放到新表中，耗时的操作
        if (oldTab != null) {
            //迭代老的表
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                //如果表中桶内容不为null
                if ((e = oldTab[j]) != null) {
                    //清空，help GC
                    oldTab[j] = null;
                    //如果桶中不存在下一个节点
                    if (e.next == null)
                        //将此桶计算hash,重新放入新桶中
                        newTab[e.hash & (newCap - 1)] = e;
                        //如果桶中元素为树形节点
                    else if (e instanceof TreeNode)
                        // 将树仓中的节点拆分为上下树仓，如果太小，则取消树仓。仅从resize调用;
                        // 红黑树这后面专门分析
                        ((TreeNode) e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        //是链表结构，且后面有节点，进行链表复制
                        //它并没有重新计算元素在数组中的位置
                        //而是采用了原始位置加原数组长度的方法计算得到位置


                        //位置没有变化的，放到lo
                        Node loHead = null, loTail = null;

                        //位置发生变化的，当到hi
                        Node hiHead = null, hiTail = null;
                        //下一个节点
                        Node next;
                        do {
                            //下一个节点
                            next = e.next;
                            // (e.hash & oldCap) 得到的是 元素的在数组中的位置是否需要移动,示例如下
                            // 示例1：
                            // e.hash=10 0000 1010
                            // oldCap=16 0001 0000
                            //	 &   =0	 0000 0000       比较高位的第一位 0
                            //结论：元素位置在扩容后数组中的位置没有发生改变

                            // 示例2：
                            // e.hash=17 0001 0001
                            // oldCap=16 0001 0000
                            //	 &   =1	 0001 0000      比较高位的第一位   1

                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            } 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) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

    
    final void treeifyBin(Node[] tab, int hash) {
        int n, index;
        Node e;
        //如果表为null 或者表容量小于 最小树化容量64
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            //扩容
            resize();
            //确定表中桶的位置，且不为null
        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);
        }
    }

    
    public void putAll(Map m) {
        putMapEntries(m, true);
    }

    
    public V remove(Object key) {
        Node e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
    }

    
    final Node removeNode(int hash, Object key, Object value,
                                boolean matchValue, boolean movable) {
        Node[] tab;
        Node p;
        int n, index;
        //表不为空，且定位到桶的位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) {
            Node node = null, e;
            K k;
            V v;
            //获取到当前节点
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
                //如果存在下一个节点
            else if ((e = p.next) != null) {
                //是红黑树
                if (p instanceof TreeNode)
                    node = ((TreeNode) p).getTreeNode(hash, key);
                else {
                    //迭代链表
                    do {
                        if (e.hash == hash &&
                                ((k = e.key) == key ||
                                        (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            //取到键
            if (node != null && (!matchValue || (v = node.value) == value ||
                    (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    //删除树节点
                    ((TreeNode) node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    //链表节点置空
                    tab[index] = node.next;
                else
                    //将节点链接到删除节点的下一个
                    p.next = node.next;
                //修改次数+1
                ++modCount;
                //数量-1
                --size;
                //回调
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

    
    public void clear() {
        Node[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }

    
    public boolean containsValue(Object value) {
        Node[] tab;
        V v;
        if ((tab = table) != null && size > 0) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                            (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }
}

红黑树源码

static final class TreeNode extends linkedHashMap.Entry {
    // 父节点
    TreeNode parent;  // red-black tree
    // 左节点
    TreeNode left;
    // 右节点
    TreeNode right;
    // 删除后需要断开next链接
    TreeNode prev;    // needed to unlink next upon deletion
    //是否为红节点
    boolean red;

    TreeNode(int hash, K key, V val, Node next) {
        super(hash, key, val, next);
    }

    
    final TreeNode root() {
        //向上迭代，获取到根节点，根节点的父节点为null
        for (TreeNode r = this, p; ; ) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }

    
    static  void moveRootToFront(Node[] tab, TreeNode root) {
        int n;
        //root不为空，表不为空
        if (root != null && tab != null && (n = tab.length) > 0) {
            //root在表中的位置（相当于取模）
            int index = (n - 1) & root.hash;
            //获取树形桶第一个节点
            TreeNode first = (TreeNode) tab[index];
            //如果root引用不是第一个节点
            if (root != first) {
                Node rn;
                //root放在第一个索引位置
                tab[index] = root;
                //根节点的前驱
                TreeNode rp = root.prev;
                //如果根节点的后继不为空
                if ((rn = root.next) != null)
                    //跟节点后继的前驱指向根节点的前驱
                    ((TreeNode) rn).prev = rp;
                //根节点的前驱不为空
                if (rp != null)
                    //根节点后继直接指向前驱
                    rp.next = rn;
                //如果树形桶第一个节点不为空
                if (first != null)
                    //第一个节点的前驱指向根节点
                    first.prev = root;
                //根节点的后继指向first
                root.next = first;
                //根节点的前驱置为null
                root.prev = null;
            }
            assert checkInvariants(root);
        }
    }

    
    final TreeNode find(int h, Object k, Class kc) {
        TreeNode p = this;
        //只要p不为null就一直循环
        do {
            int ph, dir;
            K pk;
            TreeNode pl = p.left, pr = p.right, q;
            //如果p的hash 大于 h
            if ((ph = p.hash) > h)
                //向左找
                p = pl;
            else if (ph < h)
                //如果p的hash 大于 h，向右找
                p = pr;
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                //找到了，则返回p
                return p;
            else if (pl == null)
                //左边全都遍历结束，找右边的
                p = pr;
            else if (pr == null)
                //右边全都遍历结束，找左边的
                p = pl;
            else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0)
                p = (dir < 0) ? pl : pr;
            else if ((q = pr.find(h, k, kc)) != null) //递归调用
                return q;
            else
                p = pl;
        } while (p != null);
        //没找到返回null
        return null;
    }

    
    final TreeNode getTreeNode(int h, Object k) {
        return ((parent != null) ? root() : this).find(h, k, null);
    }

    
    static int tieBreakOrder(Object a, Object b) {
        //返回与默认方法hashCode()返回的相同的给定对象的散列代码，无论给定对象的类是否覆盖hashCode()。
        int d;
        if (a == null || b == null ||
                (d = a.getClass().getName().
                        compareTo(b.getClass().getName())) == 0)
            d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                    -1 : 1);
        return d;
    }

    
    final void treeify(Node[] tab) {
        TreeNode root = null;
        for (TreeNode x = this, next; x != null; x = next) {
            //x节点的后继
            next = (TreeNode) x.next;
            x.left = x.right = null;

            //如果根节点为空
            if (root == null) {
                //初始化根节点（黑色）
                x.parent = null;
                x.red = false;
                root = x;
            } else {
                //如果根节点非空
                K k = x.key;
                int h = x.hash;
                Class kc = null;

                for (TreeNode p = root; ; ) {
                    int dir, ph;
                    K pk = p.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;
                    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;
                    }
                }
            }
        }
        //将根节点转移到树形桶的第一个位置
        moveRootToFront(tab, root);
    }

    
    final Node untreeify(HashMap map) {
        Node hd = null, tl = null;
        for (Node q = this; q != null; q = q.next) {
            Node p = map.replacementNode(q, null);
            if (tl == null)
                hd = p;
            else
                tl.next = p;
            tl = p;
        }
        return hd;
    }

    
    final TreeNode putTreeval(HashMap map, Node[] tab,
                                    int h, K k, V v) {
        Class kc = null;
        boolean searched = false;
        //返回包含此节点的树的根
        TreeNode root = (parent != null) ? root() : this;
        for (TreeNode p = root; ; ) {
            int dir, ph;
            K pk;
            //找到待插入的位置
            if ((ph = p.hash) > h)
                dir = -1;
            else if (ph < h)
                dir = 1;
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                //返回插入的节点
                return p;
            else if ((kc == null &&
                    (kc = comparableClassFor(k)) == null) ||
                    (dir = compareComparables(kc, k, pk)) == 0) {
                if (!searched) {
                    TreeNode q, ch;
                    searched = true;
                    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;
                }
                dir = tieBreakOrder(k, pk);
            }
            //判断插到哪个位置
            TreeNode xp = p;
            if ((p = (dir <= 0) ? p.left : p.right) == null) {
                Node xpn = xp.next;
                TreeNode x = map.newTreeNode(h, k, v, xpn);
                if (dir <= 0)
                    xp.left = x;
                else
                    xp.right = x;
                xp.next = x;
                x.parent = x.prev = xp;
                if (xpn != null)
                    ((TreeNode) xpn).prev = x;
                //将根节点转移到树形桶的第一个位置，平衡插入的节点
                moveRootToFront(tab, balanceInsertion(root, x));
                return null;
            }
        }
    }

    
    final void removeTreeNode(HashMap map, Node[] tab,
                              boolean movable) {
        int n;
        if (tab == null || (n = tab.length) == 0)
            return;
        int index = (n - 1) & hash;
        TreeNode first = (TreeNode) tab[index], root = first, rl;
        TreeNode succ = (TreeNode) next, pred = prev;
        if (pred == null)
            tab[index] = first = succ;
        else
            pred.next = succ;
        if (succ != null)
            succ.prev = pred;
        if (first == null)
            return;
        if (root.parent != null)
            root = root.root();
        if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) {
            //转为链表
            tab[index] = first.untreeify(map);  // too small
            return;
        }
        TreeNode p = this, pl = left, pr = right, replacement;
        if (pl != null && pr != null) {
            TreeNode s = pr, sl;
            while ((sl = s.left) != null) // find successor
                s = sl;
            boolean c = s.red;
            s.red = p.red;
            p.red = c; // swap colors
            TreeNode sr = s.right;
            TreeNode pp = p.parent;
            if (s == pr) { // p was s's direct parent
                p.parent = s;
                s.right = p;
            } else {
                TreeNode sp = s.parent;
                if ((p.parent = sp) != null) {
                    if (s == sp.left)
                        sp.left = p;
                    else
                        sp.right = p;
                }
                if ((s.right = pr) != null)
                    pr.parent = s;
            }
            p.left = null;
            if ((p.right = sr) != null)
                sr.parent = p;
            if ((s.left = pl) != null)
                pl.parent = s;
            if ((s.parent = pp) == null)
                root = s;
            else if (p == pp.left)
                pp.left = s;
            else
                pp.right = s;
            if (sr != null)
                replacement = sr;
            else
                replacement = p;
        } else if (pl != null)
            replacement = pl;
        else if (pr != null)
            replacement = pr;
        else
            replacement = p;
        if (replacement != p) {
            TreeNode pp = replacement.parent = p.parent;
            if (pp == null)
                root = replacement;
            else if (p == pp.left)
                pp.left = replacement;
            else
                pp.right = replacement;
            p.left = p.right = p.parent = null;
        }
        //平衡删除
        TreeNode r = p.red ? root : balanceDeletion(root, replacement);

        if (replacement == p) {  // detach
            TreeNode pp = p.parent;
            p.parent = null;
            if (pp != null) {
                if (p == pp.left)
                    pp.left = null;
                else if (p == pp.right)
                    pp.right = null;
            }
        }
        if (movable)
            moveRootToFront(tab, r);
    }

    
    final void split(HashMap map, Node[] tab, int index, int bit) {
        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;
            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) {
            if (lc <= UNTREEIFY_THRESHOLD)
                //变成链表
                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);
            }
        }
    }

    
    // Red-black tree methods, all adapted from CLR


    //树的左旋
    static  TreeNode rotateLeft(TreeNode root,
                                            TreeNode p) {
        TreeNode r, pp, rl;
        if (p != null && (r = p.right) != null) {
            if ((rl = p.right = r.left) != null)
                rl.parent = p;
            if ((pp = r.parent = p.parent) == null)
                (root = r).red = false;
            else if (pp.left == p)
                pp.left = r;
            else
                pp.right = r;
            r.left = p;
            p.parent = r;
        }
        return root;
    }

    //右旋
    static  TreeNode rotateRight(TreeNode root,
                                             TreeNode p) {
        TreeNode l, pp, lr;
        if (p != null && (l = p.left) != null) {
            if ((lr = p.left = l.right) != null)
                lr.parent = p;
            if ((pp = l.parent = p.parent) == null)
                (root = l).red = false;
            else if (pp.right == p)
                pp.right = l;
            else
                pp.left = l;
            l.right = p;
            p.parent = l;
        }
        return root;
    }

    
    static  TreeNode balanceInsertion(TreeNode root, TreeNode x) {
        //将插入的节点置为红色
        x.red = true;
        //xp 待插入节点的父节点
        //xpp 待插入节点的祖节点
        //xppl 祖节点的左孩子，左叔叔
        for (TreeNode xp, xpp, xppl, xppr; ; ) {
            //  待插入节点的父节点为空，则当前插入的节点为根节点
            if ((xp = x.parent) == null) {
                //置为黑色
                x.red = false;
                return x;
                //如果父节点是黑色的，或者不存在祖节点
            } else if (!xp.red || (xpp = xp.parent) == null)
                //返回根节点
                return root;
            //父节点是祖节点的左孩子
            if (xp == (xppl = xpp.left)) {
                if ((xppr = xpp.right) != null && xppr.red) {
                    xppr.red = false;
                    xp.red = false;
                    xpp.red = true;
                    x = xpp;
                } else {
                    if (x == xp.right) {

                        root = rotateLeft(root, x = xp);
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                    if (xp != null) {
                        xp.red = false;
                        if (xpp != null) {
                            xpp.red = true;
                            root = rotateRight(root, xpp);
                        }
                    }
                }
            } 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);
                        }
                    }
                }
            }
        }
    }

    //看的我脑壳疼，穷举出所有删除后影响的情况，一一解决
    static  TreeNode balanceDeletion(TreeNode root,
                                                 TreeNode x) {
        for (TreeNode xp, xpl, xpr; ; ) {
            if (x == null || x == root)
                return root;
            else if ((xp = x.parent) == null) {
                x.red = false;
                return x;
            } else if (x.red) {
                x.red = false;
                return root;
            } else if ((xpl = xp.left) == x) {
                if ((xpr = xp.right) != null && xpr.red) {
                    xpr.red = false;
                    xp.red = true;
                    root = rotateLeft(root, xp);
                    xpr = (xp = x.parent) == null ? null : xp.right;
                }
                if (xpr == null)
                    x = xp;
                else {
                    TreeNode sl = xpr.left, sr = xpr.right;
                    if ((sr == null || !sr.red) &&
                            (sl == null || !sl.red)) {
                        xpr.red = true;
                        x = xp;
                    } else {
                        if (sr == null || !sr.red) {
                            if (sl != null)
                                sl.red = false;
                            xpr.red = true;
                            root = rotateRight(root, xpr);
                            xpr = (xp = x.parent) == null ?
                                    null : xp.right;
                        }
                        if (xpr != null) {
                            xpr.red = (xp == null) ? false : xp.red;
                            if ((sr = xpr.right) != null)
                                sr.red = false;
                        }
                        if (xp != null) {
                            xp.red = false;
                            root = rotateLeft(root, xp);
                        }
                        x = root;
                    }
                }
            } else { // symmetric
                if (xpl != null && xpl.red) {
                    xpl.red = false;
                    xp.red = true;
                    root = rotateRight(root, xp);
                    xpl = (xp = x.parent) == null ? null : xp.left;
                }
                if (xpl == null)
                    x = xp;
                else {
                    TreeNode sl = xpl.left, sr = xpl.right;
                    if ((sl == null || !sl.red) &&
                            (sr == null || !sr.red)) {
                        xpl.red = true;
                        x = xp;
                    } else {
                        if (sl == null || !sl.red) {
                            if (sr != null)
                                sr.red = false;
                            xpl.red = true;
                            root = rotateLeft(root, xpl);
                            xpl = (xp = x.parent) == null ?
                                    null : xp.left;
                        }
                        if (xpl != null) {
                            xpl.red = (xp == null) ? false : xp.red;
                            if ((sl = xpl.left) != null)
                                sl.red = false;
                        }
                        if (xp != null) {
                            xp.red = false;
                            root = rotateRight(root, xp);
                        }
                        x = root;
                    }
                }
            }
        }
    }

    
    static  boolean checkInvariants(TreeNode t) {
        TreeNode tp = t.parent, tl = t.left, tr = t.right,
                tb = t.prev, tn = (TreeNode) t.next;
        if (tb != null && tb.next != t)
            return false;
        if (tn != null && tn.prev != t)
            return false;
        if (tp != null && t != tp.left && t != tp.right)
            return false;
        if (tl != null && (tl.parent != t || tl.hash > t.hash))
            return false;
        if (tr != null && (tr.parent != t || tr.hash < t.hash))
            return false;
        if (t.red && tl != null && tl.red && tr != null && tr.red)
            return false;
        if (tl != null && !checkInvariants(tl))
            return false;
        if (tr != null && !checkInvariants(tr))
            return false;
        return true;
    }
}