HashMap源碼分析
一 HashMap中的底層存儲原理
HashMap中的存儲:數組+鏈表/紅黑樹;
Entry<K,V>[] entry
在 java1.8之前其存儲結構為 :數組+鏈表,到java1.8的時候對其進行了優化,在鏈表的長度大於8的時候桶的結構將會轉換成紅黑樹,當節點數最少為6的時候,還原為鏈表。這個數值是為了防止頻繁轉換結構而影響效率(無非是在 空間和時間之間獲取的一個拍比較合適的點而已)
為了防止單鏈表過長影響效率,Hashmap中還採取了取模演算法(長度對hash值取餘數(取模演算法為了提高效率採用位與運算&)作為數組的索引值以確定元素的存放位置)
HashMap對Hash值衝突解決:當Hash值衝突之後 1.先判斷key值是否和衝突的值相等。如相等則進行判斷Value值是否相等如不相等進行替換,當key值不等的時候則以單鏈表的形式存放在一個桶中。
關於負載因子:
負載因子最直接的是影響HashMap中數組擴容的一個比例參數,默認是0.75,例如:當前HashMap中的數組的長度為length,當數組中有0.75*length的元素被沾滿的時候就會對數組擴容,另一方面:負載因數影響了Hashmap的查詢效率,當負載因數越小,那麼數組就會容易觸發擴容,數組長度較大,那麼hash值關於長度的取模散列排布中hash值衝突的幾率較小,鏈表就會交端,那麼查詢的效率就會提升。;
但是負載因子小的時候擴容的次數就會增多,對HashMap進行擴容,需要從新計算每個元素的Hash值,從新進行散列排布,這也是非常消耗性能的,所以負載因子太小也會早場put值得效率降低。
二 HashMap之中的源碼邏輯導向
1 在HashMap進行實例話的時候:僅僅對HashMap中的負載因子進行了默認賦值0.75.
2 在第一次對HashMap進行put()值得時候對數組的元素進行了初始化 擴容
3 在第二次進行put值得時候會對key的Hash值進行判斷是否衝突,若衝突則形成單鏈表
4 在put值得時候中間會插入一些判斷,對數組沾滿率的判斷,判斷是否達到閾值(是否需要擴容),對鏈表的判斷是否需要轉換成紅黑樹
5 其中每一次擴容都是初始化新的更大空間的數組,將老的數組放到新的數組中的過程
三 HashMap的插入和查詢效率
插入效率和負載因子成正比
查詢效率和負載成反比
四 HashMap的基本業務邏輯
五 HashMap中的疑難點
六 HashMap中的學習點
Hash值得計算
取模演算法
鏈表遍歷
final static triansant的應用場景
※C 標準性能測試
※gcc g加加 make cmake區別
TAG:程序員小新人學習 |