8.6.5 SortedMap接口和TreeMap实现类

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

8.6.5 SortedMap接口和TreeMap实现类

正如Set接口派生出SortedSet子接口有一个TreeSet实现类一样,Map接口也派生的SortedMap子接口也有一个TreeMap实现类.

TreeMap数据结构 红黑树

TreeMap就是一个红黑树数据结构,每个key-value对即作为红黑树的一个节点。 TreeMap存储key-value对(节点)时,需要根据key对节点进行排序。 TreeMap可以保证所有的key-value对处于有序状态。

自然排序 定制排序

TreeMap也有两种排序方式:

  • 自然排序:TreeMap的所有key必须实现Comparable接口,而且所有的key应该是同一个类的对象,否则将会抛出ClassCastException异常。
  • 定制排序:创建TreeMap时,传入一个Comparator对象,该对象负责对TreeMap中的所有key进行排序。采用定制排序时不要求Map的key实现Comparable接口。

TreeMap判断两个key相等的标准

类似于TreeSet中判断两个元素相等的标准, TreeMap中判断两个key相等的标准是:
如果两个key通过compareTo()方法返回0, 那么TreeMap就认为这两个key是相等的。

理解Comparable接口的compareTo方法

  • 如果对象.compareTo(参数)返回0,则表示该对象和参数相等.
  • 如果对象.compareTo(参数)返回正数,则表示该对象大于参数.
  • 如果对象.compareTo(参数)返回负数,则表示该对象小于参数.

为了便于记忆可以把Comparable接口的compareTo方法理解为减去的意思,也就是说对象.compareTo(参数)意思为对象减去参数.

  • 如果对象减去参数等于0,则两者相等.
  • 如果对象减去参数大于0,则对象大于参数,
  • 如果对象减去参数小于0则对象小于参数。

理解Comparator接口的compare方法

同样的Comparator接口的compare(参数1,参数2)可以理解为前面的参数减去后面的参数的计算结果.也就是参数1减去参数2,所以:

  • 如果参数1减去参数2等于0时,两者相等,
  • 如果参数1减去参数2大于0,则参数1大于参数2,
  • 如果参数1减去参数2小于0,则参数1小于参数2.

作为key的自定义类的要求

如果使用自定义类作为TreeMap的key,且想让TreeMap良好地工作,则重写该类的equals()方法和compareTo()方法时应保持一致的返回结果:
**两个key通过equals方法比较返回true时,它们通过compareTo()方法比较应该返回0**。如果equals()方法与compareTo()方法的返回结果不一致, TreeMap与Map接口的规则就会冲突。

Java使用Map来实现的Set

再次强调:Set和Map的关系十分密切,Java源码就是先实现了HashMap、TreeMap等集合,然后通过包装一个所有的value都为null的Map集合实现了Set集合类。

Set和Map的关系

再次强调:Set和Map的关系十分密切,Java源码就是先实现了HashMap、 TreeMap等集合,然后通过包装一个所有的value都为null的Map集合来实现Set集合类。

返回key或Entry的方法

与TreeSet类似的是, TreeMap中也提供了一系列根据key顺序访问key-value对的方法。

查找最大最小的key

方法 描述
K firstKey() 返回该Map中的最小key值,如果该Map为空,则返回null。
K lastKey() 返回该Map中的最大key值,如果该Map为空或不存在这样的key,则都返回null。

查找给定key的前一个或后一个key

方法 描述
K higherKey(K key) 返回该Map中大于参数key的最小key值。如果该Map为空或不存在这样的key-value对,则都返回null。
K lowerKey(K key) 返回该Map中小于参数key的最大key值。如果该Map为空或不存在这样的key,则都返回null

查找最大最小key对应的Entry

方法 描述
Map.Entry<K,​V> firstEntry() 返回该Map中最小key所对应的key-value对,如果该Map为空,则返回null。
Map.Entry<K,​V> lastEntry() 返回该Map中最大key所对应的 key-value对,如果该Map为空或不存在这样的key-value对,则都返回null。

查找给定key的前一个或后一个key对应的Entry

方法 描述
Map.Entry<K,​V> higherEntry(K key) 返回该Map中大于参数key的最小key所对应的key-value对。如果该Map为空,则返回null。
Map.Entry<K,​V> lowerEntry(K key) 返回该Map中小于参数key的最大key所对应的key-value对。如果该Map为空或不存在这样的 key-value对,则都返回null

截取子Map的方法

截取指定区间

方法 描述
SortedMap<K,​V> subMap(K fromKey, K toKey) 返回该Map的子Map,其key的范围是从fromKey(包括)到toKey(不包括)。subXXX()方法遵循前闭后开原则。
NavigableMap<K,​V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) 返回该Map的子Map,其key的范围是从 fromKey到toKey,是否包括fromKey取决于第二个参数,是否包括toKey取决于第四个参数.

向前截取

方法 描述
SortedMap<K,​V> headMap(K toKey) 返回该Map的子Map,其key的范围是小于toKey的所有key,不包括toKey.
NavigableMap<K,​V> headMap(K toKey, boolean inclusive) Returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey.

向后截取

方法 描述
SortedMap<K,​V> tailMap(K fromKey) 返回该Map的子Map,其key的范围是大于fromKey(包括)的所有key。
NavigableMap<K,​V> tailMap(K fromKey, boolean inclusive) 返回该Map的子Map,其key的范围是大于fromKey的所有key,子Map是否包括第一个fromKey取决于第二个参数.

表面上看起来这些方法很复杂,其实它们很简单。因为TreeMap中的key-value对是有序的,所以增加了访问第一个、最后一个、前一个、后一个、key-value对的方法,并提供了几个从TreeMap中截取子TreeMap的方法。

实例

下面以自然排序为例,介绍TreeMap的基本用法。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.*;

class R implements Comparable
{
    int count;
    public R(int count)
    {
        this.count = count;
    }
    public String toString()
    {
        return "R[count:" + count + "]";
    }
    // 根据count来判断两个对象是否相等。
    public boolean equals(Object obj)
    {
        if (this == obj)
            return true;
        if (obj != null && obj.getClass() == R.class)
        {
            R r = (R)obj;
            return r.count == this.count;
        }
        return false;
    }
    // 根据count属性值来判断两个对象的大小。
    public int compareTo(Object obj)
    {
        R r = (R)obj;
        return count > r.count ? 1 :
            count < r.count ? -1 : 0;
    }
}
public class TreeMapTest
{
    public static void main(String[] args)
    {
        TreeMap tm = new TreeMap();
        tm.put(new R(3) , "轻量级Java EE企业应用实战");
        tm.put(new R(-5) , "疯狂Java讲义");
        tm.put(new R(9) , "疯狂Android讲义");
        System.out.println(tm);
        // 返回该TreeMap的第一个Entry对象
        System.out.println(tm.firstEntry());
        // 返回该TreeMap的最后一个key值
        System.out.println(tm.lastKey());
        // 返回该TreeMap的比new R(2)大的最小key值。
        System.out.println(tm.higherKey(new R(2)));
        // 返回该TreeMap的比new R(2)小的最大的key-value对。
        System.out.println(tm.lowerEntry(new R(2)));
        // 返回该TreeMap的子TreeMap
        System.out.println(tm.subMap(new R(-1) , new R(4)));
    }
}

上面程序中定义了一个R类,该类重写了equals方法,并实现了Comparable接口,所以可以使用该R对象作为TreeMap的key,该TreeMap使用自然排序。运行上面程序,看到如下运行结果:

1
2
3
4
5
6
{R[count:-5]=疯狂Java讲义, R[count:3]=轻量级Java EE企业应用实战, R[count:9]=疯狂Android讲义}
R[count:-5]=疯狂Java讲义
R[count:9]
R[count:3]
R[count:-5]=疯狂Java讲义
{R[count:3]=轻量级Java EE企业应用实战}