兩個高頻設(shè)計類面試題：如何設(shè)計HashMap和線程池

你好，我是 yes。

最近在匯總面試題，但是我寫的這個版本不是背誦版，不是那種死記硬背刻板的答案。

我的本意是拋磚引玉，針對每個題目給出我自己的理解和解釋型的答案，然后背誦版本需要你們自行去總結(jié)和記憶。

因為八股文在面試中是一定要的，也就是該知道的題還是得知道的，而在理解的基礎(chǔ)上記憶會比較深刻，并且可以應(yīng)對一些變種問題。

但是不清楚這樣的形式是不是受歡迎，所以我暫時拿兩個題目先發(fā)出來看看反響。

所以如果覺得這樣的形式哪里不好，需要改進的話，請留言。

1.如果讓你設(shè)計一個 HashMap 如何設(shè)計？

這個問題我覺得可以從 HashMap 的一些關(guān)鍵點入手，例如 hash 函數(shù)、如何處理沖突、如何擴容。

可以先說下你對 HashMap 的理解。

比如：HashMap 無非就是一個存儲 格式的集合，使得通過 key 在 O(1) 的時間復(fù)雜下就能查找到 value。

基本原理就是將 key 經(jīng)過 hash 函數(shù)進行散列得到散列值，然后通過散列值對數(shù)組取模得到對應(yīng)的 index 。

所以 hash 函數(shù)很關(guān)鍵，不僅運算要快，還需要分布均勻，減少 hash 碰撞。

而因為輸入值是無限的，而數(shù)組的大小是有限的所以肯定會有碰撞，因此可以采用拉鏈法來處理沖突。

為了避免惡意的 hash 攻擊，當拉鏈超過一定長度之后可以轉(zhuǎn)為紅黑樹結(jié)構(gòu)。

當然超過一定的結(jié)點還是需要擴容的，不然碰撞就太嚴重了。

而普通的擴容會導(dǎo)致某次 put 延時較大，特別是 HashMap 存儲的數(shù)據(jù)比較多的時候，所以可以考慮和 redis 那樣搞兩個 table 延遲移動，一次可以只移動一部分。

不過這樣內(nèi)存比較吃緊，所以也是看場景來 trade off 了。

還有，最好使用之前預(yù)估準數(shù)據(jù)大小，避免頻繁的擴容。

基本上這樣答下來差不多了，HashMap 幾個關(guān)鍵要素都包含了，接下來就看面試官怎么問了。

可能會延伸到線程安全之類的問題，反正就照著 currentHashMap 的設(shè)計答。

其實有些題目看起來是問如何設(shè)計，實際上你就答你對這個東西是怎么理解的，把它原理和一些要點講一講這個題目就過了。

比如我上面說的預(yù)估準數(shù)據(jù)的大小，這種看起來和設(shè)計沒關(guān)系，但是可以讓面試官知道你對這種方面是敏感的就夠了。

所以有時候的“答非所問”是 OK 的，如果面試官覺得你答的方向不對，自然而然會提醒你，到時候你再接招就好了。

簡單地說，很多提問不是真的要死板的對著面試題而回答，因為面試官也只是籠統(tǒng)地問。

2.如果讓你設(shè)計一個線程池如何設(shè)計？

這種設(shè)計類問題還是一樣，先說下理解，表明你是知道這個東西的用處和原理的，然后開始 BB?；旧暇褪前凑宅F(xiàn)有的設(shè)計來說，再添加一些個人見解。

線程池講白了就是存儲線程的一個容器，池內(nèi)保存之前建立過的線程來重復(fù)執(zhí)行任務(wù)，減少創(chuàng)建和銷毀線程的開銷，提高任務(wù)的響應(yīng)速度，并便于線程的管理。

我個人覺得如果要設(shè)計一個線程池的話得考慮池內(nèi)工作線程的管理、任務(wù)編排執(zhí)行、線程池超負荷處理方案、監(jiān)控等方面。

要將初始化線程數(shù)、核心線程數(shù)、最大線程池都暴露出來可配置，包括超過核心線程數(shù)的線程空閑消亡相關(guān)配置。

然后任務(wù)的存儲結(jié)構(gòu)也得可配置，可以是無界隊列也可以是有界隊列，也可以根據(jù)配置，分多個隊列來分配不同優(yōu)先級的任務(wù)，也可以采用 stealing 的機制來提高線程的利用率。

再提供配置來表明此線程池是 IO 密集型還是 CPU 密集型來改變?nèi)蝿?wù)的執(zhí)行策略。

超負荷的方案可以有多種，包括丟棄任務(wù)、拒絕任務(wù)并拋出異常、丟棄最舊的任務(wù)或自定義等等。

至于監(jiān)控的話，線程池設(shè)計要埋好點，暴露出用于監(jiān)控的接口，如已處理任務(wù)數(shù)、待處理任務(wù)數(shù)、正在運行的線程數(shù)、拒絕的任務(wù)數(shù)等等信息。

我覺得基本上這樣答就差不多了，等著面試官的追問就好。

注意不需要跟面試官解釋什么叫核心線程數(shù)之類的，都懂的沒必要。

當然這種開放型問題還是仁者見仁智者見智，我這個不是標準答案，僅供參考。

建議把線程池相關(guān)的關(guān)鍵字都要說出來，表面你對線程池的內(nèi)部原理的理解是透徹的。