JDK源码分析——TreeMap

引：你想利用的Map高效的查找效率，又想拥有一个有序的Map，这个时候就需要用到TreeMap了!

详细注释：源码分析地址

概览

TreeMap集合是基于红黑树（Red-Black tree）的 NavigableMap实现。该Map根据其键的自然顺序进行排序，或者根据创建Map时提供的 Comparator 进行排序，具体取决于使用的构造方法。你可以根据自己的需要选择排序的方式。

关于不同步都和之前解析的非同步容器类似。

构造

在概览中说到我们可以在它构造时传递Comparator来决定排序的方法，所以我们就看看这个构造方法。

// 比较器
private final Comparator<? super K> comparator;
// 根节点
private transient Entry<K,V> root;
// 集合大小
private transient int size = 0;

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

增

我们看出在构造方法中只是设置了属性，并没有真正构建红黑树，那么它一定在第一次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
    // 获得key比较器
    Comparator<? super K> cpr = comparator;
    // 如果比较器对象不为空，也就是自定义了比较器
    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;
            // 相等则替换其value
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 如果比较器对象为空，使用默认的比较机制
    else {
        // 默认机制下不允许设置 null key
        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找到父节点后新建一个节点
    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;
}

大概的流程如下：

1. 判断根节点是否为空，为空，则该节点就是根节点
2. 根据比较器(可能是外部传进来的，也可能是默认的)，找到父节点。
3. 插入节点之后，就需要用红黑树的修正了。

删

public V remove(Object key) {
    // 利用比较器二分查找
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;

    // 红黑树删除
    deleteEntry(p);
    return oldValue;
}


final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = 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;
    }
    return null;
}

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);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

改

找到该key对应的节点，然后替换该值

public V replace(K key, V value) {
    // 找到节点
    Entry<K,V> p = getEntry(key);
    // 替换值
    if (p!=null) {
        V oldValue = p.value;
        p.value = value;
        return oldValue;
    }
    return null;
}

查

一批以getFirstEntry()，getLastEntry()为基础的获取头和尾元素的方法，其中包括：firstKey()，lastKey()；firstEntry()，lastEntry()；pollFirstEntry()，pollLastEntry()

//  返回第一个节点(值最小的节点)
final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        // 一直遍历左子树
        while (p.left != null)
            p = p.left;
    return p;
}

// 返回最后一个节点(值最大的节点)
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        // 一直遍历右子树
        while (p.right != null)
            p = p.right;
    return p;
}