1 TreeMap基本介绍

• Java TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序
• key大小的评判可以通过其本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器(Comparator)。
• TreeMap底层通过红黑树实现
• TreeMap是非同步的。可以通过如下方式将TreeMap包装成同步的：SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
• TreeMap 跟 HashMap是两种不同的结构，TreeMap没有使用hash相关概念

2 红黑树数据结构回顾

1. 每个节点颜色不是黑色，就是红色
2. 根节点是黑色的
3. 红色节点不能连续
4. 对于每个节点，从该节点到其树尾端的简单路径上，均包含相同数目的黑色节点

3 成员变量

    private final Comparator<? super K> comparator;  //排序器，如果空，按照key的字典顺序来排序（升序）；comparator为空时用Comparable的排序接口
    private transient Entry<K,V> root; //根节点
    private transient int size = 0; //树中entry个数 ，即红黑树大小
    private transient int modCount = 0;  //数结构被修改的次数的
     /**
     * Fields initialized to contain an instance of the entry set view
     * the first time this view is requested.  Views are stateless, so
     * there's no reason to create more than one.
     */
    private transient EntrySet entrySet;
    private transient KeySet<K> navigableKeySet;
    private transient NavigableMap<K,V> descendingMap;
     /**
     * Dummy value serving as unmatchable fence key for unbounded
     * SubMapIterators
     */
    private static final Object UNBOUNDED = new Object();
    private static final boolean RED   = false; //红节点 默认false
    private static final boolean BLACK = true;  // 黑节点 默认true

4 内部类Entry

它是组成树的节点的类型

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;   // key
        V value;  //value
        Entry<K,V> left; //左孩子
        Entry<K,V> right;  //右孩子
        Entry<K,V> parent;  //父节点
        boolean color = BLACK;  //默认黑色
        //根据 key  value 父节点创建新节点
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
        public K getKey() {
            return key;
        }
        public V getValue() {
            return value;
        }
     //替换value，返回旧value
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }
        // 重写equals方法：key 和 value的引用都相等
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
        }
        //重写hashCode方法，返回 key 和 value的hashCode 的异或运算结构
        public int hashCode() {
            int keyHash = (key==null ? 0 : key.hashCode());
            int valueHash = (value==null ? 0 : value.hashCode());
            return keyHash ^ valueHash;
        }
        public String toString() {
            return key + "=" + value;
        }
    }

5 构造函数

    // 构造函数一：不指定排序器。按照key的字典顺序来排序（升序）
    public TreeMap() {
        comparator = null;
    }
    // 构造函数二：指定排序器
     public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    //构造函数三：构造并返回跟参数m有相同键值映射结构的treeMap（m变为红黑树）
    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }
     //构造函数四：构造并返回跟参数m（有序的）有相同键值映射结构的treeMap
    public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }

Comparator Integer类型倒序排序

    public static void main(String[] args) {
        TreeMap treeMap = new TreeMap<Integer ,String>(new ComparatorObj());
        treeMap.put(2,"ss");
        treeMap.put(3,"sss");
        System.out.println(treeMap);
    }
    static class ComparatorObj implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1; //倒序排序
        }
    }

输出结果：

2022-07-11 18:02:23,871 [INFO] main: {3=sss, 2=ss}

6 重要方法分析

6.1 get方法分析

（实际调用getEntry(Object key)）

• get(Object key)方法是对接口Map的方法实现
• get(Object key)方法转为对getEntry(Object key)方法的实现分析：算法思想是根据key的自然顺序(或者比较器顺序)对二叉查找树进行查找，直到找到满足k.compareTo(p.key) == 0的entry，再返回entry的value。

源码分析如下：

public V get(Object key) {
    Entry<K,V> p = getEntry(key);  //根据key找到entry，再返回其value
    return (p==null ? null : p.value);
}
//重点分析该方法
final Entry<K,V> getEntry(Object key) {
    if (comparator != null)
        return getEntryUsingComparator(key); 
    if (key == null)
        throw new NullPointerException();  //key非空校验
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;  //自然顺序，使用Comparable的排序接口
    Entry<K,V> p = root; 
    while (p != null) {  //从根节点开始 循环遍历
        int cmp = k.compareTo(p.key);  //compareTo：左边减去右边
        if (cmp < 0) //参数key值小于父节点key
            p = p.left; //取左子节点
        else if (cmp > 0)
            p = p.right;  //参数key值大于父节点key，取右子节点
        else
            return p;  //key相等，则直接返回当前entry
    }
    return null;
}

查询方法说明：

1. 在while循环外，创建动态游标节点，游标首次指向root节点，以游标!=null作为循环条件
2. 在while循环内，根据compareTo结果，取游标的左子节点或右子节点，作为新的游标
3. 找到满足k.compareTo(p.key) == 0的entry，退出循环

getEntryUsingComparator源码：

//提供自定义排序器的查询找方法，原理类似
final Entry<K,V> getEntryUsingComparator(Object key) {
        @SuppressWarnings("unchecked")
            K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key); //cpr.compare 第一个参数减去第二个参数
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

6.2 put方法分析

public V put(K key, V value) {
    Entry<K,V> t = root;
    // 情况一：根节点为空，将当前key value作为root
    if (t == null) {
        compare(key, key); //key为null则抛异常
        root = new Entry<>(key, value, null);//初始化root
        size = 1;  //叶子个数+1
        modCount++; // 结构修改次数自增
        return null;  //新叶子，所以old value 为空
    }
    // 情况二：如果找到key相同的，则更新value ，过程类似get方法
    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    //情况三：没有相同的key，则添加新叶子。
    //经过上面的两种遍历，完成了二分法查找，找到适合插入的地方：parent。
    Entry<K,V> e = new Entry<>(key, value, parent); //创建新的entry
    //确定新增叶子作为parent的左孩子还是右孩子，插入的动作完成
    if (cmp < 0)  
        parent.left = e;  
    else
        parent.right = e;
    fixAfterInsertion(e);  //插入完成后，对二叉树进行调整
    size++;
    modCount++;
    return null;
}
//这个方法实际上是对key做null检查，如果是null会抛出异常（测试代码验证过）
public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
  }

put方法说明：

1. 如果root为空，则新增的entry作为root
2. 遍历搜索是否存在相同的key，存在则替换value。这过程也是二叉排序树的二分查找法：找到了作为插入点的parent。
3. 插入操作：找到parent，并将其left或者right指向新的entry。
4. 如果是插入，则需要对红黑树进行结构调整。 （插入：节点默认为红色，root节点：设置为黑色，覆盖节点：颜色保持不变）
5. 维护成员变量：size，modCount。

6.3 插入调整函数fixAfterInsertion()解析

/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;  //新增节点默认为红色，再进行规则判断
    // 从树末端开始遍历：父节点是红色，则需要对树进行调整
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;  //在遍历外面，确保root一定是黑色
}

方法说明：

1. 新增的节点默认为红色，并从树末端往上遍历
2. 如果新增节点的父亲是红色，则需要进行结构调整
3. 结构调整这部分有点复杂，回头再深入理解todo

6.4 删除方法remove()解析

知识回顾：
二叉排序树的删除过程：（情况一，treeMap用后继代替，其实用前驱或者后继是一样的）

源码如下：

// 调用getEntry(key)找到对应entry，调用deleteEntry 删除节点
public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;
    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}
//执行删除操作
private void deleteEntry(Entry<K,V> p) {
     //先对全局变量modCount、size 进行调整
    modCount++;
    size--;
    //情况1：左右孩子都不为空：后继节点代替
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p); //寻找后继 （另外分析）
        //将删除点的key、value、引用分别更新为代替节点
        p.key = s.key;  
        p.value = s.value;
        p = s;   //
    }
    //情况2：有1个孩子
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {
        replacement.parent = p.parent;  //左孩子父亲更新删除节点的父亲
        //父亲为root，则后继变为新的root
        if (p.parent == null)
            root = replacement;  
        //左孩子顶上
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        //右孩子顶上
        else
            p.parent.right = replacement;
        // 删除节点的left、right、parent置空：被移除出树
        p.left = p.right = p.parent = null;
        // 删除黑色节点：调整结构
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { //删除root节点
        root = null;
    } else { //  情况1：没孩子
        if (p.color == BLACK)
            fixAfterDeletion(p);
        //将父亲的左孩子或者有孩子清空
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

删除说明：

1. 删除过程遵从二叉排序树的删除特点（1、有一个孩子则孩子顶上；2两个孩子就用后继顶上，没有孩子则直接移除）
2. 节点删除，即left、right、parent置空；删除后，需要更新父亲节点的的左孩子或右孩子
3. 考虑是否需要更新全局变量root节点
4. 只有删除点是BLACK的时候，才会触发调整函数，因为删除RED节点不会破坏红黑树的任何约束，而删除BLACK节点会破坏规则4。

6.5 删除调整函数fixAfterDeletion()解析

private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> sib = rightOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else { // symmetric
            Entry<K,V> sib = leftOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }
            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }
    setColor(x, BLACK);
}

说明：结构调整这部分有点复杂，回头再深入理解todo

6.6 寻找后继函数successor()解析

//寻找任意节点后继
    static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
        if (t == null)
            return null;
            //情况1：右孩子不为空，向后代遍历：找到右孩子中孙子最小的那个节点（不断寻找left，直至为空）
        else if (t.right != null) {
            Entry<K,V> p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
        // 情况2：右孩子为空，向祖先遍历，当任意节点是它父亲的左孩子时，则该节点的父亲为t的后继
            Entry<K,V> p = t.parent;
            Entry<K,V> ch = t;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

寻找后继的算法说明：
对于任意k：

1. 情况一：k的右孩子不为空，向后代遍历：找到右孩子的子孙子中辈分最低的左孩子（不断寻找left，直至为空）
2. 情况二：key的右孩子为空，向祖先遍历：当任意节点是它父亲的左孩子时，则该节点的父亲为t的后继

右孩子不为空的后继寻找：

右孩子为空为空的后继寻找：

---

7 解惑：

1 TreeMap支持key自定义排序，而红黑树对key的固定的排序规则，两者如何兼容的?

1. 支持key自定义排序：指通过自定义的排序器，计算出任意key相对其它key的大小关系
2. 红黑树对key的固定的排序：指按照红黑树的数据结构（二叉排序树+红黑节点规则），来组织key的树状结构，其中二叉排序的大小关系是根据排序器的计算出来的
3. 两者不冲突