兩個(gè)高頻設(shè)計(jì)類(lèi)面試題：如何設(shè)計(jì)HashMap和線(xiàn)程池

你好，我是 yes。

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

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

因?yàn)榘斯晌脑诿嬖囍惺且欢ㄒ模簿褪窃撝赖念}還是得知道的，而在理解的基礎(chǔ)上記憶會(huì)比較深刻，并且可以應(yīng)對(duì)一些變種問(wèn)題。

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

所以如果覺(jué)得這樣的形式哪里不好，需要改進(jìn)的話(huà)，請(qǐng)留言。

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

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

可以先說(shuō)下你對(duì) HashMap 的理解。

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

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

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

而因?yàn)檩斎胫凳菬o(wú)限的，而數(shù)組的大小是有限的所以肯定會(huì)有碰撞，因此可以采用拉鏈法來(lái)處理沖突。

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

當(dāng)然超過(guò)一定的結(jié)點(diǎn)還是需要擴(kuò)容的，不然碰撞就太嚴(yán)重了。

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

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

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

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

可能會(huì)延伸到線(xiàn)程安全之類(lèi)的問(wèn)題，反正就照著 currentHashMap 的設(shè)計(jì)答。

其實(shí)有些題目看起來(lái)是問(wèn)如何設(shè)計(jì)，實(shí)際上你就答你對(duì)這個(gè)東西是怎么理解的，把它原理和一些要點(diǎn)講一講這個(gè)題目就過(guò)了。

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

所以有時(shí)候的“答非所問(wèn)”是 OK 的，如果面試官覺(jué)得你答的方向不對(duì)，自然而然會(huì)提醒你，到時(shí)候你再接招就好了。

簡(jiǎn)單地說(shuō)，很多提問(wèn)不是真的要死板的對(duì)著面試題而回答，因?yàn)槊嬖嚬僖仓皇腔\統(tǒng)地問(wèn)。

2.如果讓你設(shè)計(jì)一個(gè)線(xiàn)程池如何設(shè)計(jì)？

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

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

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

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

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

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

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

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

我覺(jué)得基本上這樣答就差不多了，等著面試官的追問(wèn)就好。

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

當(dāng)然這種開(kāi)放型問(wèn)題還是仁者見(jiàn)仁智者見(jiàn)智，我這個(gè)不是標(biāo)準(zhǔn)答案，僅供參考。

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