HashMap的底層實(shí)現(xiàn)原理簡單分析:

1.在使用無參構(gòu)造方法創(chuàng)建一個新的HashMap時,系統(tǒng)自動分配了一個閾值為0.75.該閾值的含義指的是,當(dāng)HashMap中存放的鍵值對總數(shù)超過桶數(shù)(無參構(gòu)造時,默認(rèn)有16個桶)*閾值時,桶數(shù)將自動進(jìn)行擴(kuò)容.而進(jìn)行帶參構(gòu)造時,可以傳只傳一個數(shù),在經(jīng)過特定的位運(yùn)算后,得到2的n次方的一個數(shù)即作為桶的數(shù)量,傳入兩個數(shù)時,第一個數(shù)的作用與只傳入一個參數(shù)時一直,第二個參數(shù)則作為閾值.

2.在向該HashMap中通過put增加元素時,先通過計算一個特殊的算法值,由key的哈希值與該值右移16位的值做異或運(yùn)算.當(dāng)key為null時,返回0.

3.第一次通過put方法時,會創(chuàng)造出長度為桶數(shù)的的鏈表數(shù)組.將之前提到的特殊算法值與桶數(shù)-1作位與運(yùn)算.得到0-桶數(shù)-1之間的一個數(shù),將該鍵值對,放在對應(yīng)的下標(biāo)的鏈表數(shù)組下

4.后續(xù)添加過程為,先計算key的特殊算法值,并放在指定的鏈表數(shù)組處,如果該鏈表處為空,之間將鍵值對放置于此.如果不為空,判斷該鏈表為節(jié)點(diǎn),樹,還是鏈表,

1)如果是單節(jié)點(diǎn),比較key值與特殊算法值,如果相同,則用新的value替換舊的value

2)如果是樹,就將該鍵值對加入

3)如果是鏈表,將該key與鏈表中所有的key值對比,當(dāng)該key與所有key都不同時,放在最后一個節(jié)點(diǎn)上,如果節(jié)點(diǎn)的數(shù)量達(dá)到9個,則開始判斷是否樹化,樹化時判斷長度是否大于32,不滿足則使桶的長度翻倍.