list/set/map的區(qū)別

　　一、List接口

　　List是一個繼承于Collection的接口，即List是集合中的一種。List是有序的隊列，List中的每一個元素都有一個索引;第一個元素的索引值是0，往后的元素的索引值依次+1。和Set不同，List中允許有重復(fù)的元素。實現(xiàn)List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

　　ArrayList

　　ArrayList是一個動態(tài)數(shù)組，也是我們最常用的集合。它允許任何符合規(guī)則的元素插入甚至包括null。每一個ArrayList都有一個初始容量：

　　private static final int DEFAULT_CAPACITY = 10;

　　隨著容器中的元素不斷增加，容器的大小也會隨著增加。在每次向容器中增加元素的同時都會進(jìn)行容量檢查，當(dāng)快溢出時，就會進(jìn)行擴(kuò)容操作。所以如果我們明確所插入元素的多少，最好指定一個初始容量值，避免過多的進(jìn)行擴(kuò)容操作而浪費(fèi)時間、效率。

　　size、isEmpty、get、set、iterator 和 listIterator 操作都以固定時間運(yùn)行。add 操作以分?jǐn)偟墓潭〞r間運(yùn)行，也就是說，添加 n 個元素需要 O(n) 時間(由于要考慮到擴(kuò)容，所以這不只是添加元素會帶來分?jǐn)偣潭〞r間開銷那樣簡單)。

　　ArrayList擅長于隨機(jī)訪問。同時ArrayList是非同步的。

　　LinkedList

　　同樣實現(xiàn)List接口的LinkedList與ArrayList不同，ArrayList是一個動態(tài)數(shù)組，而LinkedList是一個雙向鏈表。所以它除了有ArrayList的基本操作方法外還額外提供了get，remove，insert方法在LinkedList的首部或尾部。

　　由于實現(xiàn)的方式不同，LinkedList不能隨機(jī)訪問，它所有的操作都是要按照雙重鏈表的需要執(zhí)行。在列表中索引的操作將從開頭或結(jié)尾遍歷列表(從靠近指定索引的一端，節(jié)約一半時間)。這樣做的好處就是可以通過較低的代價在List中進(jìn)行插入和刪除操作。

　　與ArrayList一樣，LinkedList也是非同步的。如果多個線程同時訪問一個List，則必須自己實現(xiàn)訪問同步。一種解決方法是在創(chuàng)建List時構(gòu)造一個同步的List：

　　List list = Collections.synchronizedList(new LinkedList(…));

　　Vector

　　與ArrayList相似，但是Vector是同步的。所以說Vector是線程安全的動態(tài)數(shù)組。它的操作與ArrayList幾乎一樣。

　　Stack

　　Stack繼承自Vector，實現(xiàn)一個后進(jìn)先出的堆棧。Stack提供5個額外的方法使得Vector得以被當(dāng)作堆棧使用?；镜膒ush和pop方法，還有peek方法得到棧頂?shù)脑兀琫mpty方法測試堆棧是否為空，search方法檢測一個元素在堆棧中的位置。Stack剛創(chuàng)建后是空棧。

　　二、Set接口

　　Set是一個繼承于Collection的接口，Set是一種不包括重復(fù)元素的Collection。它維持它自己的內(nèi)部排序，所以隨機(jī)訪問沒有任何意義。與List一樣，它同樣運(yùn)行null的存在但是僅有一個。由于Set接口的特殊性，所有傳入Set集合中的元素都必須不同，關(guān)于API方面。Set的API和Collection完全一樣。實現(xiàn)了Set接口的集合有：HashSet、TreeSet、LinkedHashSet、EnumSet。

　　HashSet

　　HashSet堪稱查詢速度最快的集合，因為其內(nèi)部是以HashCode來實現(xiàn)的。集合元素可以是null,但只能放入一個null。它內(nèi)部元素的順序是由哈希碼來決定的，所以它不保證set的迭代順序;特別是它不保證該順序恒久不變。

　　TreeSet

　　TreeSet是二叉樹實現(xiàn)的，基于TreeMap，生成一個總是處于排序狀態(tài)的set，內(nèi)部以TreeMap來實現(xiàn)，不允許放入null值。它是使用元素的自然順序?qū)υ剡M(jìn)行排序，或者根據(jù)創(chuàng)建Set時提供的 Comparator 進(jìn)行排序，具體取決于使用的構(gòu)造方法。

　　LinkedHashSet

　　LinkedHashSet集合同樣是根據(jù)元素的hashCode值來決定元素的存儲位置，但是它同時使用鏈表維護(hù)元素的次序。這樣使得元素看起 來像是以插入順序保存的，也就是說，當(dāng)遍歷該集合時候，LinkedHashSet將會以元素的添加順序訪問集合的元素。LinkedHashSet在迭代訪問Set中的全部元素時，性能比HashSet好，但是插入時性能稍微遜色于HashSet。

　　三、Map接口

　　Map與List、Set接口不同，它是由一系列鍵值對組成的集合，提供了key到Value的映射。在Map中它保證了key與value之間的一一對應(yīng)關(guān)系。也就是說一個key對應(yīng)一個value，所以它不能存在相同的key值，當(dāng)然value值可以相同。實現(xiàn)map的集合有：HashMap、HashTable、TreeMap、WeakHashMap。

　　HashMap

　　以哈希表數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，查找對象時通過哈希函數(shù)計算其位置，它是為快速查詢而設(shè)計的，其內(nèi)部定義了一個hash表數(shù)組(Entry[] table)，元素會通過哈希轉(zhuǎn)換函數(shù)將元素的哈希地址轉(zhuǎn)換成數(shù)組中存放的索引，如果有沖突，則使用散列鏈表的形式將所有相同哈希地址的元素串起來，可能通過查看HashMap.Entry的源碼它是一個單鏈表結(jié)構(gòu)。

　　HashTable

　　也是以哈希表數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的，解決沖突時與HashMap也一樣也是采用了散列鏈表的形式。HashTable繼承Dictionary類，實現(xiàn)Map接口。其中Dictionary類是任何可將鍵映射到相應(yīng)值的類(如 Hashtable)的抽象父類。每個鍵和每個值都是一個對象。在任何一個 Dictionary 對象中，每個鍵至多與一個值相關(guān)聯(lián)。Map是”key-value鍵值對”接口。 HashTable采用”拉鏈法”實現(xiàn)哈希表不過性能比HashMap要低。

　　TreeMap

　　有序散列表，實現(xiàn)SortedMap接口，底層通過紅黑樹實現(xiàn)。

　　WeakHashMap

　　談WeakHashMap前先看一下Java中的引用(強(qiáng)度依次遞減)

　　1. 強(qiáng)引用：普遍對象聲明的引用，存在便不會GC

　　2. 軟引用：有用但并非必須，發(fā)生內(nèi)存溢出前，二次回收

　　3. 弱引用：只能生存到下次GC之前，無論是否內(nèi)存足夠

　　4. 虛引用：唯一目的是在這個對象被GC時能收到一個系統(tǒng)通知

　　以弱鍵實現(xiàn)的基于哈希表的Map。在 WeakHashMap 中，當(dāng)某個鍵不再正常使用時，將自動移除其條目。更精確地說，對于一個給定的鍵，其映射的存在并不阻止垃圾回收器對該鍵的丟棄，這就使該鍵成為可終止的，被終止，然后被回收。丟棄某個鍵時，其條目從映射中有效地移除，因此，該類的行為與其他的 Map 實現(xiàn)有所不同。null值和null鍵都被支持。該類具有與HashMap類相似的性能特征,并具有相同的效能參數(shù)初始容量和加載因子。像大多數(shù)集合類一樣，該類是不同步的。

　　四、總結(jié)

　　1、List、Set都是繼承自Collection接口，Map則不是

　　2、List特點(diǎn)：元素有放入順序，元素可重復(fù) ，Set特點(diǎn)：元素?zé)o放入順序，元素不可重復(fù)，重復(fù)元素會覆蓋掉，(注意：元素雖然無放入順序，但是元素在set中的位置是有該元素的HashCode決定的，其位置其實是固定的，加入Set 的Object必須定義equals()方法 ，另外list支持for循環(huán)，也就是通過下標(biāo)來遍歷，也可以用迭代器，但是set只能用迭代，因為他無序，無法用下標(biāo)來取得想要的值。)

　　3、Set和List對比：

　　Set：檢索元素效率低下，刪除和插入效率高，插入和刪除不會引起元素位置改變。

　　List：和數(shù)組類似，List可以動態(tài)增長，查找元素效率高，插入刪除元素效率低，因為會引起其他元素位置改變。

　　4、Map適合儲存鍵值對的數(shù)據(jù)

　　5、線程安全集合類與非線程安全集合類 :

　　· LinkedList、ArrayList、HashSet是非線程安全的，Vector是線程安全的;

　　· HashMap是非線程安全的，HashTable是線程安全的;

　　· StringBuilder是非線程安全的，StringBuffer是線程安全的。

　　更多關(guān)于“Java培訓(xùn)”的問題，歡迎咨詢千鋒教育在線名師。千鋒已有十余年的培訓(xùn)經(jīng)驗，課程大綱更科學(xué)更專業(yè)，有針對零基礎(chǔ)的就業(yè)班，有針對想提升技術(shù)的好程序員班，高品質(zhì)課程助理你實現(xiàn)java程序員夢想。