當前位置:編程學習大全網 - 源碼下載 - HashMap的底層數據結構以及主要參數

HashMap的底層數據結構以及主要參數

1.底層由鏈表+數組實現

?2.可以存儲null鍵和null值

? 3.線性不安全

? 4.初始容量為16,擴容每次都是2的n次冪(保證位運算)

? 5.加載因子為0.75,當Map中元素總數超過Entry數組的0.75,觸發擴容操作.

? 6.並發情況下,HashMap進行put操作會引起死循環,導致CPU利用率接近100%

? (1)HashMap底層實現數據結構為數組+鏈表的形式,JDK8及其以後的版本中使用了數組+鏈表+紅黑樹實現,解決了鏈表太長導致的查詢速度變慢的問題。

? (2)簡單來說,HashMap由數組+鏈表組成的,數組是HashMap的主體,鏈表則是主要為了解決哈希沖突而存在的。HashMap通過key的HashCode經過擾動函數處理過後得到Hash值,然後通過位運算判斷當前元素存放的位置,如果當前位置存在元素的話,就判斷該元素與要存入的元素的hash值以及key是否相同,如果相同的話,直接覆蓋,不相同就通過拉鏈法解決沖突。當Map中的元素總數超過Entry數組的0.75時,觸發擴容操作,為了減少鏈表長度,元素分配更均勻。

DEFAULT_INITIAL_CAPACITY :默認的初始化容量,1<<4位運算的結果是16,也就是默認的初始化容量為16。當然如果對要存儲的數據有壹個估計值,最好在初始化的時候顯示的指定容量大小,減少擴容時的數據搬移等帶來的效率消耗。同時,容量大小需要是2的整數倍。

MAXIMUM_CAPACITY :容量的最大值,1 << 30位,2的30次冪。

? DEFAULT_LOAD_FACTOR :默認的加載因子,設計者認為這個數值是基於時間和空間消耗上最好的數值。這個值和容量的乘積是壹個很重要的數值,也就是閾值,當達到這個值時候會產生擴容,擴容的大小大約為原來的二倍。

TREEIFY_THRESHOLD :因為jdk8以後,HashMap底層的存儲結構改為了數組+鏈表+紅黑樹的存儲結構(之前是數組+鏈表),剛開始存儲元素產生碰撞時會在碰撞的數組後面掛上壹個鏈表,當鏈表長度大於這個參數時,鏈表就可能會轉化為紅黑樹,為什麽是可能後面還有壹個參數,需要他們兩個都滿足的時候才會轉化。

UNTREEIFY_THRESHOLD :介紹上面的參數時,我們知道當長度過大時可能會產生從鏈表到紅黑樹的轉化,但是,元素不僅僅只能添加還可以刪除,或者另壹種情況,擴容後該數組槽位置上的元素數據不是很多了,還使用紅黑樹的結構就會很浪費,所以這時就可以把紅黑樹結構變回鏈表結構,什麽時候變,就是元素數量等於這個值也就是6的時候變回來(元素數量指的是壹個數組槽內的數量,不是HashMap中所有元素的數量)。

? MIN_TREEIFY_CAPACITY :鏈表樹化的壹個標準,前面說過當數組槽內的元素數量大於8時可能會轉化為紅黑樹,之所以說是可能就是因為這個值,當數組的長度小於這個值的時候,會先去進行擴容,擴容之後就有很大的可能讓數組槽內的數據可以更分散壹些了,也就不用轉化數組槽後的存儲結構了。當然,長度大於這個值並且槽內數據大於8時,那就轉化為紅黑樹吧。

  • 上一篇:如何做大公司凈資產
  • 下一篇:現在的汽車軟件有哪些
  • copyright 2024編程學習大全網