從細節出發認識原來是這樣的這樣的hashmap

Java中HashMap想必是最常用的集合類之一

Java

其中Map是屬於JCF中頂級介面 另一個是Collection

Map介面類型如下

Java

有如下幾個特點

1. size返回int表示最大容量不可能超過Integer.MAX_VALUE 否則無法表示 事實上 hashmap的最大容量為

Java

也就是其實HashMap是存在最大容量的 那麼思考為啥最大容量不是1

2. containsKey以及containsValue,get,remove均使用Object作為參數而不是泛型

what-are-the-reasons-why-map-getobject-key-is-not-fully-generic

我們在使用HashMap的時候一般會調用如下介面

Java

事實上我們調用的是經驗值（通常初始化容量為16（2^4） 負載因子為0.75）

引入了兩個新的變數：

CAPACITY 容量 表示內部數組的大小

LOAD_FACTOR 負載因子 表示在給定容量下分配數組的分配概率，通常該參數影響較大

比如說負載因子為10 那麼可以認為碰撞概率為10 也就是平均每個hash碰撞率在10 因此經驗值選擇0.75 較為合理

和這兩個參數有關的是threshold參數

threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);

該參數表示閾值 意義表示當size>=threshold 需要resize整個HashMap

1. 初始化

分析如下代碼

Java

注意細節 capacity是1左移的結果，也就是初始化容量必然是2的pow（距離傳入數字最靠近的不小於指定數字的1的左移） 而不是自己傳入的數字。（一般來說素數的衝突較小，為何選擇pow(2,n)，下文描述）table為存儲Entry的數組，也就是我們使用的實體（K-V映射）

Java

其中key為泛型key value為泛型value 並且記錄了鏈表指針next 可窺全圖

當然jdk8總當鏈表長度超過一定長度將自動轉化成紅黑樹

2.當開發者調用put時操作如下

Java

首先check key是否為空，否則特殊處理為0

Java

即null key必然放置在table[0],因此需要循環查找該鏈表 如果該鏈表中包含key為null則直接替換否則插入對應null key

3.當key不是null時 首先計算key的對應hash

Java

hash函數盡量得出均勻的hash值。因此使用了多次循環右移（Java8進行了改造）

4. 根據hash找到指定的在table的位置

Java

這邊解釋了為何使用pow(2,n)作為table的length。如果常規做法通常就是mod。但是基於框架級別的選擇除法的效率和與操作的效率相比較差。pow(2,n)-1 可以得出比如0111, 01111,011111等等

此時做與操作可以將hash值的末尾n位的值拿出來。因此對於hash的要求必須生成的hash在末端不要重複。相當於會抹去32-n的前位。 而如果不是2的倍數的情況下可能無法獲得更多的信息來作為hash分配

5. 當在對應的hash路徑下如果可以找到指定的Key那麼直接覆蓋替換（由此要求hashcode和equals兩個方法在覆蓋重寫必須一起重寫，否則很容易出現紕漏）

Java

6. 如果對應的key不存在的情況下

Java

檢測當前size是否比閾值大，如果是則需要擴容。每次擴容均是前面的容量的2倍，此時需要rehash操作 每次rehash其實由於長度變為2倍所以對於只有低位的hashcode可能並不會出現rehash操作

7. 容量為最大容量時，此時不再擴充。同時將閾值設置為最大值Integer.MAX_VALUE

當容量未達到最大容量時，此時需要將老的數據全部放到新的數組中（相當耗時）因此一個合理的負載因子和初始化容量很有必要（試想當一個大的hashmap 重頭開始擴容需要多少次，比如size為100000 10000

Java

當然由於鏈表重新transfer，其順序也發生了倒置

8. 根據計算的hash以及算出的對應的index直接 將原先數組對應的對象作為next指針即可

Java

由於通篇均沒有使用鎖，因此HashMap不是線程安全的，如果作為共享對象很容易出現各種各樣的問題。

小測試如下

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！