前言
從這章開始，我們正式進(jìn)入Java代碼的相關(guān)面試，部分較為基礎(chǔ)的、帶坑的面試題我將放在《漫聊系列》里面，而體系相對較為龐大的內(nèi)容我將單獨(dú)分為一個(gè)章節(jié)放在本系列當(dāng)中進(jìn)行講解炬转。
我們先來看Java中的集合荐吵，集合不僅是面試問的多，日常使用也多，只不過有許多細(xì)節(jié)在我們使用的過程沒有留意，而這些細(xì)節(jié)便是面試經(jīng)常問的內(nèi)容粮呢。下面我們通過幾道常問的面試題進(jìn)行相關(guān)知識點(diǎn)的學(xué)習(xí)：
1. Map懒浮，List 和 Set 的區(qū)別。
2. ArrayList隨機(jī)增刪效率真的比LinkedList低嗎？
3. HashMap 的擴(kuò)容過程是怎么樣的？
4. HashMap 是線程安全的嗎侵歇，為什么不是線程安全的(JDK7,8)骂澄？
5. 編寫一個(gè)LRU緩存工具類
本系列不會講解過多的源碼坟冲，只會以結(jié)論的形式給讀者直接提供面試題的答案紊遵，如果讀者需要往更深層次發(fā)展娃善，可以去閱覽相應(yīng)的博客進(jìn)行深度學(xué)習(xí)。
在進(jìn)入具體講解之前瑞佩，我們先看看java的集合家族：
通過上面兩張圖咧最，我們可以基本了解到集合分為兩大類，分布是Collection和Map御雕，接下來，我們會根據(jù)面試題進(jìn)一步講解這兩大集合類的點(diǎn)點(diǎn)滴滴滥搭。
1. Map酸纲，List 和 Set 的區(qū)別
Map 存儲的是映射關(guān)系即 key-value 鍵值對，而Collection存儲的是單列的集合瑟匆，其中List子類可以有序的存儲重復(fù)的值闽坡，而 Set 子類存儲無序并且不可重復(fù)的值。
一般來說愁溜，大部分人都能回答以上兩點(diǎn)疾嗅，但是回答完這些，只能說是基本知識掌握了冕象，更深層次的問題會問：
- Map 沒有繼承 Iterable 接口代承，他是如何實(shí)現(xiàn)循環(huán)的？
- Set 是利用什么來實(shí)現(xiàn)不可重復(fù)的渐扮？
以上問題就算面試官不問论悴，但是也盡量回答一下掖棉，基本上能回答這兩個(gè)問題說明你對Java的集合有更深層次的了解。
- Map 沒有繼承 Iterable 接口膀估，他是如何實(shí)現(xiàn)foreach循環(huán)的?
第一個(gè)問題幔亥，Map 類通過使用一個(gè) Set 類來實(shí)現(xiàn)一種類似于視圖的功能，并利用這個(gè) Set 實(shí)現(xiàn) foreach （因?yàn)?Set 頂層是 Iterable 接口）察纯，但是實(shí)際上這個(gè) Set 類的方法在實(shí)現(xiàn)上都是通過調(diào)用 Map 自身的方法或字段帕棉，即該 Set 類只能算是一種工具類，本身不存儲數(shù)據(jù)饼记，下面我們通過 HashMap 來簡單了解下 Map 如何通過 EntrySet 類實(shí)現(xiàn)相關(guān)功能笤昨。
EntrySet與Map的關(guān)系.png
- Map 沒有繼承 Iterable 接口膀估，他是如何實(shí)現(xiàn)foreach循環(huán)的?
可能會有人問為什么 Map 不直接繼承 Iterable 或 Collection 接口從而獲取對應(yīng)的循環(huán)功能，這里涉及到一個(gè)面向?qū)ο蟮慕涌诜蛛x原則握恳，由于 Map 主要是存儲一系列的鍵值對操作瞒窒，有針對鍵值對的操作方式，而 Collection 是存儲一個(gè)個(gè)符合某個(gè)特征對象的集合乡洼，操作方式與 Map 不一樣崇裁，再細(xì)一點(diǎn)講，Map并不算集合的一員束昵，如果想對 Map 進(jìn)行遍歷操作拔稳，則可以利用組合的方式，“借用” Collection 的特性來實(shí)現(xiàn) Map 的遍歷锹雏，而無需添加 Map 類的負(fù)擔(dān)巴比。
-
- Set 是利用什么來實(shí)現(xiàn)不可重復(fù)的？
先說結(jié)論礁遵，Set 本質(zhì)上是只有 key 的 Map轻绞，因?yàn)?Map 的 key 是不允許重復(fù)的，重復(fù)的話就無法指定一個(gè) key 搜索正確的 value 了佣耐。
同 Map 不直接繼承 Collection 或 Iterable 接口的理由一樣政勃，既然已經(jīng)有接口實(shí)現(xiàn)了對某個(gè)值的重復(fù)判定，那我就利用組合的形式借用一下這種特性兼砖，因此在 HashSet 中奸远，里面會有個(gè) HashMap 字段，當(dāng)我們 new HashSet() 的時(shí)候讽挟，構(gòu)造函數(shù)里面代碼其實(shí)是 new HashMap() 懒叛；我們調(diào)用 Set 的 add() 方法實(shí)際上就是將對象存入 HashMap當(dāng)中，只不過 value 為 同一個(gè)Object對象罷了耽梅。
下面我們通過一張圖來了解下 HashSet 如何組合 HashMap 實(shí)現(xiàn)其基本的方法薛窥。
HashSet
經(jīng)過上面兩個(gè)問題，不知道讀者有沒有看出一些共同點(diǎn)褐墅。 Set 這個(gè)類本身都不存數(shù)據(jù)拆檬，一直是一個(gè)“工具人” 的身份洪己，真正存數(shù)據(jù)的類最終還是歸屬于 Map 來存，即便是 TreeSet竟贯，內(nèi)部也是引用了一個(gè) TreeMap 類的字段答捕，只不過這些 Map 引用的 value 可能為 null 也可能為同一個(gè) Object。Set 只不過在對數(shù)據(jù)操作的時(shí)候可能有一些額外的操作屑那，即 Set 可以說是 Map 的視圖拱镐。
- Set 是利用什么來實(shí)現(xiàn)不可重復(fù)的？
2. ArrayList隨機(jī)增刪效率真的比LinkedList低嗎
很多時(shí)候，面試都會問 ArrayList 和 LinkedList 的區(qū)別持际，大部分人都能回答出
ArrayList 基于數(shù)組 沃琅， LinkedList 基于鏈表，前者的隨機(jī)訪問效率高蜘欲，后者的隨機(jī)增刪效率高益眉。
大體上，這應(yīng)該是90%面試人都會回答的內(nèi)容姥份，但是郭脂，在執(zhí)行效率上，如果不區(qū)分業(yè)務(wù)場景直接這樣回答澈歉，就無法體現(xiàn)出你在日常開發(fā)中有沒有根據(jù)業(yè)務(wù)進(jìn)行技術(shù)選型展鸡。
接下來讓我們了解下兩者在一些操作中的性能開銷情況：
| 操作 | ArrayList | LinkedList |
|---|---|---|
| 隨機(jī)查詢 | 由于是數(shù)組，幾乎無開銷 | 需要從鏈表頭進(jìn)行遍歷 |
| 隨機(jī)插入 | 1.插入位置后的數(shù)組后移 2.可能出現(xiàn)數(shù)組擴(kuò)容帶來的開銷 |
1.需要從鏈表頭進(jìn)行遍歷 2.對node節(jié)點(diǎn)進(jìn)行new |
| 隨機(jī)刪除 | 數(shù)組遷移 | 需要從鏈表頭進(jìn)行遍歷 |
從上表可以看出埃难，
- ArrayList 的開銷主要體現(xiàn)在數(shù)組的部分遷移以及數(shù)組擴(kuò)容莹弊。
- LinkedList 的開銷體現(xiàn)在鏈表的遍歷以及新增時(shí)候?qū)?node 節(jié)點(diǎn)的 new 操作。
如果業(yè)務(wù)場景是：
1. 預(yù)先知道數(shù)組大小區(qū)間范圍
2. 需要大量的隨機(jī)訪問
3. 只需要在數(shù)組靠中后的位置進(jìn)行隨機(jī)增刪
那我們就選用 ArrayList
如果業(yè)務(wù)場景是:
1. 需要經(jīng)常在鏈表靠前的位置進(jìn)行數(shù)據(jù)隨機(jī)的新增（例如隊(duì)列）或刪除
2. 數(shù)組長度不可預(yù)知
那么我們就選用 LinkedList
因此涡尘，回答題目這個(gè)問題忍弛，主要還是體現(xiàn)在需要增刪的“位置”上，如果是在靠前位置的增刪悟衩，那么 LinkedList 效率高剧罩，反之，ArrayList 的效率高座泳。不過整體的隨機(jī)增刪，ArrayList 的效率整體也是相較于 LinkedList 高幕与，因此除非某些上述特定的場景挑势，大部分時(shí)候用 ArrayList 即可。想了解更多信息可以參考以下博客內(nèi)容：ArrayList和LinkedList插入效率對比
3. HashMap 的擴(kuò)容過程是怎么樣的啦鸣？
目前 HashMap 在筆試或者技術(shù)面中幾乎是100%考的一個(gè)知識點(diǎn)潮饱，因?yàn)?HashMap 涉及了數(shù)據(jù)結(jié)構(gòu)、功能設(shè)計(jì)诫给、算法等大量的知識點(diǎn)香拉，基本上能搞懂 HashMap 的底層啦扬，可以側(cè)面說明你個(gè)人編程能力方面，以及技術(shù)方面有鉆研的精神凫碌，因此扑毡，目前對 HashMap 底層了解只能算是 Java 開發(fā)人員的基本功。
由于網(wǎng)上關(guān)于 HashMap 底層原理的介紹已經(jīng)非常多了（需要補(bǔ)基礎(chǔ)的點(diǎn)擊這里HashMap源碼解析）盛险，接下來我會簡單通過動(dòng)圖的形式介紹下jdk1.7和1.8下 HashMap 的擴(kuò)容過程瞄摊。HashMap 本身是一個(gè)是一個(gè)數(shù)組+鏈表/紅黑樹(jdk1.8)的數(shù)據(jù)結(jié)構(gòu)，而存儲的每個(gè)數(shù)據(jù)元素都是一個(gè)Entry/Node(jdk1.8) 類苦掘，每次擴(kuò)容主要是針對數(shù)組進(jìn)行擴(kuò)容换帜，然后將元素的hash進(jìn)行一系列的操作獲取其在新數(shù)組的下標(biāo)值，然后存放到對應(yīng)的新數(shù)組位置上鹤啡。因此 HashMap 擴(kuò)容的核心主要是元素?cái)?shù)據(jù)的遷移惯驼，以下代碼為jdk1.7下 HashMap 元素遷移的核心代碼：
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
//循環(huán)數(shù)組
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
//循環(huán)鏈表
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
接下來讓我們看個(gè)動(dòng)圖來了解下jdk1.7下 HashMap 在擴(kuò)容的時(shí)候是如何將一個(gè)鏈表上的元素放入到新的數(shù)組里面：
而在jdk1.8下，HashMap 的數(shù)據(jù)遷移則進(jìn)行了一些優(yōu)化递瑰，具體操作是不再進(jìn)行rehash祟牲，而直接將舊數(shù)組的長度與元素的hashCode進(jìn)行與'&'操作(這里用的不是key的hash，而是Node的hash)泣矛，然后為0的元素存放到原本的下標(biāo)位置疲眷，而為1的則存到原本的下標(biāo)+舊數(shù)組長度的位置，下面通過擴(kuò)容源碼以及幾張圖簡單了解下jdk1.8下的 HashMap 如何進(jìn)行數(shù)據(jù)遷移您朽。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//.....判斷目前數(shù)組的長度或長度*2是否大于最大值狂丝，不是的話才進(jìn)行擴(kuò)容
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//數(shù)據(jù)遷移前便將table指向新數(shù)組
table = newTab;
//對老數(shù)據(jù)進(jìn)行遷移操作
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果這個(gè)鏈表只有一個(gè)元素，直接存放
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果這個(gè)節(jié)點(diǎn)屬于紅黑樹節(jié)點(diǎn)哗总，則進(jìn)行額外操作几颜，這里不做過多闡述
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//最核心的點(diǎn)，如果該鏈表有多個(gè)元素讯屈，進(jìn)行循環(huán)遷移
//這里將鏈表內(nèi)的元素分成了兩個(gè)鏈表蛋哭，一個(gè)是高位鏈表一個(gè)是低位鏈表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//通過舊數(shù)組長度與元素的hash進(jìn)行，如果為0則算入低位鏈表
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
//與操作結(jié)果為1涮母，設(shè)置高位鏈表元素
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//將低位鏈表放入新數(shù)組的原下標(biāo)中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//將高位鏈表放入新數(shù)組的原下標(biāo)+舊數(shù)組長度的位置中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
結(jié)合上面的代碼以及下面的動(dòng)圖谆趾，讀者應(yīng)該很容易理解jdk1.8下HashMap元素的遷移過程
了解完 HashMap 的擴(kuò)容過程，在下一節(jié)我們一起看看 HashMap 在高并發(fā)情況下多個(gè)線程進(jìn)行擴(kuò)容的時(shí)候會發(fā)生什么叛本。
jdk1.7下沪蓬，HashMap 在擴(kuò)容以及數(shù)據(jù)遷移結(jié)束后，才會將 table字段指向新的數(shù)組来候，而jdk1.8下跷叉，在數(shù)據(jù)遷移前便會將 table字段指向新的數(shù)組。
4. HashMap 是線程安全的嗎，為什么不是線程安全的云挟？
介紹完基本的擴(kuò)容過程梆砸，接下來就提一提 HashMap 高并發(fā)時(shí)候產(chǎn)生的線程安全問題，因?yàn)檫@個(gè)問題也是非常不好理解的（特別jdk1.7）园欣，下面讓我們一起看看如何回答這個(gè)面試題帖世。
首先出現(xiàn)線程不安全主要體現(xiàn)在兩個(gè)點(diǎn)：
- 多個(gè)線程同時(shí)進(jìn)行 put 操作的時(shí)候，可能出現(xiàn)添加的數(shù)據(jù)被覆蓋俊庇。
- 多個(gè)線程同時(shí)進(jìn)行擴(kuò)容的操作時(shí)狮暑，則容易出現(xiàn)環(huán)鏈表，導(dǎo)致下次有線程搜索相應(yīng)的 key 的時(shí)候進(jìn)入死循環(huán) 辉饱；而在 jdk1.8 以后由于使用了尾插法搬男，基本不會出現(xiàn)環(huán)形鏈表，但會出現(xiàn)數(shù)據(jù)丟失彭沼。
接下來讓我們看看缔逛，高并發(fā)擴(kuò)容的情況下，如何導(dǎo)致查詢死循環(huán)的：
可以看出姓惑，導(dǎo)致環(huán)形鏈表的原因就是“頭插法”褐奴，因?yàn)樵诿看蝖ashmap進(jìn)行數(shù)據(jù)遷移的時(shí)候，會將鏈表進(jìn)行倒置（如果剛好這個(gè)鏈表上面的數(shù)據(jù)rehash后都處于同一個(gè)新鏈表的話）于毙，而對掛起的線程來說他并不知道鏈表已經(jīng)被倒置了敦冬，因此在他進(jìn)行新一輪的遷移的時(shí)候，又會進(jìn)行一次倒置唯沮，最終導(dǎo)致相關(guān)的節(jié)點(diǎn)next指針指向了他前面的元素脖旱。
網(wǎng)上找了許多有關(guān)于高并發(fā)下HashMap導(dǎo)致線程死循環(huán)的博客，他們線程A的條件是處于 'Entry next = e.next;' 這個(gè)語句的時(shí)候進(jìn)行掛起介蛉，但是根據(jù)實(shí)際流程走下來萌庆，這種情況不會導(dǎo)致查詢的時(shí)候進(jìn)入死循環(huán)，而是在線程A進(jìn)行擴(kuò)容的時(shí)候就已經(jīng)進(jìn)入死循環(huán)了币旧，因?yàn)楹罄m(xù)的一個(gè)語句 'e.next = newTable[i];'會將當(dāng)前e的next指針指向一個(gè)非null值践险，因此這個(gè)線程會一直在while語句塊里面，有興趣的讀者可以自己一步一步走一遍流程吹菱。
在jdk1.8中巍虫，HashMap 的數(shù)據(jù)遷移改為“尾插法”，即鏈表的元素順序不會改變鳍刷，因此jdk1.8中的高并發(fā)下使用 HashMap 幾乎不會出現(xiàn)死循環(huán)的問題垫言，但是仍然會出現(xiàn)數(shù)據(jù)的丟失，具體丟失原因還是由于多個(gè)線程同時(shí)寫的時(shí)候出現(xiàn)了數(shù)據(jù)的覆蓋倾剿，無論是否處于擴(kuò)容狀態(tài)。
5. 編寫一個(gè)LRU緩存工具類
可能不少人在筆試或面試的時(shí)候都會遇到這個(gè)問題，那就是如何快速編寫一個(gè)LRU緩存的工具類前痘，有的讀者不明白為什么在集合這章節(jié)會出現(xiàn)LRU緩存凛捏，其實(shí)我們目前可以通過一個(gè) Map 實(shí)現(xiàn)類來迅速編寫一個(gè) LRU 緩存工具類，這個(gè) Map 類便是 LinkedHashMap芹缔。LinkedHashMap 繼承于 HashMap 坯癣，只不過重寫了 HashMap 中的Node 類，改為帶有前后指針的 Entry 類最欠。
可能許多人只以為 LinkedHashMap 只是一個(gè)有序的 HashMap 示罗，但這個(gè)有序是有兩個(gè)場景應(yīng)用的，在他的構(gòu)造函數(shù)里面是表明了你這個(gè)有序到底是插入順序還是訪問順序芝硬，如果我們要實(shí)現(xiàn)LRU緩存蚜点，那么我們就得選擇訪問順序。
下面代碼中拌阴，參數(shù) accessOrder 便是用來設(shè)置你是插入順序還是訪問順序绍绘，如果為true則為訪問順序，在其他構(gòu)造函數(shù)中迟赃，該成員變量都會默認(rèn)設(shè)置為false陪拘。
LinkedHashMap 當(dāng)中，如果 accessOrder 為 true纤壁，那么頭節(jié)點(diǎn)便屬于最少使用的節(jié)點(diǎn)左刽，而尾節(jié)點(diǎn)屬于最近使用過的節(jié)點(diǎn)
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
同時(shí)，在 HashMap 里面酌媒，就已經(jīng)提前準(zhǔn)備了相應(yīng)的回調(diào)方法：獲取節(jié)點(diǎn)后的回調(diào)欠痴、插入節(jié)點(diǎn)后的回調(diào)以及刪除節(jié)點(diǎn)后的回調(diào)：
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
而這些方法，LinkedHashMap 都進(jìn)行了重寫馍佑，接下來我們主要講解下獲取回調(diào)以及插入回調(diào)斋否。
- 獲取回調(diào)
獲取回調(diào)主要是將get的節(jié)點(diǎn)放入鏈表的尾部，即將當(dāng)前節(jié)點(diǎn)賦值給 tail 成員變量拭荤，如果該節(jié)點(diǎn)存在前后關(guān)聯(lián)的節(jié)點(diǎn)茵臭，那么便將前后關(guān)聯(lián)的節(jié)點(diǎn)進(jìn)行連接。 - 插入回調(diào)
插入回調(diào)最主要的是判斷是否要?jiǎng)h除頭節(jié)點(diǎn)舅世，從而實(shí)現(xiàn) LRU 緩存旦委，這個(gè)方法會調(diào)用一個(gè) removeEldestEntry() 方法來判斷是否刪除頭節(jié)點(diǎn)，而開發(fā)者便可以通過重寫這個(gè)方法來實(shí)現(xiàn)一些自定義的判斷邏輯雏亚，最終實(shí)現(xiàn)業(yè)務(wù)相關(guān)的 LRU 緩存
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
所以缨硝，如果我們要實(shí)現(xiàn)自己的 LRU 緩存工具類，只需要繼承 LinkedHashMap 罢低，并重寫其 removeEldestEntry 方法即可查辩，如果返回true胖笛，則代表要?jiǎng)h除節(jié)點(diǎn)。最后宜岛，我們看個(gè)簡單的例子长踊，來了解如何實(shí)現(xiàn)一個(gè)基本的LRU 緩存工具類。
public class LRUCache extends LinkedHashMap<String,Object> {
private static final int maxSize = 32;
public LRUCache(int initialCapacity, float loadFactor){
super(initialCapacity,loadFactor,true);
}
@Override
protected boolean removeEldestEntry(Map.Entry<String, Object> eldest) {
return this.size() > maxSize;
}
}
總結(jié)
本章節(jié)主要是介紹了集合中的一些平時(shí)經(jīng)常被忽略的細(xì)節(jié)萍倡，同時(shí)這些細(xì)節(jié)也是面試中常問的一些點(diǎn)身弊。集合作為一個(gè)開發(fā)人員經(jīng)常使用的技術(shù)點(diǎn)，頻繁的出現(xiàn)在我們的項(xiàng)目當(dāng)中列敲，要說不會用阱佛，那是不可能的，但是里面的一些細(xì)節(jié)點(diǎn)如功能設(shè)計(jì)戴而、底層原理等凑术，確實(shí)值得我們留意和思考。
接下來填硕，我們回到最初的五個(gè)問題
1. Map麦萤，List 和 Set 的區(qū)別。
2. ArrayList隨機(jī)增刪效率真的比LinkedList低嗎扁眯？
3. HashMap 的擴(kuò)容過程是怎么樣的壮莹？
4. HashMap 是線程安全的嗎，為什么不是線程安全的(JDK7,8)姻檀？
5. 編寫一個(gè)LRU緩存工具類
如果你們可以很流暢的回答這些問題命满，那么恭喜你，該章節(jié)的內(nèi)容已經(jīng)全部掌握绣版，如果不行胶台，希望可以回到對應(yīng)問題講解的地方，或者對某個(gè)不了解的點(diǎn)進(jìn)行額外的知識搜索杂抽，盡量用自己組織的語言回答這些問題诈唬。
