hashMap源碼分析1.8

HashMap

• JDK1.8的HashMap：底層實作（數組+連結清單/紅黑樹）
• 1、為什麼要從JDK1.8之前的連結清單設計，修改為連結清單或紅黑樹的設計？
• 當某個連結清單比較長的時候，查找效率還是會降低。
• 為了提高查詢效率，那麼把table[index]下面的連結清單做調整。
• 如果table[index]的連結清單的節點的個數比較少，（8個或以内），就保持連結清單。如果超過8個，那麼就要考慮把連結清單轉為一棵紅黑樹。
• TREEIFY_THRESHOLD：樹化門檻值，從連結清單轉為紅黑樹的臨界值。
• 2、什麼時候樹化？
• table[index]下的結點數一達到8個就樹化嗎？
• 如果table[index]的節點數量已經達到8個了，還要判斷table.length是否達到64，如果沒有達到64，先擴容。
• 示範：8個->9個 length從16-》32

• 9個->10個  length從32->64
             

• 10個->11個 length已經達到64，table[index]就從Node類型轉為TreeNode類型，說明樹化
             

• MIN_TREEIFY_CAPACITY：最小樹化容量64
• 3、什麼時候從樹–>連結清單
• 當你删除結點時，這棵樹的結點個數少于6個，會反樹化，變為連結清單
• UNTREEIFY_THRESHOLD：6個
• 樹的結構太複雜，當結點少了之後，就用連結清單更好。
• 4、put的過程
• （1）[index]的計算問題
• 第一步用key的hashCode值調用hash()函數，幹擾hash值，使得(key,value)更加均勻的分布table數組中。
• JDK1.8中hash()算法更優化。
• 第二步： hash值與table.length-1做&運算，保證index在[0,length-1]範圍内
• （2）擴容問題
• 第一種：當某個table[index]的連結清單的個數達到8個，并且table.length<64，那麼會擴容
• 第二種：size >= threshold，并且table[index]!=null
• threshold = table.length * loadFator（它的預設值DEFAULT_LOAD_FACTOR：0.75）
• （3）當把(key,value)添加到連結清單中，JDK1.8是在連結清單的尾部