Jungleford's Home BlogJava分舵

          Java技術(shù)研究,兼探討歷史話(huà)題

          BlogJava 首頁(yè) 新隨筆 聯(lián)系 聚合 管理
            24 Posts :: 0 Stories :: 53 Comments :: 0 Trackbacks
          jungleford如是說(shuō)

              對(duì)于Java集合框架(Java Collections Framework,JCF),Java玩家大概都不會(huì)陌生,在C++里面相似的概念是標(biāo)準(zhǔn)模板庫(kù)(Standard Template Library,STL),主要是對(duì)一些數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的封裝。考慮到這是一個(gè)Java初學(xué)者將會(huì)經(jīng)常接觸的工具,所以有了以下的一些文字。主要是參考了
          IBM developerWorks上的一篇教程,它可能解釋得更加清晰,這里算是濃縮了一下吧,真正的來(lái)龍去脈可以看看JDK文檔里的“The Collections Framework”,說(shuō)明更為詳細(xì)。

          問(wèn)題的源頭

          • 集合:對(duì)象的容器與數(shù)據(jù)結(jié)構(gòu)
              回憶一下我們?cè)诔绦蛟O(shè)計(jì)里頭可能會(huì)面對(duì)一些什么,無(wú)非是兩類(lèi):基本類(lèi)型和復(fù)合類(lèi)型,后者常見(jiàn)的組織方式就是類(lèi)。和基本類(lèi)型不同,類(lèi)對(duì)象通常是需要以動(dòng)態(tài)方式分配的,譬如在內(nèi)存的堆空間里new一個(gè)對(duì)象,這個(gè)我們一寫(xiě)OO的程序就必然會(huì)用到。同時(shí)我們面對(duì)的不僅僅是單個(gè)的基本類(lèi)型或?qū)ο螅瑢?duì)多個(gè)這樣的數(shù)據(jù)我們通常采用的組織方式是什么?不錯(cuò),是數(shù)組,這是伴隨程序設(shè)計(jì)的一個(gè)古老概念。數(shù)組的優(yōu)點(diǎn)顯而易見(jiàn),像根據(jù)下標(biāo)檢索元素這樣的操作不費(fèi)吹灰之力,但缺點(diǎn)也很明顯:空間固定而不能動(dòng)態(tài)增長(zhǎng)(像Java這樣的強(qiáng)類(lèi)型語(yǔ)言對(duì)數(shù)組越界是及其敏感的),插入或刪除元素比較費(fèi)勁。因此數(shù)組不是解決一切集合問(wèn)題的方便工具。我們可能需要一些新的工具,研究這些工具常常就是研究數(shù)據(jù)結(jié)構(gòu),特別的,數(shù)組本身就是一種線(xiàn)性有序的數(shù)據(jù)結(jié)構(gòu)。
              數(shù)據(jù)結(jié)構(gòu)的數(shù)學(xué)基礎(chǔ)是集合論,為什么這么說(shuō)呢?上面說(shuō)過(guò),現(xiàn)在我們要研究的不是單個(gè)的基本類(lèi)型或?qū)ο螅鄠€(gè)對(duì)象的整體不就是集合嗎?從OO的角度上看,集合也是一種對(duì)象,但它是一種特殊的對(duì)象:對(duì)象的容器(注意,我們這里沒(méi)有繼續(xù)討論基本類(lèi)型的集合,因?yàn)榛绢?lèi)型和存儲(chǔ)分配方式與對(duì)象有著本質(zhì)的差別)。集合論的一個(gè)根本問(wèn)題就是:給定一個(gè)元素,集合必須能夠回答該元素是或者不是屬于這個(gè)集合。還有一個(gè)問(wèn)題也很重要,就是:如果元素是屬于一個(gè)集合,那該元素在集合中的地位應(yīng)該是唯一的,或者說(shuō)它是唯一確定的。當(dāng)然還有其它問(wèn)題,譬如查找、遍歷、排序等等,這和具體的集合類(lèi)型相關(guān),后面將會(huì)講到。
          • 無(wú)序集、有序集、映射
              談到集合的類(lèi)型,我們?cè)诟咧兴鶎W(xué)的集合概念是其中的一種,叫做“無(wú)序集”,也就是說(shuō)集合的各個(gè)元素都是平等的,沒(méi)有先后的區(qū)別,于是在無(wú)序集當(dāng)中就決不允許出現(xiàn)一模一樣的元素,否則當(dāng)取到這個(gè)元素的時(shí)候就不知道應(yīng)該取哪一個(gè),這就違反了上面的“唯一確定”原則。
              等到我們上了大學(xué),開(kāi)始知道了另一種集合類(lèi)型,叫做“有序集”(或者叫“線(xiàn)性表”,區(qū)別于以后碰到的像“樹(shù)”,“圖”這樣的非線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)),如果是計(jì)算機(jī)專(zhuān)業(yè)的,大概學(xué)過(guò)離散數(shù)學(xué)當(dāng)中的“代數(shù)結(jié)構(gòu)”,那你就更清楚的知道,“有序集”其實(shí)是一種“二元關(guān)系”,確切的說(shuō)是“偏序關(guān)系”,它是可以包含相同元素的,因?yàn)閮蓚€(gè)的相同元素的“序號(hào)”可以不同,這樣根據(jù)“序號(hào)”仍可以“唯一確定”一個(gè)元素,數(shù)組就是一種有序集,有序集的另一個(gè)特點(diǎn)就是任意兩個(gè)元素可以確定他們的順序。
              無(wú)序集,有序集,難道還有第三種可能?呵呵,它還是出現(xiàn)在我們的高中代數(shù)課本里,叫做“映射”。映射也是集合?其實(shí)自從康托爾以來(lái),集合論就認(rèn)為“萬(wàn)物皆集合”(但也就是這個(gè)斷言導(dǎo)致了集合論以后的尷尬境地,有興趣可以看看羅素或哥德?tīng)柕囊恍┙Y(jié)論,或
          google“集合論 悖論”)。映射其實(shí)是一種“元素對(duì)”的集合,就像f(a)=b, f(c)=d, ...等效于集合(無(wú)序集){(a, b), (c, d), ...},在“映射”中可以看作是(原象, 象)的集合,換一種說(shuō)法就是(關(guān)鍵字key, 值value)的集合。所以我們可以在笛卡兒正交坐標(biāo)平面上畫(huà)出漂亮的函數(shù)圖像,因?yàn)樵诩险摽磥?lái),函數(shù)(映射)就是二維平面上的一個(gè)個(gè)點(diǎn),明白了?這樣一來(lái)上面的“有序集”也好理解了,偏序關(guān)系a>b>c>d>...(不知道“偏序關(guān)系”就把它們看作是數(shù)組x[1]=a, x[2]=b, x[3]=c, x[4]=d ...好了)等效于無(wú)序集{(1, a), (2, b), (3, c), (4, d), ...},于是乎,所有的集合都等效于無(wú)序集!所以高中只教了我們一種集合,呵呵……

          JCF的全家福

              好啦好啦,這些我們都知道,又不是在上數(shù)學(xué)課,說(shuō)了這么多廢話(huà),怎么還沒(méi)扯到正題上來(lái)?JCF的影子我還沒(méi)看見(jiàn)呢!列位看官別急,這就給您道來(lái)。其實(shí)上面的概念對(duì)理解JCF非常重要。
              JCF是個(gè)頗有點(diǎn)規(guī)模的家族,看看它的類(lèi)層次關(guān)系圖就知道了,下面這張圖(圖1)摘自著名的
          Thinking in Java
          o_collection.gif
                                                   圖1 JCF層次結(jié)構(gòu)

              哇,這么多接口和類(lèi),真有點(diǎn)讓人無(wú)從下手的感覺(jué)。其實(shí)我們真正需要記住的只是這么一個(gè)超超easy的結(jié)構(gòu)(圖2):

          o_collection1.gif
                                                  圖2

              這張圖看起來(lái)舒服多了吧?但它又能說(shuō)明什么問(wèn)題呢?它怎么就能夠把握整個(gè)JCF呢?我們把
          Collection接口置于最頂上,意思是想說(shuō):Collection其實(shí)是整個(gè)JCF家族中的“祖宗”,幾乎所有的JCF成員都源自該接口,或者和它有密切的關(guān)系,Collection提供關(guān)于集合的一些通用操作的接口,包括插入(add()方法)、刪除(remove()方法)、判斷一個(gè)元素是不是其成員(contains()方法)、遍歷(iterator()方法)等等。注意了,前面的“廢話(huà)”在這里將得到體現(xiàn):Set接口體現(xiàn)的是“無(wú)序集”的概念,它是不允許有重復(fù)元素出現(xiàn)的;List接口代表“有序集”;而Map接口則是“映射”(在早期的Java版本中并不叫Map,我們?cè)诤竺鏁?huì)看到),其實(shí)Map.Entry接口就是代表一個(gè)“元素對(duì)”我們可以通過(guò)Map的entrySet()方法得到這樣一個(gè)由“元素對(duì)”組成的Set對(duì)象。我們注意到Set和List都是從“祖宗”Collection派生的,而Map不是,畢竟對(duì)一對(duì)元素的操作與對(duì)單個(gè)元素的操作還是有區(qū)別的,但是如果你仔細(xì)對(duì)照一下Collection和Map的源代碼,以及它們的直接后代AbstractCollectionAbstractMap的源代碼,你將會(huì)發(fā)現(xiàn)很多相似的地方,所以我們?nèi)匀豢梢园袽ap看成是和Collection有著血緣關(guān)系的接口,而和Set,List一起處于并列的位置。
              有了“無(wú)序集”,“有序集”和“映射”,我們就可以定義各種各樣的抽象數(shù)據(jù)結(jié)構(gòu)了,譬如圖1所示的向量,鏈表,堆棧,哈希表,平衡二叉樹(shù)等。但我們需要記住的,僅僅是圖2,置于其它的成員,在用到的時(shí)候查一下API手冊(cè)不就行了?不過(guò)一般初學(xué)者還是比較容易用到一些類(lèi),像Vector、ArrayList、HashMap,我在這里列了一張表,顯示了常見(jiàn)的JCF成員及其關(guān)系:

          集合框架的祖宗: Collection

          歷史集合

          新集合

          無(wú)序集: Set

          有序集: List

          映射:Dictionary

          映射:Map

          AbstractSet

          SortedSet

          AbstractList

          AbstractSequentialList




          Hashtable

          AbstractMap

          SortedMap

          歷史集合

          新集合



          LinkedList



          WeakHashMap



          IdentityHashMap



          HashMap



          TreeMap

          HashSet

          TreeSet

          Vector

          ArrayList

          LinkedHashSet

           

          Stack

             

          Properties

             

          LinkedHashMap

           

              可能有的概念您還不是太了解,譬如什么叫“歷史集合”,Hashtable、HashMap、TreeMap三者之間有什么區(qū)別和聯(lián)系,怎樣實(shí)現(xiàn)對(duì)一個(gè)特定集合的快速遍歷、元素查找或者排序,沒(méi)關(guān)系,我們?cè)谙旅鎸⒅鹨贿M(jìn)行研究。

          細(xì)節(jié)考慮:目標(biāo)與效率

              有了JCF的層次還不夠,重要的是對(duì)集合所容納的對(duì)象的具體操作,以前我們學(xué)數(shù)據(jù)結(jié)構(gòu)的時(shí)候可能老師總會(huì)讓你計(jì)算一個(gè)算法的時(shí)間復(fù)雜度,可能你會(huì)對(duì)這個(gè)O(f(n))很不耐煩,但事實(shí)上算法效率是一個(gè)重要的因素。

            1. 側(cè)重點(diǎn):遍歷 vs. 查找

              對(duì)集合的有兩個(gè)主要的應(yīng)用:我需要知道集合有哪些元素;根據(jù)條件找到一個(gè)特定的元素。在算法上通常稱(chēng)為“遍歷”和“查找”。不要以為我們生活中不常用哦!譬如CCTV的“幸運(yùn)52”里面,李詠?zhàn)寘①愓邎?bào)出一款PDA的準(zhǔn)確價(jià)位,他會(huì)怎么做?“2000”“高了”“1000”“低了”“1500”“低了”……直到答對(duì)為止。可能有很多人都會(huì)選擇這個(gè)策略,無(wú)論他是不是計(jì)算機(jī)專(zhuān)業(yè)出身的,也不知道他是不是了解“數(shù)據(jù)結(jié)構(gòu)”和“折半查找”,更不用說(shuō)他是不是知道還有比在無(wú)初始代價(jià)下O(log n)的時(shí)間復(fù)雜度更快的算法了,但我們經(jīng)常會(huì)自然而然地用這樣的方法,這和一個(gè)人的行業(yè)無(wú)關(guān),除非這個(gè)人的rp超強(qiáng),呵呵……
              又講了一堆題外話(huà)了,遍歷和修改似乎是一對(duì)矛盾,一個(gè)可以高效率插入刪除元素的數(shù)據(jù)結(jié)構(gòu)通常遍歷的性能并不是最優(yōu)。于是JCF在這里根據(jù)用戶(hù)的目標(biāo)實(shí)現(xiàn)了兩種定制的數(shù)據(jù)結(jié)構(gòu):哈希表(包括HashSet和HashMap)和平衡二叉樹(shù)(包括TreeSet和TreeMap)。由于可排序性是一種獨(dú)特的要求,所以引入了SortedSet和SortedMap,它們分別是AbstractSet和AbstractMap的子接口,而TreeSet和TreeMap又分別是他們的一種實(shí)現(xiàn)。熟悉數(shù)據(jù)結(jié)構(gòu)的人可能比較了解,哈希表在進(jìn)行插入、刪除、查找這樣的操作是很快的,其時(shí)間復(fù)雜度是常數(shù)級(jí)O(1);平衡二叉樹(shù)雖然插入、刪除操作比較麻煩(需要O(log n)的代價(jià)),但進(jìn)行遍歷和排序卻很快。選擇完全在于用戶(hù)的側(cè)重點(diǎn),但由于類(lèi)型轉(zhuǎn)換的方便性,通常我們用哈希表構(gòu)造一個(gè)集合以后,再把它轉(zhuǎn)換成相應(yīng)的樹(shù)集進(jìn)行遍歷,以獲得較好的效果。
          Set set1 = new HashSet();
          set1.add(elem1);
          // 通過(guò)插入元素構(gòu)造集合
          set1.add(elem2);
          set1.add(elem3);
          Set set2 = new TreeSet(set);
          Iterator all = set2.iterator();
          while (all.hasNext())
          {
          // 遍歷集合
          all.next();
          ...
          }

            2. 歷史實(shí)現(xiàn) vs. 新實(shí)現(xiàn)
              歷史實(shí)現(xiàn)(Legacy Implementations)是JCF的一個(gè)術(shù)語(yǔ),準(zhǔn)確的意義不是很清楚,但大致可以認(rèn)為在Java 2(JDK 1.2)出現(xiàn)以前的老版本中JCF的一個(gè)雛形框架。在Java 2以后,JCF才開(kāi)始完善健壯起來(lái),新實(shí)現(xiàn)中出現(xiàn)了一些新的類(lèi)用于替代老版本中的成員,但由于種種原因,老版本中很多類(lèi)都代表了傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)的精髓部分,以及一些安全原因,所以仍然被我們使用著。

          Enumeration vs. Iterator
              Enumeration是一個(gè)傳統(tǒng)的集合遍歷工具,在新的JCF中使用的是Iterator,Iterator同樣具有遍歷功能,還包含一個(gè)remove()方法來(lái)刪除當(dāng)前得到的元素。

          Dictionary vs. Map
              Dictionary是一個(gè)現(xiàn)在已經(jīng)被標(biāo)記為deprecated的類(lèi),實(shí)現(xiàn)了老版本中的映射功能,現(xiàn)在已經(jīng)完全被Map取代。它們的區(qū)別是:Dictionary中key和value不能為null,但Map卻允許空的關(guān)鍵字和值,這一點(diǎn)直接影響到它們的后代:Hashtable和HashMap。

          Vector vs. ArrayList
              Vector和ArrayList是數(shù)組在JCF中的體現(xiàn),還記得前面講過(guò)的數(shù)組的缺點(diǎn)么?Vector和ArrayList就是一種可以動(dòng)態(tài)增長(zhǎng)的數(shù)組。Vector是歷史實(shí)現(xiàn),它和ArrayList的主要區(qū)別在于,Vector是同步集合(或者說(shuō)是線(xiàn)程安全的),但ArrayList并不是同步的,由于同步需要花一定的代價(jià),所以ArrayList看起來(lái)要比Vector的存取訪問(wèn)效率更高。關(guān)于同步我們下面還將要談到。

          Hashtable vs. HashMap
              Hashtable是Dictionary的子類(lèi),屬于歷史實(shí)現(xiàn),而HashMap是Map的子類(lèi),是新實(shí)現(xiàn)。它們的區(qū)別除了上面所說(shuō)的key和value是否可以為空之外,也有同步的差別,Hashtable是同步的,但HashMap不是。HashMap的一個(gè)經(jīng)典的例子就是JSP的內(nèi)置對(duì)象session。不過(guò)不要因?yàn)镠ashtable是“老前輩”而瞧不起它哦,它的一個(gè)著名的子類(lèi)Properties我們可是經(jīng)常會(huì)用到的。
            3. 同步 vs. 不同步
              從上面的描述中我們似乎可以得出這么一個(gè)印象:歷史實(shí)現(xiàn)好像都是同步的,但新實(shí)現(xiàn)中卻沒(méi)有。需要同步操作的理由是,可能存在多個(gè)線(xiàn)程對(duì)同一個(gè)集合進(jìn)行操作的情況:譬如一個(gè)線(xiàn)程正在對(duì)某集合進(jìn)行遍歷,但與此同時(shí),另一個(gè)線(xiàn)程又在對(duì)該集合進(jìn)行插入或刪除,那么第一個(gè)線(xiàn)程的遍歷結(jié)果將是不可預(yù)測(cè)的,對(duì)于同步集合,它將會(huì)拋出一個(gè)ConcurrentModificationException異常,JCF把這種機(jī)制成為“fail-fast”。我們對(duì)比一下Vector和ArrayList的源代碼就可以發(fā)現(xiàn)Vector的很多方法都是有synchronized關(guān)鍵字修飾的,但ArrayList沒(méi)有。     在圖1中右下角落里有兩個(gè)類(lèi)叫做Collections(注意,不是Collection!)和Arrays,這是JCF里面功能強(qiáng)大的工具,但初學(xué)者往往會(huì)忽視。按JCF文檔的說(shuō)法,這兩個(gè)類(lèi)提供了封裝器實(shí)現(xiàn)(Wrapper Implementations)、數(shù)據(jù)結(jié)構(gòu)算法和數(shù)組相關(guān)的應(yīng)用。
              想必大家不會(huì)忘記上面談到的“折半查找”、“排序”等經(jīng)典算法吧,Collections類(lèi)提供了豐富的靜態(tài)方法幫助我們輕松完成這些在數(shù)據(jù)結(jié)構(gòu)課上煩人的工作:

          binarySearch:折半查找。
          sort:排序,這里是一種類(lèi)似于快速排序的方法,效率仍然是O(n * log n),但卻是一種穩(wěn)定的排序方法。
          reverse:將線(xiàn)性表進(jìn)行逆序操作,這個(gè)可是從前數(shù)據(jù)結(jié)構(gòu)的經(jīng)典考題哦!
          rotate:以某個(gè)元素為軸心將線(xiàn)性表“旋轉(zhuǎn)”——哇,這個(gè)功能太酷了!
          swap:交換一個(gè)線(xiàn)性表中兩個(gè)元素的位置。
          ……

              Collections還有一個(gè)重要功能就是“封裝器”(Wrapper),它提供了一些方法可以把一個(gè)集合轉(zhuǎn)換成一個(gè)特殊的集合:

          unmodifiableXXX:轉(zhuǎn)換成只讀集合,這里XXX代表六種基本集合接口:Collection、List、Map、Set、SortedMap和SortedSet。如果你對(duì)只讀集合進(jìn)行插入刪除操作,將會(huì)拋出
          UnsupportedOperationException異常。
          synchronizedXXX:轉(zhuǎn)換成同步集合。
          singleton:創(chuàng)建一個(gè)僅有一個(gè)元素的集合,這里singleton生成的是單元素Set,singletonListsingletonMap分別生成單元素的List和Map。
          空集:由Collections的靜態(tài)屬性
          EMPTY_SETEMPTY_LISTEMPTY_MAP表示。

              此外,我們知道把集合轉(zhuǎn)換成對(duì)象數(shù)組可以用Collection的
          toArray()方法,我們也可以方便地把一個(gè)對(duì)象數(shù)組轉(zhuǎn)換成一個(gè)線(xiàn)性表(可不要告訴我你是一個(gè)一個(gè)地add哦):Arrays.asList()。
            5. 泛型
              目前我們了解的JCF的一個(gè)重要特征是:所有加入到集合當(dāng)中的對(duì)象都將在表面上失去它們自己的特性,而看上去僅僅只是一個(gè)Object對(duì)象而已,除非你把它強(qiáng)制類(lèi)型轉(zhuǎn)換成它們?cè)瓉?lái)的對(duì)象。這一點(diǎn)很自然,集合嘛,對(duì)象的容器,它容納的是各種各樣的對(duì)象,而不僅僅是某種特定類(lèi)型的對(duì)象。J2SE 5.0出現(xiàn)以后,JCF開(kāi)始引入泛型的特性,譬如我們經(jīng)常碰到這樣的應(yīng)用,就是把集合轉(zhuǎn)換成特定的數(shù)組,雖然Collection有toArray()的方法,但可惜的是,這個(gè)數(shù)組的所有元素都是Object類(lèi)型的,我們通常的做法是用一個(gè)for循環(huán)把數(shù)組的每個(gè)元素都進(jìn)行強(qiáng)制類(lèi)型轉(zhuǎn)換,雖然可行,但看上去很笨拙,如果有了泛型,我們就可以預(yù)先指定要得到的類(lèi)型,然后一次toArray就可以得到我們期望的數(shù)組,里面的元素全部都是指定類(lèi)型了。慚愧的是,我對(duì)5.0還不是太了解,具體可以參考J2SE 5.0的JCF文檔

          小結(jié)

              我這里走馬觀花一樣把JCF的一些主要概念羅嗦了一下,Java的老手們可能比較厭煩,新手們可能更覺(jué)得像回顧了一下高中的數(shù)學(xué)課和大學(xué)的數(shù)據(jù)結(jié)構(gòu),呵呵。這只是一個(gè)小小的例子,可見(jiàn)基礎(chǔ)知識(shí)對(duì)現(xiàn)實(shí)當(dāng)中的應(yīng)用還是蠻有指導(dǎo)意義的。大師們看數(shù)學(xué),覺(jué)得那是很唯美很藝術(shù)的一樣?xùn)|西,西方一直都把數(shù)學(xué)區(qū)別于其它自然科學(xué),而認(rèn)為它更靠近于哲學(xué),像我等這樣整天還在為找工作煩得要死的俗人還是沒(méi)法入道啊,sigh……

          參考資料

          posted on 2005-04-02 21:49 jungleford 閱讀(1292) 評(píng)論(1)  編輯  收藏 所屬分類(lèi): 咖啡屋 - Java 技術(shù)研究

          Feedback

          # re: 關(guān)于集合框架的思考 2008-11-07 17:03 NickyYe
          受益匪淺,感謝  回復(fù)  更多評(píng)論
            

          主站蜘蛛池模板: 平远县| 高要市| 盘山县| 万盛区| 阳春市| 富顺县| 鸡泽县| 美姑县| 曲周县| 江孜县| 郸城县| 顺平县| 十堰市| 贵阳市| 兴仁县| 顺义区| 商河县| 德庆县| 高安市| 美姑县| 株洲市| 澄江县| 商丘市| 卢氏县| 湖南省| 象山县| 喀喇沁旗| 陇川县| 新安县| 卢氏县| 镇宁| 蒙阴县| 革吉县| 绥化市| 观塘区| 芜湖县| 天峨县| 宕昌县| 嘉义县| 昌江| 公主岭市|