概述

Java語(yǔ)言開(kāi)發(fā)經(jīng)常會(huì)使用到集合框架，如下圖所示為Java 集合框架結(jié)構(gòu)圖:

java集合.png

從圖中可以看出Java 集合主要實(shí)現(xiàn)了Map和Collection接口。

List、Set、Map 三者區(qū)別

① List (突出順序)： 存儲(chǔ)的元素是有序的、可重復(fù)的；
② Set (注重獨(dú)???): 存儲(chǔ)的元素是?序的、不可重復(fù)的；
③ Map: 使?鍵值對(duì)（kye-value）存儲(chǔ)，類(lèi)似于數(shù)學(xué)上的函數(shù) y=f(x)，“x”代表key，"y"代表 value，Key 是?序的、不可重復(fù)的，value 是?序的、可重復(fù)的，每個(gè)鍵最多映射到?個(gè)值。

集合底層數(shù)據(jù)結(jié)構(gòu)

Collection 接?下?的集合

① List 接口
Arraylist ： Object[] 數(shù)組，
Vector ： Object[] 數(shù)組，
LinkedList ： 雙向鏈表(JDK1.6 之前為循環(huán)鏈表，JDK1.7 取消了循環(huán))。
② Set 接口
HashSet （?序，唯?）: 基于 HashMap 實(shí)現(xiàn)的，底層采? HashMap 來(lái)保存元素；
LinkedHashSet ： LinkedHashSet 是 HashSet 的?類(lèi)，并且其內(nèi)部是通過(guò) LinkedHashMap 來(lái)
實(shí)現(xiàn)的。有點(diǎn)類(lèi)似于我們之前說(shuō)的 LinkedHashMap 其內(nèi)部是基于 HashMap 實(shí)現(xiàn)?樣，不過(guò)還是
有?點(diǎn)點(diǎn)區(qū)別的；
TreeSet （有序，唯?）： 紅?樹(shù)(?平衡的排序?叉樹(shù))。
③ Map 接口
HashMap ： JDK1.8 之前 HashMap 由數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體，鏈表則是主要
為了解決哈希沖突?存在的（“拉鏈法”解決沖突）。JDK1.8 以后在解決哈希沖突時(shí)有了較?的變
化，當(dāng)鏈表?度?于閾值（默認(rèn)為 8）（將鏈表轉(zhuǎn)換成紅?樹(shù)前會(huì)判斷，如果當(dāng)前數(shù)組的?度?于
64，那么會(huì)選擇先進(jìn)?數(shù)組擴(kuò)容，?不是轉(zhuǎn)換為紅?樹(shù)）時(shí)，將鏈表轉(zhuǎn)化為紅?樹(shù)，以減少搜索時(shí)
間；
LinkedHashMap ： LinkedHashMap 繼承? HashMap ，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)
即由數(shù)組和鏈表或紅?樹(shù)組成。另外， LinkedHashMap 在上?結(jié)構(gòu)的基礎(chǔ)上，增加了?條雙向鏈
表，使得上?的結(jié)構(gòu)可以保持鍵值對(duì)的插?順序。同時(shí)通過(guò)對(duì)鏈表進(jìn)?相應(yīng)的操作，實(shí)現(xiàn)了訪(fǎng)問(wèn)順
序相關(guān)邏輯；
Hashtable ： 數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突?存
在的；
TreeMap ： 紅?樹(shù)（?平衡的排序?叉樹(shù)）。

如何選擇使用集合

① 根據(jù)鍵值獲取元素值時(shí)就選? Map 接?下的集合，需要排序時(shí)選擇 TreeMap ,不需要排序時(shí)選擇 HashMap ,保證線(xiàn)程安全就選?ConcurrentHashMap ;
② 只需要存放元素值時(shí)，就選擇實(shí)現(xiàn) Collection 接?的集合，保證元素唯?時(shí)選擇實(shí)現(xiàn)Set 接?的集合?如 TreeSet 或 HashSet ，不需要就選擇實(shí)現(xiàn) List 接?的?如 ArrayList 或LinkedList ，然后再根據(jù)實(shí)現(xiàn)這些接?的集合的特點(diǎn)來(lái)選?。

為什么要使用集合

① 在實(shí)際開(kāi)發(fā)中，存儲(chǔ)的數(shù)據(jù)的類(lèi)型是多種多樣的，數(shù)組支持的類(lèi)型較固定，就出現(xiàn)了“集合”；
② 數(shù)組的缺點(diǎn)是?旦聲明之后，?度就不可變了，數(shù)組存儲(chǔ)的數(shù)據(jù)是有序、可重復(fù)的，特點(diǎn)單?；
③ 集合提?數(shù)據(jù)存儲(chǔ)靈活性，Java 集合不僅?來(lái)存儲(chǔ)不同類(lèi)型不同數(shù)量對(duì)象，還可以保存具有映射關(guān)系的數(shù)據(jù)。

集合線(xiàn)程安全選擇

常?的 Arraylist , LinkedList , Hashmap , HashSet , TreeSet , TreeMap ， PriorityQueue 都
不是線(xiàn)程安全的。如果使?線(xiàn)程安全集合的話(huà)， java.util.concurrent 包中提供很多并發(fā)容器：
① ConcurrentHashMap : 可以看作是線(xiàn)程安全的 HashMap
② CopyOnWriteArrayList :可以看作是線(xiàn)程安全的 ArrayList ，在讀多寫(xiě)少的場(chǎng)合性能?常好，遠(yuǎn)
遠(yuǎn)好于 Vector .
③ ConcurrentLinkedQueue :?效的并發(fā)隊(duì)列，使?鏈表實(shí)現(xiàn)?？梢钥醋?個(gè)線(xiàn)程安全的
LinkedList ，這是?個(gè)?阻塞隊(duì)列。
④ BlockingQueue : 這是?個(gè)接?，JDK 內(nèi)部通過(guò)鏈表、數(shù)組等?式實(shí)現(xiàn)了這個(gè)接?。表示阻塞隊(duì)
列，?常適合?于作為數(shù)據(jù)共享的通道。
⑤ ConcurrentSkipListMap :跳表的實(shí)現(xiàn)。這是?個(gè) Map ，使?跳表的數(shù)據(jù)結(jié)構(gòu)進(jìn)?快速查找。

集合子接口及方法對(duì)比

Arraylist 和 Vector 的區(qū)別?

① ArrayList 是 List 主要實(shí)現(xiàn)類(lèi)，底層使? Object[ ]存儲(chǔ)，適?于頻繁的查找?作，線(xiàn)程不安全 ；
② Vector 是 List 的古?實(shí)現(xiàn)類(lèi)，底層使? Object[ ]存儲(chǔ)，線(xiàn)程安全的。

Arraylist 與 LinkedList 區(qū)別?

① 是否保證線(xiàn)程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證線(xiàn)程安全；
② 底層數(shù)據(jù)結(jié)構(gòu)： Arraylist 底層使?的是 Object Object 數(shù)組； LinkedList 底層使?的是 雙向鏈表，數(shù)據(jù)結(jié)構(gòu)（JDK1.6 之前為循環(huán)鏈表，JDK1.7 取消了循環(huán)。
③ 插?和刪除是否受元素位置的影響：
ArrayList ArrayList 采?數(shù)組存儲(chǔ)，所以插?和刪除元素的時(shí)間復(fù)雜度受元素位置的影響。 ?如：執(zhí)? add(E e) ?法的時(shí)候， ArrayList 會(huì)默認(rèn)在將指定的元素追加到此列表的末尾，這種情況時(shí)間復(fù)雜度就是 O(1)。但是如果要在指定位置 i 插?和刪除元素的話(huà)（ add(int index, E element) ）時(shí)間復(fù)雜度就為 O(n-i)。因?yàn)樵谶M(jìn)?上述操作的時(shí)候集合中第 i 和第 i 個(gè)元素之后的(n-i)個(gè)元素都要執(zhí)?向后位/向前移?位的操作。
LinkedList LinkedList 采?鏈表存儲(chǔ)，所以對(duì)于 add(E e) add(E e) ?法的插?，刪除元素時(shí)間復(fù)雜度不受元素位置的影響，近似O(1)，如果是要在指定位置 ii 插?和刪除元素的話(huà)（ (add(int index, E element) (add(int index, E element) ） 時(shí)間復(fù)雜度近似為 o(n)) o(n)) 因?yàn)樾枰纫苿?dòng)到指定位置再插?。
④ 是否?持快速隨機(jī)訪(fǎng)問(wèn)： LinkedList 不?持?效的隨機(jī)元素訪(fǎng)問(wèn)，? ArrayList ?持。快速隨
機(jī)訪(fǎng)問(wèn)就是通過(guò)元素的序號(hào)快速獲取元素對(duì)象(對(duì)應(yīng)于 get(int index) ?法)。
⑤ 內(nèi)存空間占?： ArrayList 的空 間浪費(fèi)主要體現(xiàn)在在 list 列表的結(jié)尾會(huì)預(yù)留?定的容量空間，?
LinkedList 的空間花費(fèi)則體現(xiàn)在它的每?個(gè)元素都需要消耗? ArrayList 更多的空間（因?yàn)橐娣胖?br> 接后繼和直接前驅(qū)以及數(shù)據(jù)）。

comparable 和 Comparator 的區(qū)別

① comparable 接?實(shí)際上是出? java.lang 包 它有?個(gè) compareTo(Object obj) ?法?來(lái)排序；
② comparator 接?實(shí)際上是出? java.util 包它有?個(gè) compare(Object obj1, Object obj2) ?法?
來(lái)排序。

?較 HashSet、LinkedHashSet 和 TreeSet 三者的異同

HashSet 是 Set 接?的主要實(shí)現(xiàn)類(lèi) ，HashSet 的底層是 HashMap，線(xiàn)程不安全的，可以存儲(chǔ) null 值；
LinkedHashSet 是 HashSet 的?類(lèi)，能夠按照添加的順序遍歷；
TreeSet 底層使?紅?樹(shù)，能夠按照添加元素的順序進(jìn)?遍歷，排序的?式有?然排序和定制排序。

HashMap 和 Hashtable 的區(qū)別

① 線(xiàn)程是否安全： HashMap 是?線(xiàn)程安全的，HashTable 是線(xiàn)程安全的,因?yàn)?HashTable 內(nèi)部的?法基本都經(jīng)過(guò) synchronized 修飾。（如果保證線(xiàn)程安全就使? ConcurrentHashMap）；
② 效率： 因?yàn)榫€(xiàn)程安全，HashMap 要? HashTable 效率??點(diǎn)。另外，HashTable 基本被淘
汰，不要在代碼中使?它；
③ 對(duì) Null key 和 Null value 的?持： HashMap 可以存儲(chǔ) null 的 key 和 value，但 null 作為鍵只能?個(gè)，null 作為值可以有多個(gè)；HashTable 不允許有 null 鍵和 null 值，NullPointerException。
④ 初始容量??和每次擴(kuò)充容量??的不同 ： ① 創(chuàng)建時(shí)如果不指定容量初始值，Hashtable 默認(rèn)的初始??為 11，之后每次擴(kuò)充，容量變?yōu)樵瓉?lái)的 2n+1。HashMap 默認(rèn)的初始化??為 16。之后每次擴(kuò)充，容量變?yōu)樵瓉?lái)的 2 倍。② 創(chuàng)建時(shí)如果給定了容量初始值，那么 Hashtable 會(huì)直接使?你給定的??，? HashMap 會(huì)將其擴(kuò)充為 2 的冪次???（HashMap 中的 tableSizeFor() ?法保
證，下?給出了源代碼）。也就是說(shuō) HashMap 總是使? 2 的冪作為哈希表的??,后?會(huì)介紹到為
什么是 2 的冪次?。
⑤ 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時(shí)有了較?變化，當(dāng)鏈表?度?于閾
值（默認(rèn)為 8）（將鏈表轉(zhuǎn)換成紅?樹(shù)前會(huì)判斷，如果當(dāng)前數(shù)組的?度?于 64，那么會(huì)選擇先進(jìn)?
數(shù)組擴(kuò)容，?不是轉(zhuǎn)換為紅?樹(shù)）時(shí)，將鏈表轉(zhuǎn)化為紅?樹(shù)，以減少搜索時(shí)間。Hashtable 沒(méi)有這
樣的機(jī)制。
HashMap 中帶有初始容量的構(gòu)造函數(shù)：

public HashMap(int initialCapacity, float loadFactor) {
 if (initialCapacity < 0)
 throw new IllegalArgumentException("Illegal initial capacity: "
+
 initialCapacity);
 if (initialCapacity > MAXIMUM_CAPACITY)
 initialCapacity = MAXIMUM_CAPACITY;
 if (loadFactor <= 0 || Float.isNaN(loadFactor))
 throw new IllegalArgumentException("Illegal load factor: " +
 loadFactor);
 this.loadFactor = loadFactor;
 this.threshold = tableSizeFor(initialCapacity);
 }
 public HashMap(int initialCapacity) {
 this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }

HashMap 和 HashSet 區(qū)別

如果你看過(guò) HashSet 源碼的話(huà)就應(yīng)該知道：HashSet 底層就是基于 HashMap 實(shí)現(xiàn)的。（HashSet 的源碼?常少，因?yàn)槌?clone() 、 writeObject() 、 readObject() 是 HashSet ??不得不實(shí)現(xiàn)
之外，其他?法都是直接調(diào)? HashMap 中的?法。