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

片刻后~

小魯班：666，聽說你拿到了阿里的 Offer，能透露一下面試內容和技巧嗎？
達摩：嘿嘿嘿，沒問題鴨，叫聲爸爸我就告訴你。
小魯班：耙耙（表面笑嘻嘻，心里MMP）
達摩：其實我也不是很記得了（請繼續(xù)裝），但我還是記得那么一些。如果你是面的 Java，首先當然是JAVA的基礎知識：數(shù)據(jù)結構（Map / List / Set等）、設計模式、算法、線程相關、IO/NIO、序列化等等。其次是高級特征：反射機制，并發(fā)與鎖，JVM（GC策略，類加載機制，內存模型）等等。
小魯班：問這么多內容，那豈不是一個人都面試很久嗎？
達摩：不是的，面試官一般都會用連環(huán)炮的方式提問的。
小魯班：你說的連環(huán)炮是什么意思鴨？
達摩：那我舉個例子：

• 就比如問你?HashMap 是不是有序的？你回答不是有序的。
• 那面試官就會可能繼續(xù)問你，有沒有有序的Map實現(xiàn)類呢？你如果這個時候說不知道的話，那這塊問題就到此結束了。如果你說有 TreeMap 和 LinkedHashMap。
• 那么面試官接下來就可能會問你，TreeMap 和 LinkedHashMap 是如何保證它的順序的？如果你回答不上來，那么到此為止。如果你說 TreeMap 是通過實現(xiàn) SortMap 接口，能夠把它保存的鍵值對根據(jù) key 排序，基于紅黑樹，從而保證 TreeMap 中所有鍵值對處于有序狀態(tài)。LinkedHashMap 則是通過插入排序（就是你 put 的時候的順序是什么，取出來的時候就是什么樣子）和訪問排序（改變排序把訪問過的放到底部）讓鍵值有序。
• 那么面試官還會繼續(xù)問你，你覺得它們兩個哪個的有序實現(xiàn)比較好？如果你依然可以回答的話，那么面試官會繼續(xù)問你，你覺得還有沒有比它更好或者更高效的實現(xiàn)方式？

無窮無盡深入，直到你回答不出來或者面試官認為問題到底了。

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

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

1、為什么用HashMap？

• HashMap 是一個散列桶（數(shù)組和鏈表），它存儲的內容是鍵值對 key-value 映射
• HashMap 采用了數(shù)組和鏈表的數(shù)據(jù)結構，能在查詢和修改方便繼承了數(shù)組的線性查找和鏈表的尋址修改
• HashMap 是非 synchronized，所以 HashMap 很快
• HashMap 可以接受 null 鍵和值，而 Hashtable 則不能（原因就是 equlas() 方法需要對象，因為 HashMap 是后出的 API 經過處理才可以）

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

HashMap 是基于 hashing 的原理

我們使用 put(key, value) 存儲對象到 HashMap 中，使用 get(key) 從 HashMap 中獲取對象。當我們給 put() 方法傳遞鍵和值時，我們先對鍵調用 hashCode() 方法，計算并返回的 hashCode 是用于找到 Map 數(shù)組的 bucket 位置來儲存 Node 對象。

這里關鍵點在于指出，HashMap 是在 bucket 中儲存鍵對象和值對象，作為Map.Node 。

以下是 HashMap 初始化

簡化的模擬數(shù)據(jù)結構：

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

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

1. 對 Key 求 Hash 值，然后再計算下標
2. 如果沒有碰撞，直接放入桶中（碰撞的意思是計算得到的 Hash 值相同，需要放到同一個 bucket 中）
3. 如果碰撞了，以鏈表的方式鏈接到后面
4. 如果鏈表長度超過閥值（TREEIFY THRESHOLD==8），就把鏈表轉成紅黑樹，鏈表長度低于6，就把紅黑樹轉回鏈表
5. 如果節(jié)點已經存在就替換舊值
6. 如果桶滿了（容量16*加載因子0.75），就需要 resize（擴容2倍后重排）

以下是具體 get 過程

考慮特殊情況：如果兩個鍵的 hashcode 相同，你如何獲取值對象？

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

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

擾動函數(shù)可以減少碰撞

原理是如果兩個不相等的對象返回不同的 hashcode 的話，那么碰撞的幾率就會小些。這就意味著存鏈表結構減小，這樣取值的話就不會頻繁調用 equal 方法，從而提高 HashMap 的性能（擾動即 Hash 方法內部的算法實現(xiàn)，目的是讓不同對象返回不同hashcode）。

使用不可變的、聲明作 final 對象，并且采用合適的 equals() 和 hashCode() 方法，將會減少碰撞的發(fā)生

不可變性使得能夠緩存不同鍵的 hashcode，這將提高整個獲取對象的速度，使用 String、Integer 這樣的 wrapper 類作為鍵是非常好的選擇。

為什么 String、Integer 這樣的 wrapper 類適合作為鍵？

因為 String 是 final，而且已經重寫了 equals() 和 hashCode() 方法了。不可變性是必要的，因為為了要計算 hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的 hashcode 的話，那么就不能從 HashMap 中找到你想要的對象。

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

我們可以看到，在 hashmap 中要找到某個元素，需要根據(jù) key 的 hash 值來求得對應數(shù)組中的位置。如何計算這個位置就是 hash 算法。

前面說過，hashmap 的數(shù)據(jù)結構是數(shù)組和鏈表的結合，所以我們當然希望這個 hashmap 里面的元素位置盡量的分布均勻些，盡量使得每個位置上的元素數(shù)量只有一個。那么當我們用 hash 算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，而不用再去遍歷鏈表。 所以，我們首先想到的就是把 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));
}

簡單來說就是：

• 高16 bit 不變，低16 bit 和高16 bit 做了一個異或（得到的 hashcode 轉化為32位二進制，前16位和后16位低16 bit和高16 bit做了一個異或）
• (n·1) & hash = -> 得到下標

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

之所以選擇紅黑樹是為了解決二叉查找樹的缺陷：二叉查找樹在特殊情況下會變成一條線性結構（這就跟原來使用鏈表結構一樣了，造成層次很深的問題），遍歷查找會非常慢。而紅黑樹在插入新數(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ā)生時，使用某種探查技術在散列表中形成一個探查（測）序列。沿此序列逐個單元地查找，直到找到給定的地址。按照形成探查序列的方法不同，可將開放定址法區(qū)分為線性探查法、二次探查法、雙重散列法等。

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

問題：已知一組關鍵字為 (26，36，41，38，44，15，68，12，06，51)，用除余法構造散列函數(shù)，用線性探查法解決沖突構造這組關鍵字的散列表。
解答：為了減少沖突，通常令裝填因子 α 由除余法因子是13的散列函數(shù)計算出的上述關鍵字序列的散列地址為 (0，10，2，12，5，2，3，12，6，12)。
前5個關鍵字插入時，其相應的地址均為開放地址，故將它們直接插入 T[0]、T[10)、T[2]、T[12] 和 T[5] 中。
當插入第6個關鍵字15時，其散列地址2（即 h(15)=15％13=2）已被關鍵字 41（15和41互為同義詞）占用。故探查 h1=(2+1)％13=3，此地址開放，所以將 15 放入 T[3] 中。
當插入第7個關鍵字68時，其散列地址3已被非同義詞15先占用，故將其插入到T[4]中。
當插入第8個關鍵字12時，散列地址12已被同義詞38占用，故探查 hl=(12+1)％13=0，而 T[0] 亦被26占用，再探查 h2=(12+2)％13=1，此地址開放，可將12插入其中。
類似地，第9個關鍵字06直接插入 T[6] 中；而最后一個關鍵字51插人時，因探查的地址 12，0，1，…，6 均非空，故51插入 T[7] 中。

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

HashMap 默認的負載因子大小為0.75。也就是說，當一個 Map 填滿了75%的 bucket 時候，和其它集合類一樣（如 ArrayList 等），將會創(chuàng)建原來 HashMap 大小的兩倍的 bucket 數(shù)組來重新調整 Map 大小，并將原來的對象放入新的 bucket 數(shù)組中。這個過程叫作 rehashing。

因為它調用 hash 方法找到新的 bucket 位置。這個值只可能在兩個地方，一個是原下標的位置，另一種是在下標為 <原下標+原容量> 的位置。

9、重新調整 HashMap 大小存在什么問題嗎？

重新調整 HashMap 大小的時候，確實存在條件競爭。

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

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

HashMap 的容量是有限的。當經過多次元素插入，使得 HashMap 達到一定飽和度時，Key 映射位置發(fā)生沖突的幾率會逐漸提高。這時候， HashMap 需要擴展它的長度，也就是進行Resize。

1. 擴容：創(chuàng)建一個新的 Entry 空數(shù)組，長度是原數(shù)組的2倍
2. rehash：遍歷原 Entry 數(shù)組，把所有的 Entry 重新 Hash 到新數(shù)組

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

達摩：哎呦，小老弟不錯嘛~~意料之外呀
小魯班：嘿嘿，優(yōu)秀吧，中場休息一波，我先喝口水
達摩：不僅僅是這些哦，面試官還會問你相關的集合類對比，比如：

10、HashTable

• 數(shù)組 + 鏈表方式存儲
• 默認容量：11（質數(shù)為宜）
• put操作：首先進行索引計算 （key.hashCode() & 0x7FFFFFFF）% table.length；若在鏈表中找到了，則替換舊值，若未找到則繼續(xù)；當總元素個數(shù)超過 容量 * 加載因子 時，擴容為原來 2 倍并重新散列；將新元素加到鏈表頭部
• 對修改 Hashtable 內部共享數(shù)據(jù)的方法添加了 synchronized，保證線程安全

11、HashMap 與 HashTable 區(qū)別

• 默認容量不同，擴容不同
• 線程安全性：HashTable 安全
• 效率不同：HashTable 要慢，因為加鎖

12、可以使用 CocurrentHashMap 來代替 Hashtable 嗎？

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

13、CocurrentHashMap（JDK 1.7）

• CocurrentHashMap 是由 Segment 數(shù)組和 HashEntry 數(shù)組和鏈表組成
• Segment 是基于重入鎖（ReentrantLock）：一個數(shù)據(jù)段競爭鎖。每個 HashEntry 一個鏈表結構的元素，利用 Hash 算法得到索引確定歸屬的數(shù)據(jù)段，也就是對應到在修改時需要競爭獲取的鎖。ConcurrentHashMap 支持 CurrencyLevel（Segment 數(shù)組數(shù)量）的線程并發(fā)。每當一個線程占用鎖訪問一個 Segment 時，不會影響到其他的 Segment
• 核心數(shù)據(jù)如 value，以及鏈表都是 volatile 修飾的，保證了獲取時的可見性
• 首先是通過 key 定位到 Segment，之后在對應的 Segment 中進行具體的 put 操作如下：
  • 將當前 Segment 中的 table 通過 key 的 hashcode 定位到 HashEntry。
  • 遍歷該 HashEntry，如果不為空則判斷傳入的? key 和當前遍歷的 key 是否相等，相等則覆蓋舊的 value
  • 不為空則需要新建一個 HashEntry 并加入到 Segment 中，同時會先判斷是否需要擴容
  • 最后會解除在 1 中所獲取當前 Segment 的鎖。
• 雖然 HashEntry 中的 value 是用 volatile 關鍵詞修飾的，但是并不能保證并發(fā)的原子性，所以 put 操作時仍然需要加鎖處理

首先第一步的時候會嘗試獲取鎖，如果獲取失敗肯定就有其他線程存在競爭，則利用 scanAndLockForPut() 自旋獲取鎖。

• 嘗試自旋獲取鎖
• 如果重試的次數(shù)達到了 MAX_SCAN_RETRIES 則改為阻塞鎖獲取，保證能獲取成功。最后解除當前 Segment 的鎖

14、CocurrentHashMap（JDK 1.8）

CocurrentHashMap?拋棄了原有的 Segment 分段鎖，采用了?CAS + synchronized?來保證并發(fā)安全性。其中的?val next?都用了 volatile 修飾，保證了可見性。

最大特點是引入了 CAS

借助 Unsafe 來實現(xiàn) native code。CAS有3個操作數(shù)，內存值 V、舊的預期值 A、要修改的新值 B。當且僅當預期值 A 和內存值 V 相同時，將內存值V修改為 B，否則什么都不做。Unsafe 借助 CPU 指令 cmpxchg 來實現(xiàn)。

CAS 使用實例

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

• -1 代表 table 正在初始化
• N 表示有 -N-1 個線程正在進行擴容操作
• 如果 table 未初始化，表示table需要初始化的大小
• 如果 table 初始化完成，表示table的容量，默認是table大小的0.75倍，用這個公式算 0.75（n – (n >>> 2)）

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

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

put 過程

• 根據(jù) key 計算出 hashcode
• 判斷是否需要進行初始化
• 通過 key 定位出的 Node，如果為空表示當前位置可以寫入數(shù)據(jù)，利用 CAS 嘗試寫入，失敗則自旋保證成功
• 如果當前位置的 hashcode == MOVED == -1,則需要進行擴容
• 如果都不滿足，則利用 synchronized 鎖寫入數(shù)據(jù)
• 如果數(shù)量大于 TREEIFY_THRESHOLD 則要轉換為紅黑樹

get 過程

• 根據(jù)計算出來的 hashcode 尋址，如果就在桶上那么直接返回值
• 如果是紅黑樹那就按照樹的方式獲取值
• 就不滿足那就按照鏈表的方式遍歷獲取值

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

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

by the way

ConcurrentHashMap 在 Java 8 中存在一個 bug 會進入死循環(huán)，原因是遞歸創(chuàng)建 ConcurrentHashMap 對象，但是在 JDK 1.9 已經修復了。場景重現(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);        
        });       
    }
}

標簽： 安全 網絡

版權申明：本站文章部分自網絡，如有侵權，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權歸原作者所有，如需使用，請與原作者聯(lián)系。