在編寫 Java 程序中,我們最常用的除了八種基本數(shù)據(jù)類型,String 對(duì)象外還有一個(gè)集合類,在我們的的程序中到處充斥著集合類的身影!Java 中集合大家族的成員實(shí)在是太豐富了,有常用的 ArrayList、HashMap、HashSet,也有不常用的 Stack、Queue,有線程安全的 Vector、HashTable,也有線程不安全的 LinkedList、TreeMap 等等!
http://wiki.jikexueyuan.com/project/java-enhancement/images/20-1.png" alt="fig.1" />
上面的圖展示了整個(gè)集合大家族的成員以及他們之間的關(guān)系。下面就上面的各個(gè)接口、基類做一些簡(jiǎn)單的介紹(主要介紹各個(gè)集合的特點(diǎn)。區(qū)別),更加詳細(xì)的介紹會(huì)在不久的將來一一講解。
Collection 接口是最基本的集合接口,它不提供直接的實(shí)現(xiàn),Java SDK提供的類都是繼承自 Collection 的“子接口”如 List 和 Set。Collection 所代表的是一種規(guī)則,它所包含的元素都必須遵循一條或者多條規(guī)則。如有些允許重復(fù)而有些則不能重復(fù)、有些必須要按照順序插入而有些則是散列,有些支持排序但是有些則不支持。
在 Java 中所有實(shí)現(xiàn)了 Collection 接口的類都必須提供兩套標(biāo)準(zhǔn)的構(gòu)造函數(shù),一個(gè)是無參,用于創(chuàng)建一個(gè)空的 Collection,一個(gè)是帶有 Collection 參數(shù)的有參構(gòu)造函數(shù),用于創(chuàng)建一個(gè)新的 Collection,這個(gè)新的 Collection 與傳入進(jìn)來的 Collection 具備相同的元素。
List 接口為 Collection 直接接口。List 所代表的是有序的 Collection,即它用某種特定的插入順序來維護(hù)元素順序。用戶可以對(duì)列表中每個(gè)元素的插入位置進(jìn)行精確地控制,同時(shí)可以根據(jù)元素的整數(shù)索引(在列表中的位置)訪問元素,并搜索列表中的元素。實(shí)現(xiàn) List 接口的集合主要有:ArrayList、LinkedList、Vector、Stack。
ArrayList 是一個(gè)動(dòng)態(tài)數(shù)組,也是我們最常用的集合。它允許任何符合規(guī)則的元素插入甚至包括 null。每一個(gè) ArrayList 都有一個(gè)初始容量(10),該容量代表了數(shù)組的大小。隨著容器中的元素不斷增加,容器的大小也會(huì)隨著增加。在每次向容器中增加元素的同時(shí)都會(huì)進(jìn)行容量檢查,當(dāng)快溢出時(shí),就會(huì)進(jìn)行擴(kuò)容操作。所以如果我們明確所插入元素的多少,最好指定一個(gè)初始容量值,避免過多的進(jìn)行擴(kuò)容操作而浪費(fèi)時(shí)間、效率。
size、isEmpty、get、set、iterator 和 listIterator 操作都以固定時(shí)間運(yùn)行。add 操作以分?jǐn)偟墓潭〞r(shí)間運(yùn)行,也就是說,添加 n 個(gè)元素需要 O(n) 時(shí)間(由于要考慮到擴(kuò)容,所以這不只是添加元素會(huì)帶來分?jǐn)偣潭〞r(shí)間開銷那樣簡(jiǎn)單)。
ArrayList 擅長(zhǎng)于隨機(jī)訪問。同時(shí) ArrayList 是非同步的。
同樣實(shí)現(xiàn) List 接口的 LinkedList 與 ArrayList 不同,ArrayList是一個(gè)動(dòng)態(tài)數(shù)組,而 LinkedList 是一個(gè)雙向鏈表。所以它除了有 ArrayList 的基本操作方法外還額外提供了 get,remove,insert 方法在 LinkedList 的首部或尾部。
由于實(shí)現(xiàn)的方式不同,LinkedList 不能隨機(jī)訪問,它所有的操作都是要按照雙重鏈表的需要執(zhí)行。在列表中索引的操作將從開頭或結(jié)尾遍歷列表(從靠近指定索引的一端)。這樣做的好處就是可以通過較低的代價(jià)在 List 中進(jìn)行插入和刪除操作。
與 ArrayList 一樣,LinkedList 也是非同步的。如果多個(gè)線程同時(shí)訪問一個(gè) List,則必須自己實(shí)現(xiàn)訪問同步。一種解決方法是在創(chuàng)建 List 時(shí)構(gòu)造一個(gè)同步的 List:
List list = Collections.synchronizedList(new LinkedList(…));
與 ArrayList 相似,但是 Vector 是同步的。所以說 Vector 是線程安全的動(dòng)態(tài)數(shù)組。它的操作與 ArrayList 幾乎一樣。
Stack 繼承自 Vector,實(shí)現(xiàn)一個(gè)后進(jìn)先出的堆棧。Stack 提供 5 個(gè)額外的方法使得 Vector 得以被當(dāng)作堆棧使用?;镜?push 和 pop 方法,還有 peek 方法得到棧頂?shù)脑?,empty 方法測(cè)試堆棧是否為空,search 方法檢測(cè)一個(gè)元素在堆棧中的位置。Stack 剛創(chuàng)建后是空棧。
Set 是一種不包括重復(fù)元素的 Collection。它維持它自己的內(nèi)部排序,所以隨機(jī)訪問沒有任何意義。與 List 一樣,它同樣運(yùn)行 null 的存在但是僅有一個(gè)。由于 Set 接口的特殊性,所有傳入 Set 集合中的元素都必須不同,同時(shí)要注意任何可變對(duì)象,如果在對(duì)集合中元素進(jìn)行操作時(shí),導(dǎo)致e1.equals(e2)==true,則必定會(huì)產(chǎn)生某些問題。實(shí)現(xiàn)了 Set 接口的集合有:EnumSet、HashSet、TreeSet。
是枚舉的專用 Set。所有的元素都是枚舉類型。
HashSet 堪稱查詢速度最快的集合,因?yàn)槠鋬?nèi)部是以 HashCode 來實(shí)現(xiàn)的。它內(nèi)部元素的順序是由哈希碼來決定的,所以它不保證 set 的迭代順序;特別是它不保證該順序恒久不變。
基于 TreeMap,生成一個(gè)總是處于排序狀態(tài)的 set,內(nèi)部以 TreeMap 來實(shí)現(xiàn)。它是使用元素的自然順序?qū)υ剡M(jìn)行排序,或者根據(jù)創(chuàng)建 Set 時(shí)提供的 Comparator
進(jìn)行排序,具體取決于使用的構(gòu)造方法。
Map 與 List、Set 接口不同,它是由一系列鍵值對(duì)組成的集合,提供了 key 到 Value 的映射。同時(shí)它也沒有繼承 Collection。在 Map 中它保證了 key 與 value 之間的一一對(duì)應(yīng)關(guān)系。也就是說一個(gè) key 對(duì)應(yīng)一個(gè) value,所以它不能存在相同的 key 值,當(dāng)然 value 值可以相同。實(shí)現(xiàn) map 的有:HashMap、TreeMap、HashTable、Properties、EnumMap。
以哈希表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn),查找對(duì)象時(shí)通過哈希函數(shù)計(jì)算其位置,它是為快速查詢而設(shè)計(jì)的,其內(nèi)部定義了一個(gè) hash 表數(shù)組(Entry[] table),元素會(huì)通過哈希轉(zhuǎn)換函數(shù)將元素的哈希地址轉(zhuǎn)換成數(shù)組中存放的索引,如果有沖突,則使用散列鏈表的形式將所有相同哈希地址的元素串起來,可能通過查看 HashMap.Entry 的源碼它是一個(gè)單鏈表結(jié)構(gòu)。
鍵以某種排序規(guī)則排序,內(nèi)部以 red-black(紅-黑)樹數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn),實(shí)現(xiàn)了 SortedMap 接口
也是以哈希表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的,解決沖突時(shí)與 HashMap 也一樣也是采用了散列鏈表的形式,不過性能比 HashMap 要低
隊(duì)列,它主要分為兩大類,一類是阻塞式隊(duì)列,隊(duì)列滿了以后再插入元素則會(huì)拋出異常,主要包括 ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。另一種隊(duì)列則是雙端隊(duì)列,支持在頭、尾兩端插入和移除元素,主要包括:ArrayDeque、LinkedBlockingDeque、LinkedList。
出處:http://blog.csdn.net/softwave/article/details/4166598
1,vector 是線程同步的,所以它也是線程安全的,而 arraylist 是線程異步的,是不安全的。如果不考慮到線程的安全因素,一般用 arraylist 效率比較高。
2,如果集合中的元素的數(shù)目大于目前集合數(shù)組的長(zhǎng)度時(shí),vector 增長(zhǎng)率為目前數(shù)組長(zhǎng)度的 100%,而 arraylist 增長(zhǎng)率為目前數(shù)組長(zhǎng)度的 50%.如過在集合中使用數(shù)據(jù)量比較大的數(shù)據(jù),用 vector 有一定的優(yōu)勢(shì)。
3,如果查找一個(gè)指定位置的數(shù)據(jù),vector 和 arraylist 使用的時(shí)間是相同的,都是 0(1),這個(gè)時(shí)候使用 vector 和 arraylist 都可以。而如果移動(dòng)一個(gè)指定位置的數(shù)據(jù)花費(fèi)的時(shí)間為 0(n-i)n 為總長(zhǎng)度,這個(gè)時(shí)候就應(yīng)該考慮到使用 linklist,因?yàn)樗苿?dòng)一個(gè)指定位置的數(shù)據(jù)所花費(fèi)的時(shí)間為 0(1),而查詢一個(gè)指定位置的數(shù)據(jù)時(shí)花費(fèi)的時(shí)間為 0(i)。
ArrayList 和 Vector 是采用數(shù)組方式存儲(chǔ)數(shù)據(jù),此數(shù)組元素?cái)?shù)大于實(shí)際存儲(chǔ)的數(shù)據(jù)以便增加和插入元素,都允許直接序號(hào)索引元素,但是插入數(shù)據(jù)要設(shè)計(jì)到數(shù)組元素移動(dòng)等內(nèi)存操作,所以索引數(shù)據(jù)快插入數(shù)據(jù)慢,Vector 由于使用了 synchronized 方法(線程安全)所以性能上比 ArrayList 要差,LinkedList 使用雙向鏈表實(shí)現(xiàn)存儲(chǔ),按序號(hào)索引數(shù)據(jù)需要進(jìn)行向前或向后遍歷,但是插入數(shù)據(jù)時(shí)只需要記錄本項(xiàng)的前后項(xiàng)即可,所以插入數(shù)度較快!
1.ArrayList 是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu),LinkedList 基于鏈表的數(shù)據(jù)結(jié)構(gòu)。
2.對(duì)于隨機(jī)訪問 get 和 set,ArrayList 覺得優(yōu)于 LinkedList,因?yàn)?LinkedList 要移動(dòng)指針。
3.對(duì)于新增和刪除操作 add 和 remove,LinedList 比較占優(yōu)勢(shì),因?yàn)?ArrayList 要移動(dòng)數(shù)據(jù)。
這一點(diǎn)要看實(shí)際情況的。若只對(duì)單條數(shù)據(jù)插入或刪除,ArrayList 的速度反而優(yōu)于 LinkedList。但若是批量隨機(jī)的插入刪除數(shù)據(jù),LinkedList 的速度大大優(yōu)于 ArrayList. 因?yàn)?ArrayList 每插入一條數(shù)據(jù),要移動(dòng)插入點(diǎn)及之后的所有數(shù)據(jù)。
1、HashMap 通過 hashcode 對(duì)其內(nèi)容進(jìn)行快速查找,而 TreeMap 中所有的元素都保持著某種固定的順序,如果你需要得到一個(gè)有序的結(jié)果你就應(yīng)該使用 TreeMap(HashMap 中元素的排列順序是不固定的)。HashMap 中元素的排列順序是不固定的)。
2、HashMap 通過 hashcode 對(duì)其內(nèi)容進(jìn)行快速查找,而 TreeMap 中所有的元素都保持著某種固定的順序,如果你需要得到一個(gè)有序的結(jié)果你就應(yīng)該使用 TreeMap(HashMap 中元素的排列順序是不固定的)。集合框架”提供兩種常規(guī)的 Map 實(shí)現(xiàn):HashMap 和 TreeMap (TreeMap 實(shí)現(xiàn) SortedMap 接口)。
3、在 Map 中插入、刪除和定位元素,HashMap 是最好的選擇。但如果您要按自然順序或自定義順序遍歷鍵,那么 TreeMap 會(huì)更好。使用 HashMap 要求添加的鍵類明確定義了 hashCode() 和 equals() 的實(shí)現(xiàn)。 這個(gè) TreeMap 沒有調(diào)優(yōu)選項(xiàng),因?yàn)樵摌淇偺幱谄胶鉅顟B(tài)。
1、歷史原因:Hashtable 是基于陳舊的 Dictionary 類的,HashMap 是Java 1.2 引進(jìn)的 Map 接口的一個(gè)實(shí)現(xiàn) 。
2、同步性:Hashtable 是線程安全的,也就是說是同步的,而 HashMap 是線程序不安全的,不是同步的 。
3、值:只有 HashMap 可以讓你將空值作為一個(gè)表的條目的 key 或value。
1、對(duì)于隨機(jī)查詢與迭代遍歷操作,數(shù)組比所有的容器都要快。所以在隨機(jī)訪問中一般使用 ArrayList
2、LinkedList 使用雙向鏈表對(duì)元素的增加和刪除提供了非常好的支持,而 ArrayList 執(zhí)行增加和刪除元素需要進(jìn)行元素位移。
3、對(duì)于 Vector 而已,我們一般都是避免使用。
4、將 ArrayList 當(dāng)做首選,畢竟對(duì)于集合元素而已我們都是進(jìn)行遍歷,只有當(dāng)程序的性能因?yàn)?List 的頻繁插入和刪除而降低時(shí),再考慮 LinkedList。
1、HashSet 由于使用 HashCode 實(shí)現(xiàn),所以在某種程度上來說它的性能永遠(yuǎn)比 TreeSet 要好,尤其是進(jìn)行增加和查找操作。
3、雖然 TreeSet 沒有 HashSet 性能好,但是由于它可以維持元素的排序,所以它還是存在用武之地的。
1、HashMap 與 HashSet 同樣,支持快速查詢。雖然 HashTable 速度的速度也不慢,但是在 HashMap 面前還是稍微慢了些,所以 HashMap 在查詢方面可以取代 HashTable。
2、由于 TreeMap 需要維持內(nèi)部元素的順序,所以它通常要比 HashMap 和 HashTable 慢。
個(gè)人網(wǎng)站:CMSBLOGS