TreeMap是红黑树算法的实现,实现了SortedMap接口,要注意的是它不在使用哈希表,存储方式是一个特殊的二叉树,有关红黑树:
http://baike.baidu.com/view/133754.htm http://www.bt285.cn
这篇文章介绍的不错,我之前没有听说过二叉树,我就是看这篇文章加上看一下TreeMap的源代码才搞懂红黑树算法的.
这里不打算研究TreeMap的源代码了,因为完全是一个算法的实现,如果对这个算法不了解,肯定看不懂,我也有很多地方不是没有完全看明白,这里就谈谈TreeMap的使用吧.
TreeMap的声明:public class TreeMap extends AbstractMap implements SortedMap,Cloneable, java.io.Serializable
所以我们要知道SortedMap接口:
SortedMap表示的是一个排序的Map
public interface SortedMap extends Map
增加了几个方法的定义
SortedMap headMap(Object toKey)
SortedMap tailMap(Object fromKey)
SortedMap subMap(Object fromKey, Object toKey)
Object firstKey()
Object lastKey()
既然TreeMap是有序的,自然要求元素是可以比较大小的,如果构造函数指定Comparator的话,就使用这个Comparator比较大小,如果没有指定Comparator的话,就使用自然排序(元素要实现Comparable接口).如果这两个都不可用,就等着出错吧.
现看一下该接口的定义:
public interface Comparable{
public int compareTo(Object o);
}
该接口定义类的自然顺序,实现该接口的类就可以按这种方式排序.
一般要求:
e1.equals((Object)e2)和e1.compareTo((Object)e2)==0具有相同的值,
这样的话我们就称自然顺序就和equals一致.
这个接口有什么用呢?
如果数据或者List中的元素实现了该接口的话,我们就可以调用Collections.sort或者Arrays方法给他们排序.
如果自然顺序和equals不一致的话,如果出现在Sorted Map和Set里面,
就会出现预想不到的逻辑错误,可能你调用add的时候添加不了,而集合里面确没有这个元素.具体的讨论要接口哈希表的应用.
public interface Comparator {
int compare(Object o1, Object o2);
boolean equals(Object obj);
}
定义了两个方法,其实我们一般都只需要实现compare方法就行了,因为类都是默认从Object继承
所以会使用Object的equals方法.
Comparator一般都作为一个匿名类出现,对于没有实现Comparable的对象的集合,排序的时候
需要指定一个Comparator.
这里举例说明
对于实现了Comparable的类我们就用最简单的Integer
List list=new ArrayList();
list.add(new Integer(3));
list.add(new Integer(53));
list.add(new Integer(34));
Collections.sort(list);
对于没有实现Comparable的,我们就用Object,按照hashCode大小来排序.
List list= new ArrayList();
list.add(new Object());
list.add(new Object());
list.add(new Object());
Collections.sort(list,new Comparator(){ public int compare(Object o1, Object o2){
return (o1.hashCode()-o2.hashCode());
})
因为是二叉树,所以一般查找时间复杂度为 o(lg(n)),这个效率当然没有HashMap的效率高.不过TreeMap比HashMap功能强大,如果不需要排序的话当然不会用TreeMap,如果需要排序的话,HashMap无法胜任,当然要用TreeMap了,它可以求子Map.所以这个是适用场合问题,无法比较他们.
另外,我们也习惯了,有Map就会跟一个Set,我们都可以猜到TreeSet和通过TreeMap实现的一个SortedSet的实现.不过我觉的TreeSet好像比TreeMap用的场合多一些,求子集是很常用的呀!!