10.4 剖析TreeMap

发表于 更新于 分类于 ， ， Waline： 本文字数： 11k 阅读时长 ≈ 10 分钟

10.4 剖析TreeMap

在介绍HashMap时，我们提到，HashMap有一个重要局限，键值对之间没有特定的顺序，我们还提到，Map接口有另一个重要的实现类TreeMap，在TreeMap中，键值对之间按键有序，TreeMap的实现基础是排序二叉树，10.3节介绍了排序二叉树的基本概念和算法，本节我们来详细讨论TreeMap。除了Map接口，因为有序，TreeMap还实现了更多接口和方法。下面，我们先来介绍TreeMap的用法，然后介绍其内部实现。

10.4.1 基本用法

TreeMap有两个基本构造方法：

1
2
public TreeMap()
public TreeMap(Comparator<? super K> comparator)

第一个为默认构造方法，如果使用默认构造方法，要求Map中的键实现Comparabe接口，TreeMap内部进行各种比较时会调用键的Comparable接口中的compareTo方法。

第二个接受一个比较器对象comparator，如果comparator不为null，在TreeMap内部进行比较时会调用这个comparator的compare方法，而不再调用键的compareTo方法，也不再要求键实现Comparable接口。

应该用哪一个呢？第一个更为简单，但要求键实现Comparable接口，且期望的排序和键的比较结果是一致的；第二个更为灵活，不要求键实现Comparable接口，比较器可以用灵活复杂的方式进行实现。

需要强调的是，TreeMap是按键而不是按值有序，无论哪一种，都是对键而非值进行比较。

看段简单的示例代码：

1
2
3
4
5
6
7
8
Map<String, String> map   = new TreeMap<>();
map.put("a", "abstract");
map.put("c", "call");
map.put("b", "basic");
map.put("T", "tree");
for(Entry<String, String> kv : map.entrySet()){
    System.out.print(kv.getKey()+"="+kv.getValue()+" ");
}

创建了一个TreeMap，但只是当作Map使用，不过迭代时，其输出却是按键排序的，输出为：

1
T=tree a=abstract b=basic c=call

T排在最前面，是因为大写字母的ASCII码都小于小写字母。如果希望忽略大小写呢？可以传递一个比较器，String类有一个静态成员CASE_INSENSITIVE_ORDER，它就是一个忽略大小写的Comparator对象，替换第一行代码为：

1
Map<String, String> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);

输出就会变为：

1
a=abstract b=basic c=call T=tree

正常排序是从小到大，如果希望逆序呢？可以传递一个不同的Comparator对象，第一行代码可以替换为：

1
2
3
4
5
6
Map<String, String> map   = new TreeMap<>(new Comparator<String>(){
    @Override
    public int compare(String o1, String o2) {
        return o2.compareTo(o1);
    }
});

这样，输出会变为：

1
c=call b=basic a=abstract T=tree

为什么这样就可以逆序呢？正常排序中，compare方法内是o1.compareTo(o2)，两个对象翻过来，自然就是逆序了，Collections类有一个静态方法reverseOrder()可以返回一个逆序比较器，也就是说，上面的代码也可以替换为：

1
Map<String, String> map = new TreeMap<>(Collections.reverseOrder());

如果希望逆序且忽略大小写呢？第一行可以替换为：

1
Map<String, String> map   = new TreeMap<>(Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));

需要说明的是，TreeMap使用键的比较结果对键进行排重，即使键实际上不同，但只要比较结果相同，它们就会被认为相同，键只会保存一份。比如，如下代码：

1
2
3
4
5
6
Map<String, String> map   = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
map.put("T", "tree");
map.put("t", "try");
for(Entry<String, String> kv : map.entrySet()){
    System.out.print(kv.getKey()+"="+kv.getValue()+" ");
}

看上去有两个不同的键”T”和”t”，但因为比较器忽略大小写，所以只会有一个，输出会是：

1
T=try

键为第一次put时的，这里即”T”，而值为最后一次put时的，这里即”try”。

我们再来看一个例子，键为字符串形式的日期，值为一个统计数字，希望按照日期输出，代码为：

1
2
3
4
5
6
7
Map<String, Integer> map   = new TreeMap<>();
map.put("2016-7-3", 100);
map.put("2016-7-10", 120);
map.put("2016-8-1", 90);
for(Entry<String, Integer> kv : map.entrySet()){
    System.out.println(kv.getKey()+", "+kv.getValue());
}

输出为：

1
2
3
2016-7-10,120
2016-7-3,100
2016-8-1,90

7月10号的排在了7月3号的前面，与期望的不符，这是因为，它们是按照字符串比较的，按字符串，2016-7-10就是小于2016-7-3，因为第一个不同之处1小于3。

怎么解决呢？可以使用一个自定义的比较器，将字符串转换为日期，按日期进行比较，第一行代码可以改为：

1
2
3
4
5
6
7
8
9
10
11
12
Map<String, Integer> map   = new TreeMap<>(new Comparator<String>() {
    SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
    @Override
    public int compare(String o1, String o2) {
        try {
            return sdf.parse(o1).compareTo(sdf.parse(o2));
        } catch (ParseException e) {
            e.printStackTrace();
            return 0;
        }
    }
});

这样，输出就符合期望了，会变为：

1
2
3
2016-7-3,100
2016-7-10,120
2016-8-1,90

以上就是TreeMap的基本用法，与HashMap相比：相同的是，它们都实现了Map接口，都可以按Map进行操作。不同的是，迭代时，TreeMap按键有序，为了实现有序，它要求要么键实现Comparable接口，要么创建TreeMap时传递一个Comparator对象。

由于TreeMap按键有序，它还支持更多接口和方法，具体来说，它还实现了Sorted-Map和NavigableMap接口，而NavigableMap接口扩展了SortedMap，通过这两个接口，可以方便地根据键的顺序进行查找，如第一个、最后一个、某一范围的键、邻近键等，限于篇幅，我们就不介绍了，具体可参见API文档。

10.4.2 实现原理

TreeMap内部是用红黑树实现的，红黑树是一种大致平衡的排序二叉树，10.3节我们介绍了排序二叉树的基本概念和算法，本节主要看TreeMap的一些代码实现（基于Java 7），先来看TreeMap的内部组成。

1．内部组成

TreeMap内部主要有如下成员：

1
2
3
private final Comparator<? super K> comparator;
private transient Entry<K, V> root = null;
private transient int size = 0;

comparator就是比较器，在构造方法中传递，如果没传，就是null。size为当前键值对个数。root指向树的根节点，从根节点可以访问到每个节点，节点的类型为Entry。Entry是TreeMap的一个内部类，其内部成员和构造方法为：

1
2
3
4
5
6
7
8
9
10
11
12
13
static final class Entry<K, V> implements Map.Entry<K, V> {
    K key;
    V value;
    Entry<K, V> left = null;
    Entry<K, V> right = null;
    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;
    }
}

每个节点除了键（key）和值（value）之外，还有三个引用，分别指向其左孩子（left）、右孩子（right）和父节点（parent），对于根节点，父节点为null，对于叶子节点，孩子节点都为null，还有一个成员color表示颜色，TreeMap是用红黑树实现的，每个节点都有一个颜色，非黑即红。

了解了TreeMap的内部组成，我们来看一些主要方法的实现代码。

2．保存键值对

put方法的代码稍微有点长，我们分段来看。先看第一段，添加第一个节点的情况：

1
2
3
4
5
6
7
8
9
10
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;
    }
    //…

当添加第一个节点时，root为null，执行的就是这段代码，主要就是新建一个节点，设置root指向它，size设置为1, modCount++的含义与之前章节介绍的类似，用于迭代过程中检测结构性变化。

令人费解的是compare调用，compare(key, key); , key与key比，有什么意义呢？我们看compare方法的代码：

1
2
3
4
final int compare(Object k1, Object k2) {
      return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

其实，这里的目的不是为了比较，而是为了检查key的类型和null，如果类型不匹配或为null，那么compare方法会抛出异常。

如果不是第一次添加，会执行后面的代码，添加的关键步骤是寻找父节点。寻找父节点根据是否设置了comparator分为两种情况，我们先来看已设置的情况，代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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);
}

寻找是一个从根节点开始循环的过程，在循环中，cmp保存比较结果，t指向当前比较节点，parent为t的父节点，循环结束后parent就是要找的父节点。t一开始指向根节点，从根节点开始比较键，如果小于根节点，就将t设为左孩子，与左孩子比较，大于就与右孩子比较，就这样一直比，直到t为null或比较结果为0。如果比较结果为0，表示已经有这个键了，设置值，然后返回。如果t为null，则当退出循环时，parent就指向待插入节点的父节点。

我们再来看没有设置comparator的情况，代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
else {
    if(key == null)
        throw new NullPointerException();
    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);
}

基本逻辑是一样的，当退出循环时parent指向父节点，只是如果没有设置comparator，则假设key一定实现了Comparable接口，使用Comparable接口的compareTo方法进行比较。

找到父节点后，就是新建一个节点，根据新的键与父节点键的比较结果，插入作为左孩子或右孩子，并增加size和modCount，代码如下：

1
2
3
4
5
6
7
8
Entry<K, V> e = new Entry<>(key, value, parent);
if(cmp < 0)
    parent.left = e;
else
    parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;

代码大部分都容易理解，不过，里面有一行重要调用fixAfterInsertion(e); ，它就是在调整树的结构，使之符合红黑树的约束，保持大致平衡，其代码我们就不介绍了。

稍微总结一下，其基本思路就是：循环比较找到父节点，并插入作为其左孩子或右孩子，然后调整保持树的大致平衡。

3．根据键获取值

根据键获取值的代码为：

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

就是根据key找对应节点p，找到节点后获取值p.value，来看getEntry的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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();
    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;
}

如果comparator不为空，调用单独的方法getEntryUsingComparator，否则，假定key实现了Comparable接口，使用接口的compareTo方法进行比较，找的逻辑也很简单，从根开始找，小于往左边找，大于往右边找，直到找到为止，如果没找到，返回null。getEntry-UsingComparator方法的逻辑类似，就不赘述了。

4．查看是否包含某个值

TreeMap可以高效地按键进行查找，但如果要根据值进行查找，则需要遍历，我们来看代码：

1
2
3
4
5
6
public boolean containsValue(Object value) {
    for(Entry<K, V> e = getFirstEntry(); e ! = null; e = successor(e))
        if(valEquals(value, e.value))
            return true;
    return false;
}

主体就是一个循环遍历，getFirstEntry方法返回第一个节点，successor方法返回给定节点的后继节点，valEquals就是比较值，从第一个节点开始，逐个进行比较，直到找到为止，如果循环结束也没找到则返回false。getFirstEntry的代码为：

1
2
3
4
5
6
7
final Entry<K, V> getFirstEntry() {
    Entry<K, V> p = root;
    if(p ! = null)
        while (p.left ! = null)
            p = p.left;
    return p;
}

代码很简单，第一个节点就是最左边的节点。

10.3节我们介绍过找后继节点的算法，successor的具体代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static <K, V> TreeMap.Entry<K, V> successor(Entry<K, V> t) {
    if(t == null)
        return null;
    else if(t.right ! = null) {
        Entry<K, V> p = t.right;
        while (p.left ! = null)
            p = p.left;
        return p;
    } else {
        Entry<K, V> p = t.parent;
        Entry<K, V> ch = t;
        while(p ! = null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

如10.3节后继算法所述，有两种情况：
1）如果有右孩子（t.right! =null），则后继节点为右子树中最小的节点。
2）如果没有右孩子，后继节点为某祖先节点，从当前节点往上找，如果它是父节点的右孩子，则继续找父节点，直到它不是右孩子或父节点为空，第一个非右孩子节点的父亲节点就是后继节点，如果父节点为空，则后继节点为null。

代码与算法是对应的，就不再赘述了，这个描述比较抽象，可以参考图10-7，进行对照。

5．根据键删除键值对

根据键删除键值对的代码为：

1
2
3
4
5
6
7
8
public V remove(Object key) {
    Entry<K, V> p = getEntry(key);
    if(p == null)
        return null;
    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

根据key找到节点，调用deleteEntry删除节点，然后返回原来的值。

10.3节介绍过节点删除的算法，节点有三种情况：
1）叶子节点：这个容易处理，直接修改父节点对应引用置null即可。
2）只有一个孩子：就是在父亲节点和孩子节点直接建立链接。
3）有两个孩子：先找到后继节点，找到后，替换当前节点的内容为后继节点，然后再删除后继节点，因为这个后继节点一定没有左孩子，所以就将两个孩子的情况转换为了前面两种情况。

deleteEntry的具体代码也稍微有点长，我们分段来看：

1
2
3
4
5
6
7
8
9
10
11
private void deleteEntry(Entry<K, V> p) {
    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) {
        Entry<K, V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    } //p has 2 children

这里处理的就是两个孩子的情况，s为后继，当前节点p的key和value设置为了s的key和value，然后将待删节点p指向了s，这样就转换为了一个孩子或叶子节点的情况。

再往下看一个孩子情况的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//Start fixup at replacement node, if it exists.
Entry<K, V> replacement = (p.left ! = null ? p.left : p.right);
if(replacement ! = null) {
    //Link replacement to parent
    replacement.parent = p.parent;
    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.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.

p为待删节点，replacement为要替换p的孩子节点，主体代码就是在p的父节点p.parent和replacement之间建立链接，以替换p.parent和p原来的链接，如果p.parent为null，则修改root以指向新的根。fixAfterDeletion重新平衡树。

最后来看叶子节点的情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
} 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;
    }
}

再具体分为两种情况：一种是删除最后一个节点，修改root为null；另一种是根据待删节点是父节点的左孩子还是右孩子，相应的设置孩子节点为null。

以上就是TreeMap的基本实现原理，与10.3节介绍的排序二叉树的基本概念和算法是一致的，只是TreeMap用了红黑树。

10.4.3 小结

本节介绍了TreeMap的用法和实现原理，与HashMap相比，TreeMap同样实现了Map接口，但内部使用红黑树实现。红黑树是统计效率比较高的大致平衡的排序二叉树，这决定了它有如下特点：
1）按键有序，TreeMap同样实现了SortedMap和NavigableMap接口，可以方便地根据键的顺序进行查找，如第一个、最后一个、某一范围的键、邻近键等。
2）为了按键有序，TreeMap要求键实现Comparable接口或通过构造方法提供一个Com-parator对象。
3）根据键保存、查找、删除的效率比较高，为O(h), h为树的高度，在树平衡的情况下，h为log2(N), N为节点数。

应该用HashMap还是TreeMap呢？不要求排序，优先考虑HashMap，要求排序，考虑TreeMap。HashMap有对应的TreeMap, HashSet也有对应的TreeSet，下节，我们来看TreeSet。