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用的場合多一些,求子集是很常用的呀!!