bt下載與小說(shuō)520

          bt下載與小說(shuō)520

            BlogJava :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
            16 隨筆 :: 0 文章 :: 6 評(píng)論 :: 0 Trackbacks

          TreeMap是紅黑樹(shù)算法的實(shí)現(xiàn),實(shí)現(xiàn)了SortedMap接口,要注意的是它不在使用哈希表,存儲(chǔ)方式是一個(gè)特殊的二叉樹(shù),有關(guān)紅黑樹(shù):
          http://baike.baidu.com/view/133754.htm  http://www.bt285.cn

          這篇文章介紹的不錯(cuò),我之前沒(méi)有聽(tīng)說(shuō)過(guò)二叉樹(shù),我就是看這篇文章加上看一下TreeMap的源代碼才搞懂紅黑樹(shù)算法的.

           

          這里不打算研究TreeMap的源代碼了,因?yàn)橥耆且粋€(gè)算法的實(shí)現(xiàn),如果對(duì)這個(gè)算法不了解,肯定看不懂,我也有很多地方不是沒(méi)有完全看明白,這里就談?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比較大小,如果沒(méi)有指定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í)候添加不了,而集合里面確沒(méi)有這個(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ì)于沒(méi)有實(shí)現(xiàn)Comparable的對(duì)象的集合,排序的時(shí)候
          需要指定一個(gè)Comparator.

          這里舉例說(shuō)明
          對(duì)于實(shí)現(xiàn)了Comparable的類我們就用最簡(jiǎn)單的Integer
          List list=new ArrayList();
          list.add(new Integer(3));
          list.add(new Integer(53));
          list.add(new Integer(34));
          Collections.sort(list);

          對(duì)于沒(méi)有實(shí)現(xiàn)Comparable的,我們就用Object,按照hashCode大小來(lái)排序.
          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ù),所以一般查找時(shí)間復(fù)雜度為 o(lg(n)),這個(gè)效率當(dāng)然沒(méi)有HashMap的效率高.不過(guò)TreeMap比HashMap功能強(qiáng)大,如果不需要排序的話當(dāng)然不會(huì)用TreeMap,如果需要排序的話,HashMap無(wú)法勝任,當(dāng)然要用TreeMap了,它可以求子Map.所以這個(gè)是適用場(chǎng)合問(wèn)題,無(wú)法比較他們.
           
          另外,我們也習(xí)慣了,有Map就會(huì)跟一個(gè)Set,我們都可以猜到TreeSet和通過(guò)TreeMap實(shí)現(xiàn)的一個(gè)SortedSet的實(shí)現(xiàn).不過(guò)我覺(jué)的TreeSet好像比TreeMap用的場(chǎng)合多一些,求子集是很常用的呀!!

          posted on 2008-10-30 20:59 bt下載 閱讀(3295) 評(píng)論(1)  編輯  收藏

          評(píng)論

          # re: TreeMap的使用及注意事項(xiàng) 2008-11-01 17:10 金山詞霸2008
          二叉樹(shù)的查找時(shí)間復(fù)雜度為 o(lg(n))也基本滿意了  回復(fù)  更多評(píng)論
            


          只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


          網(wǎng)站導(dǎo)航:
           
          主站蜘蛛池模板: 墨脱县| 平舆县| 邢台县| 渭源县| 平远县| 门头沟区| 连城县| 巩义市| 遵义县| 凤凰县| 山阳县| 吴忠市| 桑日县| 梅州市| 新宁县| 周口市| 浏阳市| 额尔古纳市| 永福县| 安阳市| 张家川| 周口市| 西盟| 泰安市| 策勒县| 衢州市| 开远市| 繁峙县| 武城县| 洪雅县| 明水县| 汝南县| 道孚县| 黄大仙区| 繁昌县| 弋阳县| 余庆县| 大方县| 南郑县| 八宿县| 镇坪县|