• 8.6.5 SortedMap接口和TreeMap实现类
  • TreeMap两种排序方式
  • TreeMap判断两个key相等的标准
  • compareTo方法比较大小
  • 作为key的自定义类的要求
  • Set和Map的关系
  • 返回key或Entry的方法
  • 截取子Map的方法
  • 实例

8.6.5 SortedMap接口和TreeMap实现类

正如Set接口派生出SortedSet子接口有一个TreeSet实现类一样,Map接口也派生的SortedMap子接口也有一个TreeMap实现类.
TreeMap就是一个红黑树数据结构,每个key-value对即作为红黑树的一个节点。 TreeMap存储key-value对(节点)时,需要根据key对节点进行排序。 TreeMap可以保证所有的key-value对处于有序状态。

TreeMap两种排序方式

TreeMap也有两种排序方式。

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

TreeMap判断两个key相等的标准

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

compareTo方法比较大小

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

为了便于记忆可以把Comparable接口的compareTo方法理解为减去的意思,也就是说对象.compareTo(参数)意思为对象减去参数.如果对象减去参数等于0,则两者相等.如果对象减去参数大于0,则对象大于参数,如果对象减去参数小于0则对象小于参数。

同样的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接口的规则就会冲突。

Set和Map的关系

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

返回key或Entry的方法

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

方法	描述
Object firstKey()	返回该Map中的最小key值,如果该Map为空,则返回null。
Object lastKey()	返回该Map中的最大key值,如果该Map为空或不存在这样的key,则都返回null。
Map.Entry firstEntry()	返回该Map中最小key所对应的key-value对,如果该Map为空,则返回null。
Map.Entry lastEntry()	返回该Map中最大key所对应的 key-value对,如果该Map为空或不存在这样的key-value对,则都返回null。
Object higherKey(Object key)	返回该Map中大于参数key的最小key值。如果该Map为空或不存在这样的key-value对,则都返回null。
Object lowerKey(Object key)	返回该Map中小于参数key的最大key值。如果该Map为空或不存在这样的key,则都返回null
Map.Entry higherEntry(Object key)	返回该Map中大于参数key的最小key所对应的key-value对。如果该Map为空,则返回null。
Map.Entry lowerEntry(Object key)	返回该Map中小于参数key的最大key所对应的key-value对。如果该Map为空或不存在这样的 key-value对,则都返回null

截取子Map的方法

方法	描述
SortedMap subMap(Object fromKey, Object toKey)	返回该Map的子Map,其key的范围是从fromKey(包括)到toKey(不包括)。subXXX()方法遵循前闭后开原则。
NavigableMap subMap(Object fromKey, boolean fromInclusive, Object toKey, boolean tolnclusive)	返回该Map的子Map,其key的范围是从 fromKey到toKey,是否包括fromKey取决于第二个参数,是否包括toKey取决于第四个参数.
NavigableMap headMap(Object toKey, boolean inclusive)	返回该Map的子Map,其key的范围是小于toKey的所有key,是否包括toKey取决于第二个参数
SortedMap headMap(Object toKey)	返回该Map的子Map,其key的范围是小于toKey的所有key,不包括toKey.
NavigableMap tailMap(Object fromKey, boolean inclusive)	返回该Map的子Map,其key的范围是大于fromKey的所有key,子Map是否包括第一个fromKey取决于第二个参数.
SortedMap tailMap(Object fromKey)	返回该Map的子Map,其key的范围是大于fromKey(包括)的所有key。

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

实例

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

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使用自然排序。运行上面程序,看到如下运行结果:

原文链接: 8.6.5 SortedMap接口和TreeMap实现类