查看: 467|回復: 0

天下無難試之HashMap面試刁難大全

發表于 2018-10-29 15:47:31
HashMap的結構無疑是Java面試中出現頻率最高的一道題,這個題是如此之常見,應該每個人都會信手拈來。可是就在我經歷過的無數【允許我夸張一下】面試當中,能完整回答我提出的HashMap問題的人卻是寥寥無幾,如今這道題我已經問的有點厭煩了。
HashMap的結構是怎樣的?
二維結構,第一維是數組,第二維是鏈表
Get方法的流程是怎樣的?
先調用Key的hashcode方法拿到對象的hash值,然后用hash值對第一維數組的長度進行取模,得到數組的下標。這個數組下標所在的元素就是第二維鏈表的表頭。然后遍歷這個鏈表,使用Key的equals同鏈表元素進行比較,匹配成功即返回鏈表元素里存放的值。
Get方法的時間復雜度是多少?
小伙伴們在回答這道題是有很多人會開始懷疑人生,他們的腦細胞這個時候會出現短路現象。明明是O(1)啊,平時都記得牢牢的,可是剛才Get方法的流程里需要遍歷鏈表,遍歷的時間復雜度難道不是O(n)么?此刻觀察這些孩子們的表情是非常卡哇伊呢的。當然還有些甚至是科班的小伙伴居然沒聽過時間復雜度,想到這里我也開始懷疑人生了。當他們卡殼的時候,我會稍微提醒一下,問下面的這一道題。
假如HashMap里的元素有100w個,請問第二維鏈表的長度大概是多少?
嗦嘎!鏈表的長度很短,相比總元素的個數可以忽略不計。這個時候小伙伴們的眼睛通常會開始發光,很童貞。作為面試官是很喜歡看到這種眼神的。我使用反射統計過HashMap里面鏈表的長度,在HashMap里放了100w個隨機字符串鍵值對,發現鏈表的長度幾乎從來沒有超過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里面的字典是如何擴容的么?
好,如果這道題你也回答正確了,恭喜你,毫無無疑,你是一位很有錢途的高級程序員
歡迎工作一到五年的java工程師朋友們加入Java填坑之路:860113481
群內提供免費的Java架構學習資料(里面有高可用、高并發、高性能及分布式、Jvm性能調優、Spring源碼,MyBatis,Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多個知識點的架構資料)合理利用自己每一分每一秒的時間來學習提升自己,不要再用"沒有時間“來掩飾自己思想上的懶惰!趁年輕,使勁拼,給未來的自己一個交代!



回復

使用道具 舉報