聊聊java中的哪些Map：（九）TreeMap源码分析

冬天里的懒猫

发布于 2020-09-07 15:09:35

2030

发布于 2020-09-07 15:09:35

文章被收录于专栏：做不甩锅的后端做不甩锅的后端

1.类结构及其成员变量

1.1 类结构

TreeMap的类继承结构如下图：

可以看到，TreeMap继承了AbstractMap，此外实现了NavigableMap、Cloneable和Serializable接口。而NavigableMap接口又继承了SortedMap。这与ConcurrentSkipListMap的情况类似，因而也是有序的。

/**
 * A Red-Black tree based {@link NavigableMap} implementation.
 * The map is sorted according to the {@linkplain Comparable natural
 * ordering} of its keys, or by a {@link Comparator} provided at map
 * creation time, depending on which constructor is used.
 *
 * <p>This implementation provides guaranteed log(n) time cost for the
 * {@code containsKey}, {@code get}, {@code put} and {@code remove}
 * operations.  Algorithms are adaptations of those in Cormen, Leiserson, and
 * Rivest's <em>Introduction to Algorithms</em>.
 *
 * <p>Note that the ordering maintained by a tree map, like any sorted map, and
 * whether or not an explicit comparator is provided, must be <em>consistent
 * with {@code equals}</em> if this sorted map is to correctly implement the
 * {@code Map} interface.  (See {@code Comparable} or {@code Comparator} for a
 * precise definition of <em>consistent with equals</em>.)  This is so because
 * the {@code Map} interface is defined in terms of the {@code equals}
 * operation, but a sorted map performs all key comparisons using its {@code
 * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
 * this method are, from the standpoint of the sorted map, equal.  The behavior
 * of a sorted map <em>is</em> well-defined even if its ordering is
 * inconsistent with {@code equals}; it just fails to obey the general contract
 * of the {@code Map} interface.
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a map concurrently, and at least one of the
 * threads modifies the map structurally, it <em>must</em> be synchronized
 * externally.  (A structural modification is any operation that adds or
 * deletes one or more mappings; merely changing the value associated
 * with an existing key is not a structural modification.)  This is
 * typically accomplished by synchronizing on some object that naturally
 * encapsulates the map.
 * If no such object exists, the map should be "wrapped" using the
 * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the map: <pre>
 *   SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
 *
 * <p>The iterators returned by the {@code iterator} method of the collections
 * returned by all of this class's "collection view methods" are
 * <em>fail-fast</em>: if the map is structurally modified at any time after
 * the iterator is created, in any way except through the iterator's own
 * {@code remove} method, the iterator will throw a {@link
 * ConcurrentModificationException}.  Thus, in the face of concurrent
 * modification, the iterator fails quickly and cleanly, rather than risking
 * arbitrary, non-deterministic behavior at an undetermined time in the future.
 *
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:   <em>the fail-fast behavior of iterators
 * should be used only to detect bugs.</em>
 *
 * <p>All {@code Map.Entry} pairs returned by methods in this class
 * and its views represent snapshots of mappings at the time they were
 * produced. They do <strong>not</strong> support the {@code Entry.setValue}
 * method. (Note however that it is possible to change mappings in the
 * associated map using {@code put}.)
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 *
 * @author  Josh Bloch and Doug Lea
 * @see Map
 * @see HashMap
 * @see Hashtable
 * @see Comparable
 * @see Comparator
 * @see Collection
 * @since 1.2
 */

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
}

其注释大意为： TreeMap是一个基于红黑树的NavigableMap实现，可以根据Comparable实现自然排序，或者Comparator排序，至于根据哪个排序取决于构造函数。这个实现对containsKey、get、put、remove提供了恒定的时间复杂度log(n)。这个算法是对Cormen、Leiserson和Rivest算法的改进。请注意，TreeMap与任何排序的map一样，维护的顺序，以及是否提供显示比较必须与equals方法一致，以便排序的map能够正确实现。之所以这样，是因为map接口是根据equals的操作定义的，但是排序之后的map使用compareTo或者compare方法执行比较，因此从排序map的角度来看，此方法认为相等的两个key是相等的。排序后的map的行为是明确定义的，即使其排序与equals不一致，它也只是无法遵守map的一般约定。需要注意的是，这个实现是非同步的。如果多线程并发访问，最后一个线程修改了这个map的结构，它必须在外部进行同步。结构的修改是指添加或者删除一个或者多个映射。使用key进行更新不是属于结构修改。这是通常通过封装TreeMap对象来实现。如果这个对象不存在，那么应该使用Collections.synchronizedSortedMap方法。最好是在创建的时候完成，以防止不同步的访问。如下：

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

这个类的所有集合视图方法返回的集合的iterator的迭代器都是fail-fast的。如果在迭代器被映射之后的任何时间对结构进行修改，除非通过迭代器自己的remove方法，否则将抛出ConcurrentModificationException，因此，面对并发修改，迭代器将快速失败，而不是冒着未来不确定的时间产生任意不确定的风险。注意，迭代器的fail-fast并不是一个担保的行为，因为通常来说，存在不同步修改的并发修改的情况下，不可能做出任何严格的保证，快速失败的迭代器将会最大努力的抛出ConcurrentModificationException。因此，编写任何依赖于此异常的程序代码以确保其正确性都是错误的。迭代器的快速失败机制仅仅用于检测错误。此类中的方法返回的所有Entry对其视图均表示生成map的快照，他们不支持Entry.setValue方法，不过请注意，可以使用put更改关联map中的映射。另外，TreeMap还是java集合框架的成员。

1.2 成员变量

由于TreeMap并不涉及线程安全和扩容，因此成员变量非常简单：

/**
 * The comparator used to maintain order in this tree map, or
 * null if it uses the natural ordering of its keys.
 *
 * @serial
 */
private final Comparator<? super K> comparator;

private transient Entry<K,V> root;

/**
 * The number of entries in the tree
 */
private transient int size = 0;

/**
 * The number of structural modifications to the tree.
 */
private transient int modCount = 0;

comparator 是用于进行比较的比较器。root指向根节点，由于红黑树是一个树形结构，因此不再需要数组之类的结构来存储。size用于存放tree中元素的长度。modCount则是在fail-fast机制所依赖的。

2. 核心内部类Entry

TreeMap是基于红黑树的数据结构，TreeMap实现了Map.Entry接口。具有key、value、left、right、parent等属性。

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;

    /**
     * Make a new cell with given key, value, and parent, and with
     * {@code null} child links, and BLACK color.
     */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }

    /**
     * Returns the key.
     *
     * @return the key
     */
    public K getKey() {
        return key;
    }

    /**
     * Returns the value associated with the key.
     *
     * @return the value associated with the key
     */
    public V getValue() {
        return value;
    }

    /**
     * Replaces the value currently associated with the key with the given
     * value.
     *
     * @return the value associated with the key before this method was
     *         called
     */
    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;
    }
}

这个类的结构也非常简单，需要注意的是，其hashCode方法，实际上是keyHash ^ valueHash。虽然key和value都不支持为空，但是还做了特殊处理。

3.基本原理之红黑树

在要搞懂红黑树之前，我们需要先弄清楚，二叉搜索树（Binary Search Tree）和平衡二叉树（AVL树）是什么，之后再来理解红黑树(RB树)。

3.1 二叉搜索树（Binary Search Tree）

定义：它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。二叉搜索树的概念看起来复杂，实际上非常简单，要求就一个，任意节点，其值大于左节点，小于右节点。如下就是一个二叉搜索树：

如果这个二叉搜索树比较平衡的话，其查找的时间复杂度为(log n)。但是需要注意的是，二叉搜索树如果使用不当非常容易退化为链表，导致时间复杂度退化为n。为了解决这个问题，就出现了平衡二叉树（AVL树）。

3.2 平衡二叉树（AVL Tree）

平衡二叉树实际上是二叉搜索树的一种特殊情况。但是其带有平衡条件。要求每个节点的左右子树的高度绝对值最多为1（平衡因子）。平衡二叉树通过一系列平衡操作，左旋、右旋等，来保证了平衡二叉树的平衡性。

这样就将查询的时间复杂度恒定在(log n)。但是代价就是在插入和删除的时候会带来非常高的时间消耗。将插入和删除的时间复杂度都变成了(log n)。

3.3 红黑树

红黑树是平衡二叉树的一个变种，其也是在二叉搜索树上进化而来，但是其转置是根据红黑标记而来。而不是像平衡二叉树那样做统一的要求。其平衡性相对平衡二叉树要低。颜色规则为：

1.任意节点的颜色要么黑色，要么红色。
2.根节点是黑色。
3.如果一个节点为红色，其子节点一定是黑色。（不能允许有两个连续向连的红色节点）
4.任意节点到其下面的空节点，（空接点为黑色）。的路径上，黑色节点的数量相同。通过从根节点到空节点的任意路径进行颜色约束，红黑树可以确保没用一条路径比其他路径的长度多出2倍。因此红黑树是一个近似平衡的树。（节点的平衡因子不能大于1）

红黑树是一个近似平衡的二叉树。也是采用旋转的方式来实现。但是由于其的近似特性，不用旋转到AVL树那种完全平衡的二叉树。AVL树一定是保证左边节点都是满的，如果存在不满的情况一定会出现在右侧。因此AVL树要保证平衡性，旋转的过程会更加复杂，耗时会更长。 实际上这也是大多数集合框架底层采用红黑树的原因。其插入和删除的效率高于AVL数，但是检索效率不会低多少。

4.构造函数

4.1 TreeMap()

支持空的构造函数：

public TreeMap() {
    comparator = null;
}

4.2 TreeMap(Comparator<? super K> comparator)

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

此方法只是传入了一个比较器。

4.3 TreeMap(Map<? extends K, ? extends V> m)

从其他map中put

public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

内部通过putAll方法实现。

public void putAll(Map<? extends K, ? extends V> map) {
    int mapSize = map.size();
    if (size==0 && mapSize!=0 && map instanceof SortedMap) {
        Comparator<?> c = ((SortedMap<?,?>)map).comparator();
        if (c == comparator || (c != null && c.equals(comparator))) {
            ++modCount;
            try {
                buildFromSorted(mapSize, map.entrySet().iterator(),
                                null, null);
            } catch (java.io.IOException cannotHappen) {
            } catch (ClassNotFoundException cannotHappen) {
            }
            return;
        }
    }
    super.putAll(map);
}

如果为SortedMap的子类，则通过Sorted的方法实现。buildFromSorted。反之则通过父类的方法，遍历之后再插入。

4.4 TreeMap(SortedMap<K, ? extends V> m)

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) {
    }
}

通过buildFromSorted 实现sorted的插入。

5.重要方法

下面对TreeMap的一些重要方法的源码进行分析：

5.1 get

get方法：

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

实际上调用的是getEntry方法：

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    //如果比较器为空
    if (comparator != null)
        return getEntryUsingComparator(key);
    //如果key为空 则返回NPE异常 key不支持为空
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
       //key是可比较的
        Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    //如果不为空则根据比较结果左右遍历
    while (p != null) {
        int cmp = k.compareTo(p.key);
        //小于0则左树遍历
        if (cmp < 0)
            p = p.left;
        //大于0则右树遍历
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

5.2 put

put源码：

public V put(K key, V value) {
    Entry<K,V> t = root;
    //t为root节点，如果t为空
    if (t == null) {
        //可比较性校验
        compare(key, key); // type (and possibly null) check
        //直接在root节点创建
        root = new Entry<>(key, value, null);
        //增加计数器和modCount
        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);
            //小于0左树遍历
            if (cmp < 0)
                t = t.left;
            //大于0右树遍历
            else if (cmp > 0)
                t = t.right;
            //反之则直接修改值
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
    //如果key为空 则NPE异常
        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;
}

上述即是put方法。

5.3 remove

reomve方法源码如下：

public V remove(Object key) {
   //通过get方法找到p
    Entry<K,V> p = getEntry(key);
    //如果p为null则没找到 直接返回null
    if (p == null)
        return null;
    //将oldValue存储并返回，然后通过deleteEntry删除节点
    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

操作逻辑在deleteEntry中：

private void deleteEntry(Entry<K,V> p) {
    //增加modCount次数和减少size
    modCount++;
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    //如果左右都不为空 
    if (p.left != null && p.right != null) {
       //后继节点 左右和父节点三个节点进行判断 按这个顺序取 之后将p的key和value改为后继节点
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        //将p和后继节点合并
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    //替换节点 p的左 右 只要不为空 按这个次序
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    //如果还有替换节点
    if (replacement != null) {
        // Link replacement to parent
        //将p的parent指向这个节点
        replacement.parent = p.parent;
        //如果parent为null 则将root指向它
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        //将p的指征都清空 以便GC回收
        p.left = p.right = p.parent = null;

        //颜色检测
        // Fix replacement
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        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;
        }
    }
}

5.4 fixAfterInsertion

这是在insert之后，进行红黑树颜色校验：

 /** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
    //先将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;
}

根据红黑树的规则，对颜色进行check，并修改为对应的颜色。

5.5 fixAfterDeletion

fixAfterDeletion是在删除元素之后再进行平衡的方法：

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

通过上述代码根据红黑树的规则进行检查。

6.总结

本文对TreeMap的源码进行了分析，实际上，再分析了前的HashMap和ConcurrentHashMap的源码之后，TreeMap的源码要相对简单得多。其核心就是红黑树，然后左右旋转。关于红黑树的具体操作，本文并没有进行描述。红黑树是一种比平衡二叉树在插入和删除上效率更好，检索的时候效率与平衡二叉树基本一致的数据结构，相比平衡二叉树，在插入和删除从操作上可以节约时间。这也是为什么HashMap底层会引入红黑树的原因之一。红黑树会大量应用于操作系统底层的各种数据结构。 **需要注意的是，TreeMap不支持key为null的情况，但是支持value为null。这介于HashMap和concurrentHashMap之间。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-09-02 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树