首先要說一下，本文對(duì)這些Java集合框架的面試題只做了一個(gè)總結(jié)式的回答崔涂，對(duì)每一道題目阳掐，都值得深入去了解一下（什么是扎實(shí)基本功，這些就是基本功~~）堪伍，后續(xù)可能對(duì)每一道題目拆開獨(dú)立篇章來深入講解一下锚烦。
大家看到這些總結(jié)觅闽，有疑惑的帝雇，就趕緊去查一查深入了解一下，當(dāng)然也歡迎指出文中錯(cuò)誤之處蛉拙。
以下是大綱：
HashMap和HashTable的區(qū)別尸闸？
說一下 HashMap 的底層結(jié)構(gòu)？
為什么HashMap是線程不安全的
ArrayList 和 LinkedList 的區(qū)別是什么孕锄？
ArrayList 和 Vector 的區(qū)別是什么吮廉？
Array 和 ArrayList 有何區(qū)別？
說一下 HashSet 的實(shí)現(xiàn)原理畸肆？
如何決定使用 HashMap 還是 TreeMap宦芦？
List、Set轴脐、Map 之間的區(qū)別是什么调卑？
HashMap怎樣解決hash沖突
1.HashMap和HashTable的區(qū)別？
HashMap 不是線程安全的
HashMap 是 map 接口的實(shí)現(xiàn)類大咱，是將鍵映射到值的對(duì)象恬涧，其中鍵和值都是對(duì)象，并且不能包含重復(fù)鍵碴巾，但可以包含重復(fù)值溯捆。HashMap 允許 null key 和 null value，而 HashTable 不允許厦瓢。
HashTable 是線程安全 Collection提揍。
HashMap 是 HashTable 的輕量級(jí)實(shí)現(xiàn)啤月，他們都完成了Map 接口，主要區(qū)別在于 HashMap 允許 null key 和 null value,由于非線程安全劳跃，效率上可能高于 Hashtable顽冶。
區(qū)別：
HashMap允許將 null 作為一個(gè) entry 的 key 或者 value，而 Hashtable 不允許售碳。
HashMap 把 Hashtable 的 contains 方法去掉了强重，改成 containsValue 和 containsKey。因?yàn)?contains 方法容易讓人引起誤解贸人。
HashTable 繼承自 Dictionary 類间景，而 HashMap 是 Java1.2 引進(jìn)的 Map interface 的一個(gè)實(shí)現(xiàn)。
HashTable 的方法是 Synchronize 的艺智，而 HashMap 不是倘要，在多個(gè)線程訪問 Hashtable 時(shí)，不需要自己為它的方法實(shí)現(xiàn)同步十拣，而 HashMap 就必須為之提供外同步封拧。
2.說一下 HashMap 的底層結(jié)構(gòu)？
HashMap的主干是一個(gè)Entry數(shù)組夭问。Entry是HashMap的基本組成單元泽西，每一個(gè)Entry包含一個(gè)key-value鍵值對(duì)。整體結(jié)構(gòu)圖：
HashMap由數(shù)組+鏈表組成的缰趋。
數(shù)組是HashMap的主體捧杉，鏈表則是主要為了解決哈希沖突而存在的，如果定位到的數(shù)組位置不含鏈表（當(dāng)前entry的next指向null）秘血，那么對(duì)于查找味抖，添加等操作很快，僅需一次尋址即可灰粮；如果定位到的數(shù)組包含鏈表仔涩，對(duì)于添加操作，其時(shí)間復(fù)雜度為O(n)粘舟，首先遍歷鏈表熔脂，存在即覆蓋，否則新增蓖乘；對(duì)于查找操作來講锤悄，仍需遍歷鏈表，然后通過key對(duì)象的equals方法逐一比對(duì)查找嘉抒。所以零聚，性能考慮，HashMap中的鏈表出現(xiàn)越少，性能才會(huì)越好隶症。
3.為什么HashMap是線程不安全的
見20期：【20期】你知道為什么HashMap是線程不安全的嗎政模？
4.ArrayList 和 LinkedList 的區(qū)別是什么？
ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)蚂会，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)淋样。
對(duì)于隨機(jī)訪問get和set，ArrayList覺得優(yōu)于LinkedList胁住，因?yàn)長(zhǎng)inkedList要移動(dòng)指針趁猴。
對(duì)于新增和刪除操作add和remove，LinedList比較占優(yōu)勢(shì)彪见，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)儡司。
5.ArrayList 和 Vector 的區(qū)別是什么？
1.同步性：
Vector是線程安全的余指，也就是說是它的方法之間是線程同步的捕犬，而ArrayList是線程序不安全的，它的方法之間是線程不同步的酵镜。如果只有一個(gè)線程會(huì)訪問到集合碉碉，那最好是使用ArrayList，因?yàn)樗豢紤]線程安全淮韭，效率會(huì)高些垢粮；如果有多個(gè)線程會(huì)訪問到集合，那最好是使用Vector缸濒，因?yàn)椴恍枰覀冏约涸偃タ紤]和編寫線程安全的代碼足丢。
PS：對(duì)于Vector&ArrayList粱腻、Hashtable&HashMap庇配，要記住線程安全的問題，記住Vector與Hashtable是舊的绍些，是java一誕生就提供了的捞慌，它們是線程安全的，ArrayList與HashMap是java2時(shí)才提供的柬批，它們是線程不安全的啸澡。所以，我們講課時(shí)先講老的氮帐。
2.數(shù)據(jù)增長(zhǎng)：
ArrayList與Vector都有一個(gè)初始的容量大小嗅虏，當(dāng)存儲(chǔ)進(jìn)它們里面的元素的個(gè)數(shù)超過了容量時(shí)，就需要增加ArrayList與Vector的存儲(chǔ)空間上沐，每次要增加存儲(chǔ)空間時(shí)皮服，不是只增加一個(gè)存儲(chǔ)單元，而是增加多個(gè)存儲(chǔ)單元，每次增加的存儲(chǔ)單元的個(gè)數(shù)在內(nèi)存空間利用與程序效率之間要取得一定的平衡龄广。
Vector默認(rèn)增長(zhǎng)為原來兩倍硫眯，而ArrayList的增長(zhǎng)策略在文檔中沒有明確規(guī)定（從源代碼看到的是增長(zhǎng)為原來的1.5倍）。ArrayList與Vector都可以設(shè)置初始的空間大小择同，Vector還可以設(shè)置增長(zhǎng)的空間大小两入，而ArrayList沒有提供設(shè)置增長(zhǎng)空間的方法。
即Vector增長(zhǎng)原來的一倍敲才，ArrayList增加原來的0.5倍裹纳。
6.Array 和 ArrayList 有何區(qū)別？
Array 可以包含基本數(shù)據(jù)類型和引用類型紧武，ArrayList只能包含引用類型痊夭。
ArrayList是基于數(shù)組實(shí)現(xiàn)的，Array大小不可以調(diào)整大小脏里，但ArrayList可以通過內(nèi)部方法自動(dòng)調(diào)整容量她我。
ArrayList是List接口的實(shí)現(xiàn)類，相比Array支持更多的方法和特性迫横。
7.說一下 HashSet 的實(shí)現(xiàn)原理番舆？
1.HashSet是基于HashMap實(shí)現(xiàn)的，默認(rèn)構(gòu)造函數(shù)是構(gòu)建一個(gè)初始容量為16矾踱，負(fù)載因子為0.75 的HashMap恨狈。封裝了一個(gè) HashMap 對(duì)象來存儲(chǔ)所有的集合元素，所有放入 HashSet 中的集合元素實(shí)際上由 HashMap 的 key 來保存呛讲，而 HashMap 的 value 則存儲(chǔ)了一個(gè) PRESENT禾怠，它是一個(gè)靜態(tài)的 Object 對(duì)象。
2.當(dāng)我們?cè)噲D把某個(gè)類的對(duì)象當(dāng)成 HashMap的 key贝搁，或試圖將這個(gè)類的對(duì)象放入 HashSet 中保存時(shí)吗氏，重寫該類的equals(Object obj)方法和 hashCode() 方法很重要，而且這兩個(gè)方法的返回值必須保持一致：當(dāng)該類的兩個(gè)的 hashCode() 返回值相同時(shí)雷逆，它們通過 equals() 方法比較也應(yīng)該返回 true弦讽。通常來說，所有參與計(jì)算 hashCode() 返回值的關(guān)鍵屬性膀哲，都應(yīng)該用于作為 equals() 比較的標(biāo)準(zhǔn)往产。
3.HashSet的其他操作都是基于HashMap的。
8.如何決定使用 HashMap 還是 TreeMap某宪？
見03期：【03期】如何決定使用 HashMap 還是 TreeMap仿村？
9.List、Set兴喂、Map 之間的區(qū)別是什么蔼囊？
List(列表)
List的元素以線性方式存儲(chǔ)包颁，可以存放重復(fù)對(duì)象，List主要有以下兩個(gè)實(shí)現(xiàn)類：
1.ArrayList:?長(zhǎng)度可變的數(shù)組压真，可以對(duì)元素進(jìn)行隨機(jī)的訪問娩嚼，向ArrayList中插入與刪除元素的速度慢。JDK8中ArrayList擴(kuò)容的實(shí)現(xiàn)是通過grow()方法里使用語句newCapacity = oldCapacity + (oldCapacity >> 1)（即1.5倍擴(kuò)容）計(jì)算容量滴肿，然后調(diào)用Arrays.copyof()方法進(jìn)行對(duì)原數(shù)組進(jìn)行復(fù)制岳悟。
LinkedList:?采用鏈表數(shù)據(jù)結(jié)構(gòu)，插入和刪除速度快泼差，但訪問速度慢贵少。
Set(集合)
Set中的對(duì)象不按特定(HashCode)的方式排序，并且沒有重復(fù)對(duì)象堆缘，Set主要有以下兩個(gè)實(shí)現(xiàn)類：
1.HashSet：HashSet按照哈希算法來存取集合中的對(duì)象滔灶，存取速度比較快。當(dāng)HashSet中的元素個(gè)數(shù)超過數(shù)組大小*loadFactor（默認(rèn)值為0.75）時(shí)吼肥，就會(huì)進(jìn)行近似兩倍擴(kuò)容（newCapacity = (oldCapacity << 1) + 1）录平。
2.TreeSet：TreeSet實(shí)現(xiàn)了SortedSet接口，能夠?qū)现械膶?duì)象進(jìn)行排序缀皱。
Map(映射)
Map是一種把鍵對(duì)象和值對(duì)象映射的集合斗这，它的每一個(gè)元素都包含一個(gè)鍵對(duì)象和值對(duì)象。Map主要有以下實(shí)現(xiàn)類：
HashMap：HashMap基于散列表實(shí)現(xiàn)啤斗，其插入和查詢的開銷是固定的表箭，可以通過構(gòu)造器設(shè)置容量和負(fù)載因子來調(diào)整容器的性能。
LinkedHashMap：類似于HashMap钮莲，但是迭代遍歷它時(shí)免钻，取得的順序是其插入次序，或者是最近最少使用(LRU)的次序崔拥。
TreeMap：TreeMap基于紅黑樹實(shí)現(xiàn)极舔。查看時(shí)，它們會(huì)被排序握童。TreeMap是唯一的帶有subMap()方法的Map姆怪，subMap()可以返回一個(gè)子樹。
