TreeMap是基于红黑树（一种自平衡的二叉查找树）实现的一个保证有序性的Map。

1
2
3

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

• TreeMap 继承于AbstractMap，所以它是一个Map，即一个key-value集合。
• TreeMap 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。
• TreeMap 实现了Cloneable接口，意味着它能被克隆。
• TreeMap 实现了java.io.Serializable接口，意味着它支持序列化。

TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。

另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

NavigableMap 接口

先看看它的签名：

1

public interface NavigableMap<K,V> extends SortedMap<K,V>

发现它继承于 SortedMap，再看看SortedMap 的签名。

SortedMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public interface SortedMap<K,V> extends Map<K,V> {
    /**
     * 用于在此Map中对key进行排序的比较器，如果为null，则使用key的compareTo()函数进行比较。
     */
    Comparator<? super K> comparator();
    /**
     * 返回一个key的范围为从fromKey到toKey的局部视图（包括fromKey，不包括toKey，包左不包右），
     * 如果fromKey和toKey是相等的，则返回一个空视图。
     * 返回的局部视图同样是此Map的集合视图，所以对它的操作是会与Map互相影响的。
     */
    SortedMap<K,V> subMap(K fromKey, K toKey);
    /**
     * 返回一个严格地小于toKey的局部视图。
     */
    SortedMap<K,V> headMap(K toKey);
    /**
     * 返回一个大于或等于fromKey的局部视图。
     */
    SortedMap<K,V> tailMap(K fromKey);
    /**
     * 返回当前Map中的第一个key（最小）。
     */
    K firstKey();
    /**
     * 返回当前Map中的最后一个key（最大）。
     */
    K lastKey();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
}

正如其名，SortedMap说明这个Map时有序的。顺序一般由key的Comparable接口 提供的自然顺序，或者也可以是再创建SortedMap实例时指定一个Comparator 来决定。

Comparable 和 Comparator 的区别

• Comparable：一般表示类的自然序，比如定义一个Student类，学号为默认排序。

  要用 Comparable 的话需要 Student 类去实现 Comparable 接口。

• Comparator：一般表示类在某种场合下需要定制化排序，比如按照Student类的age排序。

  要用 Comparator 的话只需要在创建 TreeMap 时传入一个 Comparator 的匿名内部类即可。

插入SortedMap 的key类都必须实现Comparable接口或者Comparator（当创建SortedMap时指定了Comparator，则key必须实现Comparator；否则必须实现Comparable接口），否则在put()元素时会报 ClassCastException。

此外，SortedMap的顺序性应该与equals()方法保持一致，即当k1.compareTo(k2)或comparator.compare(k1,k2)为true时，k1.equals(k2)也应该为true。

回过头来看 NavigableMap，它是 JDK 1.6 新增的，在SortedMap的基础上增加了一些“导航方法”来返回与搜索目标最近的元素。

• lowEntry()：返回第一个比给定Map.Entry小的元素。
• floorEntry()：返回第一个比给定Map.Entry小或相等的元素
• ceilingEntry()：返回第一个比给定Map.Entry大或相等的元素
• higherEntry()：返回第一个比给定Map.Entry大的元素

CRUD时的比较过程

整个TreeMap 增删改查中没有使用元素的hashCode()

• put()、get()、remove()、containsKey()： 等比较key的方法仅通过comparator或comparable。
• containsValue()、replace(k,oldVal,newVal)： 等比较value的方法都使用了equals()方法
• putAll(SortedMap map)： 添加一个已有的SortedMap到TreeMap中，会先获取map的Comparator p2，如果本TreeMap创建时指定了Comparator p1，则会比较 if (p2 == p1|| (p1 != null && p1.equals(p2))) 是否为true，否则会拒绝添加map到TreeMap中

• ← Previous Post
• Next Post →