TreeMap是紅黑樹算法的實(shí)現(xiàn),實(shí)現(xiàn)了SortedMap接口,要注意的是它不在使用哈希表,存儲(chǔ)方式是一個(gè)特殊的二叉樹,有關(guān)紅黑樹:
http://baike.baidu.com/view/133754.htm http://www.bt285.cn
這篇文章介紹的不錯(cuò),我之前沒有聽說過二叉樹,我就是看這篇文章加上看一下TreeMap的源代碼才搞懂紅黑樹算法的.
這里不打算研究TreeMap的源代碼了,因?yàn)橥耆且粋€(gè)算法的實(shí)現(xiàn),如果對(duì)這個(gè)算法不了解,肯定看不懂,我也有很多地方不是沒有完全看明白,這里就談?wù)凾reeMap的使用吧.
TreeMap的聲明:public class TreeMap extends AbstractMap implements SortedMap,Cloneable, java.io.Serializable
所以我們要知道SortedMap接口:
SortedMap表示的是一個(gè)排序的Map
public interface SortedMap extends Map
增加了幾個(gè)方法的定義
SortedMap headMap(Object toKey)
SortedMap tailMap(Object fromKey)
SortedMap subMap(Object fromKey, Object toKey)
Object firstKey()
Object lastKey()
既然TreeMap是有序的,自然要求元素是可以比較大小的,如果構(gòu)造函數(shù)指定Comparator的話,就使用這個(gè)Comparator比較大小,如果沒有指定Comparator的話,就使用自然排序(元素要實(shí)現(xiàn)Comparable接口).如果這兩個(gè)都不可用,就等著出錯(cuò)吧.
現(xiàn)看一下該接口的定義:
public interface Comparable{
public int compareTo(Object o);
}
該接口定義類的自然順序,實(shí)現(xiàn)該接口的類就可以按這種方式排序.
一般要求:
e1.equals((Object)e2)和e1.compareTo((Object)e2)==0具有相同的值,
這樣的話我們就稱自然順序就和equals一致.
這個(gè)接口有什么用呢?
如果數(shù)據(jù)或者List中的元素實(shí)現(xiàn)了該接口的話,我們就可以調(diào)用Collections.sort或者Arrays方法給他們排序.
如果自然順序和equals不一致的話,如果出現(xiàn)在Sorted Map和Set里面,
就會(huì)出現(xiàn)預(yù)想不到的邏輯錯(cuò)誤,可能你調(diào)用add的時(shí)候添加不了,而集合里面確沒有這個(gè)元素.具體的討論要接口哈希表的應(yīng)用.
public interface Comparator {
int compare(Object o1, Object o2);
boolean equals(Object obj);
}
定義了兩個(gè)方法,其實(shí)我們一般都只需要實(shí)現(xiàn)compare方法就行了,因?yàn)轭惗际悄J(rèn)從Object繼承
所以會(huì)使用Object的equals方法.
Comparator一般都作為一個(gè)匿名類出現(xiàn),對(duì)于沒有實(shí)現(xiàn)Comparable的對(duì)象的集合,排序的時(shí)候
需要指定一個(gè)Comparator.
這里舉例說明
對(duì)于實(shí)現(xiàn)了Comparable的類我們就用最簡單的Integer
List list=new ArrayList();
list.add(new Integer(3));
list.add(new Integer(53));
list.add(new Integer(34));
Collections.sort(list);
對(duì)于沒有實(shí)現(xiàn)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());
})
因?yàn)槭嵌鏄?所以一般查找時(shí)間復(fù)雜度為 o(lg(n)),這個(gè)效率當(dāng)然沒有HashMap的效率高.不過TreeMap比HashMap功能強(qiáng)大,如果不需要排序的話當(dāng)然不會(huì)用TreeMap,如果需要排序的話,HashMap無法勝任,當(dāng)然要用TreeMap了,它可以求子Map.所以這個(gè)是適用場合問題,無法比較他們.
另外,我們也習(xí)慣了,有Map就會(huì)跟一個(gè)Set,我們都可以猜到TreeSet和通過TreeMap實(shí)現(xiàn)的一個(gè)SortedSet的實(shí)現(xiàn).不過我覺的TreeSet好像比TreeMap用的場合多一些,求子集是很常用的呀!!