一文带你深入了解Java TreeMap

@Test
    public void test1() {
        Map<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(16, "a");
        treeMap.put(1, "b");
        treeMap.put(4, "c");
        treeMap.put(3, "d");
        treeMap.put(8, "e");
        // 遍历
        System.out.println("默认排序：");
        treeMap.forEach((key, value) -> {
            System.out.println("key: " + key + ", value: " + value);
        });

        // 构造方法传入比较器
        Map<Integer, String> tree2Map = new TreeMap<>((o1, o2) -> o2 - o1);
        tree2Map.put(16, "a");
        tree2Map.put(1, "b");
        tree2Map.put(4, "c");
        tree2Map.put(3, "d");
        tree2Map.put(8, "e");
        // 遍历
        System.out.println("倒序排序：");
        tree2Map.forEach((key, value) -> {
            System.out.println("key: " + key + ", value: " + value);
        });
    }

@Test
    public void test2() {
        Map<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(null, "a");
    }

@Test
    public void test3() {
        NavigableMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(16, "a");
        treeMap.put(1, "b");
        treeMap.put(4, "c");
        treeMap.put(3, "d");
        treeMap.put(8, "e");

        // 获取大于等于5的key
        Integer ceilingKey = treeMap.ceilingKey(5);
        System.out.println("ceilingKey 5 is " + ceilingKey);

        // 获取最大的key
        Integer lastKey = treeMap.lastKey();
        System.out.println("lastKey is " + lastKey);
    }

//这是一个比较器，方便插入查找元素等操作
private final Comparator<? super K> comparator;
//红黑树的根节点：每个节点是一个Entry
private transient Entry<K,V> root;
//集合元素数量
private transient int size = 0;
//集合修改的记录
private transient int modCount = 0;

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
     	//左子树
        Entry<K,V> left;
     	//右子树
        Entry<K,V> right;
     	//父节点
        Entry<K,V> parent;
     	//每个节点的颜色：红黑树属性。
        boolean color = BLACK;
        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;
        }
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        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());
        }

        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;
        }
    }

public V get(Object key) {
        //调用 getEntry方法查找
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p. value);
}

final Entry<K,V> getEntry(Object key) {
    / 如果比较器为空，只是用key作为比较器查询
    if (comparator != null) 
        return getEntryUsinGComparator(key);
    if (key == null)
        throw new NullPointerException();
    Comparable<? super K> k = (Comparable<? super K>) key;
    // 取得root节点
    Entry<K,V> p = root;
   //核心来了：从root节点开始查找，根据比较器判断是在左子树还是右子树
    while (p != null) {
        int cmp = k.compareTo(p.key );
        if (cmp < 0)
            p = p. left;
        else if (cmp > 0)
            p = p. right;
        else
           return p;
    }

public V put(K key, V value) {
        Entry<K,V> t = root;
       // 1.如果根节点为 null，将新节点设为根节点
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
      //如果root不为null，说明已存在元素 
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
    //如果比较器不为null 则使用比较器
        if (cpr != null) {
            //找到元素的插入位置
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                 //当前key小于节点key 向左子树查找
                if (cmp < 0)
                    t = t.left;
                    //当前key大于节点key 向右子树查找
                else if (cmp > 0)
                    t = t.right;
                else
                    //相等的情况下 直接更新节点值
                    return t.setValue(value);
            } while (t != null);
        }
            //如果比较器为null 则使用默认比较器
        else {
            //如果key为null  则抛出异常
            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);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
      //根据比较结果决定插入到左子树还是右子树
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
    //保持红黑树性质，进行红黑树的旋转等操作
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

private void fixAfterInsertion(Entry<K,V> x) {
    // 将新插入节点的颜色设置为红色
    x. color = RED;
    // while循环，保证新插入节点x不是根节点或者新插入节点x的父节点不是红色（这两种情况不需要调整）
    while (x != null && x != root && x. parent.color == RED) {
        // 如果新插入节点x的父节点是祖父节点的左孩子
        if (parentOf(x) == leftOf(parentOf (parentOf(x)))) {
            // 取得新插入节点x的叔叔节点
            Entry<K,V> y = rightOf(parentOf (parentOf(x)));
            // 如果新插入x的父节点是红色
            if (colorOf(y) == RED) {
                // 将x的父节点设置为黑色
                setColor(parentOf (x), BLACK);
                // 将x的叔叔节点设置为黑色
                setColor(y, BLACK);
                // 将x的祖父节点设置为红色
                setColor(parentOf (parentOf(x)), RED);
                // 将x指向祖父节点，如果x的祖父节点的父节点是红色，按照上面的步奏继续循环
                x = parentOf(parentOf (x));
            } else {
                // 如果新插入x的叔叔节点是黑色或缺少，且x的父节点是祖父节点的右孩子
                if (x == rightOf( parentOf(x))) {
                    // 左旋父节点
                    x = parentOf(x);
                    rotateLeft(x);
                }
                // 如果新插入x的叔叔节点是黑色或缺少，且x的父节点是祖父节点的左孩子
                // 将x的父节点设置为黑色
                setColor(parentOf (x), BLACK);
                // 将x的祖父节点设置为红色
                setColor(parentOf (parentOf(x)), RED);
                // 右旋x的祖父节点
                rotateRight( parentOf(parentOf (x)));
            }
        } else { // 如果新插入节点x的父节点是祖父节点的右孩子和上面的相似
            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;
}

public V remove(Object key) {
        // 根据key查找到对应的节点对象
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;

        // 记录key对应的value，供返回使用
        V oldValue = p. value;
        // 删除节点
        deleteEntry(p);
        return oldValue;
}

private void deleteEntry(Entry<K,V> p) {
        modCount++;
        //元素个数减一
        size--;
        // 如果被删除的节点p的左孩子和右孩子都不为空，则查找其替代节
        if (p.left != null && p. right != null) {
            // 查找p的替代节点
            Entry<K,V> s = successor (p);
            p. key = s.key ;
            p. value = s.value ;
            p = s;
        }
        Entry<K,V> replacement = (p. left != null ? p.left : p. right);
        if (replacement != null) { 
            // 将p的父节点拷贝给替代节点
            replacement. parent = p.parent ;
            // 如果替代节点p的父节点为空，也就是p为跟节点，则将replacement设置为根节点
            if (p.parent == null)
                root = replacement;
            // 如果替代节点p是其父节点的左孩子，则将replacement设置为其父节点的左孩子
            else if (p == p.parent. left)
                p. parent.left   = replacement;
            // 如果替代节点p是其父节点的左孩子，则将replacement设置为其父节点的右孩子
            else
                p. parent.right = replacement;
            // 将替代节点p的left、right、parent的指针都指向空
            p. left = p.right = p.parent = null;
            // 如果替代节点p的颜色是黑色，则需要调整红黑树以保持其平衡
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            // 如果要替代节点p没有父节点，代表p为根节点，直接删除即可
            root = null;
        } else {
            // 如果p的颜色是黑色，则调整红黑树
            if (p.color == BLACK)
                fixAfterDeletion(p);
            // 下面删除替代节点p
            if (p.parent != null) {
                // 解除p的父节点对p的引用
                if (p == p.parent .left)
                    p. parent.left = null;
                else if (p == p.parent. right)
                    p. parent.right = null;
                // 解除p对p父节点的引用
                p. parent = null;
            }
        }
    }