TreeMap本质

是对红黑树的实现,下面代码TreeMap节点的结构

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

重点分析put方法，可以看出就是对红黑树插入的实现

  public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check
            root = new Entry<>(key, value, null);  // 如果treemap是空的，第一个节点为根节点
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        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);
        }
        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 != 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));  // 祖父节点赋值给x
                } else {
                    if (x == rightOf(parentOf(x))) {  // 叔叔节点为黑色
                        x = parentOf(x);  // 父节点赋值给x
                        rotateLeft(x);  // 以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;  // 保证根节点为黑色
    }

总结：从源码中可以确定，TreeMap就是对红黑树的实现，也是底层存储数据的结构