對(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)
數(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ú)序集、有序集、映射
等到我們上了大學(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:
圖1 JCF層次結(jié)構(gòu)
哇,這么多接口和類(lèi),真有點(diǎn)讓人無(wú)從下手的感覺(jué)。其實(shí)我們真正需要記住的只是這么一個(gè)超超easy的結(jié)構(gòu)(圖2):
圖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的源代碼,以及它們的直接后代AbstractCollection和AbstractMap的源代碼,你將會(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 | ||||||
歷史集合 |
新集合 |
||||||||
可能有的概念您還不是太了解,譬如什么叫“歷史集合”,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)
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. 不同步
- 4. 容易遺忘的工具:Collections和Arrays
想必大家不會(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,singletonList和singletonMap分別生成單元素的List和Map。
空集:由Collections的靜態(tài)屬性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示。
此外,我們知道把集合轉(zhuǎn)換成對(duì)象數(shù)組可以用Collection的toArray()方法,我們也可以方便地把一個(gè)對(duì)象數(shù)組轉(zhuǎn)換成一個(gè)線(xiàn)性表(可不要告訴我你是一個(gè)一個(gè)地add哦):Arrays.asList()。
- 5. 泛型
小結(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……
參考資料
- IBM developerWorks教程: Java 集合框架
- J2SE Documentation: The Collections Framework
- The Java Tutorial
- JCF API