我們希望候選者具有手動實現(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這樣的核心概念以及擴容機制?；旧衔也粫錾钊肟疾炝耍梢詐ass了。
問題三：平時在使用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ī)缀跏莻€硬性要求了。后一個問題似乎更難一些，主要是進一步考察面試者對細節(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)細節(jié)，比如為什么HashMap中bucket的大小為什么是2的冪之類的實現(xiàn)細節(jié)。
HashMap涉及的知識點特別多，文中的一些問題做了簡要的回答以及提示。我并不會給出所謂的標(biāo)準(zhǔn)答案，其實在面試的過程中面試官并不要求面試者對所有問題都給出答案，重要的還是要考察面試者對問題的思考過程。有些問題，比如問題一、問題二、屬于元知識的考察，不知道是不可原諒的，但是后面的一些問題比如問題四擴展，就很開放。是我在思考如何讓編譯器做更多的編譯檢查，以及如何對源代碼做更多的靜態(tài)分析考慮的問題。
