線性表,鏈表,哈希表是常用的數(shù)據(jù)結(jié)構(gòu),在進(jìn)行Java開(kāi)發(fā)時(shí),JDK已經(jīng)為我們提供了一系列相應(yīng)的類來(lái)實(shí)現(xiàn)基本的數(shù)據(jù)結(jié)構(gòu)。這些類均在java.util包中。本文試圖通過(guò)簡(jiǎn)單的描述,向讀者闡述各個(gè)類的作用以及如何正確使用這些類。 Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ├Hashtable ├HashMap └WeakHashMap Collection接口 Collection是最基本的集合接口,一個(gè)Collection代表一組Object,即Collection的元素(Elements)。一些Collection允許相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接繼承自Collection的類,Java SDK提供的類都是繼承自Collection的“子接口”如List和Set。 所有實(shí)現(xiàn)Collection接口的類都必須提供兩個(gè)標(biāo)準(zhǔn)的構(gòu)造函數(shù):無(wú)參數(shù)的構(gòu)造函數(shù)用于創(chuàng)建一個(gè)空的Collection,有一個(gè)Collection參數(shù)的構(gòu)造函數(shù)用于創(chuàng)建一個(gè)新的Collection,這個(gè)新的Collection與傳入的Collection有相同的元素。后一個(gè)構(gòu)造函數(shù)允許用戶復(fù)制一個(gè)Collection。 如何遍歷Collection中的每一個(gè)元素?不論Collection的實(shí)際類型如何,它都支持一個(gè)iterator()的方法,該方法返回一個(gè)迭代子,使用該迭代子即可逐一訪問(wèn)Collection中每一個(gè)元素。典型的用法如下: Iterator it = collection.iterator(); // 獲得一個(gè)迭代子 while(it.hasNext()) { Object obj = it.next(); // 得到下一個(gè)元素 } 由Collection接口派生的兩個(gè)接口是List和Set。 List接口 List是有序的Collection,使用此接口能夠精確的控制每個(gè)元素插入的位置。用戶能夠使用索引(元素在List中的位置,類似于數(shù)組下標(biāo))來(lái)訪問(wèn)List中的元素,這類似于Java的數(shù)組。 和下面要提到的Set不同,List允許有相同的元素。 除了具有Collection接口必備的iterator()方法外,List還提供一個(gè)listIterator()方法,返回一個(gè)ListIterator接口,和標(biāo)準(zhǔn)的Iterator接口相比,ListIterator多了一些add()之類的方法,允許添加,刪除,設(shè)定元素,還能向前或向后遍歷。 實(shí)現(xiàn)List接口的常用類有LinkedList,ArrayList,Vector和Stack。 LinkedList類 LinkedList實(shí)現(xiàn)了List接口,允許null元素。此外LinkedList提供額外的get,remove,insert方法在LinkedList的首部或尾部。這些操作使LinkedList可被用作堆棧(stack),隊(duì)列(queue)或雙向隊(duì)列(deque)。 注意LinkedList沒(méi)有同步方法。如果多個(gè)線程同時(shí)訪問(wèn)一個(gè)List,則必須自己實(shí)現(xiàn)訪問(wèn)同步。一種解決方法是在創(chuàng)建List時(shí)構(gòu)造一個(gè)同步的List: List list = Collections.synchronizedList(new LinkedList(...)); ArrayList類 ArrayList實(shí)現(xiàn)了可變大小的數(shù)組。它允許所有元素,包括null。ArrayList沒(méi)有同步。 size,isEmpty,get,set方法運(yùn)行時(shí)間為常數(shù)。但是add方法開(kāi)銷為分?jǐn)偟某?shù),添加n個(gè)元素需要O(n)的時(shí)間。其他的方法運(yùn)行時(shí)間為線性。 每個(gè)ArrayList實(shí)例都有一個(gè)容量(Capacity),即用于存儲(chǔ)元素的數(shù)組的大小。這個(gè)容量可隨著不斷添加新元素而自動(dòng)增加,但是增長(zhǎng)算法并沒(méi)有定義。當(dāng)需要插入大量元素時(shí),在插入前可以調(diào)用ensureCapacity方法來(lái)增加ArrayList的容量以提高插入效率。 和LinkedList一樣,ArrayList也是非同步的(unsynchronized)。 Vector類 Vector非常類似ArrayList,但是Vector是同步的。由Vector創(chuàng)建的Iterator,雖然和ArrayList創(chuàng)建的Iterator是同一接口,但是,因?yàn)閂ector是同步的,當(dāng)一個(gè)Iterator被創(chuàng)建而且正在被使用,另一個(gè)線程改變了Vector的狀態(tài)(例如,添加或刪除了一些元素),這時(shí)調(diào)用Iterator的方法時(shí)將拋出ConcurrentModificationException,因此必須捕獲該異常。 Stack 類 Stack繼承自Vector,實(shí)現(xiàn)一個(gè)后進(jìn)先出的堆棧。Stack提供5個(gè)額外的方法使得Vector得以被當(dāng)作堆棧使用?;镜膒ush和pop方法,還有peek方法得到棧頂?shù)脑兀琫mpty方法測(cè)試堆棧是否為空,search方法檢測(cè)一個(gè)元素在堆棧中的位置。Stack剛創(chuàng)建后是空棧。 Set接口 Set是一種不包含重復(fù)的元素的Collection,即任意的兩個(gè)元素e1和e2都有e1.equals(e2)=false,Set最多有一個(gè)null元素。 很明顯,Set的構(gòu)造函數(shù)有一個(gè)約束條件,傳入的Collection參數(shù)不能包含重復(fù)的元素。 請(qǐng)注意:必須小心操作可變對(duì)象(Mutable Object)。如果一個(gè)Set中的可變?cè)馗淖兞俗陨頎顟B(tài)導(dǎo)致Object.equals(Object)=true將導(dǎo)致一些問(wèn)題。 Map接口 請(qǐng)注意,Map沒(méi)有繼承Collection接口,Map提供key到value的映射。一個(gè)Map中不能包含相同的key,每個(gè)key只能映射一個(gè)value。Map接口提供3種集合的視圖,Map的內(nèi)容可以被當(dāng)作一組key集合,一組value集合,或者一組key-value映射。 Hashtable類 Hashtable繼承Map接口,實(shí)現(xiàn)一個(gè)key-value映射的哈希表。任何非空(non-null)的對(duì)象都可作為key或者value。 添加數(shù)據(jù)使用put(key, value),取出數(shù)據(jù)使用get(key),這兩個(gè)基本操作的時(shí)間開(kāi)銷為常數(shù)。 Hashtable通過(guò)initial capacity和load factor兩個(gè)參數(shù)調(diào)整性能。通常缺省的load factor 0.75較好地實(shí)現(xiàn)了時(shí)間和空間的均衡。增大load factor可以節(jié)省空間但相應(yīng)的查找時(shí)間將增大,這會(huì)影響像get和put這樣的操作。 使用Hashtable的簡(jiǎn)單示例如下,將1,2,3放到Hashtable中,他們的key分別是”one”,”two”,”three”: Hashtable numbers = new Hashtable(); numbers.put(“one”, new Integer(1)); numbers.put(“two”, new Integer(2)); numbers.put(“three”, new Integer(3)); 要取出一個(gè)數(shù),比如2,用相應(yīng)的key: Integer n = (Integer)numbers.get(“two”); System.out.println(“two = ” + n); 由于作為key的對(duì)象將通過(guò)計(jì)算其散列函數(shù)來(lái)確定與之對(duì)應(yīng)的value的位置,因此任何作為key的對(duì)象都必須實(shí)現(xiàn)hashCode和equals方法。hashCode和equals方法繼承自根類Object,如果你用自定義的類當(dāng)作key的話,要相當(dāng)小心,按照散列函數(shù)的定義,如果兩個(gè)對(duì)象相同,即obj1.equals(obj2)=true,則它們的hashCode必須相同,但如果兩個(gè)對(duì)象不同,則它們的hashCode不一定不同,如果兩個(gè)不同對(duì)象的hashCode相同,這種現(xiàn)象稱為沖突,沖突會(huì)導(dǎo)致操作哈希表的時(shí)間開(kāi)銷增大,所以盡量定義好的hashCode()方法,能加快哈希表的操作。 如果相同的對(duì)象有不同的hashCode,對(duì)哈希表的操作會(huì)出現(xiàn)意想不到的結(jié)果(期待的get方法返回null),要避免這種問(wèn)題,只需要牢記一條:要同時(shí)復(fù)寫equals方法和hashCode方法,而不要只寫其中一個(gè)。 Hashtable是同步的。 HashMap類 HashMap和Hashtable類似,不同之處在于HashMap是非同步的,并且允許null,即null value和null key。,但是將HashMap視為Collection時(shí)(values()方法可返回Collection),其迭代子操作時(shí)間開(kāi)銷和HashMap的容量成比例。因此,如果迭代操作的性能相當(dāng)重要的話,不要將HashMap的初始化容量設(shè)得過(guò)高,或者load factor過(guò)低。 WeakHashMap類 WeakHashMap是一種改進(jìn)的HashMap,它對(duì)key實(shí)行“弱引用”,如果一個(gè)key不再被外部所引用,那么該key可以被GC回收。 總結(jié) 如果涉及到堆棧,隊(duì)列等操作,應(yīng)該考慮用List,對(duì)于需要快速插入,刪除元素,應(yīng)該使用LinkedList,如果需要快速隨機(jī)訪問(wèn)元素,應(yīng)該使用ArrayList。 如果程序在單線程環(huán)境中,或者訪問(wèn)僅僅在一個(gè)線程中進(jìn)行,考慮非同步的類,其效率較高,如果多個(gè)線程可能同時(shí)操作一個(gè)類,應(yīng)該使用同步的類。 要特別注意對(duì)哈希表的操作,作為key的對(duì)象要正確復(fù)寫equals和hashCode方法。 盡量返回接口而非實(shí)際的類型,如返回List而非ArrayList,這樣如果以后需要將ArrayList換成LinkedList時(shí),客戶端代碼不用改變。這就是針對(duì)抽象編程。 同步性 Vector是同步的。這個(gè)類中的一些方法保證了Vector中的對(duì)象是線程安全的。而ArrayList則是異步的,因此ArrayList中的對(duì)象并不是線程安全的。因?yàn)橥降囊髸?huì)影響執(zhí)行的效率,所以如果你不需要線程安全的集合那么使用ArrayList是一個(gè)很好的選擇,這樣可以避免由于同步帶來(lái)的不必要的性能開(kāi)銷。 數(shù)據(jù)增長(zhǎng) 從內(nèi)部實(shí)現(xiàn)機(jī)制來(lái)講ArrayList和Vector都是使用數(shù)組(Array)來(lái)控制集合中的對(duì)象。當(dāng)你向這兩種類型中增加元素的時(shí)候,如果元素的數(shù)目超出了內(nèi)部數(shù)組目前的長(zhǎng)度它們都需要擴(kuò)展內(nèi)部數(shù)組的長(zhǎng)度,Vector缺省情況下自動(dòng)增長(zhǎng)原來(lái)一倍的數(shù)組長(zhǎng)度,ArrayList是原來(lái)的50%,所以最后你獲得的這個(gè)集合所占的空間總是比你實(shí)際需要的要大。所以如果你要在集合中保存大量的數(shù)據(jù)那么使用Vector有一些優(yōu)勢(shì),因?yàn)槟憧梢酝ㄟ^(guò)設(shè)置集合的初始化大小來(lái)避免不必要的資源開(kāi)銷。 使用模式 在ArrayList和Vector中,從一個(gè)指定的位置(通過(guò)索引)查找數(shù)據(jù)或是在集合的末尾增加、移除一個(gè)元素所花費(fèi)的時(shí)間是一樣的,這個(gè)時(shí)間我們用O(1)表示。但是,如果在集合的其他位置增加或移除元素那么花費(fèi)的時(shí)間會(huì)呈線形增長(zhǎng):O(n-i),其中n代表集合中元素的個(gè)數(shù),i代表元素增加或移除元素的索引位置。為什么會(huì)這樣呢?以為在進(jìn)行上述操作的時(shí)候集合中第i和第i個(gè)元素之后的所有元素都要執(zhí)行位移的操作。這一切意味著什么呢? 這意味著,你只是查找特定位置的元素或只在集合的末端增加、移除元素,那么使用Vector或ArrayList都可以。如果是其他操作,你最好選擇其他的集合操作類。比如,LinkList集合類在增加或移除集合中任何位置的元素所花費(fèi)的時(shí)間都是一樣的—O(1),但它在索引一個(gè)元素的使用缺比較慢-O(i),其中i是索引的位置.使用ArrayList也很容易,因?yàn)槟憧梢院?jiǎn)單的使用索引來(lái)代替創(chuàng)建iterator對(duì)象的操作。LinkList也會(huì)為每個(gè)插入的元素創(chuàng)建對(duì)象,所有你要明白它也會(huì)帶來(lái)額外的開(kāi)銷。 最后,在《Practical Java》一書(shū)中Peter Haggar建議使用一個(gè)簡(jiǎn)單的數(shù)組(Array)來(lái)代替Vector或ArrayList。尤其是對(duì)于執(zhí)行效率要求高的程序更應(yīng)如此。因?yàn)槭褂脭?shù)組(Array)避免了同步、額外的方法調(diào)用和不必要的重新分配空間的操作。 |
聯(lián)系客服