集合容器学习之TreeMap

TreeMap是另一种重要的Map。TreeMap中元素有序排列，内部使用红黑树来管理数据。红黑树虽然比较复杂，但可以保证任意元素可以在O(logn)时间内找到。

红黑树

首先简单介绍一下红黑树：红黑树是一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
红黑树有如下性质：

  1. 每个节点都只能是红色或者黑色
  2. 根节点是黑色
  3. 每个叶节点（NIL节点，空节点）是黑色的。
  4. 如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。所以红黑树它是复杂而高效的，其检索效率O(log n)。
红黑树的增删非常复杂，由于时间的原因，本文就不深入探寻了。可以通过 Java提高篇（二七）—–TreeMap和教你初步了解红黑树以及算法导论来深入学习。

构造方法

首先来看一看TreeMap的构造方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public TreeMap() {
    comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(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) {
    }
}

构造方法一共有4种。可以发现，构造方法主要的作用就是指定相应的comparator，也就是比较的规则。如果不指定，那么 必须在key中实现Comparable接口，重写comparaTo方法 。

put、get和remove方法

增删改实际上都是维护TreeMap红黑树上的节点，进行修改。只要掌握了红黑树原理，这些方法自然就明白了。

Comparable接口

对于TreeMap来说，Comparable非常重要。如果不指定比较器，那么key必须实现Comparable接口，来定义内置比较器。我们来学习一下Comparable接口的使用。
Comparable接口是一个比较协议，通过其中的compareTo方法来体现具体的逻辑。一旦类实现了Comparable接口，就可以跟许多泛型算法以及依赖于接口的集合实现。如果正在编写一个值类， 它具有明显的内在排序关系，比如字母、值或年代，那么就应该实现Comparable接口 ：

1
2
3
public interface Comparable<T> {
	public int compareTo(T o);
}

compareTo中应该这样实现：当该对象小于、等于或大于指定对象的时候，分别返回一个负整数、0、正整数。如果由于指定对象的类型原因无法比较，那么抛出ClassCastException异常。需要注意的是，实现的compareTo方法必须具有 自反性、对称性和传递性 。
我们可以这样使用Comparable：

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
public class Person implements Comparable<Person1>
{
    private int age;
    private String name;
    public Person(String name, int age)
    {
        this.name = name;
        this.age = age;
    }
    @Override
    public int compareTo(Person o)
    {
        return this.age-o.age;
    }
    @Override
    public String toString()
    {
        return name+":"+age;
    }

    public static void main(String[] args) {
	    Person person = new Person("zzh",18);
	       Person person2 = new Person("jj",17);
	       Person person3 = new Person("qq",19);
		List<Person1> list = new ArrayList<>();
		list.add(person1);
		list.add(person2);
		list.add(person3);

		System.out.println(list);
		Collections.sort(list);
		System.out.println(list);
	}
}

输出：

[zzh:18, jj:17, qq:19]
[jj:17, zzh:18, qq:19]

如果一个类无法修改或没有在这个类中实现Comparable接口，那么我们可以使用 比较器Comparator ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//将上一段代码的Person类去掉Comparable实现
//将main方法贴在下面
public static void main(String[] args) {
    Person person = new Person("zzh",18);
       Person person2 = new Person("jj",17);
       Person person3 = new Person("qq",19);
	List<Person1> list = new ArrayList<>();
	list.add(person1);
	list.add(person2);
	list.add(person3);

	System.out.println(list);
	Collections.sort(list2,new Comparator<Person2>(){
       @Override
       public int compare(Person2 o1, Person2 o2)
       {
           if(o1 == null || o2 == null)
               return 0;
           return o1.getAge()-o2.getAge();
       }
    });
	System.out.println(list);
}

可以灵活的使用Comparable接口或Comparator类来灵活的与集合工具类配合排序。

小结

TreeMap是内部为红黑树的排序树，查找速度为log(n)，可以通过指定Comparator比较器来实现比较的过程。

参考
Effective java 第12条
Comparable与Comparator浅析