TreeMap

重要的属性

Comparator<? super K> comparator	比较器
Entry<K,V> root	根节点
int size	集合长度

特点

1. 有序的集合，基于key进行排序

2. 使用红黑树结构实现

Entry

Entry

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

put

TreeMap.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);
        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节点
            parent = t;
            //key与t节点的key进行比较
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)    //key < t.key，则key在t的左侧；令t=t的左子节点，继续递归
                t = t.left;
            else if (cmp > 0)   //key > t.key，则key在t的右侧；令t=t的右子节点，继续递归
                t = t.right;
            else
                return t.setValue(value); //key = t.key，则说明有相同的key，更新value
        } while (t != null);    //从根节点一直遍历到叶子节点
    }
    else {
        if (key == null)
            throw new NullPointerException();
            //key必须实现Comparable接口
            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对象，根据cmp的比值来决定成为左或右子节点
     */

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

fixAfterInsertion()

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

左旋转

private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

右旋转

private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}