主要內(nèi)容：

　　Arraylist與LinkedList異同

　　ArrayList與Vector區(qū)別

　　HashMap的底層實(shí)現(xiàn)

　　HashMap和Hashtable的區(qū)別

　　HashMap的長(zhǎng)度為什么是2的冪次方

　　HashSet和HashMap區(qū)別

　　ConcurrentHashMap和Hashtable的區(qū)別

　　ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層具體實(shí)現(xiàn)

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

　　Arraylist與LinkedList異同

　　1.是否保證線程安全：ArrayList和LinkedList都是不同步的，也就是不保證線程安全；

　　2.底層數(shù)據(jù)結(jié)構(gòu)：Arraylist底層使用的是Object數(shù)組；LinkedList底層使用的是雙向循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)；

　　3.插入和刪除是否受元素位置的影響：①ArrayList采用數(shù)組存儲(chǔ)，所以插入和刪除元素的時(shí)間復(fù)雜度受元素位置的影響。比如：執(zhí)行add(Ee)方法的時(shí)候，ArrayList會(huì)默認(rèn)在將指定的元素追加到此列表的末尾，這種情況時(shí)間復(fù)雜度就是O(1)。但是如果要在指定位置i插入和刪除元素的話（add(intindex,Eelement)）時(shí)間復(fù)雜度就為O(n-i)。因?yàn)樵谶M(jìn)行上述操作的時(shí)候集合中第i和第i個(gè)元素之后的(n-i)個(gè)元素都要執(zhí)行向后位/向前移一位的操作。②LinkedList采用鏈表存儲(chǔ)，所以插入，刪除元素時(shí)間復(fù)雜度不受元素位置的影響，都是近似O（1）而數(shù)組為近似O（n）。

　　4.是否支持快速隨機(jī)訪問：LinkedList不支持高效的隨機(jī)元素訪問，而ArrayList實(shí)現(xiàn)了RandmoAccess接口，所以有隨機(jī)訪問功能。快速隨機(jī)訪問就是通過元素的序號(hào)快速獲取元素對(duì)象(對(duì)應(yīng)于get(intindex)方法)。

　　5.內(nèi)存空間占用：ArrayList的空間浪費(fèi)主要體現(xiàn)在在list列表的結(jié)尾會(huì)預(yù)留一定的容量空間，而LinkedList的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗比ArrayList更多的空間（因?yàn)橐娣胖苯雍罄^和直接前驅(qū)以及數(shù)據(jù)）。

　　補(bǔ)充：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之雙向鏈表

　　雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表，如下圖所示，同時(shí)下圖也是LinkedList底層使用的是雙向循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)。

　　ArrayList與Vector區(qū)別

　　Vector類的所有方法都是同步的。可以由兩個(gè)線程安全地訪問一個(gè)Vector對(duì)象、但是一個(gè)線程訪問Vector的話代碼要在同步操作上耗費(fèi)大量的時(shí)間。

　　Arraylist不是同步的，所以在不需要保證線程安全時(shí)時(shí)建議使用Arraylist。

　　HashMap的底層實(shí)現(xiàn)

　　JDK1.8之前

　　JDK1.8之前HashMap由數(shù)組+鏈表組成的（“鏈表散列”即數(shù)組和鏈表的結(jié)合體），數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（HashMap采用“拉鏈法也就是鏈地址法”解決沖突），如果定位到的數(shù)組位置不含鏈表（當(dāng)前entry的next指向null）,那么對(duì)于查找，添加等操作很快，僅需一次尋址即可；如果定位到的數(shù)組包含鏈表，對(duì)于添加操作，其時(shí)間復(fù)雜度依然為O(1)，因?yàn)樽钚碌腅ntry會(huì)插入鏈表頭部，即需要簡(jiǎn)單改變引用鏈即可，而對(duì)于查找操作來講，此時(shí)就需要遍歷鏈表，然后通過key對(duì)象的equals方法逐一比對(duì)查找.

　　所謂“拉鏈法”就是將鏈表和數(shù)組相結(jié)合。也就是說創(chuàng)建一個(gè)鏈表數(shù)組，數(shù)組中每一格就是一個(gè)鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。

　　JDK1.8之后

　　相比于之前的版本，JDK1.8之后在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時(shí)間。

　　TreeMap、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹。紅黑樹就是為了解決二叉查找樹的缺陷，因?yàn)槎娌檎覙湓谀承┣闆r下會(huì)退化成一個(gè)線性結(jié)構(gòu)。

　　HashMap和Hashtable的區(qū)別

　　線程是否安全：HashMap是非線程安全的，HashTable是線程安全的；HashTable內(nèi)部的方法基本都經(jīng)過synchronized修飾。（如果你要保證線程安全的話就使用ConcurrentHashMap吧！）；

　　效率：因?yàn)榫€程安全的問題，HashMap要比HashTable效率高一點(diǎn)。另外，HashTable基本被淘汰，不要在代碼中使用它；

　　對(duì)Nullkey和Nullvalue的支持：HashMap中，null可以作為鍵，這樣的鍵只有一個(gè)，可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為null。。但是在HashTable中put進(jìn)的鍵值只要有一個(gè)null，直接拋出NullPointerException。

　　初始容量大小和每次擴(kuò)充容量大小的不同：①創(chuàng)建時(shí)如果不指定容量初始值，Hashtable默認(rèn)的初始大小為11，之后每次擴(kuò)充，容量變?yōu)樵瓉淼?n+1。HashMap默認(rèn)的初始化大小為16。之后每次擴(kuò)充，容量變?yōu)樵瓉淼?倍。②創(chuàng)建時(shí)如果給定了容量初始值，那么Hashtable會(huì)直接使用你給定的大小，而HashMap會(huì)將其擴(kuò)充為2的冪次方大小。也就是說HashMap總是使用2的冪次方作為哈希表的大小,后面會(huì)介紹到為什么是2的冪次方。

　　底層數(shù)據(jù)結(jié)構(gòu)：JDK1.8以后的HashMap在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時(shí)間。Hashtable沒有這樣的機(jī)制。

　　HashMap的長(zhǎng)度為什么是2的冪次方

　　為了能讓HashMap存取高效，盡量較少碰撞，也就是要盡量把數(shù)據(jù)分配均勻，每個(gè)鏈表/紅黑樹長(zhǎng)度大致相同。這個(gè)實(shí)現(xiàn)就是把數(shù)據(jù)存到哪個(gè)鏈表/紅黑樹中的算法。

　　這個(gè)算法應(yīng)該如何設(shè)計(jì)呢？

　　我們首先可能會(huì)想到采用%取余的操作來實(shí)現(xiàn)。但是，重點(diǎn)來了：“取余(%)操作中如果除數(shù)是2的冪次則等價(jià)于與其除數(shù)減一的與(&)操作（也就是說hash%length==hash&(length-1)的前提是length是2的n次方；）。”并且采用二進(jìn)制位操作&，相對(duì)于%能夠提高運(yùn)算效率，這就解釋了HashMap的長(zhǎng)度為什么是2的冪次方。

　　HashSet和HashMap區(qū)別

　　ConcurrentHashMap和Hashtable的區(qū)別

　　ConcurrentHashMap和Hashtable的區(qū)別主要體現(xiàn)在實(shí)現(xiàn)線程安全的方式上不同。

　　底層數(shù)據(jù)結(jié)構(gòu)：JDK1.7的ConcurrentHashMap底層采用分段的數(shù)組+鏈表實(shí)現(xiàn)，JDK1.8采用的數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)類似，數(shù)組+鏈表/紅黑二叉樹。Hashtable和JDK1.8之前的HashMap的底層數(shù)據(jù)結(jié)構(gòu)類似都是采用數(shù)組+鏈表的形式，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的；

　　實(shí)現(xiàn)線程安全的方式（重要）：①在JDK1.7的時(shí)候，ConcurrentHashMap（分段鎖）對(duì)整個(gè)桶數(shù)組進(jìn)行了分割分段(Segment)，每一把鎖只鎖容器其中一部分?jǐn)?shù)據(jù)，多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)，就不會(huì)存在鎖競(jìng)爭(zhēng)，提高并發(fā)訪問率。（默認(rèn)分配16個(gè)Segment，比Hashtable效率提高16倍。）到了JDK1.8的時(shí)候已經(jīng)摒棄了Segment的概念，而是直接用Node數(shù)組+鏈表/紅黑樹的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，并發(fā)控制使用synchronized和CAS來操作。（JDK1.6以后對(duì)synchronized鎖做了很多優(yōu)化）整個(gè)看起來就像是優(yōu)化過且線程安全的HashMap，雖然在JDK1.8中還能看到Segment的數(shù)據(jù)結(jié)構(gòu)，但是已經(jīng)簡(jiǎn)化了屬性，只是為了兼容舊版本；②Hashtable(同一把鎖):使用synchronized來保證線程安全，效率非常低下。當(dāng)一個(gè)線程訪問同步方法時(shí)，其他線程也訪問同步方法，可能會(huì)進(jìn)入阻塞或輪詢狀態(tài)，如使用put添加元素，另一個(gè)線程不能使用put添加元素，也不能使用get，競(jìng)爭(zhēng)越激烈效率越低。

　　兩者的對(duì)比圖：

　　JDK1.7的ConcurrentHashMap：

　　JDK1.8的ConcurrentHashMap（TreeBin:紅黑二叉樹節(jié)點(diǎn)；Node:鏈表節(jié)點(diǎn)）：

　　ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層具體實(shí)現(xiàn)

　　JDK1.7（上面有示意圖）

　　首先將數(shù)據(jù)分為一段一段的存儲(chǔ)，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個(gè)線程占用鎖訪問其中一個(gè)段數(shù)據(jù)時(shí)，其他段的數(shù)據(jù)也能被其他線程訪問。

　　ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HahEntry數(shù)組結(jié)構(gòu)組成。

　　Segment實(shí)現(xiàn)了ReentrantLock,所以Segment是一種可重入鎖，扮演鎖的角色。HashEntry用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)。

　　staticclassSegment<K,V>extendsReentrantLockimplementsSerializable{}

　　一個(gè)ConcurrentHashMap里包含一個(gè)Segment數(shù)組。Segment的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)，一個(gè)Segment包含一個(gè)HashEntry數(shù)組，每個(gè)HashEntry是一個(gè)鏈表結(jié)構(gòu)的元素，每個(gè)Segment守護(hù)著一個(gè)HashEntry數(shù)組里的元素，當(dāng)對(duì)HashEntry數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)，必須首先獲得對(duì)應(yīng)的Segment的鎖。

　　JDK1.8（上面有示意圖）

　　ConcurrentHashMap取消了Segment分段鎖，采用CAS和synchronized來保證并發(fā)安全。數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)類似，數(shù)組+鏈表/紅黑二叉樹。

　　synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點(diǎn)，這樣只要hash不沖突，就不會(huì)產(chǎn)生并發(fā)，效率又提升N倍。

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

　　Collection

　　1.List

　　Arraylist：Object數(shù)組

　　Vector：Object數(shù)組

　　LinkedList：雙向循環(huán)鏈表

　　2.Set

　　HashSet（無序，唯一）:基于HashMap實(shí)現(xiàn)的，底層采用HashMap來保存元素。HashMap底層數(shù)據(jù)結(jié)構(gòu)見下。

　　LinkedHashSet：LinkedHashSet繼承與HashSet，并且其內(nèi)部是通過LinkedHashMap來實(shí)現(xiàn)的。有點(diǎn)類似于我們之前說的LinkedHashMap其內(nèi)部是基于Hashmap實(shí)現(xiàn)一樣，不過還是有一點(diǎn)點(diǎn)區(qū)別的。

　　TreeSet（有序，唯一）：紅黑樹(自平衡的排序二叉樹。)

　　Map

　　HashMap：JDK1.8之前HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8以后在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時(shí)間

　　LinkedHashMap:LinkedHashMap繼承自HashMap，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹組成。另外，LinkedHashMap在上面結(jié)構(gòu)的基礎(chǔ)上，增加了一條雙向鏈表，使得上面的結(jié)構(gòu)可以保持鍵值對(duì)的插入順序。同時(shí)通過對(duì)鏈表進(jìn)行相應(yīng)的操作，實(shí)現(xiàn)了訪問順序相關(guān)邏輯。詳細(xì)可以查看：《LinkedHashMap源碼詳細(xì)分析（JDK1.8）》：https://www.imooc.com/article/22931

　　HashTable:數(shù)組+鏈表組成的，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的

　　TreeMap:紅黑樹（自平衡的排序二叉樹）

　　以上就是動(dòng)力節(jié)點(diǎn)Java培訓(xùn)機(jī)構(gòu)介紹的“這幾道Java集合框架面試題在面試中幾乎必問”的內(nèi)容，希望通過此文，能夠幫助到那些正在找工作的Java程序員，更多Java面試題請(qǐng)?jiān)诰€咨詢，有專業(yè)老師為你提供名企Java面試題。

　　相關(guān)推薦

　　Java面試題請(qǐng)點(diǎn)擊：http://m.ilovecolors.com.cn/tutorial_baseinterviewquestions/