現(xiàn)在是晚上11點了，學(xué)校屠豬館的自習室因為太晚要關(guān)閉了，勤奮且疲憊的小魯班也從屠豬館出來了，正準備回宿舍洗洗睡，由于自習室位置比較偏僻所以是接收不到手機網(wǎng)絡(luò)信號的，因此小魯班從兜里掏出手機的時候，信息可真是炸了呀，小魯班心想，微信群平時都沒什么人聊天，今晚肯定是發(fā)生了什么大事，仔細一看，才發(fā)現(xiàn)原來是小魯班的室友達摩（光頭）拿到了阿里巴巴JAVA開發(fā)實習生的offer，此時小魯班真替他室友感到高興的同時，心里也難免會產(chǎn)生一絲絲的失落感，那是因為自己投了很多份簡歷，別說拿不拿得到offer，就連給面試邀的公司也都寥寥無幾，小魯班這會可真是受到了一萬點真實暴擊，不過小魯班還是很樂觀的，很快調(diào)整了心態(tài)，帶上耳機，慢慢的走回了宿舍，正打算準備向他那神室友達摩取取經(jīng)。

片刻后~

小魯班：666，聽說你拿到了阿里的offer，能透露一下面試內(nèi)容和技巧嗎

達摩：嘿嘿嘿，沒問題鴨，叫聲爸爸我就告訴你

小魯班：baba（表面笑嘻嘻，心里MMP）

達摩：其實我也不是很記得了（請繼續(xù)裝），但我還是記得那么一些，如果你是面的JAVA，首先當然是

• JAVA的基礎(chǔ)知識： 數(shù)據(jù)結(jié)構(gòu)（Map,List,Set等）,設(shè)計模式，算法，線程相關(guān)，IO/NIO，序列化等等

• 其次是高級特征： 反射機制，并發(fā)與鎖，JVM（GC策略，類加載機制，內(nèi)存模型）等等

小魯班：問這么多內(nèi)容，那豈不是一個人都面試很久嗎？

達摩：不是的，面試官一般都會用連環(huán)炮的方式提問的。

小魯班：你說的連環(huán)炮是什么意思鴨？

達摩：那我舉個例子

就比如問你HashMap是不是有序的？

你回答不是有序的。那面試官就會可能繼續(xù)問你，有沒有有序的Map實現(xiàn)類呢？

你如果這個時候說不知道的話，那這塊問題就到此結(jié)束了。如果你說有TreeMap和LinkedHashMap。

那么面試官接下來就可能會問你，TreeMap和LinkedHashMap是如何保證它的順序的？

如果你回答不上來，那么到此為止。如果你說TreeMap是通過實現(xiàn)SortMap接口，能夠把它保存的鍵值對根據(jù)key排序，基于紅黑樹，從而保證TreeMap中所有鍵值對處于有序狀 態(tài)。LinkedHashMap則是通過插入排序（就是你put的時候的順序是什么，取出來的時候就是什么樣子）和訪問排序（改變排序把訪問過的放到底部）讓鍵值有序。

那么面試官還會繼續(xù)問你，你覺得它們兩個哪個的有序?qū)崿F(xiàn)比較好？

如果你依然可以回答的話，那么面試官會繼續(xù)問你，你覺得還有沒有比它更好或者更高效的實現(xiàn)方式。。無窮無盡深入，直到你回答不出來或者面試官認為問題到底了

小魯班捏了一把汗，我去。。。這是魔鬼吧，那我們來試試唄（因為小魯班剛剛在自習室才看了這章的知識，想趁機裝一波逼，畢竟剛剛叫了聲爸爸~~）

于是達摩and小魯班就開始了對決：

1、為什么用HashMap？

• HashMap是一個散列桶（數(shù)組和鏈表），它存儲的內(nèi)容是鍵值對(key-value)映射

• HashMap采用了數(shù)組和鏈表的數(shù)據(jù)結(jié)構(gòu)，能在查詢和修改方便繼承了數(shù)組的線性查找和鏈表的尋址修改

• HashMap是非synchronized，所以HashMap很快

• HashMap可以接受null鍵和值，而Hashtable則不能（原因就是equlas()方法需要對象，因為HashMap是后出的API經(jīng)過處理才可以）

2、HashMap的工作原理是什么？

• HashMap是基于hashing的原理，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象。當我們給put()方法傳遞鍵和值時，我們先對鍵調(diào)用hashCode()方法，計算并返回的hashCode是用于找到Map數(shù)組的bucket位置來儲存Node 對象。這里關(guān)鍵點在于指出，HashMap是在bucket中儲存鍵對象和值對象，作為Map.Node 。

• 以下是HashMap初始化 ，簡單模擬數(shù)據(jù)結(jié)構(gòu)

Node[] table=new Node[16]  散列桶初始化，table  
class Node {  
 hash;//hash值  
      key;//鍵  
 value;//值  
 node next;//用于指向鏈表的下一層（產(chǎn)生沖突，用拉鏈法）  
  
}  

• 以下是具體的put過程（JDK1.8版）

1、對Key求Hash值，然后再計算下標

2、如果沒有碰撞，直接放入桶中（碰撞的意思是計算得到的Hash值相同，需要放到同一個bucket中）

3、如果碰撞了，以鏈表的方式鏈接到后面

4、如果鏈表長度超過閥值( TREEIFY THRESHOLD==8)，就把鏈表轉(zhuǎn)成紅黑樹，鏈表長度低于6，就把紅黑樹轉(zhuǎn)回鏈表

5、如果節(jié)點已經(jīng)存在就替換舊值

6、如果桶滿了(容量16*加載因子0.75)，就需要 resize（擴容2倍后重排）

• 以下是具體get過程(考慮特殊情況如果兩個鍵的hashcode相同，你如何獲取值對象？)

當我們調(diào)用get()方法，HashMap會使用鍵對象的hashcode找到bucket位置，找到bucket位置之后，會調(diào)用keys.equals()方法去找到鏈表中正確的節(jié)點，最終找到要找的值對象。

3、有什么方法可以減少碰撞？

• 擾動函數(shù)可以減少碰撞，原理是如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這就意味著存鏈表結(jié)構(gòu)減小，這樣取值的話就不會頻繁調(diào)用equal方法，這樣就能提高HashMap的性能。（擾動即Hash方法內(nèi)部的算法實現(xiàn)，目的是讓不同對象返回不同hashcode。）

• 使用不可變的、聲明作final的對象，并且采用合適的equals()和hashCode()方法的話，將會減少碰撞的發(fā)生。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個獲取對象的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇。為什么String, Interger這樣的wrapper類適合作為鍵？因為String是final的，而且已經(jīng)重寫了equals()和hashCode()方法了。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。

4、HashMap中hash函數(shù)怎么是是實現(xiàn)的?

我們可以看到在hashmap中要找到某個元素，需要根據(jù)key的hash值來求得對應(yīng)數(shù)組中的位置。如何計算這個位置就是hash算法。前面說過hashmap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，所以我們當然希望這個hashmap里面的元素位置盡量的分布均勻些，盡量使得每個位置上的元素數(shù)量只有一個，那么當我們用hash算法求得這個位置的時候，馬上就可以知道對應(yīng)位置的元素就是我們要的，而不用再去遍歷鏈表。所以我們首先想到的就是把hashcode對數(shù)組長度取模運算，這樣一來，元素的分布相對來說是比較均勻的。但是，“?！边\算的消耗還是比較大的，能不能找一種更快速，消耗更小的方式，我們來看看JDK1.8的源碼是怎么做的（被樓主修飾了一下）

static final int hash(Object key) {  
    if (key == null){  
        return 0;  
    }  
     int h;  
     h=key.hashCode()；返回散列值也就是hashcode  
      // ^ ：按位異或  
      // >>>:無符號右移，忽略符號位，空位都以0補齊  
      //其中n是數(shù)組的長度，即Map的數(shù)組部分初始化長度  
     return  (n-1)&(h ^ (h >>> 16));  
}  

簡單來說就是

1、高16bt不變，低16bit和高16bit做了一個異或(得到的HASHCODE轉(zhuǎn)化為32位的二進制，前16位和后16位低16bit和高16bit做了一個異或)

2、(n·1)&hash=->得到下標

5、拉鏈法導(dǎo)致的鏈表過深問題為什么不用二叉查找樹代替，而選擇紅黑樹？為什么不一直使用紅黑樹？

之所以選擇紅黑樹是為了解決二叉查找樹的缺陷，二叉查找樹在特殊情況下會變成一條線性結(jié)構(gòu)（這就跟原來使用鏈表結(jié)構(gòu)一樣了，造成很深的問題），遍歷查找會非常慢。而紅黑樹在插入新數(shù)據(jù)后可能需要通過左旋，右旋、變色這些操作來保持平衡，引入紅黑樹就是為了查找數(shù)據(jù)快，解決鏈表查詢深度的問題，我們知道紅黑樹屬于平衡二叉樹，但是為了保持“平衡”是需要付出代價的，但是該代價所損耗的資源要比遍歷線性鏈表要少，所以當長度大于8的時候，會使用紅黑樹，如果鏈表長度很短的話，根本不需要引入紅黑樹，引入反而會慢。

6、說說你對紅黑樹的見解？

1、每個節(jié)點非紅即黑

2、根節(jié)點總是黑色的

3、如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的（反之不一定）

4、每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）

5、從根節(jié)點到葉節(jié)點或空子節(jié)點的每條路徑，必須包含相同數(shù)目的黑色節(jié)點（即相同的黑色高度）

7、解決hash 碰撞還有那些辦法？

開放定址法。

當沖突發(fā)生時，使用某種探查技術(shù)在散列表中形成一個探查(測)序列。沿此序列逐個單元地查找，直到找到給定的地址。

按照形成探查序列的方法不同，可將開放定址法區(qū)分為線性探查法、二次探查法、雙重散列法等。

下面給一個線性探查法的例子

問題：已知一組關(guān)鍵字為(26，36，41，38，44，15，68，12，06，51)，用除余法構(gòu)造散列函數(shù)，用線性探查法解決沖突構(gòu)造這組關(guān)鍵字的散列表。

解答：為了減少沖突，通常令裝填因子α由除余法因子是13的散列函數(shù)計算出的上述關(guān)鍵字序列的散列地址為(0，10，2，12，5，2，3，12，6，12)。

前5個關(guān)鍵字插入時，其相應(yīng)的地址均為開放地址，故將它們直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。

當插入第6個關(guān)鍵字15時，其散列地址2(即h(15)=15％13=2)已被關(guān)鍵字41(15和41互為同義詞)占用。故探查h1=(2+1)％13=3，此地址開放，所以將15放入T[3]中。

當插入第7個關(guān)鍵字68時，其散列地址3已被非同義詞15先占用，故將其插入到T[4]中。

當插入第8個關(guān)鍵字12時，散列地址12已被同義詞38占用，故探查hl=(12+1)％13=0，而T[0]亦被26占用，再探查h2=(12+2)％13=1，此地址開放，可將12插入其中。

類似地，第9個關(guān)鍵字06直接插入T[6]中；而最后一個關(guān)鍵字51插人時，因探查的地址12，0，1，…，6均非空，故51插入T[7]中。

8、如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦？

默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組，來重新調(diào)整map的大小，并將原來的對象放入新的bucket數(shù)組中。這個過程叫作rehashing，因為它調(diào)用hash方法找到新的bucket位置。這個值只可能在兩個地方，一個是原下標的位置，另一種是在下標為<原下標+原容量>的位置

9、重新調(diào)整HashMap大小存在什么問題嗎？

• 當重新調(diào)整HashMap大小的時候，確實存在條件競爭，因為如果兩個線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了，它們會同時試著調(diào)整大小。在調(diào)整大小的過程中，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發(fā)生了，那么就死循環(huán)了。(多線程的環(huán)境下不使用HashMap）

• 為什么多線程會導(dǎo)致死循環(huán)，它是怎么發(fā)生的？

HashMap的容量是有限的。當經(jīng)過多次元素插入，使得HashMap達到一定飽和度時，Key映射位置發(fā)生沖突的幾率會逐漸提高。這時候，HashMap需要擴展它的長度，也就是進行Resize。1.擴容：創(chuàng)建一個新的Entry空數(shù)組，長度是原數(shù)組的2倍。2.ReHash：遍歷原Entry數(shù)組，把所有的Entry重新Hash到新數(shù)組。

（這個過程比較燒腦，暫不作流程圖演示，有興趣去看看我的另一篇博文"HashMap擴容全過程"）

達摩：哎呦，小老弟不錯嘛~~意料之外呀

小魯班：嘿嘿，優(yōu)秀吧，中場休息一波，我先喝口水

達摩：不僅僅是這些哦，面試官還會問你相關(guān)的集合類對比，比如：

10、HashTable

• 數(shù)組 + 鏈表方式存儲

• 默認容量：11(質(zhì)數(shù) 為宜)

• put:

• 索引計算 : （key.hashCode() & 0x7FFFFFFF）% table.length

• 若在鏈表中找到了，則替換舊值，若未找到則繼續(xù)

• 當總元素個數(shù)超過容量*加載因子時，擴容為原來 2 倍并重新散列。

• 將新元素加到鏈表頭部

• 對修改 Hashtable 內(nèi)部共享數(shù)據(jù)的方法添加了 synchronized，保證線程安全。

11、HashMap ，HashTable 區(qū)別

• 默認容量不同。擴容不同

• 線程安全性，HashTable 安全

• 效率不同 HashTable 要慢因為加鎖

12、ConcurrentHashMap 原理

1、最大特點是引入了 CAS（借助 Unsafe 來實現(xiàn)【native code】）

• CAS有3個操作數(shù)，內(nèi)存值V，舊的預(yù)期值A(chǔ)，要修改的新值B。當且僅當預(yù)期值A(chǔ)和內(nèi)存值V相同時，將內(nèi)存值V修改為B，否則什么都不做。

• Unsafe 借助 CPU 指令 cmpxchg 來實現(xiàn)

• 使用實例：

1、對 sizeCtl 的控制都是用 CAS 來實現(xiàn)的

1、sizeCtl ：默認為0，用來控制 table 的初始化和擴容操作。

• -1 代表table正在初始化

• N 表示有 -N-1 個線程正在進行擴容操作

• 如果table未初始化，表示table需要初始化的大小。

• 如果table初始化完成，表示table的容量，默認是table大小的0.75倍，居然用這個公式算0.75（n - (n >>> 2)）。

4、CAS 會出現(xiàn)的問題：ABA

• 對變量增加一個版本號，每次修改，版本號加 1，比較的時候比較版本號。

13、我們可以使用CocurrentHashMap來代替Hashtable嗎？

• 我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據(jù)同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的線程安全性。它們都可以用于多線程的環(huán)境，但是當Hashtable的大小增加到一定的時候，性能會急劇下降，因為迭代時需要被鎖定很長的時間。因為ConcurrentHashMap引入了分割(segmentation)，不論它變得多么大，僅僅需要鎖定map的某個部分，而其它的線程不需要等到迭代完成才能訪問map。簡而言之，在迭代的過程中，ConcurrentHashMap僅僅鎖定map的某個部分，而Hashtable則會鎖定整個map。

此時躺著床上的張飛哄了一聲：睡覺了睡覺了~

見此不太妙：小魯班立馬回到床上（泉水），把被子蓋過頭，心里有一絲絲愉悅感，不對。好像還沒洗澡。。。

by the way

CocurrentHashMap在JAVA8中存在一個bug，會進入死循環(huán)，原因是遞歸創(chuàng)建ConcurrentHashMap 對象，但是在1.9已經(jīng)修復(fù)了,場景重現(xiàn)如下

public class ConcurrentHashMapDemo{  
  
    private Map<Integer,Integer> cache =new ConcurrentHashMap<>(15);  
  
    public static void main(String[]args){  
        ConcurrentHashMapDemo ch =    new ConcurrentHashMapDemo();  
        System.out.println(ch.fibonaacci(80));  
    }  
  
    public int fibonaacci(Integer i){  
        if(i==0||i ==1) {  
            return i;  
    }  
  
    return cache.computeIfAbsent(i,(key) -> {  
        System.out.println("fibonaacci : "+key);  
        return fibonaacci(key -1)+fibonaacci(key - 2);  
    });  
  
    }  
}