Categories
程式開發

手把手教你錘面試官01——HashMap面試全攻略


本文是手把手教你錘面試官系列第一篇文章,該系列主要為大家分析和講解在面試過程中,遇到面試官經常提出的面試問題如何進行攻防。另外本系列的文章也會提供許多小技巧給大家去間接試探出面試官的技術能力和專業水平,從而達到碾壓面試官的目的。本系列文章只適用於JAVA工程師。

很多面試官喜歡問HashMap的一個原因就是因為HashMap我們經常在開發中用到,而且它線程不安全。這裡有幾個隱藏的問題:

0.HashMap的結構是怎麼樣的?

1.HashMap為什麼線程不安全?

2.HashMap線程不安全在程序中的體現是什麼?

3.既然HashMap線程不安全,為什麼我們還經常用它?

4.怎麼樣可以讓HashMap線程安全?

0.0回答

因為HashMap的數據結構是散列結構,散列結構就是我們說的key-value結構,它由一個數組和多個鍊錶組成。每個數組節點對應一個鍊錶。 key值是一個數組存放,value的值放在多個鍊錶中存放。下圖就是一個典型的散列結構的圖,左邊是一個數組,右邊是每個數組節點對應的鍊錶。

手把手教你錘面試官01——HashMap面試全攻略 1

1.1回答

HashMap中put操作的主函數,如果沒有hash碰撞則會直接插入元素。如果線程A和線程B同時進行put操作,剛好這兩條不同的數據hash值一樣,並且該位置數據為null,所以這線程A、B都會進入下面代碼的第6行代碼中。

假設一種情況,線程A進入後還未進行數據插入時掛起,而線程B正常執行,從而正常插入數據,然後線程A獲取CPU時間片,此時線程A不用再進行hash判斷了,問題出現:線程A會把線程B插入的數據給覆蓋,發生線程不安全。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则会直接插入元素
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

2.2回答

多線程操作HashMap的場景下,會發生HashMap的值被覆蓋,從而導致數據丟失。既同一個數組對應的鍊錶被反复替換。另外,如果面試官問,會不會出現死循環或者數組下標越界。你就可以盡情的嘲諷,這個問題在JDK1.8已經不會出現了,難道貴公司還用JDK1.8以下版本? (這樣做的好處是避免遇到面試官問你紅黑二叉樹還有HashMap的擴容機制,盡量避開)

3.3回答

廢話,因為好用嘛。請看下圖,下圖是JAVA官方API中截取出來的類圖。從下面這張圖我們可以看出來Map是一個接口,我們常用的實現類有HashMap、HashTable、LinkedHashMap、TreeMap。

HashTable類是線程安全的,它使用synchronize來做線程安全,全局只有一把鎖,在線程競爭比較激烈的情況下hashtable的效率是比較低下的。因為當一個線程訪問hashtable的同步方法時,其他線程再次嘗試訪問的時候,會進入阻塞或者輪詢狀態,進而導致線程掛起。當你在多線程場景下使用Map,雖然不能使用HashMap但也盡量別使用HashTable。其實我個人覺得這個類可以廢掉了。

LinkedHashMap就更不用說了,本身也是線程不安全的,而且每次插入的時候都要自己排序一次,每次排序都要進行一次遍歷查詢。你都用map了,你還會在意插入的順序嘛?大多數情況你也不會在意插入的節點順序。除非你一定要記錄Map中節點插入的先後順序,否則使用LinkedHashMap只會消耗性能。

TreeMap合LinkedHashMap一樣,線程不安全而且要排序。

手把手教你錘面試官01——HashMap面試全攻略 2

4.4回答

在多线程场景下放弃使用HashMap,可以使用CurrentHashMap替代HashMap。CurrentHashMap是綫程安全的,因为它和HashTable一样加了锁。而且我们上边也提到了,由于HashTable 使用一把锁(锁住整个链表结构)处理并发问题,多个线程竞争一把锁,容易线程阻塞、挂起。而CurrentHashMap采用CAS + synchronized + Node + 红黑树的多段分級锁的机制,可以对链表进行非常细粒度的加锁,不容易造成线程阻塞。

額外技巧

知己知彼,百戰不殆。在面試過程中如果不知道面試官專業水平深淺的時候,可以在進行回答的時候故意漏出一個比較大的破綻。如果面試官沒有提出異議,則說明水平不高,回答的時候盡量往底層走就可以唬住對方,讓主動權在你手上。比方說回答HashMap的問題時,可以賣一個破綻——HashMap的默認長度是8(其實是16)。如果面試官沒有提出異議,則說明該面試官對於HashMap這塊最多也就是知道它線程不安全,可用CurrentHashMap替代。本文上面粗淺的內容最夠你吊打對方。如果對方指正你默認長度是16,你可以先說,沒錯就是16,剛才一時緊張口誤了。然後儘量避開對方提問HashMap擴容機制、鍊錶紅黑二叉樹轉換等問題。