閱讀相關文章，請關注微信公眾號【碼洞】

HashMap的結構無疑是Java面試中出現頻率最高的一道題贪染，這個題是如此之常見涂乌，應該每個人都會信手拈來「倒眩可是就在我經歷過的無數【允許我夸張一下】面試當中放妈，能完整回答我提出的HashMap問題的人卻是寥寥無幾北救，如今這道題我已經問的有點厭煩了。

HashMap的結構是怎樣的芜抒？

二維結構珍策，第一維是數組，第二維是鏈表

Get方法的流程是怎樣的宅倒？

先調用Key的hashcode方法拿到對象的hash值攘宙，然后用hash值對第一維數組的長度進行取模，得到數組的下標拐迁。這個數組下標所在的元素就是第二維鏈表的表頭蹭劈。然后遍歷這個鏈表，使用Key的equals同鏈表元素進行比較线召，匹配成功即返回鏈表元素里存放的值铺韧。

Get方法的時間復雜度是多少？

小伙伴們在回答這道題是有很多人會開始懷疑人生缓淹，他們的腦細胞這個時候會出現短路現象哈打。明明是O(1)啊，平時都記得牢牢的割卖，可是剛才Get方法的流程里需要遍歷鏈表前酿，遍歷的時間復雜度難道不是O(n)么？此刻觀察這些孩子們的表情是非撑羲荩卡哇伊呢的。當然還有些甚至是科班的小伙伴居然沒聽過時間復雜度淹仑，想到這里我也開始懷疑人生了丙挽。當他們卡殼的時候，我會稍微提醒一下匀借，問下面的這一道題颜阐。

假如HashMap里的元素有100w個，請問第二維鏈表的長度大概是多少吓肋？

嗦嘎凳怨！鏈表的長度很短，相比總元素的個數可以忽略不計是鬼。這個時候小伙伴們的眼睛通常會開始發(fā)光肤舞，很童貞。作為面試官是很喜歡看到這種眼神的均蜜。我使用反射統計過HashMap里面鏈表的長度李剖，在HashMap里放了100w個隨機字符串鍵值對，發(fā)現鏈表的長度幾乎從來沒有超過7這個數字囤耳，當我增大loadFactor的時候篙顺，才會偶爾冒出幾個長度為8的鏈表來偶芍。于是問題又來了。

既然鏈表如此短德玫，為啥Java8要對HashMap的鏈表進行改造匪蟀，使用紅黑樹來代替鏈表呢？

有很多同學都沒具體去深入關注Java8的新特性宰僧，如果他們回答不上來材彪，我也不會感到失望。因為到這個問題的時候撒桨，已經只剩下15%的同學不到了查刻，如果再打擊他們，看著他們落寞的身影走出了大門凤类，我都要對自己感到失望了穗泵，怎么招個人就如此困難？

這道題的關鍵在于如果Key的hashcode不是隨機的谜疤，而是人為特殊構造的話佃延，那么第二維鏈表可能會無比的長，而且分布極為不均勻夷磕，這個時候就會出現性能問題履肃。比如我們把對象的hashcode都統一返回一個常量，最終的結果就是hashmap會退化為一維鏈表坐桩，Get方法的性能巨降為O(n)尺棋，使用紅黑樹可以將性能提升到O(log(n))。

請解釋一下HashMap的參數loadFactor绵跷，它的作用是什么膘螟？

loadFactor表示HashMap的擁擠程度，影響hash操作到同一個數組位置的概率碾局。默認loadFactor等于0.75荆残，當HashMap里面容納的元素已經達到HashMap數組長度的75%時，表示HashMap太擠了净当，需要擴容内斯，在HashMap的構造器中可以定制loadFactor。

請說明一下HashMap擴容的過程

擴容需要重新分配一個新數組像啼，新數組是老數組的2倍長俘闯，然后遍歷整個老結構，把所有的元素挨個重新hash分配到新結構中去埋合。這個rehash的過程是很耗時的备徐，特別是HashMap很大的時候，會導致程序卡頓甚颂，而2倍內存的關系還會導致內存瞬間溢出蜜猾，實際上是3倍內存秀菱，因為老結構的內存在rehash結束之前還不能立即回收。那為什么不能在HashMap比較大的時候擴容擴少一點呢蹭睡，關于這個問題我也沒有非常滿意的答案衍菱，我只知道hash的取模操作使用的是按位操作，按位操作需要限制數組的長度必須是2的指數肩豁。另外就是Java堆內存底層用的是TcMalloc這類library脊串，它們在內存管理的分配單位就是以2的指數的單位，2倍內存的遞增有助于減少內存碎片清钥，減少內存管理的負擔琼锋。

HashMap是線程安全的么？

當然不是祟昭，線程安全的HashMap是ConcurrentHashMap缕坎。關于ConcurrentHashMap還可以問很多問題，這就需要另一篇文章來具體講解了篡悟。

你了解Redis么谜叹，你知道Redis里面的字典是如何擴容的么？

好搬葬，如果這道題你也回答正確了荷腊，恭喜你，毫無無疑急凰，你是一位很有錢途的高級程序員女仰。

你了解Python么，你知道Python里面字典的結構是怎樣的么抡锈？

這個就屬于附加題了董栽，如果這道題你也回答對了，那我的眼睛就要發(fā)射紫外線了企孩。

想閱讀相關文章，請關注知乎專欄【碼洞】