Java集合：HashMap
- 2021 年 9 月 19 日
- 筆記
Hashmap是一個存儲key-value的映射表。
優點：
- 索引數據快，查找一個數據對的時間複雜度是O(1)
- 增加、刪除一個數據的時間複雜度是O(1)
- key不能重複，可以存儲一個null值
存儲：
- 通過key的hashcode值存儲在指定數組下標中
- 用鏈表存儲hashcode值一樣，都是key不一樣的數據，鏈表長度大於8時轉換為紅黑樹（為了提高查詢效率）
HashMap的內部結構
Hashmap封裝了一個Node數組進行存儲key-value的鍵值對，常用的get和put等都是對這個Node數組進行操作。
Node有四個屬性：key、value、hash、next
- hash：32位的整數，通過key的hashcode計算出來，hash&(數組長度-1) = 元素在數組的下標
- next：指向Node節點的指針，不同的key計算出來的hash值可能是一樣的，如果要存儲的下標位置已經有值了，用鏈表將元素連起來
初始化HashMap：一開始HashMap內部是一個空的Node數組，插入數據後才會被創建
HashMap的常用操作
HashMap一開始的Node數組是空的，在第一次put元素後會默認創建一個長度為n = 16的數組
put一個key-value元素進入map中
計算key的hashcode值算出hash，得出index=hash&(長度-1)，將元素存在數組[index]的位置。
有兩種情況：
- index這個位置已經有key了，比如當數組的長度是16時，33&(16-1) = 1. , 1 & (16 – 1) = 1 ; key值不同，但是index一樣。
這裡就用到了Node的next屬性，讓數組index下標所在的（最後一個）元素的next指向插入的元素，
- 可以直接將元素存入數組中
通過key從map中get一個元素
計算key的hashcode值算出hash，得出index=hash&(長度-1)
有兩種情況：
- 如果數組[index]的值為null，就說明不存在這個元素
- 不為null，還得比較key值，通過遍歷鏈表（如果有的話），一個個比較key值，返回key相同的元素，或null
HashMap的優化操作
- 數組長度n永遠是2的冪：hash&(n-1)是元素在數組的下標，（2的冪-1）的二進制會是一連串的1，然後與hash值進行與運算
- 與運算之後的結果永遠不會超過數組的界限
- 充分的利用了hash值二進制
- 負載因子：hashmap設置了一個0.75的閾值，也就是數組中的元素數量大於數組長度的0.75時，進行數組擴容，擴展成原來的兩倍
- 當數組長度不夠時，會出現很多的hash衝突，就是鏈表很長，檢索效率慢，擴容後通過hash&(n-1)會讓很長的鏈表散開
- 鏈錶轉換成紅黑樹：鏈表長度大於8，但是數組元素數量沒達到閾值，會選擇將鏈錶轉換為紅黑樹，提高查詢效率
- 要求數組長度已經大於64，避免數組擴容和鏈錶轉紅黑樹的衝突
- hash值的計算：hash值的前16位與key的hashcode一樣，後16位由hashcode的前16位與後16位異或運算得到
- 充分利用hashcode的值，增加隨機性，減少hash衝突
