權威hashmap,讀透一篇即可KO面試官指南(升級版)

之前已經發了一篇: ,大多數同學都受益匪淺,但是有的人說,我可是要面架構師的男人,你這篇還不夠!於是出了這篇升級版

1:hashmap簡介(如下,數組-鏈表形式)

HashMap的存儲結構

權威hashmap,讀透一篇即可KO面試官指南(升級版)

圖中,紫色部分即代表哈希表,也稱為哈希數組(默認數組大小是16,每對key-value鍵值對其實是存在map的內部類entry裡的),數組的每個元素都是一個單鏈表的頭節點,跟著的綠色鏈表是用來解決衝突的,如果不同的key映射到了數組的同一位置處,就將其放入單鏈表中

2:hashmap原理(即put和get原理)

2.1 put原理

1.根據key獲取對應hash值:int hash = hash(key.hash.hashcode())

2.根據hash值和數組長度確定對應數組引int i = indexFor(hash, table.length); 簡單理解就是i = hash值%模以 數組長度(其實是按位與運算)。如果不同的key都映射到了數組的同一位置處,就將其放入單鏈表中。且新來的是放在頭節點。

2.2 get原理

1.通過hash獲得對應數組位置,遍歷該數組所在鏈表(key.equals())

3:hashcode相同,衝突怎麼辦?

“頭插法”,放到對應的鏈表的頭部。

3.1:為什麼是頭插法(其設計原理是什麼)?

因為HashMap的發明者認為,後插入的Entry被查找的可能性更大(因為get查詢的時候會遍歷整個鏈表)。

4.hashmap的默認數組長度是多少?

默認為16

4.1 為什麼?

之所以選擇16,是為了服務於從key映射到index的hash算法(看下面)。

5:hashmap達到默認負載因子(0.75)怎麼辦?

自動雙倍擴容,擴容後重新計算每個鍵值對位置。且長度必須為16或者2的冪次

5.1為啥要16或者2的冪次?

  • 若不是16或者2的冪次,位運算的結果不夠均勻分佈,顯然不符合Hash算法均勻分佈的原則。
  • 反觀長度16或者其他2的冪,Length-1的值是所有二進制位全為1,這種情況下,index的結果等同於HashCode後幾位的值。只要輸入的HashCode本身分佈均勻,Hash算法的結果就是均勻的。

6:hashmap是線程安全的嗎?

不是。

6.2 為什麼?

因為沒加鎖

6.3 那在併發時會導致什麼問題?

hashmap在接近臨界點時,若此時兩個或者多個線程進行put操作,都會進行resize(擴容)和ReHash(為key重新計算所在位置),而ReHash在併發的情況下可能會形成鏈表環。

6.4 如何判斷有環形表?

最優:首先創建兩個指針A和B(在java裡就是兩個對象引用),同時指向這個鏈表的頭節點。然後開始一個大循環,在循環體中,讓指針A每次向下移動一個節點,讓指針B每次向下移動兩個節點,然後比較兩個指針指向的節點是否相同。如果相同,則判斷出鏈表有環,如果不同,則繼續下一次循環。

理解:此方法也可以用一個更生動的例子來形容:在一個環形跑道上,兩個運動員在同一地點起跑,一個運動員速度快,一個運動員速度慢。當兩人跑了一段時間,速度快的運動員必然會從速度慢的運動員身後再次追上並超過,原因很簡單,因為跑道是環形的。

權威hashmap,讀透一篇即可KO面試官指南(升級版)

7: hashmap 和 hashtable 區別?

線程: 不安全 安全(synchronized修飾)

效率: 更高 略低

數組默認值: 16 11

null值: key-value都允許 不允許(拋異常)

其中key為null的map對象就在索引為0的位置上

8:那hashmap不安全,hashtable性能又低,怎麼辦?

用concurrenthashmap,即保證安全,性能又可以保障

8.1 那concurrenthashmap究竟是什麼?

整個ConcurrentHashMap的結構如下:

權威hashmap,讀透一篇即可KO面試官指南(升級版)

理解:hashmap是有entry數組組成,而concurrenthashmap則是Segment數組。那Segment是什麼呢?Segment本身就相當於一個HashMap對象。同HashMap一樣,Segment包含一個HashEntry數組,數組中的每一個HashEntry既是一個鍵值對,也是一個鏈表的頭節點。

單一的Segment結構如下(是不是看著就是hashmap):

權威hashmap,讀透一篇即可KO面試官指南(升級版)

像這樣的Segment對象,在ConcurrentHashMap集合中有多少個呢?有2的N次方個,共同保存在一個名為segments的數組當中。

可以說,ConcurrentHashMap是一個二級哈希表。在一個總的哈希表下面,有若干個子哈希表。(這樣類比理解hashmap)

8.2:那他的put和get方法呢(對比hashmap的普通和get方法)?

Put方法:

  • 1.為輸入的Key做Hash運算,得到hash值。
  • 2.通過hash值,定位到對應的Segment對象
  • 3.獲取可重入鎖
  • 4.再次通過hash值,定位到Segment當中數組的具體位置。
  • 5.插入或覆蓋HashEntry對象。
  • 6.釋放鎖。

Get方法:

  • 1.為輸入的Key做Hash運算,得到hash值。
  • 2.通過hash值,定位到對應的Segment對象
  • 3.再次通過hash值,定位到Segment當中數組的具體位置。

由此可見,和hashmap相比,ConcurrentHashMap在讀寫的時候都需要進行二次定位。先定位到Segment,再定位到Segment內的具體數組下標。

9: hashmap 和 concurrenthashmap區別?

線程: 不安全 安全

10:為啥concurrenthashmap和hashtable都是線程安全,但是前者性能更高

因為前者是用的分段鎖,根據hash值鎖住對應鏈表,當hash值不同時,使其能實現並行插入,效率更高,而hashtable會鎖住整個map

當需要put元素的時候,並不是對整個hashmap進行加鎖,而是先通過hashcode來知道他要放在那一個分段中,然後對這個分段進行加鎖,所以當多線程put的時候,只要不是放在同一個分段中,就實現了真正的並行的插入。

但是,在統計size的時候,就是獲取hashmap全局信息的時候,就需要獲取所有的分段鎖才能統計。

分段鎖的設計目的是細化鎖的粒度,當操作不需要更新整個數組的時候,就僅僅針對數組中的一部分行加鎖操作。

11.java7的hashmap和java8的hashmap的區別(1.8做了哪些優化)?

為了加快查詢效率(因為get()需要遍歷整張鏈表),java8的hashmap引入了紅黑樹結構,當某一鏈表的元素>8時,該鏈表就會轉成紅黑樹結構,查詢效率更高


分享到:


相關文章: