我們希望候選者具有手動實現(xiàn)HashMap的能力；研究過JDK中HashMap的源代碼，以及不同版本JDK中使用的優(yōu)化機制。
在java面試中集合類似乎已經(jīng)是繞不開的話題，對于一個中高級java程序員來說如果對集合類的內(nèi)部原理不了解罩阵，基本上面試都會被pass掉。下面從面試官的角度來聊聊一個候選者應(yīng)該對HashMap了解到什么程度才算是合格启摄。
問題一：在日常開發(fā)中使用過的java集合類有哪些稿壁？
一般應(yīng)聘者都會回答ArrayList，LinkedList歉备，HashMap傅是，HashSet等等。如果連這幾個集合類都不知道蕾羊，基本上可以pass了喧笔。
問題二：能描述一下HashMap的實現(xiàn)原理嗎？
其實HashMap是典型的空間換時間的一種技術(shù)手段龟再。如果面試者在這個問題中不能很好的闡述HashMap的實現(xiàn)原理书闸，比如不知道如何解決hash沖突，不知道loadFactor這樣的核心概念以及擴容機制利凑〗ⅲ基本上我不會做深入考察了嫌术，可以pass了。
問題三：平時在使用HashMap時一般使用什么類型的元素作為Key牌借？
面試者通常會回答度气，使用String或者Integer這樣的類。這個時候可以繼續(xù)追問為什么使用String膨报、Integer呢蚯嫌？這些類有什么特點？如果面試者有很好的思考丙躏，可以回答出這些類是Immutable的，并且這些類已經(jīng)很規(guī)范的覆寫了hashCode()以及equals()方法束凑。作為不可變類天生是線程安全的晒旅，而且可以很好的優(yōu)化比如可以緩存hash值，避免重復(fù)計算等等汪诉，那么基本上這道題算是過關(guān)了废恋。
問題四：如果讓你實現(xiàn)一個自定義的class作為HashMap的key該如何實現(xiàn)？
這個問題其實隱藏著幾個知識點扒寄，覆寫hashCode以及equals方法應(yīng)該遵循的原則鱼鼓，在jdk文檔以及《effective java》中都有明確的描述。當(dāng)然這也在考察應(yīng)聘者是如何自實現(xiàn)一個Immutable類该编。如果面試者這個問題也能回答的很好迄本，基本上可以獲得一點面試官的好感了。
問題四延伸：你能設(shè)計一個算法（輸入是java源文件）课竣，判斷一個類是否是Immutable的嗎嘉赎？
這道題考察面非常非常廣。如果這個問題面試者回答上了于樟，我覺得面試者的基礎(chǔ)知識無需考察了公条。可以繼續(xù)考察高并發(fā)與分布式架構(gòu)設(shè)計了迂曲。
問題五：如何衡量一個hash算法的好壞靶橱，你知道的常用hash算法有哪些？
如果面試者的技術(shù)面比較寬路捧，或者算法基礎(chǔ)以及數(shù)論基礎(chǔ)比較好关霸，這個問題才可以做很好的回答。首先鬓长，hashCode()不要求唯一但是要盡可能的均勻分布谒拴，而且算法效率要盡可能的快。如果面試者能回答出一些常用的算法涉波，比如MurMurHash（萌萌噠的名字）基本上已經(jīng)可以俘獲面試官了英上。如果面試者有編譯器的背景說出了如何在編譯領(lǐng)域使用完美哈希的場景炭序，那就太棒了，畢竟編譯原理學(xué)的好的人太少了苍日。當(dāng)然不要忘記了惭聂，還可以再考察一下java中String類的hashCode()的實現(xiàn)：
public int hashCode() {
int h = hash;
if (h == 0 && count > 0) {
int off = offset;
char val[] = value;
int len = count;
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}
為什么 h = 31 * h + val[off++]; 這一行使用31 ，而不是別的數(shù)字相恃，這是一個魔術(shù)嗎辜纲？
如果都結(jié)束了，不要忘了再問一句你知道hash攻擊嗎拦耐？有避免手段嗎耕腾？就看面試者對各個jdk版本對HashMap的優(yōu)化是否了解了。這就引出了另一個數(shù)據(jù)結(jié)構(gòu)紅黑樹了杀糯∩ò常可以根據(jù)崗位需要繼續(xù)考察rb-tree，b-tree固翰，lsm-tree等常用數(shù)據(jù)結(jié)構(gòu)以及典型應(yīng)用場景狼纬。
問題六： HashMap是線程安全的嗎？ 如果多個線程操作同一個HashMap對象會產(chǎn)生哪些非正陈罴剩現(xiàn)象疗琉？
其實這已經(jīng)開始考察面試者對并發(fā)知識的掌握情況了。HashMap在resize時候如果多個線程并發(fā)操作如何導(dǎo)致死鎖的歉铝。面試者不一定知道盈简，但是可以讓面試者分析。畢竟很多類庫在并發(fā)場景中不恰當(dāng)使用HashMap導(dǎo)致過生產(chǎn)問題太示。
問題七： ConcurrentHashMap vs HashTable 他們是如何處理并發(fā)的送火？為什么有了ConcurrentHashMap 沒有把 HashTable 用@Deprecated注解廢棄掉？
這個時候問題已經(jīng)升級了先匪，希望面試者分析過這兩個類的源代碼种吸。我們是希望面試者能夠知道ConcurrentHashMap 的內(nèi)部實現(xiàn)原理，而且?guī)缀跏莻€硬性要求了呀非。后一個問題似乎更難一些坚俗，主要是進一步考察面試者對細(xì)節(jié)的一些思考。
問題八：假如在一個沒有GC的語言（比如c語言）中實現(xiàn)一個HashMap岸裙，如何處理表擴容以及收縮問題猖败？
現(xiàn)在很多內(nèi)存數(shù)據(jù)庫，比如redis內(nèi)部使用的還是HashMap這種數(shù)據(jù)結(jié)構(gòu)降允，但是在數(shù)據(jù)量特別大的時候比如100W的記錄數(shù)恩闻，在遇到擴容的時候如果暴力的擴容2倍，然后做rehash剧董，肯定是有問題的幢尚。那么如何避免呢破停？當(dāng)緩存的數(shù)據(jù)不斷的被刪除或者到期失效，如何有效的管理內(nèi)存空間呢尉剩？這些都是值得面試者思考的問題真慢。
其他問題
可以追問一些技術(shù)實現(xiàn)細(xì)節(jié)，比如為什么HashMap中bucket的大小為什么是2的冪之類的實現(xiàn)細(xì)節(jié)理茎。
HashMap涉及的知識點特別多黑界，文中的一些問題做了簡要的回答以及提示。我并不會給出所謂的標(biāo)準(zhǔn)答案皂林，其實在面試的過程中面試官并不要求面試者對所有問題都給出答案朗鸠，重要的還是要考察面試者對問題的思考過程。有些問題础倍，比如問題一童社、問題二、屬于元知識的考察著隆，不知道是不可原諒的，但是后面的一些問題比如問題四擴展呀癣，就很開放美浦。是我在思考如何讓編譯器做更多的編譯檢查，以及如何對源代碼做更多的靜態(tài)分析考慮的問題项栏。
