一,HashMap的基本資料結構
HashMap繼承了Map抽象類,實作了Map,Cloneable,Serializable接口。
- 1.7 數組 + 連結清單
- 1.8 數組 + (連結清單 | 紅黑樹)
HashMap類中的元素是Node類,翻譯過來就是節點,是定義在HashMap中的一個内部類。(IT楓鬥者怎麼樣)
Node的基本屬性
- hash:key的哈希值
- key:節點的key,類型和定義HashMap時的key相同
- value:節點的value,類型和定義HashMap時的value相同
- next:該節點的下一節點
二, 為什麼要進行樹化?樹化的規則?
樹化意義
hash 表的查找,更新的時間複雜度是 O(1),而紅黑樹的查找,更新的時間複雜度是 O(log_2n ),TreeNode 占用空間也比普通 Node 的大,如非必要,盡量還是使用連結清單。(IT楓鬥者怎麼樣)
但是紅黑樹用來避免 DoS 攻擊,防止連結清單超長時性能下降O(n),樹化應當是偶然情況,是保底政策。
樹化規則
HashMap裡面定義了一個常量TREEIFY_THRESHOLD = 8,當連結清單長度超過樹化門檻值 8 時,先嘗試調用resize()方法進行擴容來減少連結清單長度,如果數組容量已經 >=64(MIN_TREEIFY_CAPACITY),才會進行樹化,Node節點轉為TreeNode節點(TreeNode也是HashMap中定義的内部類)。
TreeNode除了Node的基本屬性,還儲存了父節點parent, 左孩子left,右孩子right,還有紅黑樹用到的red屬性。(IT楓鬥者怎麼樣)
Note:
hash 值如果足夠随機,則在 hash 表内按泊松分布,在擴容因子(factor) 0.75 的情況下,長度超過 8 的連結清單出現機率是千萬分之6,樹化門檻值選擇 8 就是為了讓樹化幾率足夠小。
如果數組擴容還不到64,連結清單長度未減少,連結清單長度是有可能超過8的。(IT楓鬥者怎麼樣)
三,HashMap的索引是如何計算的?
- 首先,計算對象的 hashCode(),得到原始hash值
- 再進行調用 HashMap 的 hash() 方法進行二次哈希,得到二次hash值
- 最後 & (capacity – 1) 得到索引(使用二次hash值和數組容量 - 1進行位與運算)
四,數組容量為何是 2 的 n 次幂?
- 計算索引時效率更高:如果是 2 的 n 次幂可以使用位與運算代替取模
- 擴容時重新計算索引效率更高:hash(原始hash) & oldCap(原始容量) == 0 的元素留在原來位置 ,否則新位置 = 舊位置 + oldCap(原始容量)
五,為什麼要進行二次 hash?
- 二次 hash() 是為了綜合高位資料,讓哈希分布更為均勻
- 二次 hash 是為了配合 容量是 2 的 n 次幂 這一設計前提,如果 hash 表的容量不是 2 的 n 次幂,則不必二次 hash
- 容量是 2 的 n 次幂 這一設計計算索引效率更好,但 hash 的散列性就不好,需要二次 hash 來作為補償,沒有采用這一設計的典型例子是 Hashtable
六,HashMap的Put流程
- HashMap 是懶惰建立數組的,首次使用才建立數組
- 計算索引(桶下标)
- 如果桶(bucket)下标還沒人占用,建立 Node 占位傳回
- 如果桶下标已經有人占用
- a、已經是 TreeNode 走紅黑樹的添加或更新邏輯
- b、是普通 Node,走連結清單的添加或更新邏輯,如果連結清單長度超過樹化門檻值,走樹化邏輯
- 傳回前檢查容量是否超過門檻值,一旦超過進行擴容。(IT楓鬥者怎麼樣)
七,HashMap如何進行擴容。
什麼時候觸發擴容?
一般情況下,當元素數量超過門檻值時便會觸發擴容。每次擴容的容量都是之前容量的2倍。
HashMap的容量是有上限的,必須小于1<<30,即1073741824。如果容量超出了這個數,則不再增長,且門檻值會被設定為Integer.MAX_VALUE(
即永遠不會超出門檻值了)。(IT楓鬥者怎麼樣)
這要分HashMap1.7和HashMap1.8情況
HashMap1.7
在JDK1.7的擴容機制相對簡單,有以下特質:
- 空參數的構造函數:以預設容量、預設負載因子、預設門檻值初始化數組。内部數組是空數組。
- 有參構造函數:根據參數确定容量、負載因子、門檻值等。
- 第一次put時會初始化數組,其容量變為不小于指定容量的2的幂數。然後根據負載因子确定門檻值。
- 如果不是第一次擴容,則 新容量=舊容量X2 新門檻值=新容量X負載因子。
HashMap 1.8
HashMap的容量變化通常存在以下幾種情況:
- 空參數的構造函數:執行個體化的HashMap預設内部數組是null,即沒有執行個體化。第一次調用put方法時,則會開始第一次初始化擴容,長度為16。
- 有參構造函數:用于指定容量。會根據指定的正整數找到不小于指定容量的2的幂數,将這個數設定指派給門檻值(threshold)。第一次調用put方法時,會将門檻值指派給容量,然後讓 門檻值=容量X負載因子(是以并不是我們手動指定了容量就一定不會觸發擴容,超過門檻值後一樣會擴容!!)(IT楓鬥者怎麼樣)
- 如果不是第一次擴容,則容量變為原來的2倍,門檻值也變為原來的2倍。
此外還有幾個細節需要注意:
- 首次put時,先會觸發擴容(算是初始化),然後存入資料,然後判斷是否需要擴容;
- 不是首次put,則不再初始化,直接存入資料,然後判斷是否需要擴容;
- 1.7 是大于門檻值(threshold = factor * capacity )且沒有空位時才擴容,而 1.8 是大于門檻值就擴容
- 1.7是先擴容再插入資料,1.8是先插入資料再擴容
- 擴容是一個特别耗性能的操作,是以當程式員在使用HashMap的時候,估算map的大小,初始化的時候給一個大緻的數值,避免map進行頻繁的擴容
- HashMap的容量達到2的30次方,就不會再進行擴容了。(IT楓鬥者怎麼樣)
八,擴容因子(factor)為何預設是 0.75?
在空間占用與查詢時間之間取得較好的權衡
- 大于0.75,空間節省了,但連結清單就會比較長影響性能
- 小于0.75,沖突減少了,但擴容就會更頻繁,空間占用也更多
九,HashMap的key
- HashMap 的 key 可以為 null,但 Map 的其他實作則不然
- 作為 key 的對象,必須實作 hashCode 和 equals,并且 key 的内容不能修改(不可變)
- key 的 hashCode 應該有良好的散列性。(IT楓鬥者怎麼樣)
十,總結HashMap1.7和1.8有什麼不同?
1. 資料結構
- 1.7 數組 + 連結清單
- 1.8 數組 + (連結清單 | 紅黑樹)
2. 初始化方式
- 1.7中resize()方法負責擴容,inflateTable()負責建立表;
- 1.8中resize()方法在表為空時,建立表;在表不為空時,擴容。(IT楓鬥者怎麼樣)
3. 擴容方式
擴容時機
1.7在插入資料之前擴容,而1.8插入資料成功之後擴容;
1.7 是大于門檻值(threshold = factor * capacity )且沒有空位時才擴容,而 1.8 是大于門檻值就擴容。(IT楓鬥者怎麼樣)
插入方式
1.7 是頭插法,1.8是尾插法,是以1.7可能會出現并發死鍊現象,兩者在并發情況下都會出現資料錯亂
索引計算
1.8在擴容時計算索引做了優化。(IT楓鬥者怎麼樣)