什么是集合
集合框架：用于存儲數(shù)據(jù)的容器钞速。
集合框架是為表示和操作集合而規(guī)定的一種統(tǒng)一的標準的體系結(jié)構(gòu)僧免。
任何集合框架都包含三大塊內(nèi)容：對外的接口禽额、接口的實現(xiàn)和對集合運算的算法聋溜。
接口：表示集合的抽象數(shù)據(jù)類型谆膳。接口允許我們操作集合時不必關(guān)注具體實現(xiàn)，從而達到“多
態(tài)”撮躁。在面向?qū)ο缶幊陶Z言中漱病，接口通常用來形成規(guī)范。
實現(xiàn)：集合接口的具體實現(xiàn)把曼，是重用性很高的數(shù)據(jù)結(jié)構(gòu)杨帽。
算法：在一個實現(xiàn)了某個集合框架中的接口的對象身上完成某種有用的計算的方法，例如查
找祝迂、排序等睦尽。這些算法通常是多態(tài)的，因為相同的方法可以在同一個接口被多個類實現(xiàn)時有
不同的表現(xiàn)型雳。事實上当凡，算法是可復(fù)用的函數(shù)。
它減少了程序設(shè)計的辛勞纠俭。
集合框架通過提供有用的數(shù)據(jù)結(jié)構(gòu)和算法使你能集中注意力于你的程序的重要部分上沿量，而不
是為了讓程序能正常運轉(zhuǎn)而將注意力于低層設(shè)計上。
通過這些在無關(guān) API 之間的簡易的互用性冤荆，使你免除了為改編對象或轉(zhuǎn)換代碼以便聯(lián)合這
些 API 而去寫大量的代碼朴则。 它提高了程序速度和質(zhì)量。
集合的特點集合的特點主要有如下兩點：
對象封裝數(shù)據(jù)钓简，對象多了也需要存儲乌妒。集合用于存儲對象。
對象的個數(shù)確定可以使用數(shù)組外邓，對象的個數(shù)不確定的可以用集合撤蚊。因為集合是可變長度的。
集合和數(shù)組的區(qū)別
數(shù)組是固定長度的损话；集合可變長度的侦啸。
數(shù)組可以存儲基本數(shù)據(jù)類型，也可以存儲引用數(shù)據(jù)類型丧枪；集合只能存儲引用數(shù)據(jù)類型句携。
數(shù)組存儲的元素必須是同一個數(shù)據(jù)類型喉悴；集合存儲的對象可以是不同數(shù)據(jù)類型爬橡。
數(shù)據(jù)結(jié)構(gòu)：就是容器中存儲數(shù)據(jù)的方式莉擒。
對于集合容器，有很多種恋博。因為每一個容器的自身特點不同服赎，其實原理在于每個容器的內(nèi)部
數(shù)據(jù)結(jié)構(gòu)不同葵蒂。
集合容器在不斷向上抽取過程中，出現(xiàn)了集合體系重虑。在使用一個體系的原則：參閱頂層內(nèi)容。
建立底層對象秦士。
使用集合框架的好處容量自增長缺厉；
提供了高性能的數(shù)據(jù)結(jié)構(gòu)和算法，使編碼更輕松隧土，提高了程序速度和質(zhì)量提针；
允許不同 API 之間的互操作，API 之間可以來回傳遞集合曹傀；
可以方便地擴展或改寫集合辐脖，提高代碼復(fù)用性和可操作性。
通過使用 JDK 自帶的集合類皆愉，可以降低代碼維護和學習新 API 成本嗜价。
常用的集合類有哪些？
Map 接口和 Collection 接口是所有集合框架的父接口：
Collection 接口的子接口包括：Set 接口和 List 接口
Map 接口的實現(xiàn)類主要有：HashMap幕庐、TreeMap久锥、Hashtable、ConcurrentHashMap
以及 Properties 等
Set 接口的實現(xiàn)類主要有：HashSet异剥、TreeSet瑟由、LinkedHashSet 等
List 接口的實現(xiàn)類主要有：ArrayList、LinkedList冤寿、Stack 以及 Vector 等
List歹苦，Set，Map 三者的區(qū)別督怜？List殴瘦、Set、Map 是否繼承自 Collection 接口亮蛔？List痴施、Map、
Set 三個接口存取元素時究流，各有什么特點辣吃？
Java 容器分為 Collection 和 Map 兩大類，Collection 集合的子接口有 Set芬探、
List神得、Queue
三種子接口。我們比較常用的是 Set偷仿、List哩簿，Map 接口不是 collection 的子接口宵蕉。
Collection 集合主要有 List 和 Set 兩大接口List：一個有序（元素存入集合的順序和取出的順序一致）容器，元素可以重復(fù)节榜，可以插入
多個 null 元素羡玛，元素都有索引。常用的實現(xiàn)類有 ArrayList宗苍、LinkedList 和 Vector稼稿。
Set：一個無序（存入和取出順序有可能不一致）容器，不可以存儲重復(fù)元素讳窟，只允許存入
一個 null 元素让歼，必須保證元素唯一性。Set 接口常用實現(xiàn)類是 HashSet丽啡、LinkedHashSet
以及 TreeSet谋右。
Map 是一個鍵值對集合，存儲鍵补箍、值和之間的映射改执。 Key 無序，唯一馏予；value 不要求有序天梧，
允許重復(fù)。Map 沒有繼承于 Collection 接口霞丧，從 Map 集合中檢索元素時呢岗，只要給出鍵對
象，就會返回對應(yīng)的值對象蛹尝。
Map 的 常 用 實 現(xiàn) 類 ： HashMap 后豫、 TreeMap 、 HashTable 突那、 LinkedHashMap 挫酿、
ConcurrentHashMap
集合框架底層數(shù)據(jù)結(jié)構(gòu)
Collection
List
Arraylist： Object 數(shù)組
Vector： Object 數(shù)組
LinkedList： 雙向循環(huán)鏈表
Set
HashSet（無序，唯一）：基于 HashMap 實現(xiàn)的愕难，底層采用 HashMap 來保存元素
LinkedHashSet ：
LinkedHashSet 繼 承 與
HashSet 早龟， 并 且 其 內(nèi) 部 是 通 過LinkedHashMap 來實現(xiàn)的。有點類似于我們之前說的 LinkedHashMap 其內(nèi)部是基于
Hashmap 實現(xiàn)一樣猫缭，不過還是有一點點區(qū)別的葱弟。
TreeSet（有序，唯一）： 紅黑樹(自平衡的排序二叉樹猜丹。)
Map
HashMap： JDK1.8 之前 HashMap 由數(shù)組+鏈表組成的芝加，數(shù)組是 HashMap 的主體，鏈
表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8 以后在解決哈希沖
突時有了較大的變化射窒，當鏈表長度大于閾值（默認為 8）時藏杖，將鏈表轉(zhuǎn)化為紅黑樹将塑，以減少
搜索時間
LinkedHashMap：LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈式
散列結(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹組成蝌麸。另外点寥，LinkedHashMap 在上面結(jié)構(gòu)的基礎(chǔ)上，
增加了一條雙向鏈表祥楣，使得上面的結(jié)構(gòu)可以保持鍵值對的插入順序开财。同時通過對鏈表進行相
應(yīng)的操作，實現(xiàn)了訪問順序相關(guān)邏輯误褪。
HashTable： 數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體碾褂，鏈表則是主要為了解決哈希
沖突而存在的
TreeMap： 紅黑樹（自平衡的排序二叉樹）
哪些集合類是線程安全的兽间？
vector：就比 arraylist 多了個同步化機制（線程安全），因為效率較低正塌，現(xiàn)在已經(jīng)不太建議
使用嘀略。在 web 應(yīng)用中，特別是前臺頁面乓诽，往往效率（頁面響應(yīng)速度）是優(yōu)先考慮的帜羊。
statck：堆棧類，先進后出鸠天。
hashtable：就比 hashmap 多了個線程安全讼育。
enumeration：枚舉，相當于迭代器稠集。Java 集合的快速失敗機制 “fail-fast”奶段？
是 java 集合的一種錯誤檢測機制，當多個線程對集合進行結(jié)構(gòu)上的改變的操作時剥纷，有可能
會產(chǎn)生 fail-fast 機制痹籍。
例如：假設(shè)存在兩個線程（線程 1、線程 2）晦鞋，線程 1 通過 Iterator 在遍歷集合 A 中的元素蹲缠，
在某個時候線程 2 修改了集合 A 的結(jié)構(gòu)（是結(jié)構(gòu)上面的修改，而不是簡單的修改集合元素
的內(nèi)容）悠垛，那么這個時候程序就會拋出 ConcurrentModificationException 異常线定，從而產(chǎn)
生 fail-fast 機制。
原因：迭代器在遍歷時直接訪問集合中的內(nèi)容鼎文，并且在遍歷過程中使用一個 modCount 變
量渔肩。集合在被遍歷期間如果內(nèi)容發(fā)生變化，就會改變 modCount 的值拇惋。每當?shù)魇褂?/p>
hashNext()/next() 遍 歷 下 一 個 元 素 之 前 周偎， 都 會 檢 測 modCount 變 量 是 否 為
expectedmodCount 值抹剩，是的話就返回遍歷；否則拋出異常蓉坎，終止遍歷澳眷。
解決辦法：
在遍歷過程中，所有涉及到改變 modCount 值得地方全部加上 synchronized蛉艾。
使用 CopyOnWriteArrayList 來替換 ArrayList
怎么確保一個集合不能被修改钳踊？
可以使用 Collections. unmodifiableCollection(Collection c) 方法來創(chuàng)建一個只讀集合，這樣改變集合的任何操作都會拋出 Java. lang. UnsupportedOperationException 異常勿侯。
示例代碼如下：
List<String> list = new ArrayList<>();
list. add("x");
Collection<String> clist = Collections. unmodifiableCollection(list);
clist. add("y"); // 運行時此行報錯
System. out. println(list. size());
Collection 接口
List 接口
迭代器 Iterator 是什么拓瞪？
Iterator 接口提供遍歷任何 Collection 的接口。我們可以從一個 Collection 中使用迭代
器方法來獲取迭代器實例助琐。迭代器取代了 Java 集合框架中的 Enumeration祭埂，迭代器允許
調(diào)用者在迭代過程中移除元素。
Iterator 怎么使用兵钮？有什么特點蛆橡？
Iterator 使用代碼如下：
List<String> list = new ArrayList<>();
Iterator<String> it = list. iterator();while(it. hasNext()){
String obj = it. next();
System. out. println(obj);
}
Iterator 的特點是只能單向遍歷，但是更加安全掘譬，因為它可以確保泰演，在當前遍歷的集合元素
被更改的時候，就會拋出 ConcurrentModificationException 異常葱轩。
如何邊遍歷邊移除 Collection 中的元素睦焕？
邊遍歷邊修改 Collection 的唯一正確方式是使用 Iterator.remove() 方法，如下：
Iterator<Integer> it = list.iterator();
while(it.hasNext()){
*// do something*
it.remove();
}
一種最常見的錯誤代碼如下：
for(Integer i : list){
list.remove(i)
}運行以上錯誤代碼會報 ConcurrentModificationException 異常酿箭。這是因為當使用
foreach(for(Integer i : list)) 語句時复亏，會自動生成一個 iterator 來遍歷該 list，但同時該
list 正在被 Iterator.remove() 修改缭嫡。Java 一般不允許一個線程在遍歷 Collection 時另
一個線程修改它缔御。
Iterator 和 ListIterator 有什么區(qū)別？
Iterator 可以遍歷 Set 和 List 集合妇蛀，而 ListIterator 只能遍歷 List耕突。
Iterator 只能單向遍歷，而 ListIterator 可以雙向遍歷（向前/后遍歷）评架。
ListIterator 實現(xiàn) Iterator 接口眷茁，然后添加了一些額外的功能，比如添加一個元素纵诞、替換
一個元素上祈、獲取前面或后面元素的索引位置。
遍歷一個 List 有哪些不同的方式？每種方法的實現(xiàn)原理是什么登刺？Java 中 List 遍歷的最
佳實踐是什么籽腕？
遍歷方式有以下幾種：
for 循環(huán)遍歷，基于計數(shù)器纸俭。在集合外部維護一個計數(shù)器皇耗，然后依次讀取每一個位置的元素，
當讀取到最后一個元素后停止揍很。
迭代器遍歷郎楼，Iterator。Iterator 是面向?qū)ο蟮囊粋€設(shè)計模式窒悔，目的是屏蔽不同數(shù)據(jù)集合的
特點呜袁，統(tǒng)一遍歷集合的接口。Java 在 Collections 中支持了 Iterator 模式简珠。
foreach 循環(huán)遍歷傅寡。foreach 內(nèi)部也是采用了 Iterator 的方式實現(xiàn)，使用時不需要顯式聲明 Iterator 或計數(shù)器北救。優(yōu)點是代碼簡潔，不易出錯芜抒；缺點是只能做簡單的遍歷珍策，不能在遍
歷過程中操作數(shù)據(jù)集合，例如刪除宅倒、替換攘宙。
最佳實踐：Java Collections 框架中提供了一個 RandomAccess 接口，用來標記 List 實
現(xiàn)是否支持 Random Access拐迁。
如果一個數(shù)據(jù)集合實現(xiàn)了該接口蹭劈，就意味著它支持 Random Access，按位置讀取元素的平
均時間復(fù)雜度為 O(1)线召，如 ArrayList铺韧。
如果沒有實現(xiàn)該接口，表示不支持 Random Access缓淹，如 LinkedList哈打。
推薦的做法就是，支持 Random Access 的列表可用 for 循環(huán)遍歷讯壶，否則建議用 Iterator
或 foreach 遍歷料仗。
說一下 ArrayList 的優(yōu)缺點
ArrayList 的優(yōu)點如下：
ArrayList 底層以數(shù)組實現(xiàn)，是一種隨機訪問模式伏蚊。ArrayList 實現(xiàn)了 RandomAccess 接
口立轧，因此查找的時候非常快。
ArrayList 在順序添加一個元素的時候非常方便氛改。
ArrayList 的缺點如下：
刪除元素的時候帐萎，需要做一次元素復(fù)制操作。如果要復(fù)制的元素很多平窘，那么就會比較耗費性
能吓肋。插入元素的時候，也需要做一次元素復(fù)制操作瑰艘，缺點同上是鬼。
ArrayList 比較適合順序添加、隨機訪問的場景紫新。
如何實現(xiàn)數(shù)組和 List 之間的轉(zhuǎn)換均蜜？
數(shù)組轉(zhuǎn) List：使用 Arrays. asList(array) 進行轉(zhuǎn)換。
List 轉(zhuǎn)數(shù)組：使用 List 自帶的 toArray() 方法芒率。
代碼示例：
// list to array
List<String> list = new ArrayList<String>();
list.add("123");
list.add("456");
list.toArray();
// array to list
String[] array = new String[]{"123","456"};
Arrays.asList(array);
ArrayList 和 LinkedList 的區(qū)別是什么囤耳？
數(shù)據(jù)結(jié)構(gòu)實現(xiàn)：ArrayList 是動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，而 LinkedList 是雙向鏈表的數(shù)據(jù)
結(jié)構(gòu)實現(xiàn)偶芍。
隨機訪問效率：ArrayList 比 LinkedList 在隨機訪問的時候效率要高充择，因為 LinkedList 是線性的數(shù)據(jù)存儲方式，所以需要移動指針從前往后依次查找匪蟀。
增加和刪除效率：在非首尾的增加和刪除操作椎麦，LinkedList 要比 ArrayList 效率要高，因
為 ArrayList 增刪操作要影響數(shù)組內(nèi)的其他數(shù)據(jù)的下標材彪。
內(nèi)存空間占用：LinkedList 比 ArrayList 更占內(nèi)存观挎，因為 LinkedList 的節(jié)點除了存儲數(shù)
據(jù)，還存儲了兩個引用段化，一個指向前一個元素嘁捷，一個指向后一個元素。
線程安全：ArrayList 和 LinkedList 都是不同步的显熏，也就是不保證線程安全雄嚣；
綜合來說，在需要頻繁讀取集合中的元素時佃延，更推薦使用 ArrayList现诀，而在插入和刪除操作
較多時，更推薦使用 LinkedList履肃。
補充：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之雙向鏈表
雙向鏈表也叫雙鏈表仔沿，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針尺棋，分別指向直接后
繼和直接前驅(qū)封锉。所以绵跷，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)
點和后繼結(jié)點成福。
ArrayList 和 Vector 的區(qū)別是什么碾局？
這兩個類都實現(xiàn)了 List 接口（List 接口繼承了 Collection 接口），他們都是有序集合
線程安全：Vector 使用了 Synchronized 來實現(xiàn)線程同步奴艾，是線程安全的净当，而 ArrayList
是非線程安全的。
性能：ArrayList 在性能方面要優(yōu)于 Vector蕴潦。
擴容：ArrayList 和 Vector 都會根據(jù)實際的需要動態(tài)的調(diào)整容量像啼，只不過在 Vector 擴容每次會增加 1 倍，而 ArrayList 只會增加 50%潭苞。
Vector 類的所有方法都是同步的忽冻。可以由兩個線程安全地訪問一個 Vector 對象此疹、但是一個
線程訪問 Vector 的話代碼要在同步操作上耗費大量的時間僧诚。
Arraylist 不是同步的，所以在不需要保證線程安全時時建議使用 Arraylist蝗碎。
插入數(shù)據(jù)時湖笨，ArrayList、LinkedList蹦骑、Vector 誰速度較快赶么？闡述 ArrayList、Vector脊串、
LinkedList 的存儲性能和特性？
ArrayList清钥、LinkedList琼锋、Vector 底層的實現(xiàn)都是使用數(shù)組方式存儲數(shù)據(jù)。數(shù)組元素數(shù)大于
實際存儲的數(shù)據(jù)以便增加和插入元素祟昭，它們都允許直接按序號索引元素缕坎，但是插入元素要涉
及數(shù)組元素移動等內(nèi)存操作，所以索引數(shù)據(jù)快而插入數(shù)據(jù)慢篡悟。
Vector 中的方法由于加了 synchronized 修飾谜叹，因此 Vector 是線程安全容器，但性能上
較 ArrayList 差搬葬。
LinkedList 使用雙向鏈表實現(xiàn)存儲荷腊，按序號索引數(shù)據(jù)需要進行前向或后向遍歷，但插入數(shù)
據(jù)時只需要記錄當前項的前后項即可急凰，所以 LinkedList 插入速度較快女仰。
多線程場景下如何使用 ArrayList？
ArrayList 不 是 線 程 安 全 的 ， 如 果 遇 到 多 線 程 場 景 疾忍， 可 以 通 過 Collections 的
synchronizedList 方法將其轉(zhuǎn)換成線程安全的容器后再使用乔外。例如像下面這樣：List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");
for (int i = 0; i < synchronizedList.size(); i++) {
System.out.println(synchronizedList.get(i));
}
為什么 ArrayList 的 elementData 加上 transient 修飾？
ArrayList 中的數(shù)組定義如下：
private transient Object[] elementData;
1
再看一下 ArrayList 的定義：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
可以看到 ArrayList 實現(xiàn)了 Serializable 接口一罩，這意味著 ArrayList 支持序列化杨幼。
transient 的作用是說不希望 elementData 數(shù)組被序列化，重寫了 writeObject 實現(xiàn)：
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{*// Write out element count, and any hidden stuff*
int expectedModCount = modCount;
s.defaultWriteObject();
*// Write out array length*
s.writeInt(elementData.length);
*// Write out all elements in the proper order.*
for (int i=0; i<size; i++)
s.writeObject(elementData[i]);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
每次序列化時聂渊，先調(diào)用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient
元素差购，然后遍歷 elementData，只序列化已存入的元素歧沪，這樣既加快了序列化的速度歹撒，又
減小了序列化之后的文件大小。
List 和 Set 的區(qū)別
List , Set 都是繼承自 Collection 接口
List 特點：一個有序（元素存入集合的順序和取出的順序一致）容器诊胞，元素可以重復(fù)暖夭，可
以插入多個 null 元素，元素都有索引撵孤。常用的實現(xiàn)類有 ArrayList迈着、LinkedList 和 Vector。Set 特點：一個無序（存入和取出順序有可能不一致）容器邪码，不可以存儲重復(fù)元素裕菠，只允許
存 入 一 個 null 元 素 ， 必 須 保 證 元 素 唯 一 性 闭专。 Set 接 口 常 用 實 現(xiàn) 類 是 HashSet 奴潘、
LinkedHashSet 以及 TreeSet。
另外 List 支持 for 循環(huán)影钉，也就是通過下標來遍歷画髓，也可以用迭代器，但是 set 只能用迭代平委，
因為他無序奈虾，無法用下標來取得想要的值。
Set 和 List 對比
Set：檢索元素效率低下廉赔，刪除和插入效率高肉微，插入和刪除不會引起元素位置改變。
List：和數(shù)組類似蜡塌，List 可以動態(tài)增長碉纳，查找元素效率高崎岂，插入刪除元素效率低请祖，因為會引
起其他元素位置改變
Set 接口
說一下 HashSet 的實現(xiàn)原理泵三？
HashSet 是基于 HashMap 實現(xiàn)的，HashSet 的值存放于 HashMap 的 key 上竖伯，HashMap
的 value 統(tǒng)一為 PRESENT刽辙，因此 HashSet 的實現(xiàn)比較簡單勺爱，相關(guān) HashSet 的操作促煮，基
本上都是直接調(diào)用底層 HashMap 的相關(guān)方法來完成，HashSet 不允許重復(fù)的值库菲。
HashSet 如何檢查重復(fù)账忘？HashSet 是如何保證數(shù)據(jù)不可重復(fù)的？
向 HashSet 中 add ()元素時熙宇，判斷元素是否存在的依據(jù)鳖擒，不僅要比較 hash 值，同時還要
結(jié)合 equles 方法比較烫止。HashSet 中的 add ()方法會使用 HashMap 的 put()方法蒋荚。
HashMap 的 key 是唯一的，由源碼可以看出 HashSet 添加進去的值就是作為
HashMap 的 key馆蠕，并且在 HashMap 中如果 K/V 相同時期升，會用新的 V 覆蓋掉舊的 V，然
后返回舊的 V互躬。所以不會重復(fù)（ HashMap 比較 key 是否相等是先比較 hashcode 再比較
equals ）播赁。
以下是 HashSet 部分源碼：
private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
// 調(diào)用 HashMap 的 put 方法,PRESENT 是一個至始至終都相同的虛值
return map.put(e, PRESENT)==null;
}
hashCode（）與 equals（）的相關(guān)規(guī)定：如果兩個對象相等，則 hashcode 一定也是相同的
兩個對象相等,對兩個 equals 方法返回 true
兩個對象有相同的 hashcode 值吼渡，它們也不一定是相等的
綜上容为，equals 方法被覆蓋過，則 hashCode 方法也必須被覆蓋
hashCode()的默認行為是對堆上的對象產(chǎn)生獨特值寺酪。如果沒有重寫 hashCode()坎背，則該 class
的兩個對象無論如何都不會相等（即使這兩個對象指向相同的數(shù)據(jù)）。
==與 equals 的區(qū)別
==是判斷兩個變量或?qū)嵗遣皇侵赶蛲粋€內(nèi)存空間 equals 是判斷兩個變量或?qū)嵗?/p>
向的內(nèi)存空間的值是不是相同
==是指對內(nèi)存地址進行比較 equals()是對字符串的內(nèi)容進行比較 3.==指引用是否相同
equals()指的是值是否相同
HashSet 與 HashMap 的區(qū)別
HashMap
HashSet
實現(xiàn)了 Map 接口 實現(xiàn) Set 接口
存儲鍵值對 僅存儲對象
調(diào)用 put（）向 map 中添加元素
調(diào)用 add（）方法向 Set 中添加元素
HashMap 使用鍵（Key）計算 Hashcode
HashSet 使用成員對象來計算 hashcode 值寄雀，
對于兩個對象來說 hashcode 可能相同沼瘫，所以 equals()方法用來判斷對象的相等性，如果
兩個對象不同的話咙俩，那么返回 false
HashMap 相對于 HashSet 較快，因為它是使用唯一的鍵獲取對象 HashSet
較HashMap 來說比較慢
Queue
BlockingQueue 是什么湿故？
Java.util.concurrent.BlockingQueue 是一個隊列阿趁，在進行檢索或移除一個元素的時候，它
會等待隊列變?yōu)榉强仗持恚划斣谔砑右粋€元素時脖阵，它會等待隊列中的可用空間。BlockingQueue
接口是 Java 集合框架的一部分墅茉，主要用于實現(xiàn)生產(chǎn)者-消費者模式命黔。我們不需要擔心等待生
產(chǎn)者有可用的空間悍募，或消費者有可用的對象，因為它都在 BlockingQueue 的實現(xiàn)類中被處
理 了 坠宴。 Java 提 供 了 集 中 BlockingQueue 的 實 現(xiàn) ， 比 如 ArrayBlockingQueue 副砍、
LinkedBlockingQueue、PriorityBlockingQueue,庄岖、SynchronousQueue 等。
在 Queue 中 poll()和 remove()有什么區(qū)別心剥？
相同點：都是返回第一個元素刘陶，并在隊列中刪除返回的對象匙隔。
不 同 點 ： 如 果 沒 有 元 素 poll() 會 返 回 null 纷责， 而 remove() 會 直 接 拋 出
NoSuchElementException 異常再膳。
代碼示例：
Queue<String> queue = new LinkedList<String>();
queue. offer("string"); // add
System. out. println(queue. poll());
System. out. println(queue. remove());
System. out. println(queue. size());Map 接口
說一下 HashMap 的實現(xiàn)原理喂柒？
HashMap 概述： HashMap 是基于哈希表的 Map 接口的非同步實現(xiàn)灾杰。此實現(xiàn)提供所有可
選的映射操作艳吠，并允許使用 null 值和 null 鍵昭娩。此類不保證映射的順序栏渺，特別是它不保證該
順序恒久不變迈嘹。
HashMap 的數(shù)據(jù)結(jié)構(gòu)： 在 Java 編程語言中秀仲，最基本的結(jié)構(gòu)就是兩種神僵，一個是數(shù)組沛励，另外
一個是模擬指針（引用）目派，所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個基本結(jié)構(gòu)來構(gòu)造的企蹭，HashMap
也不例外谅摄。HashMap 實際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)送漠，即數(shù)組和鏈表的結(jié)合體闽寡。
HashMap 基于 Hash 算法實現(xiàn)的
當我們往 Hashmap 中 put 元素時，利用 key 的 hashCode 重新 hash 計算出當前對象的
元素在數(shù)組中的下標
存儲時，如果出現(xiàn) hash 值相同的 key句惯，此時有兩種情況抢野。(1)如果 key 相同指孤，則覆蓋原始值恃轩；
(2)如果 key 不同（出現(xiàn)沖突）叉跛，則將當前的 key-value 放入鏈表中
獲取時鸣峭，直接找到 hash 值對應(yīng)的下標摊溶，在進一步判斷 key 是否相同莫换，從而找到對應(yīng)值浓镜。
理解了以上過程就不難明白 HashMap 是如何解決 hash 沖突的問題，核心就是使用了數(shù)組
的存儲方式哄啄，然后將沖突的 key 的對象放入鏈表中咨跌，一旦發(fā)現(xiàn)沖突就在鏈表中做進一步的
對比锌半。
需要注意 Jdk 1.8 中對 HashMap 的實現(xiàn)做了優(yōu)化殉摔，當鏈表中的節(jié)點數(shù)據(jù)超過八個之后逸月，該
鏈表會轉(zhuǎn)為紅黑樹來提高查詢效率碗硬，從原來的 O(n)到 O(logn)HashMap 在 JDK1.7 和 JDK1.8 中有哪些不同恩尾？HashMap 的底層實現(xiàn)
在 Java 中，保存數(shù)據(jù)有兩種比較簡單的數(shù)據(jù)結(jié)構(gòu)：數(shù)組和鏈表猎物。數(shù)組的特點是：尋址容易蔫磨，
插入和刪除困難堤如；鏈表的特點是：尋址困難，但插入和刪除容易榔至；所以我們將數(shù)組和鏈表結(jié)
合在一起唧取，發(fā)揮兩者各自的優(yōu)勢枫弟，使用一種叫做拉鏈法的方式可以解決哈希沖突。
JDK1.8 之前
JDK1.8 之前采用的是拉鏈法韩容。拉鏈法：將鏈表和數(shù)組相結(jié)合宙攻。也就是說創(chuàng)建一個鏈表數(shù)組，
數(shù)組中每一格就是一個鏈表溢陪。若遇到哈希沖突形真，則將沖突的值加到鏈表中即可。
JDK1.8 之后
相比于之前的版本蛾坯，jdk1.8 在解決哈希沖突時有了較大的變化脉课，當鏈表長度大于閾值（默
認為 8）時，將鏈表轉(zhuǎn)化為紅黑樹呈驶，以減少搜索時間俐东。
JDK1.7 VS JDK1.8 比較
JDK1.8 主要解決或優(yōu)化了一下問題：
resize 擴容優(yōu)化引入了紅黑樹，目的是避免單條鏈表過長而影響查詢效率砌庄，紅黑樹算法請參考
解決了多線程死循環(huán)問題娄昆，但仍是非線程安全的哺眯，多線程時可能會造成數(shù)據(jù)丟失問題奶卓。
不同
JDK 1.7 JDK 1.8
存儲結(jié)構(gòu)
數(shù)組 + 鏈表 數(shù)組 + 鏈表 + 紅黑樹
初始化方式 單獨函數(shù)：inflateTable() 直接集成到了擴容函數(shù) resize()中
hash 值計算方式 擾動處理 = 9 次擾動 = 4 次位運算 + 5 次異或運算 擾動處理 = 2 次
擾動 = 1 次位運算 + 1 次異或運算
存放數(shù)據(jù)的規(guī)則 無沖突時，存放數(shù)組盏浙；沖突時废膘，存放鏈表
無沖突時，存放數(shù)組孵稽；沖突
& 鏈表長度 < 8：存放單鏈表；沖突 & 鏈表長度 > 8：樹化并存放紅黑樹
插入數(shù)據(jù)方式
頭插法（先講原位置的數(shù)據(jù)移到后 1 位接校，再插入數(shù)據(jù)到該位置）
尾
插法（直接插入到鏈表尾部/紅黑樹）
擴容后存儲位置的計算方式
全部按照原來方法進行計算（即 hashCode ->> 擾動函數(shù)
->> (h&length-1)） 按照擴容后的規(guī)律計算（即擴容后的位置=原位置 or 原位置 + 舊
容量）
HashMap 的 put 方法的具體流程？
當我們 put 的時候诽凌，首先計算 key 的 hash 值侣诵，這里調(diào)用了 hash 方法财搁，hash 方法實際是
讓 key.hashCode()與 key.hashCode()>>>16 進行異或操作，高 16bit 補 0越锈，一個數(shù)和 0
異或不變，所以 hash 函數(shù)大概的作用就是：高 16bit 不變，低 16bit 和高 16bit 做了一
個異或铲咨，目的是減少碰撞。按照函數(shù)注釋摇天，因為 bucket 數(shù)組大小是 2 的冪泉坐，計算下標 index
= (table.length - 1) & hash，如果不做 hash 處理纯丸，相當于散列生效的只有幾個低 bit 位，
為了減少散列的碰撞滑凉，設(shè)計者綜合考慮了速度咒钟、作用朱嘴、質(zhì)量之后，使用高 16bit 和低 16bit
異或來簡單處理減少碰撞壤追，而且 JDK8 中用了復(fù)雜度 O（logn）的樹結(jié)構(gòu)來提升碰撞下的性能。
putVal 方法執(zhí)行流程圖
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//實現(xiàn) Map.put 和相關(guān)方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步驟①：tab 為空則創(chuàng)建
// table 未初始化或者長度為 0悼做，進行擴容
if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;
// 步驟②：計算 index，并對 null 做處理
// (n - 1) & hash 確定元素存放在哪個桶中，桶為空纵搁，新生成結(jié)點放入桶中(此時腾誉，這
個結(jié)點是放在數(shù)組中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 桶中已經(jīng)存在元素
else {
Node<K,V> e; K k;
// 步驟③：節(jié)點 key 存在，直接覆蓋 value
// 比較桶中第一個元素(數(shù)組中的結(jié)點)的 hash 值相等，key 相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 將第一個元素賦值給 e热押，用 e 來記錄
e = p;
// 步驟④：判斷該鏈為紅黑樹
// hash 值不相等拥褂，即 key 不相等饺鹃；為紅黑樹結(jié)點
// 如果當前元素類型為 TreeNode，表示為紅黑樹，putTreeVal 返回待存放的
node, e 可能為 null
else if (p instanceof TreeNode)
// 放入樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 步驟⑤：該鏈為鏈表
// 為鏈表結(jié)點
else {
// 在鏈表最末插入結(jié)點
for (int binCount = 0; ; ++binCount) {
// 到達鏈表的尾部
//判斷該鏈表尾部指針是不是空的
if ((e = p.next) == null) {
// 在尾部插入新結(jié)點
p.next = newNode(hash, key, value, null);
//判斷鏈表的長度是否達到轉(zhuǎn)化紅黑樹的臨界值归苍，臨界值為 8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//鏈表結(jié)構(gòu)轉(zhuǎn)樹形結(jié)構(gòu)
treeifyBin(tab, hash);
// 跳出循環(huán)
break;
}
// 判斷鏈表中結(jié)點的 key 值與插入的元素的 key 值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等齿拂，跳出循環(huán)break;
// 用于遍歷桶中的鏈表吗购，與前面的 e = p.next 組合，可以遍歷鏈表
p = e;
}
}
//判斷當前的 key 已經(jīng)存在的情況下踱启，再來一個相同的 hash 值、key 值時冠蒋，返回
新來的 value 這個值
if (e != null) {
// 記錄 e 的 value
V oldValue = e.value;
// onlyIfAbsent 為 false 或者舊值為 null
if (!onlyIfAbsent || oldValue == null)
//用新值替換舊值
e.value = value;
// 訪問后回調(diào)
afterNodeAccess(e);
// 返回舊值
return oldValue;
}
}
// 結(jié)構(gòu)性修改
++modCount;// 步驟⑥：超過最大容量就擴容
// 實際大小大于閾值則擴容
if (++size > threshold)
resize();
// 插入后回調(diào)
afterNodeInsertion(evict);
return null;
}
①.判斷鍵值對數(shù)組 table[i]是否為空或為 null，否則執(zhí)行 resize()進行擴容脑融；
②.根據(jù)鍵值 key 計算 hash 值得到插入的數(shù)組索引 i，如果 table[i]==null膜宋，直接新建節(jié)點
添加，轉(zhuǎn)向⑥乃秀，如果 table[i]不為空肛著，轉(zhuǎn)向③；
③.判斷 table[i]的首個元素是否和 key 一樣跺讯，如果相同直接覆蓋 value枢贿，否則轉(zhuǎn)向④，這里
的相同指的是 hashCode 以及 equals局荚；
④.判斷 table[i] 是否為 treeNode，即 table[i] 是否是紅黑樹愈污，如果是紅黑樹耀态，則直接在
樹中插入鍵值對，否則轉(zhuǎn)向⑤暂雹；
⑤.遍歷 table[i]首装，判斷鏈表長度是否大于 8，大于 8 的話把鏈表轉(zhuǎn)換為紅黑樹杭跪，在紅黑樹中
執(zhí)行插入操作仙逻，否則進行鏈表的插入操作；遍歷過程中若發(fā)現(xiàn) key 已經(jīng)存在直接覆蓋 value即可涧尿；
⑥.插入成功后桨醋，判斷實際存在的鍵值對數(shù)量 size 是否超多了最大容量 threshold，如果超
過现斋，進行擴容喜最。
HashMap 的擴容操作是怎么實現(xiàn)的？
①.在 jdk1.8 中庄蹋，resize 方法是在 hashmap 中的鍵值對大于閥值時或者初始化時瞬内，就調(diào)用
resize 方法進行擴容迷雪；
②.每次擴展的時候，都是擴展 2 倍虫蝶；
③.擴展后 Node 對象的位置要么在原位置章咧，要么移動到原偏移量兩倍的位置。
在 putVal()中能真，我們看到在這個函數(shù)里面使用到了 2 次 resize()方法赁严，resize()方法表示的
在進行第一次初始化時會對其進行擴容，或者當該數(shù)組的實際大小大于其臨界值值(第一次
為 12),這個時候在擴容的同時也會伴隨的桶上面的元素進行重新分發(fā)粉铐，這也是 JDK1.8 版本
的一個優(yōu)化的地方疼约，在 1.7 中，擴容之后需要重新去計算其 Hash 值蝙泼，根據(jù) Hash 值對其進
行分發(fā)程剥，但在 1.8 版本中，則是根據(jù)在同一個桶的位置中進行判斷(e.hash & oldCap)是否
為 0汤踏，重新進行 hash 分配后织鲸，該元素的位置要么停留在原始位置，要么移動到原始位置+
增加的數(shù)組大小這個位置上
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;//oldTab 指向 hash 桶數(shù)組
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {//如果 oldCap 不為空的話溪胶，就是 hash 桶數(shù)組不為空
if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了搂擦，就賦值為整數(shù)最
大的閥值
threshold = Integer.MAX_VALUE;
return oldTab;//返回
}//如果當前 hash 桶數(shù)組的長度在擴容后仍然小于最大容量 并且 oldCap 大于默
認值 16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 雙倍擴容閥值 threshold
}
// 舊的容量為 0，但 threshold 大于零哗脖，代表有參構(gòu)造有 cap 傳入瀑踢，threshold 已經(jīng)
被初始化成最小 2 的 n 次冪
// 直接將該值賦給新的容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 無參構(gòu)造創(chuàng)建的 map，給出默認容量和 threshold 16, 16*0.75
else {
// zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新的 threshold = 新的 cap * 0.75
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr
=
(newCap
<
MAXIMUM_CAPACITY
&&
ft
<
(float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 計算出新的數(shù)組長度后賦給當前成員變量 table
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶數(shù)
組
table = newTab;//將新數(shù)組的值復(fù)制給舊的 hash 桶數(shù)組
// 如果原先的數(shù)組沒有初始化懒熙，那么 resize 的初始化工作到此結(jié)束丘损，否則進入擴容元
素重排邏輯普办，使其均勻的分散
if (oldTab != null) {
// 遍歷新數(shù)組的所有桶下標
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;if ((e = oldTab[j]) != null) {
// 舊數(shù)組的桶下標賦給臨時變量 e工扎，并且解除舊數(shù)組中的引用，否則就
數(shù)組無法被 GC 回收
oldTab[j] = null;
// 如果 e.next==null衔蹲，代表桶中就一個元素肢娘，不存在鏈表或者紅黑樹
if (e.next == null)
// 用同樣的 hash 映射算法把該元素加入新的數(shù)組
newTab[e.hash & (newCap - 1)] = e;
// 如果 e 是 TreeNode 并且 e.next!=null，那么處理樹中元素的重排
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// e 是鏈表的頭并且 e.next!=null舆驶，那么處理鏈表中元素重排
else { // preserve order
// loHead,loTail 代表擴容后不用變換下標橱健，見注 1
Node<K,V> loHead = null, loTail = null;
// hiHead,hiTail 代表擴容后變換下標，見注 1
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍歷鏈表
do {
next = e.next;
if ((e.hash & oldCap) == 0) {if (loTail == null)
// 初始化 head 指向鏈表當前元素 e沙廉，e 不一定是鏈表
的第一個元素拘荡，初始化后 loHead
// 代表下標保持不變的鏈表的頭元素
loHead = e;
else
// loTail.next 指向當前 e
loTail.next = e;
// loTail 指向當前的元素 e
// 初始化后，loTail 和 loHead 指向相同的內(nèi)存撬陵，所以當
loTail.next 指向下一個元素時珊皿，
// 底層數(shù)組中的元素的 next 引用也相應(yīng)發(fā)生變化网缝，造成
lowHead.next.next.....
// 跟隨 loTail 同步，使得 lowHead 可以鏈接到所有屬于該
鏈表的元素蟋定。
loTail = e;
}
else {
if (hiTail == null)
// 初 始 化 head 指 向 鏈 表當 前 元 素 e, 初 始 化后
hiHead 代表下標更改的鏈表頭元素
hiHead = e;else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 遍歷結(jié)束, 將 tail 指向 null粉臊，并把鏈表頭放入新數(shù)組的相應(yīng)下標，
形成新的映射驶兜。
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}HashMap 是怎么解決哈希沖突的扼仲？
答：在解決這個問題之前，我們首先需要知道什么是哈希沖突抄淑，而在了解哈希沖突之前我們
還要知道什么是哈希才行屠凶；
什么是哈希？
Hash蝇狼，一般翻譯為“散列”阅畴，也有直接音譯為“哈希”的迅耘，這就是把任意長度的輸入通過
散列算法贱枣，變換成固定長度的輸出，該輸出就是散列值（哈希值）颤专；這種轉(zhuǎn)換是一種壓縮映
射纽哥，也就是，散列值的空間通常遠小于輸入的空間栖秕，不同的輸入可能會散列成相同的輸出春塌，
所以不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一
固定長度的消息摘要的函數(shù)簇捍。
所有散列函數(shù)都有如下一個基本特性**：根據(jù)同一散列函數(shù)計算出的散列值如果不同只壳，那么
輸入值肯定也不同。但是暑塑，根據(jù)同一散列函數(shù)計算出的散列值如果相同吼句，輸入值不一定相同
**。
什么是哈希沖突事格？
當兩個不同的輸入值惕艳，根據(jù)同一散列函數(shù)計算出相同的散列值的現(xiàn)象，我們就把它叫做碰撞
（哈希碰撞）驹愚。
HashMap 的數(shù)據(jù)結(jié)構(gòu)
在 Java 中远搪，保存數(shù)據(jù)有兩種比較簡單的數(shù)據(jù)結(jié)構(gòu)：數(shù)組和鏈表。數(shù)組的特點是：尋址容易逢捺，
插入和刪除困難谁鳍；鏈表的特點是：尋址困難，但插入和刪除容易；所以我們將數(shù)組和鏈表結(jié)合在一起倘潜，發(fā)揮兩者各自的優(yōu)勢余佛，使用一種叫做鏈地址法的方式可以解決哈希沖突：
這樣我們就可以將擁有相同哈希值的對象組織成一個鏈表放在hash值所對應(yīng)的bucket下，
但 相 比 于 hashCode 返 回 的 int 類 型 窍荧， 我 們 HashMap 初 始 的 容 量 大 小
DEFAULT_INITIAL_CAPACITY = 1 << 4（即 2 的四次方 16）要遠小于 int 類型的范圍辉巡，
所以我們?nèi)绻皇菃渭兊挠胔ashCode取余來獲取對應(yīng)的bucket這將會大大增加哈希碰撞
的概率，并且最壞情況下還會將 HashMap 變成一個單鏈表蕊退，所以我們還需要對 hashCode
作一定的優(yōu)化
hash()函數(shù)
上面提到的問題郊楣，主要是因為如果使用 hashCode 取余，那么相當于參與運算的只有
hashCode 的低位瓤荔，高位是沒有起到任何作用的净蚤，所以我們的思路就是讓 hashCode 取值
出的高位也參與運算，進一步降低 hash 碰撞的概率输硝，使得數(shù)據(jù)分布更平均今瀑，我們把這樣的
操作稱為擾動，在 JDK 1.8 中的 hash()函數(shù)如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 與自己右移 16 位
進行異或運算（高低位異或）
}這比在 JDK 1.7 中点把，更為簡潔橘荠，相比在 1.7 中的 4 次位運算，5 次異或運算（9 次擾動）郎逃，
在 1.8 中哥童，只進行了 1 次位運算和 1 次異或運算（2 次擾動）；
JDK1.8 新增紅黑樹
通過上面的鏈地址法（使用散列表）和擾動函數(shù)我們成功讓我們的數(shù)據(jù)分布更平均褒翰，哈希碰
撞減少贮懈，但是當我們的 HashMap 中存在大量數(shù)據(jù)時，加入我們某個 bucket 下對應(yīng)的鏈表
有 n 個元素优训，那么遍歷時間復(fù)雜度就為 O(n)朵你，為了針對這個問題，JDK1.8 在 HashMap 中
新增了紅黑樹的數(shù)據(jù)結(jié)構(gòu)揣非，進一步使得遍歷復(fù)雜度降低至 O(logn)抡医；
總結(jié)
簡單總結(jié)一下 HashMap 是使用了哪些方法來有效解決哈希沖突的：
1. 使用鏈地址法（使用散列表）來鏈接擁有相同 hash 值的數(shù)據(jù)；
2. 使用 2 次擾動函數(shù)（hash 函數(shù)）來降低哈希沖突的概率妆兑，使得數(shù)據(jù)分布更平均魂拦；
3. 引入紅黑樹進一步降低遍歷的時間復(fù)雜度毛仪，使得遍歷更快搁嗓；
能否使用任何類作為 Map 的 key？
可以使用任何類作為 Map 的 key箱靴，然而在使用之前腺逛，需要考慮以下幾點：如果類重寫了 equals() 方法，也應(yīng)該重寫 hashCode() 方法衡怀。
類的所有實例需要遵循與 equals() 和 hashCode() 相關(guān)的規(guī)則棍矛。
如果一個類沒有使用 equals()安疗，不應(yīng)該在 hashCode() 中使用它。
用戶自定義 Key 類最佳實踐是使之為不可變的够委，這樣 hashCode() 值可以被緩存起來荐类，
擁有更好的性能。不可變的類也可以確保 hashCode() 和 equals() 在未來不會改變茁帽，這
樣就會解決與可變相關(guān)的問題了玉罐。
為什么 HashMap 中 String、Integer 這樣的包裝類適合作為 K潘拨？
答：String吊输、Integer 等包裝類的特性能夠保證 Hash 值的不可更改性和計算準確性，能夠
有效的減少 Hash 碰撞的幾率
都是 final 類型铁追，即不可變性季蚂，保證 key 的不可更改性，不會存在獲取 hash 值不同的情況
內(nèi)部已重寫了 equals()琅束、hashCode()等方法扭屁，遵守了 HashMap 內(nèi)部的規(guī)范（不清楚可以
去上面看看 putValue 的過程），不容易出現(xiàn) Hash 值計算錯誤的情況涩禀；
如果使用 Object 作為 HashMap 的 Key疯搅，應(yīng)該怎么辦呢？
答：重寫 hashCode()和 equals()方法
重寫 hashCode()是因為需要計算存儲數(shù)據(jù)的存儲位置埋泵，需要注意不要試圖從散列碼計算中
排除掉一個對象的關(guān)鍵部分來提高性能幔欧，這樣雖然能更快但可能會導(dǎo)致更多的 Hash 碰撞；重寫 equals()方法丽声，需要遵守自反性礁蔗、對稱性、傳遞性雁社、一致性以及對于任何非 null 的引
用值 x浴井，x.equals(null)必須返回 false 的這幾個特性，目的是為了保證 key 在哈希表中的唯
一性霉撵；
HashMap 為什么不直接使用 hashCode()處理后的哈希值直接作為 table 的下標磺浙？
答：hashCode()方法返回的是 int 整數(shù)類型，其范圍為-(2 ^ 31)~(2 ^ 31 - 1)徒坡，約有 40
億個映射空間撕氧，而 HashMap 的容量范圍是在 16（初始化默認值）~2 ^ 30，HashMap
通常情況下是取不到最大值的喇完，并且設(shè)備上也難以提供這么多的存儲空間伦泥，從而導(dǎo)致通過
hashCode()計算出的哈希值可能不在數(shù)組大小范圍內(nèi)，進而無法匹配存儲位置；
那怎么解決呢不脯？
HashMap 自己實現(xiàn)了自己的 hash()方法府怯，通過兩次擾動使得它自己的哈希值高低位自行進
行異或運算，降低哈希碰撞概率也使得數(shù)據(jù)分布更平均防楷；
在保證數(shù)組長度為 2 的冪次方的時候牺丙，使用 hash()運算之后的值與運算（&）（數(shù)組長度 -
1）來獲取數(shù)組下標的方式進行存儲涕烧，這樣一來是比取余操作更加有效率癌佩，二來也是因為只
有當數(shù)組長度為 2 的冪次方時，h&(length-1)才等價于 h%length瞧剖，三來解決了“哈希值
與數(shù)組大小范圍不匹配”的問題肖揣；
HashMap 的長度為什么是 2 的冪次方
為了能讓 HashMap 存取高效民假，盡量較少碰撞，也就是要盡量把數(shù)據(jù)分配均勻龙优，每個鏈表
/紅黑樹長度大致相同羊异。這個實現(xiàn)就是把數(shù)據(jù)存到哪個鏈表/紅黑樹中的算法。
這個算法應(yīng)該如何設(shè)計呢彤断？我們首先可能會想到采用%取余的操作來實現(xiàn)野舶。但是，重點來了：“取余(%)操作中如果除
數(shù) 是 2 的 冪 次 則 等 價 于 與 其 除 數(shù) 減 一 的 與 (&) 操 作 （ 也 就 是 說
hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方宰衙；）平道。” 并且 采用二
進制位操作 &供炼，相對于%能夠提高運算效率一屋，這就解釋了 HashMap 的長度為什么是 2 的
冪次方。
那為什么是兩次擾動呢袋哼？
答：這樣就是加大哈希值低位的隨機性冀墨，使得分布更均勻，從而提高對應(yīng)數(shù)組存儲下標位置
的隨機性&均勻性涛贯，最終減少 Hash 沖突诽嘉，兩次就夠了，已經(jīng)達到了高位低位同時參與運算
的目的弟翘；
HashMap 與 HashTable 有什么區(qū)別虫腋？
線程安全： HashMap 是非線程安全的，HashTable 是線程安全的稀余；HashTable 內(nèi)部的
方 法 基 本 都 經(jīng) 過 synchronized 修 飾 悦冀。（ 如 果 你 要 保 證 線 程 安 全 的 話 就 使 用
ConcurrentHashMap 吧！）滚躯；
效率： 因為線程安全的問題雏门，HashMap 要比 HashTable 效率高一點。另外掸掏，HashTable
基本被淘汰茁影，不要在代碼中使用它；
對 Null key 和 Null value 的支持： HashMap 中丧凤，null 可以作為鍵募闲，這樣的鍵只有一個，
可以有一個或多個鍵所對應(yīng)的值為 null愿待。但是在 HashTable 中 put 進的鍵值只要有一個
null浩螺，直接拋 NullPointerException。**初始容量大小和每次擴充容量大小的不同 **： ①創(chuàng)建時如果不指定容量初始值仍侥，
Hashtable 默認的初始大小為 11要出，之后每次擴充，容量變?yōu)樵瓉淼?2n+1农渊。HashMap 默
認的初始化大小為 16患蹂。之后每次擴充，容量變?yōu)樵瓉淼?2 倍砸紊。②創(chuàng)建時如果給定了容量初
始值传于，那么 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為 2 的冪次
方大小醉顽。也就是說 HashMap 總是使用 2 的冪作為哈希表的大小沼溜，后面會介紹到為什么是
2 的冪次方。
底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化游添，當鏈表長
度大于閾值（默認為 8）時系草，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間唆涝。Hashtable 沒有這
樣的機制悄但。
推薦使用：在 Hashtable 的類注釋可以看到，Hashtable 是保留類不建議使用石抡，推薦在
單線程環(huán)境下使用 HashMap 替代檐嚣，如果需要多線程使用則用 ConcurrentHashMap 替
代。
如何決定使用 HashMap 還是 TreeMap啰扛？
對于在 Map 中插入嚎京、刪除和定位元素這類操作，HashMap 是最好的選擇隐解。然而鞍帝，假如你
需要對一個有序的 key 集合進行遍歷，TreeMap 是更好的選擇煞茫∨劣浚基于你的 collection 的大
小摄凡，也許向 HashMap 中添加元素會更快，將 map 換為 TreeMap 進行有序 key 的遍歷蚓曼。
HashMap 和 ConcurrentHashMap 的區(qū)別
ConcurrentHashMap 對整個桶數(shù)組進行了分割分段(Segment)亲澡，然后在每一個分段上都
用 lock 鎖進行保護，相對于 HashTable 的 synchronized 鎖的粒度更精細了一些纫版，并發(fā)性
能更好床绪，而 HashMap 沒有鎖機制，不是線程安全的其弊。（JDK1.8 之后 ConcurrentHashMap
啟用了一種全新的方式實現(xiàn),利用 CAS 算法癞己。）HashMap 的鍵值對允許有 null，但是 ConCurrentHashMap 都不允許梭伐。
ConcurrentHashMap 和 Hashtable 的區(qū)別痹雅？
ConcurrentHashMap 和 Hashtable 的區(qū)別主要體現(xiàn)在實現(xiàn)線程安全的方式上不同。
底層數(shù)據(jù)結(jié)構(gòu)： JDK1.7 的 ConcurrentHashMap 底層采用 分段的數(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 的主體铃将，鏈表則是主要為了解決哈希沖突而存在的；
實現(xiàn)線程安全的方式（重要）： ① 在 JDK1.7 的時候哑梳，ConcurrentHashMap（分段鎖） 對
整個桶數(shù)組進行了分割分段(Segment)劲阎，每一把鎖只鎖容器其中一部分數(shù)據(jù)，多線程訪問容
器里不同數(shù)據(jù)段的數(shù)據(jù)鸠真，就不會存在鎖競爭悯仙，提高并發(fā)訪問率。（默認分配 16 個 Segment吠卷，
比 Hashtable 效率提高 16 倍锡垄。） 到了 JDK1.8 的時候已經(jīng)摒棄了 Segment 的概念，而是
直接用 Node 數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)祭隔，并發(fā)控制使用 synchronized 和
CAS 來操作货岭。（JDK1.6 以后 對 synchronized 鎖做了很多優(yōu)化） 整個看起來就像是優(yōu)化
過且線程安全的 HashMap，雖然在 JDK1.8 中還能看到 Segment 的數(shù)據(jù)結(jié)構(gòu)疾渴，但是已
經(jīng)簡化了屬性千贯，只是為了兼容舊版本；② Hashtable(同一把鎖) :使用 synchronized 來保
證線程安全搞坝，效率非常低下搔谴。當一個線程訪問同步方法時，其他線程也訪問同步方法桩撮，可能
會進入阻塞或輪詢狀態(tài)敦第，如使用 put 添加元素峰弹，另一個線程不能使用 put 添加元素，也
不能使用 get芜果，競爭會越來越激烈效率越低鞠呈。
兩者的對比圖：
HashTable:JDK1.7 的 ConcurrentHashMap：
JDK1.8 的 ConcurrentHashMap（TreeBin: 紅黑二叉樹節(jié)點 Node: 鏈表節(jié)點）：
答：ConcurrentHashMap 結(jié)合了 HashMap 和 HashTable 二者的優(yōu)勢。HashMap 沒
有考慮同步师幕，HashTable 考慮了同步的問題粟按。但是 HashTable 在每次同步執(zhí)行時都要鎖
住整個結(jié)構(gòu)诬滩。 ConcurrentHashMap 鎖的方式是稍微細粒度的霹粥。
ConcurrentHashMap 底層具體實現(xiàn)知道嗎？實現(xiàn)原理是什么疼鸟？
JDK1.7
首先將數(shù)據(jù)分為一段一段的存儲后控，然后給每一段數(shù)據(jù)配一把鎖，當一個線程占用鎖訪問其中
一個段數(shù)據(jù)時空镜，其他段的數(shù)據(jù)也能被其他線程訪問浩淘。
在 JDK1.7 中，ConcurrentHashMap 采用 Segment + HashEntry 的方式進行實現(xiàn)吴攒，結(jié)構(gòu)如下：
一個 ConcurrentHashMap 里包含一個 Segment 數(shù)組张抄。Segment 的結(jié)構(gòu)和 HashMap
類似，是一種數(shù)組和鏈表結(jié)構(gòu)洼怔，一個 Segment 包含一個 HashEntry 數(shù)組署惯，每個
HashEntry 是一個鏈表結(jié)構(gòu)的元素，每個 Segment 守護著一個 HashEntry 數(shù)組里的元
素镣隶，當對 HashEntry 數(shù)組的數(shù)據(jù)進行修改時极谊，必須首先獲得對應(yīng)的 Segment 的鎖。
該類包含兩個靜態(tài)內(nèi)部類 HashEntry 和 Segment 安岂；前者用來封裝映射表的鍵值對轻猖，后
者用來充當鎖的角色；
Segment 是一種可重入的鎖 ReentrantLock域那，每個 Segment 守護一個 HashEntry 數(shù)
組里得元素咙边，當對 HashEntry 數(shù)組的數(shù)據(jù)進行修改時，必須首先獲得對應(yīng)的 Segment 鎖次员。
JDK1.8
在 JDK1.8 中样眠，放棄 了 Segment 臃腫的設(shè) 計，取而代之的 是采用 Node + CAS +
Synchronized 來保證并發(fā)安全進行實現(xiàn)翠肘，synchronized 只鎖定當前鏈表或紅黑二叉樹的
首節(jié)點檐束，這樣只要 hash 不沖突，就不會產(chǎn)生并發(fā)束倍，效率又提升 N 倍被丧。
結(jié)構(gòu)如下：附加源碼盟戏，有需要的可以看看
插入元素過程（建議去看看源碼）：
如果相應(yīng)位置的 Node 還沒有初始化，則調(diào)用 CAS 插入相應(yīng)的數(shù)據(jù)甥桂；
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break;
// no lock when adding to empty bin
}
如果相應(yīng)位置的 Node 不為空柿究，且當前該節(jié)點不處于移動狀態(tài)，則對該節(jié)點加 synchronized
鎖黄选，如果該節(jié)點的 hash 不小于 0蝇摸，則遍歷鏈表更新節(jié)點或插入新節(jié)點；
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value, null);
break;
}
}
}
如果該節(jié)點是 TreeBin 類型的節(jié)點办陷，說明是紅黑樹結(jié)構(gòu)貌夕，則通過 putTreeVal 方法往紅黑樹
中插入節(jié)點；如果 binCount 不為 0民镜，說明 put 操作對數(shù)據(jù)產(chǎn)生了影響啡专，如果當前鏈表的個
數(shù)達到 8 個，則通過 treeifyBin 方法轉(zhuǎn)化為紅黑樹制圈，如果 oldVal 不為空们童，說明是一次更新
操作，沒有對元素個數(shù)產(chǎn)生影響鲸鹦，則直接返回舊值慧库；
如果插入的是一個新節(jié)點，則執(zhí)行 addCount()方法嘗試更新元素個數(shù) baseCount馋嗜；
輔助工具類
Array 和 ArrayList 有何區(qū)別齐板？
Array 可以存儲基本數(shù)據(jù)類型和對象，ArrayList 只能存儲對象嵌戈。
Array 是指定固定大小的覆积，而 ArrayList 大小是自動擴展的。Array 內(nèi)置方法沒有 ArrayList 多熟呛，比如 addAll宽档、removeAll、iteration 等方法只有
ArrayList 有庵朝。
對于基本類型數(shù)據(jù)吗冤，集合使用自動裝箱來減少編碼工作量。但是九府，當處理固定大小的基本數(shù)
據(jù)類型的時候椎瘟，這種方式相對比較慢。
如何實現(xiàn) Array 和 List 之間的轉(zhuǎn)換侄旬？
Array 轉(zhuǎn) List： Arrays. asList(array) 肺蔚；
List 轉(zhuǎn) Array：List 的 toArray() 方法。
comparable 和 comparator 的區(qū)別儡羔？
comparable 接口實際上是出自 java.lang 包宣羊，它有一個 compareTo(Object obj)方法用來
排序
comparator 接口實際上是出自 java.util 包璧诵，它有一個 compare(Object obj1, Object
obj2)方法用來排序
一般我們需要對一個集合使用自定義排序時，我們就要重寫 compareTo 方法或 compare
方法仇冯，當我們需要對某一個集合實現(xiàn)兩種排序方式之宿，比如一個 song 對象中的歌名和歌手名
分別采用一種排序方法的話，我們可以重寫 compareTo 方法和使用自制的 Comparator
方法或者以兩個 Comparator 來實現(xiàn)歌名排序和歌星名排序苛坚，第二種代表我們只能使用兩
個參數(shù)版的 Collections.sort().
Collection 和 Collections 有什么區(qū)別比被？
java.util.Collection 是一個集合接口（集合類的一個頂級接口）。它提供了對集合對象進行
基本操作的通用接口方法泼舱。Collection 接口在 Java 類庫中有很多具體的實現(xiàn)等缀。Collection接口的意義是為各種具體的集合提供了最大化的統(tǒng)一操作方式，其直接繼承接口有 List 與
Set柠掂。
Collections 則是集合類的一個工具類/幫助類项滑，其中提供了一系列靜態(tài)方法依沮，用于對集合中
元素進行排序涯贞、搜索以及線程安全等各種操作。
TreeMap 和 TreeSet 在排序時如何比較元素危喉？Collections 工具類中的 sort()方法如何
比較元素宋渔？
TreeSet 要求存放的對象所屬的類必須實現(xiàn) Comparable 接口，該接口提供了比較元素的
compareTo()方法辜限，當插入元素時會回調(diào)該方法比較元素的大小皇拣。TreeMap 要求存放的鍵
值對映射的鍵必須實現(xiàn) Comparable 接口從而根據(jù)鍵對元素進 行排 序。
Collections 工具類的 sort 方法有兩種重載的形式薄嫡，
第一種要求傳入的待排序容器中存放的對象比較實現(xiàn) Comparable 接口以實現(xiàn)元素的比
較氧急；
第二種不強制性的要求容器中的元素必須可比較，但是要求傳入第二個參數(shù)毫深，參數(shù)是
Comparator 接口的子類型（需要重寫 compare 方法實現(xiàn)元素的比較）吩坝，相當于一個臨時
定義的排序規(guī)則，其實就是通過接口注入比較元素大小的算法哑蔫，也是對回調(diào)模式的應(yīng)用（Java
中對函數(shù)式編程的支持）钉寝。
