1.什么是集合

集合框架：用于存儲(chǔ)數(shù)據(jù)的容器。

集合框架是為表示和操作集合而規(guī)定的一種統(tǒng)一的標(biāo)準(zhǔn)的體系結(jié)構(gòu)方咆。 任何集合框架都包含三大塊內(nèi)容：對(duì)外的接口牌废、接口的實(shí)現(xiàn)和對(duì)集合運(yùn)算的算 法阴汇。

接口：表示集合的抽象數(shù)據(jù)類(lèi)型备埃。接口允許我們操作集合時(shí)不必關(guān)注具體實(shí)現(xiàn)冰悠， 從而達(dá)到“多態(tài)”堡妒。在面向?qū)ο缶幊陶Z(yǔ)言中，接口通常用來(lái)形成規(guī)范溉卓。

實(shí)現(xiàn)：集合接口的具體實(shí)現(xiàn)皮迟，是重用性很高的數(shù)據(jù)結(jié)構(gòu)。
算法：在一個(gè)實(shí)現(xiàn)了某個(gè)集合框架中的接口的對(duì)象身上完成某種有用的計(jì)算的方 法桑寨，例如查找万栅、排序等。這些算法通常是多態(tài)的西疤，因?yàn)橄嗤姆椒梢栽谕粋€(gè) 接口被多個(gè)類(lèi)實(shí)現(xiàn)時(shí)有不同的表現(xiàn)烦粒。事實(shí)上，算法是可復(fù)用的函數(shù)代赁。 它減少了程序設(shè)計(jì)的辛勞扰她。

集合框架通過(guò)提供有用的數(shù)據(jù)結(jié)構(gòu)和算法使你能集中注意力于你的程序的重要部 分上，而不是為了讓程序能正常運(yùn)轉(zhuǎn)而將注意力于底層設(shè)計(jì)上芭碍。

通過(guò)這些在無(wú)關(guān)API之間的簡(jiǎn)易的互用性徒役，使你免除了為改編對(duì)象或轉(zhuǎn)換代碼以 便聯(lián)合這些API而去寫(xiě)大量的代碼。 它提高了程序速度和質(zhì)量窖壕。

2.集合的特點(diǎn)

集合的特點(diǎn)主要有如下兩點(diǎn)：

• 對(duì)象封裝數(shù)據(jù)忧勿，對(duì)象多了也需要存儲(chǔ)。集合用于存儲(chǔ)對(duì)象瞻讽。
• 對(duì)象的個(gè)數(shù)確定可以使用數(shù)組鸳吸，對(duì)象的個(gè)數(shù)不確定的可以用集合。因 為集合是可變長(zhǎng)度的速勇。

3.集合和數(shù)組的區(qū)別

• 數(shù)組是固定長(zhǎng)度的晌砾；集合可變長(zhǎng)度的。
• 數(shù)組可以存儲(chǔ)基本數(shù)據(jù)類(lèi)型烦磁，也可以存儲(chǔ)引用數(shù)據(jù)類(lèi)型养匈；集合只能存 儲(chǔ)引用數(shù)據(jù)類(lèi)型。
• 數(shù)組存儲(chǔ)的元素必須是同一個(gè)數(shù)據(jù)類(lèi)型都伪；集合存儲(chǔ)的對(duì)象可以是不同 數(shù)據(jù)類(lèi)型呕乎。

數(shù)據(jù)結(jié)構(gòu)：就是容器中存儲(chǔ)數(shù)據(jù)的方式。

對(duì)于集合容器陨晶，有很多種猬仁。因?yàn)槊恳粋€(gè)容器的自身特點(diǎn)不同，其實(shí)原理在于每個(gè) 容器的內(nèi)部數(shù)據(jù)結(jié)構(gòu)不同。

集合容器在不斷向上抽取過(guò)程中逐虚，出現(xiàn)了集合體系聋溜。在使用一個(gè)體系的原則：參 閱頂層內(nèi)容。建立底層對(duì)象叭爱。

4.使用集合框架的好處

1. 容量自增長(zhǎng)撮躁；
2. 提供了高性能的數(shù)據(jù)結(jié)構(gòu)和算法，使編碼更輕松买雾，提高了程序速度和質(zhì) 量把曼；
3. 允許不同 API 之間的互操作，API之間可以來(lái)回傳遞集合漓穿；
4. 可以方便地?cái)U(kuò)展或改寫(xiě)集合嗤军，提高代碼復(fù)用性和可操作性。
5. 通過(guò)使用JDK自帶的集合類(lèi)晃危，可以降低代碼維護(hù)和學(xué)習(xí)新API成本叙赚。

5.常用的集合類(lèi)有哪些？

Map接口和Collection接口是所有集合框架的父接口：

1. Collection接口的子接口包括：Set接口和List接口
2. Map接口的實(shí)現(xiàn)類(lèi)主要有：HashMap僚饭、TreeMap震叮、Hashtable、 ConcurrentHashMap以及Properties等
3. Set接口的實(shí)現(xiàn)類(lèi)主要有：HashSet鳍鸵、TreeSet苇瓣、LinkedHashSet等
4. List接口的實(shí)現(xiàn)類(lèi)主要有：ArrayList、LinkedList偿乖、Stack以及Vector等

6.List击罪，Set，Map三者的區(qū)別贪薪？List媳禁、Set、Map 是否繼 承自 Collection 接口古掏？List损话、Map、Set 三個(gè)接口存取 元素時(shí)槽唾，各有什么特點(diǎn)？

Collection.png

Map.png

Java 容器分為 Collection 和 Map 兩大類(lèi)光涂，Collection集合的子接口有Set庞萍、 List、Queue三種子接口忘闻。我們比較常用的是Set钝计、List，Map接口不是 collection的子接口。

Collection集合主要有List和Set兩大接口

• List：一個(gè)有序（元素存入集合的順序和取出的順序一致）容器私恬，元素可以重 復(fù)债沮，可以插入多個(gè)null元素，元素都有索引本鸣。常用的實(shí)現(xiàn)類(lèi)有 ArrayList疫衩、LinkedList 和 Vector。
• Set：一個(gè)無(wú)序（存入和取出順序有可能不一致）容器荣德，不可以存儲(chǔ)重復(fù)元素闷煤， 只允許存入一個(gè)null元素，必須保證元素唯一性涮瞻。Set 接口常用實(shí)現(xiàn)類(lèi)是 HashSet鲤拿、 LinkedHashSet 以及 TreeSet。

Map是一個(gè)鍵值對(duì)集合署咽，存儲(chǔ)鍵近顷、值和之間的映射。 Key無(wú)序宁否，唯一窒升；value 不 要求有序，允許重復(fù)家淤。Map沒(méi)有繼承于Collection接口异剥，從Map集合中檢索元 素時(shí)，只要給出鍵對(duì)象絮重，就會(huì)返回對(duì)應(yīng)的值對(duì)象冤寿。

Map 的常用實(shí)現(xiàn)類(lèi)：HashMap、TreeMap青伤、HashTable督怜、LinkedHashMap、 ConcurrentHashMap

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

Collection

**List **

• Arraylist： Object數(shù)組
• Vector： Object數(shù)組
• LinkedList： 雙向循環(huán)鏈表

**Set **

• HashSet（無(wú)序狠角，唯一）：基于 HashMap 實(shí)現(xiàn)的号杠，底層采用 HashMap 來(lái)保存元素
• LinkedHashSet： LinkedHashSet 繼承與 HashSet，并且其內(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ū)別的。
• LinkedHashSet是Set集合的一個(gè)實(shí)現(xiàn)立帖，具有set集合不重復(fù)的特點(diǎn)眼溶，同時(shí)具有可預(yù)測(cè)的迭代順序，也就是我們插入的順序晓勇。并且linkedHashSet是一個(gè)非線(xiàn)程安全的集合堂飞。如果有多個(gè)線(xiàn)程同時(shí)訪(fǎng)問(wèn)當(dāng)前l(fā)inkedhashset集合容器灌旧，并且有一個(gè)線(xiàn)程對(duì)當(dāng)前容器中的元素做了修改，那么必須要在外部實(shí)現(xiàn)同步保證數(shù)據(jù)的冥等性
• TreeSet（有序绰筛，唯一）： 紅黑樹(shù)(自平衡的排序二叉樹(shù)枢泰。
• Map
• HashMap： JDK1.8之前HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主 體铝噩，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8以后
  在解決哈希沖突時(shí)有了較大的變化衡蚂，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(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ù)）

8.哪些集合類(lèi)是線(xiàn)程安全的？

• vector：就比arraylist多了個(gè)同步化機(jī)制（線(xiàn)程安全）衬横，因?yàn)樾瘦^低裹粤，現(xiàn)在已 經(jīng)不太建議使用。在web應(yīng)用中蜂林，特別是前臺(tái)頁(yè)面遥诉，往往效率（頁(yè)面響應(yīng)速度）是優(yōu) 先考慮的。
• statck：堆棧類(lèi)噪叙，先進(jìn)后出矮锈。
• hashtable：就比hashmap多了個(gè)線(xiàn)程安全。
• enumeration：枚舉睁蕾，相當(dāng)于迭代器苞笨。

9.Java集合的快速失敗機(jī)制 “fail-fast”？

是java集合的一種錯(cuò)誤檢測(cè)機(jī)制子眶，當(dāng)多個(gè)線(xiàn)程對(duì)集合進(jìn)行結(jié)構(gòu)上的改變的操作 時(shí)瀑凝，有可能會(huì)產(chǎn)生 fail-fast 機(jī)制。

例如：假設(shè)存在兩個(gè)線(xiàn)程（線(xiàn)程1臭杰、線(xiàn)程2）猜丹，線(xiàn)程1通過(guò)Iterator在遍歷集合A中 的元素，在某個(gè)時(shí)候線(xiàn)程2修改了集合A的結(jié)構(gòu)（是結(jié)構(gòu)上面的修改硅卢，而不是簡(jiǎn) 單的修改集合元素的內(nèi)容）射窒，那么這個(gè)時(shí)候程序就會(huì)拋出ConcurrentModificationException 異常，從而產(chǎn)生fail-fast機(jī)制将塑。

原因：迭代器在遍歷時(shí)直接訪(fǎng)問(wèn)集合中的內(nèi)容脉顿，并且在遍歷過(guò)程中使用一個(gè) modCount 變量。集合在被遍歷期間如果內(nèi)容發(fā)生變化点寥，就會(huì)改變modCount 的值艾疟。每當(dāng)?shù)魇褂胔ashNext()/next()遍歷下一個(gè)元素之前，都會(huì)檢測(cè) modCount變量是否為expectedmodCount值敢辩，是的話(huà)就返回遍歷蔽莱；否則拋出 異常，終止遍歷戚长。

解決辦法：

1. 在遍歷過(guò)程中盗冷，所有涉及到改變modCount值得地方全部加上 synchronized。
2. 使用CopyOnWriteArrayList來(lái)替換ArrayList

10.怎么確保一個(gè)集合不能被修改同廉？

可以使用 Collections. unmodifiableCollection(Collection c) 方法來(lái)創(chuàng)建一個(gè) 只讀集合仪糖，這樣改變集合的任何操作都會(huì)拋出 Java. lang. UnsupportedOperationException 異常。 示例代碼如下：

 List<String> list = new ArrayList<>(); 
 list. add("x"); 
 Collection<String> clist = Collections. unmodifiableCollection(list); 
 clist. add("y"); // 運(yùn)行時(shí)此行報(bào)錯(cuò) 
 System. out. println(list. size()); 

11.迭代器 Iterator 是什么迫肖？

Iterator 接口提供遍歷任何 Collection 的接口锅劝。我們可以從一個(gè) Collection 中使用迭代器方法來(lái)獲取迭代器實(shí)例。迭代器取代了 Java 集合框架中的 Enumeration蟆湖，迭代器允許調(diào)用者在迭代過(guò)程中移除元素故爵。

12.Iterator 怎么使用？有什么特點(diǎn)隅津？

Iterator 使用代碼如下：

1   List<String> list = new ArrayList
2   Iterator<String> it = list. iterator
3   while(it. hasNext()){
4   String obj = it. next();
5   System. out. println(obj);
6   }

Iterator 的特點(diǎn)是只能單向遍歷诬垂，但是更加安全，因?yàn)樗梢源_保饥瓷，在當(dāng)前遍歷的集合元素被更改的時(shí)候饿凛，就會(huì)拋出 ConcurrentModificationException 異常。

13.如何邊遍歷邊移除 Collection 中的元素鼎天？

邊遍歷邊修改 Collection 的唯一正確方式是使用 Iterator.remove() 方法罢防，如下：

1   Iterator<Integer> it = list.iterator();
2   while(it.hasNext()){
3   *// do something*
4   it.remove();5   
5   }

一種常見(jiàn)的錯(cuò)誤代碼如下：

1   for(Integer i : list){
2   list.remove(i)
3   }

運(yùn)行以上錯(cuò)誤代碼會(huì)報(bào) ConcurrentModificationException 異常。這是因?yàn)楫?dāng)使用 foreach(for(Integer i : list)) 語(yǔ)句時(shí)棺克，會(huì)自動(dòng)生成一個(gè)iterator 來(lái)遍歷該 list悠垛，但同時(shí)該 list 正在被 Iterator.remove() 修改。Java 一般不允許一個(gè)線(xiàn)程在遍歷 Collection 時(shí)另一個(gè)線(xiàn)程修改它娜谊。

14.Iterator 和 ListIterator 有什么區(qū)別确买？

• Iterator 可以遍歷 Set 和 List 集合，而 ListIterator 只能遍歷 List纱皆。
• Iterator 只能單向遍歷湾趾，而 ListIterator 可以雙向遍歷（向前/后遍歷）芭商。
• ListIterator 實(shí)現(xiàn) Iterator 接口，然后添加了一些額外的功能搀缠，比如添加一個(gè)元素铛楣、替換一個(gè)元素、獲取前面或后面元素的索引位置艺普。

15.遍歷一個(gè) List 有哪些不同的方式簸州？每種方法的實(shí)現(xiàn)原理是什么？Java 中 List 遍歷的最佳實(shí)踐是什么歧譬？

遍歷方式有以下幾種：

1. for 循環(huán)遍歷岸浑，基于計(jì)數(shù)器。在集合外部維護(hù)一個(gè)計(jì)數(shù)器瑰步，然后依次讀 取每一個(gè)位置的元素矢洲，當(dāng)讀取到后一個(gè)元素后停止。

2. 迭代器遍歷面氓，Iterator兵钮。Iterator 是面向?qū)ο蟮囊粋€(gè)設(shè)計(jì)模式，目的是屏 蔽不同數(shù)據(jù)集合的特點(diǎn)舌界，統(tǒng)一遍歷集合的接口掘譬。Java 在 Collections 中支 持了 Iterator 模式。

3. foreach 循環(huán)遍歷呻拌。foreach 內(nèi)部也是采用了 Iterator 的方式實(shí)現(xiàn)葱轩，使 用時(shí)不需要顯式聲明 Iterator 或計(jì)數(shù)器。優(yōu)點(diǎn)是代碼簡(jiǎn)潔藐握，不易出錯(cuò)靴拱；缺 點(diǎn)是只能做簡(jiǎn)單的遍歷，不能在遍歷過(guò)程中操作數(shù)據(jù)集合猾普，例如刪除袜炕、替 換。

最佳實(shí)踐：Java Collections 框架中提供了一個(gè) RandomAccess 接口初家，用來(lái)標(biāo) 記 List 實(shí)現(xiàn)是否支持 Random Access偎窘。

• 如果一個(gè)數(shù)據(jù)集合實(shí)現(xiàn)了該接口，就意味著它支持 Random Access溜在，按位置讀 取元素的平均時(shí)間復(fù)雜度為 O(1)陌知，如ArrayList。
• 如果沒(méi)有實(shí)現(xiàn)該接口掖肋，表示不支持 Random Access仆葡，如LinkedList。 推薦的做法就是志笼，支持 Random Access 的列表可用 for 循環(huán)遍歷沿盅，否則建議 用 Iterator 或 foreach 遍歷把篓。

16.說(shuō)一下 ArrayList 的優(yōu)缺點(diǎn)

ArrayList的優(yōu)點(diǎn)如下：

• ArrayList 底層以數(shù)組實(shí)現(xiàn)，是一種隨機(jī)訪(fǎng)問(wèn)模式嗡呼。ArrayList 實(shí)現(xiàn)了 RandomAccess 接口纸俭，因此查找的時(shí)候非常快南窗。
• ArrayList 在順序添加一個(gè)元素的時(shí)候非常方便。

ArrayList 的缺點(diǎn)如下：

• 刪除元素的時(shí)候郎楼，需要做一次元素復(fù)制操作万伤。如果要復(fù)制的元素很多，那么就會(huì)比較耗費(fèi)性能呜袁。
• 插入元素的時(shí)候敌买，也需要做一次元素復(fù)制操作，缺點(diǎn)同上阶界。

ArrayList 比較適合順序添加虹钮、隨機(jī)訪(fǎng)問(wèn)的場(chǎng)景。

17.如何實(shí)現(xiàn)數(shù)組和 List 之間的轉(zhuǎn)換膘融？

數(shù)組轉(zhuǎn) List：使用 Arrays. asList(array) 進(jìn)行轉(zhuǎn)換芙粱。

List 轉(zhuǎn)數(shù)組：使用 List 自帶的 toArray() 方法。代碼示例：

1   // list to array
2   List<String> list = new ArrayList<String>();
3   list.add("123");
4   list.add("456");
5   list.toArray();
6
7   // array to list
8   String[] array = new String[]{"123","456"};
9   Arrays.asList(array);

18.ArrayList 和 LinkedList 的區(qū)別是什么氧映？

• 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)：ArrayList 是動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)春畔，而 LinkedList 是雙向鏈表的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。
• 隨機(jī)訪(fǎng)問(wèn)效率：ArrayList 比 LinkedList 在隨機(jī)訪(fǎng)問(wèn)的時(shí)候效率要高岛都，因?yàn)?LinkedList 是線(xiàn)性的數(shù)據(jù)存儲(chǔ)方式律姨，所以需要移動(dòng)指針從前往后依次查找。
• 增加和刪除效率：在非首尾的增加和刪除操作臼疫，LinkedList 要比 ArrayList 效率要高择份，因?yàn)?ArrayList 增刪操作要影響數(shù)組內(nèi)的其他數(shù)據(jù)的下標(biāo)。
• 內(nèi)存空間占用：LinkedList 比 ArrayList 更占內(nèi)存烫堤，因?yàn)?LinkedList 的節(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)荣赶，還存儲(chǔ)了兩個(gè)引用，一個(gè)指向前一個(gè)元素塔逃，一個(gè)指向后一個(gè)元素讯壶。
• 線(xiàn)程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保證線(xiàn)程安全湾盗；

綜合來(lái)說(shuō)伏蚊，在需要頻繁讀取集合中的元素時(shí)，更推薦使用 ArrayList格粪，而在插入和刪除操作較多時(shí)躏吊，更推薦使用 LinkedList氛改。

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

雙向鏈表也叫雙鏈表，是鏈表的一種比伏，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針胜卤，分別指向直接后繼和直接前驅(qū)。所以赁项，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始葛躏，都可以很方便地訪(fǎng)問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。

19.ArrayList 和 Vector 的區(qū)別是什么悠菜？

這兩個(gè)類(lèi)都實(shí)現(xiàn)了 List 接口（List 接口繼承了 Collection 接口）舰攒，他們都是有序集合

線(xiàn)程安全：Vector 使用了 Synchronized 來(lái)實(shí)現(xiàn)線(xiàn)程同步，是線(xiàn)程安全的悔醋，而ArrayList 是非線(xiàn)程安全的摩窃。

性能：ArrayList 在性能方面要優(yōu)于 Vector。

擴(kuò)容：ArrayList 和 Vector 都會(huì)根據(jù)實(shí)際的需要?jiǎng)討B(tài)的調(diào)整容量芬骄，只不過(guò)在

Vector 擴(kuò)容每次會(huì)增加 1 倍猾愿，而 ArrayList 只會(huì)增加 50%。

Vector類(lèi)的所有方法都是同步的账阻〉倜兀可以由兩個(gè)線(xiàn)程安全地訪(fǎng)問(wèn)一個(gè)Vector對(duì)

象、但是一個(gè)線(xiàn)程訪(fǎng)問(wèn)Vector的話(huà)代碼要在同步操作上耗費(fèi)大量的時(shí)間宰僧。

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

20.插入數(shù)據(jù)時(shí)琴儿，ArrayList段化、LinkedList、Vector誰(shuí)速度較快造成？闡述 ArrayList显熏、Vector、LinkedList 的存儲(chǔ)性能和特性晒屎？

ArrayList喘蟆、LinkedList、Vector 底層的實(shí)現(xiàn)都是使用數(shù)組方式存儲(chǔ)數(shù)據(jù)鼓鲁。數(shù)組

元素?cái)?shù)大于實(shí)際存儲(chǔ)的數(shù)據(jù)以便增加和插入元素蕴轨，它們都允許直接按序號(hào)索引元素，但是插入元素要涉及數(shù)組元素移動(dòng)等內(nèi)存操作骇吭，所以索引數(shù)據(jù)快而插入數(shù)據(jù)慢橙弱。

Vector 中的方法由于加了 synchronized 修飾，因此 Vector是線(xiàn)程安全容器，但性能上較ArrayList差棘脐。

LinkedList 使用雙向鏈表實(shí)現(xiàn)存儲(chǔ)斜筐，按序號(hào)索引數(shù)據(jù)需要進(jìn)行前向或后向遍歷，但插入數(shù)據(jù)時(shí)只需要記錄當(dāng)前項(xiàng)的前后項(xiàng)即可蛀缝，所以 LinkedList插入速度較快顷链。

21.多線(xiàn)程場(chǎng)景下如何使用 ArrayList？

ArrayList 不是線(xiàn)程安全的屈梁，如果遇到多線(xiàn)程場(chǎng)景嗤练，可以通過(guò) Collections 的

synchronizedList 方法將其轉(zhuǎn)換成線(xiàn)程安全的容器后再使用。例如像下面這樣：

22.多線(xiàn)程場(chǎng)景下如何使用 ArrayList俘闯？

ArrayList 不是線(xiàn)程安全的潭苞，如果遇到多線(xiàn)程場(chǎng)景，可以通過(guò) Collections 的

synchronizedList 方法將其轉(zhuǎn)換成線(xiàn)程安全的容器后再使用真朗。例如像下面這樣：

2   synchronizedList.add("aaa");
3   synchronizedList.add("bbb");
4
5   for (int i = 0; i < synchronizedList.size(); i++) {
6   System.out.println(synchronizedList.get(i));
7   }

23.為什么 ArrayList 的 elementData 加上 transient 修飾？ ArrayList 中的數(shù)組定義如下：

private transient Object[] elementData;

再看一下 ArrayList 的定義：

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

可以看到 ArrayList 實(shí)現(xiàn)了 Serializable 接口僧诚，這意味著 ArrayList 支持序列化遮婶。transient 的作用是說(shuō)不希望 elementData 數(shù)組被序列化，重寫(xiě)了writeObject 實(shí)現(xiàn)：

1 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOE xception{ 
2  *// Write out element count, and any hidden stuff* 
3  int expectedModCount = modCount; 
4  s.defaultWriteObject(); 
5  *// Write out array length* 
6  s.writeInt(elementData.length); 
7  *// Write out all elements in the proper order.* 
8  for (int i=0; i<size; i++) 
9  s.writeObject(elementData[i]); 
10  if (modCount != expectedModCount) { 
11  throw new ConcurrentModificationException();
12 }

每次序列化時(shí)湖笨，先調(diào)用 defaultWriteObject() 方法序列化 ArrayList 中的非transient 元素旗扑，然后遍歷 elementData，只序列化已存入的元素慈省，這樣既加快了序列化的速度臀防，又減小了序列化之后的文件大小。

24.List 和 Set 的區(qū)別

List , Set 都是繼承自Collection 接口

List 特點(diǎn)：一個(gè)有序（元素存入集合的順序和取出的順序一致）容器边败，元素可以重復(fù)袱衷，可以插入多個(gè)null元素，元素都有索引笑窜。常用的實(shí)現(xiàn)類(lèi)有 ArrayList致燥、

LinkedList 和 Vector。

Set 特點(diǎn)：一個(gè)無(wú)序（存入和取出順序有可能不一致）容器排截，不可以存儲(chǔ)重復(fù)元素嫌蚤，只允許存入一個(gè)null元素，必須保證元素唯一性断傲。Set 接口常用實(shí)現(xiàn)類(lèi)是

HashSet脱吱、LinkedHashSet 以及 TreeSet。

另外 List 支持for循環(huán)认罩，也就是通過(guò)下標(biāo)來(lái)遍歷箱蝠，也可以用迭代器，但是set只能用迭代，因?yàn)樗麩o(wú)序抡锈，無(wú)法用下標(biāo)來(lái)取得想要的值疾忍。

Set和List對(duì)比

Set：檢索元素效率低下，刪除和插入效率高床三，插入和刪除不會(huì)引起元素位置改變一罩。

List：和數(shù)組類(lèi)似，List可以動(dòng)態(tài)增長(zhǎng)撇簿，查找元素效率高聂渊，插入刪除元素效率低，因?yàn)闀?huì)引起其他元素位置改變

25.說(shuō)一下 HashSet 的實(shí)現(xiàn)原理四瘫？

HashSet 是基于 HashMap 實(shí)現(xiàn)的汉嗽，HashSet的值存放于HashMap的key上，

HashMap的value統(tǒng)一為PRESENT找蜜，因此 HashSet 的實(shí)現(xiàn)比較簡(jiǎn)單饼暑，相關(guān) HashSet 的操作，基本上都是直接調(diào)用底層 HashMap 的相關(guān)方法來(lái)完成洗做，

HashSet 不允許重復(fù)的值弓叛。

26.HashSet如何檢查重復(fù)？HashSet是如何保證數(shù)據(jù)不可重復(fù)的诚纸？

向HashSet 中add ()元素時(shí)撰筷，判斷元素是否存在的依據(jù)，不僅要比較hash值畦徘，同時(shí)還要結(jié)合equles 方法比較毕籽。

HashSet 中的add ()方法會(huì)使用HashMap 的put()方法。

HashMap 的 key 是唯一的井辆，由源碼可以看出 HashSet 添加進(jìn)去的值就是作為 HashMap 的key关筒，并且在HashMap中如果K/V相同時(shí)，會(huì)用新的V覆蓋掉舊的V掘剪，然后返回舊的V平委。所以不會(huì)重復(fù)（ HashMap 比較key是否相等是先比較 hashcode 再比較equals ）。

以下是HashSet 部分源碼：

1   private static final Object PRESENT = new Object();
2   private transient HashMap<E,Object> map;
3
4   public HashSet() {
<>
5   map = new HashMap ();
6   }
7
8   public boolean add(E e) {
9   // 調(diào)用HashMap的put方法,PRESENT是一個(gè)至始至終都相同的虛值
10  return map.put(e, PRESENT)==null;
11  }

hashCode（）與equals（）的相關(guān)規(guī)定：

1. 如果兩個(gè)對(duì)象相等夺谁，則hashcode一定也是相同的

2. 兩個(gè)對(duì)象相等,對(duì)兩個(gè)equals方法返回true

3. 兩個(gè)對(duì)象有相同的hashcode值廉赔，它們也不一定是相等的

4. 綜上，equals方法被覆蓋過(guò)匾鸥，則hashCode方法也必須被覆蓋

5. hashCode()的默認(rèn)行為是對(duì)堆上的對(duì)象產(chǎn)生獨(dú)特值蜡塌。如果沒(méi)有重寫(xiě)hashCode()，則該class的兩個(gè)對(duì)象無(wú)論如何都不會(huì)相等（即使這兩個(gè)對(duì)象指向相同的數(shù)據(jù)）勿负。

==與equals的區(qū)別

1. ==是判斷兩個(gè)變量或?qū)嵗遣皇侵赶蛲粋€(gè)內(nèi)存空間 equals是判斷兩個(gè)變量或?qū)嵗赶虻膬?nèi)存空間的值是不是相同

2. ==是指對(duì)內(nèi)存地址進(jìn)行比較 equals()是對(duì)字符串的內(nèi)容進(jìn)行比較3.== 指引用是否相同 equals()指的是值是否相同

27.HashSet與HashMap的區(qū)別

28.BlockingQueue是什么？

Java.util.concurrent.BlockingQueue是一個(gè)隊(duì)列房资，在進(jìn)行檢索或移除一個(gè)元素的時(shí)候蜕劝，它會(huì)等待隊(duì)列變?yōu)榉强眨划?dāng)在添加一個(gè)元素時(shí)轰异，它會(huì)等待隊(duì)列中的可用空間岖沛。BlockingQueue接口是Java集合框架的一部分，主要用于實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者模式搭独。我們不需要擔(dān)心等待生產(chǎn)者有可用的空間婴削，或消費(fèi)者有可用的對(duì)象，因?yàn)樗荚贐lockingQueue的實(shí)現(xiàn)類(lèi)中被處理了牙肝。Java提供了集中 BlockingQueue的實(shí)現(xiàn)唉俗，比如ArrayBlockingQueue、

LinkedBlockingQueue配椭、PriorityBlockingQueue,互躬、SynchronousQueue等。在 Queue 中 poll()和 remove()有什么區(qū)別颂郎？

• 相同點(diǎn)：都是返回第一個(gè)元素，并在隊(duì)列中刪除返回的對(duì)象容为。
• 不同點(diǎn)：如果沒(méi)有元素 poll()會(huì)返回 null乓序，而 remove()會(huì)直接拋出 NoSuchElementException 異常。

代碼示例：

1   Queue<String> queue = new LinkedList<String>();
2   queue. offer("string"); // add
3   System. out. println(queue. poll());
4   System. out. println(queue. remove());
5   System. out. println(queue. size());

29.說(shuō)一下 HashMap 的實(shí)現(xiàn)原理坎背？

HashMap概述： HashMap是基于哈希表的Map接口的非同步實(shí)現(xiàn)替劈。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵得滤。此類(lèi)不保證映射的順序陨献，特別是它不保證該順序恒久不變。

HashMap的數(shù)據(jù)結(jié)構(gòu)： 在Java編程語(yǔ)言中懂更， 基本的結(jié)構(gòu)就是兩種眨业，一個(gè)是數(shù)組，另外一個(gè)是模擬指針（引用）沮协，所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個(gè)基本結(jié)構(gòu)來(lái)構(gòu)造的龄捡，HashMap也不例外。HashMap實(shí)際上是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)慷暂，即數(shù)組和鏈表的結(jié)合體聘殖。

HashMap 基于 Hash 算法實(shí)現(xiàn)的

1. 當(dāng)我們往Hashmap中put元素時(shí)，利用key的hashCode重新hash計(jì)算出當(dāng)前對(duì)象的元素在數(shù)組中的下標(biāo)

2. 存儲(chǔ)時(shí)，如果出現(xiàn)hash值相同的key奸腺，此時(shí)有兩種情況餐禁。(1)如果key相

同，則覆蓋原始值突照；(2)如果key不同（出現(xiàn)沖突）帮非，則將當(dāng)前的key-value 放入鏈表中

3. 獲取時(shí)，直接找到hash值對(duì)應(yīng)的下標(biāo)绷旗，在進(jìn)一步判斷key是否相同喜鼓，從而找到對(duì)應(yīng)值。

4. 理解了以上過(guò)程就不難明白HashMap是如何解決hash沖突的問(wèn)題衔肢，核心就是使用了數(shù)組的存儲(chǔ)方式庄岖，然后將沖突的key的對(duì)象放入鏈表中，一旦發(fā)現(xiàn)沖突就在鏈表中做進(jìn)一步的對(duì)比角骤。

需要注意Jdk 1.8中對(duì)HashMap的實(shí)現(xiàn)做了優(yōu)化隅忿，當(dāng)鏈表中的節(jié)點(diǎn)數(shù)據(jù)超過(guò)八個(gè)之后，該鏈表會(huì)轉(zhuǎn)為紅黑樹(shù)來(lái)提高查詢(xún)效率邦尊，從原來(lái)的O(n)到O(logn)

30.HashMap在JDK1.7和JDK1.8中有哪些不同背桐？ HashMap的底層實(shí)現(xiàn)

在Java中，保存數(shù)據(jù)有兩種比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)：數(shù)組和鏈表蝉揍。數(shù)組的特點(diǎn)是：尋址容易链峭，插入和刪除困難；鏈表的特點(diǎn)是：尋址困難又沾，但插入和刪除容易弊仪；所以我們將數(shù)組和鏈表結(jié)合在一起，發(fā)揮兩者各自的優(yōu)勢(shì)杖刷，使用一種叫做拉鏈法的方式可以解決哈希沖突励饵。

JDK1.8之前

JDK1.8之前采用的是拉鏈法。拉鏈法：將鏈表和數(shù)組相結(jié)合滑燃。也就是說(shuō)創(chuàng)建一個(gè)鏈表數(shù)組瓦糕，數(shù)組中每一格就是一個(gè)鏈表羔砾。若遇到哈希沖突尊浪，則將沖突的值加到鏈表中即可堕油。

JDK1.8之后

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

JDK1.7 VS JDK1.8 比較

JDK1.8主要解決或優(yōu)化了一下問(wèn)題：

1. resize 擴(kuò)容優(yōu)化

2. 引入了紅黑樹(shù)孽椰，目的是避免單條鏈表過(guò)長(zhǎng)而影響查詢(xún)效率昭娩，紅黑樹(shù)算法請(qǐng)參考

3. 解決了多線(xiàn)程死循環(huán)問(wèn)題，但仍是非線(xiàn)程安全的黍匾，多線(xiàn)程時(shí)可能會(huì)造成數(shù)據(jù)丟失問(wèn)題栏渺。

   
   
   image.png

31.HashMap的put方法的具體流程？

當(dāng)我們put的時(shí)候锐涯，首先計(jì)算 key的hash值磕诊，這里調(diào)用了 hash方法，hash方法實(shí)際是讓key.hashCode()與key.hashCode()>>>16進(jìn)行異或操作纹腌，高16bit補(bǔ)0霎终，一個(gè)數(shù)和0異或不變，所以 hash 函數(shù)大概的作用就是：高16bit不變升薯，低16bit和高

16bit做了一個(gè)異或莱褒，目的是減少碰撞。按照函數(shù)注釋?zhuān)驗(yàn)閎ucket數(shù)組大小是2的冪涎劈，計(jì)算下標(biāo)index = (table.length - 1) & hash广凸，如果不做 hash 處理，相當(dāng)于散列生效的只有幾個(gè)低 bit 位蛛枚，為了減少散列的碰撞谅海，設(shè)計(jì)者綜合考慮了速度、作用蹦浦、質(zhì)量之后扭吁，使用高16bit和低16bit異或來(lái)簡(jiǎn)單處理減少碰撞，而且

JDK8中用了復(fù)雜度 O（logn）的樹(shù)結(jié)構(gòu)來(lái)提升碰撞下的性能盲镶。

putVal方法執(zhí)行流程圖
①.判斷鍵值對(duì)數(shù)組table[i]是否為空或?yàn)閚ull智末，否則執(zhí)行resize()進(jìn)行擴(kuò)容；

②.根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i徒河，如果table[i]==null，直接新建節(jié)點(diǎn)添加送漠，轉(zhuǎn)向⑥顽照，如果table[i]不為空，轉(zhuǎn)向③闽寡；

③.判斷table[i]的首個(gè)元素是否和key一樣代兵，如果相同直接覆蓋value，否則轉(zhuǎn)向

④爷狈，這里的相同指的是hashCode以及equals植影；

④.判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹(shù)涎永，如果是紅黑樹(shù)思币，則直接在樹(shù)中插入鍵值對(duì)鹿响，否則轉(zhuǎn)向⑤；

⑤.遍歷table[i]谷饿，判斷鏈表長(zhǎng)度是否大于8惶我，大于8的話(huà)把鏈表轉(zhuǎn)換為紅黑樹(shù)，在紅黑樹(shù)中執(zhí)行插入操作博投，否則進(jìn)行鏈表的插入操作绸贡；遍歷過(guò)程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可；

⑥.插入成功后毅哗，判斷實(shí)際存在的鍵值對(duì)數(shù)量size是否超多了 大容量threshold听怕，如果超過(guò)，進(jìn)行擴(kuò)容虑绵。

32.HashMap的擴(kuò)容操作是怎么實(shí)現(xiàn)的尿瞭？

①.在jdk1.8中，resize方法是在hashmap中的鍵值對(duì)大于閥值時(shí)或者初始化時(shí)蒸殿，就調(diào)用resize方法進(jìn)行擴(kuò)容筷厘；

②.每次擴(kuò)展的時(shí)候，都是擴(kuò)展2倍宏所；

③.擴(kuò)展后Node對(duì)象的位置要么在原位置酥艳，要么移動(dòng)到原偏移量?jī)杀兜奈恢谩Ｔ趐utVal()中爬骤，我們看到在這個(gè)函數(shù)里面使用到了2次resize()方法充石，resize()方法表示的在進(jìn)行第一次初始化時(shí)會(huì)對(duì)其進(jìn)行擴(kuò)容，或者當(dāng)該數(shù)組的實(shí)際大小大于其臨界值值(第一次為12),這個(gè)時(shí)候在擴(kuò)容的同時(shí)也會(huì)伴隨的桶上面的元素進(jìn)行重新分發(fā)霞玄，這也是JDK1.8版本的一個(gè)優(yōu)化的地方骤铃，在1.7中，擴(kuò)容之后需要重新去計(jì)算其Hash值坷剧，根據(jù)Hash值對(duì)其進(jìn)行分發(fā)惰爬，但在1.8版本中，則是根據(jù)在同一個(gè)桶的位置中進(jìn)行判斷(e.hash & oldCap)是否為0惫企，重新進(jìn)行hash分配后撕瞧，該元素的位置要么停留在原始位置，要么移動(dòng)到原始位置+增加的數(shù)組大小這個(gè)位置上

33.HashMap是怎么解決哈希沖突的狞尔？

答：在解決這個(gè)問(wèn)題之前丛版，我們首先需要知道什么是哈希沖突，而在了解哈希沖突之前我們還要知道什么是哈希才行偏序；什么是哈希页畦？

Hash，一般翻譯為“散列”研儒，也有直接音譯為“哈显ビВ”的独令，這就是把任意長(zhǎng)度的輸入通過(guò)散列算法，變換成固定長(zhǎng)度的輸出州胳，該輸出就是散列值（哈希值）记焊；這種轉(zhuǎn)換是一種壓縮映射，也就是栓撞，散列值的空間通常遠(yuǎn)小于輸入的空間遍膜，不同的輸入可能會(huì)散列成相同的輸出，所以不可能從散列值來(lái)唯一的確定輸入值瓤湘。簡(jiǎn)單的說(shuō)就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)瓢颅。

所有散列函數(shù)都有如下一個(gè)基本特性：根據(jù)同一散列函數(shù)計(jì)算出的散列值如果不同，那么輸入值肯定也不同弛说。但是挽懦，根據(jù)同一散列函數(shù)計(jì)算出的散列值如果相同，輸入值不一定相同木人。

什么是哈希沖突信柿？

當(dāng)兩個(gè)不同的輸入值，根據(jù)同一散列函數(shù)計(jì)算出相同的散列值的現(xiàn)象醒第，我們就把它叫做碰撞（哈希碰撞）渔嚷。

HashMap的數(shù)據(jù)結(jié)構(gòu)

在Java中，保存數(shù)據(jù)有兩種比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)：數(shù)組和鏈表稠曼。數(shù)組的特點(diǎn)是：尋址容易形病，插入和刪除困難；鏈表的特點(diǎn)是：尋址困難霞幅，但插入和刪除容易漠吻；所以我們將數(shù)組和鏈表結(jié)合在一起，發(fā)揮兩者各自的優(yōu)勢(shì)司恳，使用一種叫做鏈地址法的方式可以解決哈希沖突：
這樣我們就可以將擁有相同哈希值的對(duì)象(img)組織成一個(gè)鏈表放在hash值所對(duì)應(yīng)的 bucket下途乃，但相比于hashCode返回的int類(lèi)型，我們HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要遠(yuǎn)小于int類(lèi)型的范圍扔傅，所以我們?nèi)绻皇菃渭兊挠胔ashCode取余來(lái)獲取對(duì)應(yīng)的bucket這將會(huì)大大增加哈希碰撞的概率欺劳，并且最壞情況下還會(huì)將HashMap變成一個(gè)單鏈表，所以我們還需要對(duì)hashCode作一定的優(yōu)化 hash()函數(shù)

上面提到的問(wèn)題铅鲤，主要是因?yàn)槿绻褂胔ashCode取余，那么相當(dāng)于參與運(yùn)算的只有hashCode的低位枫弟，高位是沒(méi)有起到任何作用的邢享，所以我們的思路就是讓 hashCode取值出的高位也參與運(yùn)算，進(jìn)一步降低hash
碰撞的概率淡诗，使得數(shù)據(jù)分布更平均骇塘，我們把這樣的操作稱(chēng)為擾動(dòng)伊履，在JDK 1.8中的hash()函數(shù)如下：
這比在JDK 1.7中，更為簡(jiǎn)潔款违，相比在1.7中的4次位運(yùn)算唐瀑，5次異或運(yùn)算（9次擾動(dòng)），在1.8中插爹，只進(jìn)行了1次位運(yùn)算和1次異或運(yùn)算（2次擾動(dòng)）哄辣；

34.能否使用任何類(lèi)作為 Map 的 key？

可以使用任何類(lèi)作為 Map 的 key赠尾，然而在使用之前力穗，需要考慮以下幾點(diǎn)： 如果類(lèi)重寫(xiě)了 equals() 方法，也應(yīng)該重寫(xiě) hashCode() 方法气嫁。類(lèi)的所有實(shí)例需要遵循與 equals() 和 hashCode() 相關(guān)的規(guī)則当窗。

如果一個(gè)類(lèi)沒(méi)有使用 equals()，不應(yīng)該在 hashCode() 中使用它寸宵。

用戶(hù)自定義 Key 類(lèi) 佳實(shí)踐是使之為不可變的崖面，這樣 hashCode() 值可以被緩存起來(lái)，擁有更好的性能梯影。不可變的類(lèi)也可以確保 hashCode() 和 equals() 在未來(lái)不會(huì)改變巫员，這樣就會(huì)解決與可變相關(guān)的問(wèn)題了。

35.為什么HashMap中String光酣、Integer這樣的包裝類(lèi)適合作為K疏遏？

答：String、Integer等包裝類(lèi)的特性能夠保證Hash值的不可更改性和計(jì)算準(zhǔn)確性救军，能夠有效的減少Hash碰撞的幾率

1. 都是final類(lèi)型财异，即不可變性，保證key的不可更改性唱遭，不會(huì)存在獲取 hash值不同的情況

內(nèi)部已重寫(xiě)了equals()戳寸、hashCode()等方法，遵守了HashMap內(nèi)部的規(guī)范（不清楚可以去上面看看putValue的過(guò)程）拷泽，不容易出現(xiàn)Hash值計(jì)算錯(cuò)誤的情況）

36.如果使用Object作為HashMap的Key疫鹊，應(yīng)該怎么辦呢？

答：重寫(xiě)hashCode()和equals()方法

1. 重寫(xiě)hashCode()是因?yàn)樾枰?jì)算存儲(chǔ)數(shù)據(jù)的存儲(chǔ)位置司致，需要注意不要試圖從散列碼計(jì)算中排除掉一個(gè)對(duì)象的關(guān)鍵部分來(lái)提高性能拆吆，這樣雖然能更快但可能會(huì)導(dǎo)致更多的Hash碰撞；

2. 重寫(xiě)equals()方法脂矫，需要遵守自反性枣耀、對(duì)稱(chēng)性、傳遞性庭再、一致性以及對(duì)于任何非null的引用值x捞奕，x.equals(null)必須返回false的這幾個(gè)特性牺堰，目的是為了保證key在哈希表中的唯一性

37.HashMap為什么不直接使用hashCode()處理后的哈希 值直接作為table的下標(biāo)？

答：hashCode()方法返回的是int整數(shù)類(lèi)型颅围，其范圍為-(2 ^ 31)~(2 ^ 31 - 1)伟葫，約有40億個(gè)映射空間，而HashMap的容量范圍是在16（初始化默認(rèn)值）~2 ^ 30院促，HashMap通常情況下是取不到 大值的筏养，并且設(shè)備上也難以提供這么多的存儲(chǔ)空間，從而導(dǎo)致通過(guò)hashCode()計(jì)算出的哈希值可能不在數(shù)組大小范圍內(nèi)一疯，進(jìn)而無(wú)法匹配存儲(chǔ)位置撼玄；

那怎么解決呢？

1. HashMap自己實(shí)現(xiàn)了自己的hash()方法墩邀，通過(guò)兩次擾動(dòng)使得它自己的哈希值高低位自行進(jìn)行異或運(yùn)算掌猛，降低哈希碰撞概率也使得數(shù)據(jù)分布更平均；

2. 在保證數(shù)組長(zhǎng)度為2的冪次方的時(shí)候眉睹，使用hash()運(yùn)算之后的值與運(yùn)算

（&）（數(shù)組長(zhǎng)度 - 1）來(lái)獲取數(shù)組下標(biāo)的方式進(jìn)行存儲(chǔ)荔茬，這樣一來(lái)是比取

余操作更加有效率，二來(lái)也是因?yàn)橹挥挟?dāng)數(shù)組長(zhǎng)度為2的冪次方時(shí)竹海，h&

(length-1)才等價(jià)于h%length慕蔚，三來(lái)解決了“哈希值與數(shù)組大小范圍不匹配"的問(wèn)題

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

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

這個(gè)算法應(yīng)該如何設(shè)計(jì)呢坏瞄？我們首先可能會(huì)想到采用%取余的操作來(lái)實(shí)現(xiàn)。但是甩卓，重點(diǎn)來(lái)了：“取余(%)操作中如果除數(shù)是2的冪次則等價(jià)于與其除數(shù)減一的與(&)操作（也就是說(shuō) hash%length==hash&(length-1)的前提是 length 是2的 n 次方鸠匀；）∮馐粒” 并且 采用二進(jìn)制位操作 &缀棍，相對(duì)于%能夠提高運(yùn)算效率，這就解釋了 HashMap 的長(zhǎng)度為什么是2的冪次方机错。

那為什么是兩次擾動(dòng)呢爬范？答：這樣就是加大哈希值低位的隨機(jī)性，使得分布更均勻弱匪，從而提高對(duì)應(yīng)數(shù)組存儲(chǔ)下標(biāo)位置的隨機(jī)性&均勻性青瀑， 終減少Hash沖突，兩次就夠了，已經(jīng)達(dá)到了高位低位同時(shí)參與運(yùn)算的目的狱窘。

39.HashMap 與 HashTable 有什么區(qū)別？

1. 線(xiàn)程安全： HashMap 是非線(xiàn)程安全的财搁，HashTable 是線(xiàn)程安全的蘸炸；

HashTable 內(nèi)部的方法基本都經(jīng)過(guò) synchronized 修飾。（如果你要保證線(xiàn)程安全的話(huà)就使用 ConcurrentHashMap 吧＜獗肌）搭儒；

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

3. 對(duì)Null key 和Null value的支持： HashMap 中铃岔，null 可以作為鍵，這樣的鍵只有一個(gè)峭火，可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為 null毁习。但是在

HashTable 中 put 進(jìn)的鍵值只要有一個(gè) null，直接拋NullPointerException卖丸。

4. **初始容量大小和每次擴(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的冪次方大小裳仆。也就是說(shuō) HashMap 總是使用2的冪作為哈希表的大小，后面會(huì)介紹到為什么是2 的冪次方孤钦。

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

6. 推薦使用：在 Hashtable 的類(lèi)注釋可以看到俊扭，Hashtable 是保留類(lèi)不建議使用队橙，推薦在單線(xiàn)程環(huán)境下使用 HashMap 替代，如果需要多線(xiàn)程使用則用 ConcurrentHashMap 替代。

40.如何決定使用 HashMap 還是TreeMap捐康？

對(duì)于在Map中插入仇矾、刪除和定位元素這類(lèi)操作，HashMap是 好的選擇解总。然而贮匕，假如你需要對(duì)一個(gè)有序的key集合進(jìn)行遍歷，TreeMap是更好的選擇花枫】萄危基于你的collection的大小，也許向HashMap中添加元素會(huì)更快劳翰，將map換為T(mén)reeMap進(jìn)行有序key的遍歷敦锌。

41.HashMap 和 ConcurrentHashMap 的區(qū)別

1. ConcurrentHashMap對(duì)整個(gè)桶數(shù)組進(jìn)行了分割分段(Segment)，然后在每一個(gè)分段上都用lock鎖進(jìn)行保護(hù)佳簸，相對(duì)于HashTable的synchronized 鎖的粒度更精細(xì)了一些乙墙，并發(fā)性能更好，而HashMap沒(méi)有鎖機(jī)制溺蕉，不是線(xiàn)程安全的伶丐。（JDK1.8之后ConcurrentHashMap啟了一種全新的方式實(shí)現(xiàn),利用CAS算法。）

2. HashMap的鍵值對(duì)允許有null疯特，但是ConCurrentHashMap都不允許哗魂。

42.ConcurrentHashMap 和 Hashtable 的區(qū)別？

ConcurrentHashMap 和 Hashtable 的區(qū)別主要體現(xiàn)在實(shí)現(xiàn)線(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ù)組+鏈表/紅黑

二叉樹(shù)邻吞。Hashtable 和 JDK1.8 之前的 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)類(lèi)似都是采用 數(shù)組+鏈表 的形式组题，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的抱冷；

實(shí)現(xiàn)線(xiàn)程安全的方式（重要）： ① 在JDK1.7的時(shí)候崔列，

ConcurrentHashMap（分段鎖） 對(duì)整個(gè)桶數(shù)組進(jìn)行了分割分段(Segment)，每一把鎖只鎖容器其中一部分?jǐn)?shù)據(jù)旺遮，多線(xiàn)程訪(fǎng)問(wèn)容器里不同數(shù)據(jù)段的數(shù)據(jù)赵讯，就不會(huì)存在鎖競(jìng)爭(zhēng)，提高并發(fā)訪(fǎng)問(wèn)率耿眉。（默認(rèn)分配16個(gè)Segment圆雁，比Hashtable效率提高16倍齐遵。）

到了 JDK1.8 的時(shí)候已經(jīng)摒棄了Segment的概念，而是直接用

Node 數(shù)組+鏈表+紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)营罢，并發(fā)控制使用

synchronized 和 CAS 來(lái)操作戈稿。（JDK1.6以后 對(duì) synchronized鎖做了很多優(yōu)化） 整個(gè)看起來(lái)就像是優(yōu)化過(guò)且線(xiàn)程安全的 HashMap，雖然在JDK1.8中還

能看到 Segment 的數(shù)據(jù)結(jié)構(gòu)，但是已經(jīng)簡(jiǎn)化了屬性，只是為了兼容舊版本江滨；②

Hashtable(同一把鎖) :使用 synchronized 來(lái)保證線(xiàn)程安全，效率非常低下厌均。當(dāng)一個(gè)線(xiàn)程訪(fǎng)問(wèn)同步方法時(shí)牙寞，其他線(xiàn)程也訪(fǎng)問(wèn)同步方法，可能會(huì)進(jìn)入阻塞或輪詢(xún)狀態(tài)莫秆，如使用 put 添加元素，另一個(gè)線(xiàn)程不能使用 put 添加元素悔详，也不能使用 get镊屎，競(jìng)爭(zhēng)會(huì)越來(lái)越激烈效率越低。

兩者的對(duì)比圖：

HashTable:

image-20201109165808848.png

JDK1.7的ConcurrentHashMap：

image-20201109165820466.png

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

image-20201109165840129.png

43.ConcurrentHashMap 底層具體實(shí)現(xiàn)知道嗎？實(shí)現(xiàn)原理是什么拼弃？

JDK1.7

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

在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式進(jìn)行實(shí)

現(xiàn)盯孙，結(jié)構(gòu)如下：

一個(gè) ConcurrentHashMap 里包含一個(gè) Segment 數(shù)組鲁森。Segment 的結(jié)構(gòu)和 HashMap類(lèi)似，是一種數(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的鎖。

1. 該類(lèi)包含兩個(gè)靜態(tài)內(nèi)部類(lèi) HashE(img)ntry 和 Segment 透罢；前者用來(lái)封裝映射表的鍵值對(duì)榜晦，后者用來(lái)充當(dāng)鎖的角色；

2. Segment 是一種可重入的鎖 ReentrantLock羽圃，每個(gè) Segment 守護(hù)一個(gè)HashEntry 數(shù)組里得元素乾胶，當(dāng)對(duì) HashEntry 數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)抖剿，必須首先獲得對(duì)應(yīng)的 Segment 鎖。

JDK1.8

在JDK1.8中识窿，放棄了Segment臃腫的設(shè)計(jì)斩郎，取而代之的是采用Node + CAS + Synchronized來(lái)保證并發(fā)安全進(jìn)行實(shí)現(xiàn)，synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹(shù)的首節(jié)點(diǎn)喻频，這樣只要hash不沖突缩宜，就不會(huì)產(chǎn)生并發(fā)，效率又提升N 倍甥温。

44.Array 和 ArrayList 有何區(qū)別锻煌？

• Array 可以存儲(chǔ)基本數(shù)據(jù)類(lèi)型和對(duì)象，ArrayList 只能存儲(chǔ)對(duì)象姻蚓。
• Array 是指定固定大小的宋梧，而 ArrayList 大小是自動(dòng)擴(kuò)展的。
• Array 內(nèi)置方法沒(méi)有 ArrayList 多狰挡，比如 addAll捂龄、removeAll、iteration 等方法只有 ArrayList 有加叁。

對(duì)于基本類(lèi)型數(shù)據(jù)倦沧，集合使用自動(dòng)裝箱來(lái)減少編碼工作量。但是它匕，當(dāng)處理固定大小的基本數(shù)據(jù)類(lèi)型的時(shí)候展融，這種方式相對(duì)比較慢。

如何實(shí)現(xiàn) Array 和 List 之間的轉(zhuǎn)換豫柬？

• Array 轉(zhuǎn) List： Arrays. asList(array) 愈污；
• List 轉(zhuǎn) Array：List 的 toArray() 方法。

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)排序

一般我們需要對(duì)一個(gè)集合使用自定義排序時(shí)创夜，我們就要重寫(xiě)compareTo方法或 compare方法杭跪，當(dāng)我們需要對(duì)某一個(gè)集合實(shí)現(xiàn)兩種排序方式，比如一個(gè)song對(duì)象中的歌名和歌手名分別采用一種排序方法的話(huà)驰吓，我們可以重寫(xiě)compareTo方法和使用自制的Comparator方法或者以?xún)蓚€(gè)Comparator來(lái)實(shí)現(xiàn)歌名排序和歌星名排序涧尿，第二種代表我們只能使用兩個(gè)參數(shù)版的Collections.sort().

Collection 和 Collections 有什么區(qū)別？

• java.util.Collection 是一個(gè)集合接口（集合類(lèi)的一個(gè)頂級(jí)接口）檬贰。它提供了對(duì)集合對(duì)象進(jìn)行基本操作的通用接口方法姑廉。Collection接口在Java 類(lèi)庫(kù)中有很多具體的實(shí)現(xiàn)。Collection接口的意義是為各種具體的集合提供了大化的統(tǒng)一操作方式翁涤，其直接繼承接口有List與Set桥言。
• Collections則是集合類(lèi)的一個(gè)工具類(lèi)/幫助類(lèi)萌踱，其中提供了一系列靜態(tài)方法，用于對(duì)集合中元素進(jìn)行排序号阿、搜索以及線(xiàn)程安全等各種操作并鸵。

45.TreeMap 和 TreeSet 在排序時(shí)如何比較元素？ Collections 工具類(lèi)中的 sort()方法如何比較元素扔涧？

TreeSet 要求存放的對(duì)象所屬的類(lèi)必須實(shí)現(xiàn) Comparable 接口园担，該接口提供了比較元素的 compareTo()方法，當(dāng)插入元素時(shí)會(huì)回調(diào)該方法比較元素的大小枯夜。

TreeMap 要求存放的鍵值對(duì)映射的鍵必須實(shí)現(xiàn) Comparable 接口從而根據(jù)鍵對(duì)元素進(jìn)行排序弯汰。

Collections 工具類(lèi)的 sort 方法有兩種重載的形式，

第一種要求傳入的待排序容器中存放的對(duì)象比較實(shí)現(xiàn) Comparable 接口以實(shí)現(xiàn)元素的比較湖雹；

第二種不強(qiáng)制性的要求容器中的元素必須可比較蝙泼，但是要求傳入第二個(gè)參數(shù)，參數(shù)是Comparator 接口的子類(lèi)型（需要重寫(xiě) compare 方法實(shí)現(xiàn)元素的比較）劝枣，相當(dāng)于一個(gè)臨時(shí)定義的排序規(guī)則，其實(shí)就是通過(guò)接口注入比較元素大小的算法织鲸，也是對(duì)回調(diào)模式的應(yīng)用（Java 中對(duì)函數(shù)式編程的支持）舔腾。