1 前言

該文章的内容是建立在讀者對HashMap有初步了解的基礎上的

HashMap中有很多知識點，比如哈希表、位運算、連結清單、紅黑樹等，HashMap 的源碼也是很值得大家去學習的

2 哈希表

在講源碼之前首先了解一下什麼是哈希表

Hash表也稱為散清單，也有直接譯作哈希表，Hash表是一種根據關鍵碼值（key-value）而直接進行通路的資料結構。也就是說它通過把關鍵碼值映射到表中的一個位置來通路記錄，以此來加快查找的速度。

這個映射函數叫做

散列函數

，存放記錄的數組叫做

散清單

。在連結清單、數組等資料結構中，查找某個關鍵字，通常要周遊整個資料結構，也就是O(N)的時間級，但是對于哈希表來說，隻是O(1)的時間級。

Java集合源碼解析之——HashMap1 前言2 哈希表3 HashMap4 字段屬性5 構造函數6 擴容機制7 JDK1.8中擴容機制改進8 JDK1.8中hash()改進

① 存放在哈希表中的資料是

key-value鍵值對

，比如存放哈希表的資料為:

{Key1-Value1, Key2-Value2, Key3-Value3, Key4-Value4, Key5-Value5}
如果我們想查找是否存在鍵值對 Key3-Value3，首先通過 Key3 經過散列函數，得到值 k3，然後通過 k3 和散清單對應的值找到是 Value3。

② 當然也有可能存放哈希表的值隻是 Value1,Value2,Value3這種類型：

{Value1, Value2, Value3, Value4, Value5}
這時候我們可以假設 Value1 是等于 Key1的，也就是{Value1-Value1, Value2-Value2, Value3-Value3, Value4-Value4, Value5-Value5}可以将 Value1經過散列函數轉換成與散清單對應的值。

為了更好地了解Hash表，我們以漢語詞典為例

漢語字典的優點是我們可以通過前面的拼音目錄快速定位到所要查找的漢字。當給定我們某個漢字時，大腦會自動将漢字轉換成拼音（如果我們認識，不認識可以通過偏旁部首），這個轉換的過程我們可以看成是一個散列函數，之後在根據轉換得到的拼音找到該字所在的頁碼，進而找到該漢字。

漢語字典是哈希表的典型實作，但是我們仔細思考，會發現如果多個 key 通過散列函數會得到相同的值，這時候怎麼辦？

對于這個問題，多個 key 通過散列函數得到相同的值，這其實也是哈希表最大的問題——

沖突

。

如何解決這個問題，我們先來看看漢語字典的方法：

① 開放位址法 。 當遇到沖突，此時通過另一種函數再計算一遍，得到相應的映射關系 。比如對于漢語字典，一個字 “餘”，拼音是“yu”，我們将其放在頁碼為567(假設在該位置)，這時候又來了一個漢字“于”，拼音也是“yu”，那麼這時候我們要是按照轉換規則，也得将其放在頁碼為567的位置，但是我們發現這個頁碼已經被占用了，這時候怎麼辦？我們可以在通過另一種函數，得到的值加1。那麼漢字"于"就會被放在576+1=577的位置。
② 鍊位址法 。 當遇到沖突，直接往目前沖突位置的子數組或者子連結清單裡面填充即可 。比如對于漢語字典，我們可以将字典的每一頁都看成是一個子數組或者子連結清單，當遇到沖突了，直接往目前頁碼的子數組或者子連結清單裡面填充即可。那麼我們進行同音字查找的時候，可能需要周遊其子數組或者子連結清單。如下圖所示：

Java集合源碼解析之——HashMap1 前言2 哈希表3 HashMap4 字段屬性5 構造函數6 擴容機制7 JDK1.8中擴容機制改進8 JDK1.8中hash()改進

對于開放位址法，可能會遇到二次沖突，三次沖突，是以需要良好的散列函數，分布的越均勻越好。

對于鍊位址法，雖然不會造成二次沖突，但是如果一次沖突很多，那麼會造成子數組或者子連結清單很長，那麼我們查找所需周遊的時間也會很長。

3 HashMap

顧名思義，HashMap 是一個利用哈希表原理來存儲元素的集合。遇到沖突時，HashMap 是采用的鍊位址法來解決。

3.1 HashMap定義

HashMap 是一個散清單，它存儲的内容是鍵值對(key-value)映射，而且 key 和 value 都可以為 null。

java.util.HashMap 繼承 AbstractMap 抽象類，同時實作 Map、 Cloneable、 Serializable 接口

public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable { 
            //... 
        }

3.2 關于實作 Map 接口

Map 接口定義了一組鍵值對映射通用的操作。儲存一組成對的鍵-值對象，提供key（鍵）到value（值）的映射，Map中的key不要求有序，不允許重複。value同樣不要求有序，但可以重複。

但是我們發現該接口方法有很多，我們設計某個鍵值對的集合有時候并不像實作那麼多方法，那該怎麼辦？

JDK 還為我們提供了一個抽象類 AbstractMap ，該抽象類繼承 Map 接口，是以如果我們不想實作所有的 Map 接口方法，就可以選擇繼承抽象類 AbstractMap 。

但是我們發現 HashMap 類即繼承了 AbstractMap 接口，也實作了 Map 接口，這樣做難道不是多此一舉？LinkedHashSet 集合也有這樣的寫法。
據 java 集合架構的創始人Josh Bloch描述，這樣的寫法是一個失誤。在java集合架構中，類似這樣的寫法很多，最開始寫java集合架構的時候，他認為這樣寫，在某些地方可能是有價值的，直到他意識到錯了。顯然的，JDK的維護者，後來不認為這個小小的失誤值得去修改，是以就這樣存在下來了。

3.3 關于實作Cloneable 及 Serializable 接口

HashMap 集合還實作了 Cloneable 接口以及 Serializable 接口，分别用來進行對象克隆以及将對象進行序列化。

4 字段屬性

//序列化和反序列化時，通過該字段進行版本一緻性驗證
private static final long serialVersionUID = 362498820763181265L;

//預設 HashMap 集合初始容量為16（必須是 2 的倍數）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//集合的最大容量，如果通過帶參構造指定的最大容量超過此數，預設還是使用此數
static final int MAXIMUM_CAPACITY = 1 << 30;

//預設的填充因子(裝載因子)
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//當桶(bucket)上的結點數大于這個值時會轉成紅黑樹(JDK1.8新增)
static final int TREEIFY_THRESHOLD = 8;

//當桶(bucket)上的節點數小于這個值時會轉成連結清單(JDK1.8新增)
static final int UNTREEIFY_THRESHOLD = 6;

//(JDK1.8新增)當集合中的容量大于這個值時，表中的桶才能進行樹形化 ，否則桶内元素太多時會擴容，而不是樹形化,
//為了避免進行擴容、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;

//初始化使用，長度總是2的幂
transient Node<K,V>[] table;

//儲存緩存的entrySet()
transient Set<Map.Entry<K,V>> entrySet;

//此映射中包含的鍵值映射的數量。（集合存儲鍵值對的數量）
transient int size;

//跟前面ArrayList和LinkedList集合中的字段modCount一樣，記錄集合被修改的次數
//主要用于疊代器中的快速失敗
transient int modCount;

//調整大小的下一個大小值（容量*加載因子）。capacity * loadfactor
int threshold;

//散清單的加載因子
final float loadFactor;

4.1 字段屬性講解

①

Node<K,V>[ ] table

HashMap 是由數組+連結清單+紅黑樹組成，這裡的數組就是 table 字段。後面對其進行初始化長度預設是 DEFAULT_INITIAL_CAPACITY= 16。而且 JDK 聲明數組的長度總是 2的n次方(一定是合數)，為什麼這裡要求是合數，一般雜湊演算法為了避免沖突都要求長度是質數，這裡為什麼要求是合數，下面在介紹 HashMap 的hashCode() 方法(散列函數)，再進行講解。

②

size

集合中存放key-value 的實時對數。

③

loadFactor

裝載因子，是用來衡量 HashMap 滿的程度，計算HashMap的實時裝載因子的方法為：size/capacity，而不是占用桶的數量去除以capacity。capacity 是桶的總數，也就是 table 的長度length。

④

threshold

計算公式：capacity * loadFactor。這個值是目前已占用數組長度的最大值。過這個數目就重新resize(擴容)，擴容後的 HashMap 容量是之前容量的兩倍

5 構造函數

① 預設無參構造函數

//預設構造函數，初始化加載因子loadFactor = 0.75
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

② 指定初始容量的構造函數

public HashMap(int initialCapacity, float loadFactor) {
        //初始化容量不能小于 0 ，否則抛出異常
        if (initialCapacity < 0) 
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);

        //如果初始化容量大于2的30次方，則初始化容量都為2的30次方
        if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;

        //如果加載因子小于0，或者加載因子是一個非數值，抛出異常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
}

//傳回大于等于initialCapacity的最小的二次幂數值
//>>> 操作符表示無符号右移，高位取0
//| 按位或運算
static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

6 擴容機制

JDK1.7使用數組+連結清單；JDK1.8使用數組+連結清單+紅黑樹。

連結清單長度大于8轉為紅黑樹，紅黑樹的節點數小于6轉化為連結清單。

loadFactor裝載因子（一般為0.75）：用來衡量 HashMap 滿的程度。

loadFactor = size/capacity
threshold = capacity * loadFactor

裝載因子非常重要，應嚴格限制在 0.7~0.8 以下，預設的負載因子0.75，是對空間和時間效率的一個平衡選擇。超過 0.8 ，查表時的CPU緩存按照指數曲線上升。

如果記憶體空間很多而又對時間效率要求很高，可以降低負載因子loadFactor 的值；相反，如果記憶體空間緊張而對時間效率要求不高，可以增加負載因子 loadFactor 的值，這個值可以大于1。

裝載因子調小，這樣比較容易觸發擴容機制，擴容機制觸發，占用更多的記憶體空間，但是可以減少桶内部的連結清單化和樹形化，進而增加查找效率，也就是以空間換時間。

7 JDK1.8中擴容機制改進

擴容涉及到

rehash

、

複制資料

等操作，是以非常耗能。

相比于JDK1.7，JDK1.8使用的是2次幂的擴充(指長度擴為原來2倍)，是以，元素的位置要麼是在原位置，要麼是在原位置再移動 2^n的位置。

resize() 1.7傳參自定義newcap，1.8自動擴容2倍

JDK1.8在擴充HashMap的時候，不需要像JDK1.7的實作那樣重新計算hash，隻需要看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”。(深入了解請看這篇文章)

這個設計确實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認為是随機的，是以resize的過程，均勻的把之前的沖突的節點分散到新的bucket了。這一塊就是

JDK1.8新增的優化點

。

//源碼
//該語句判斷是否落在“原索引”，還是落在“原索引+oldCap”
if ((e.hash & oldCap) == 0){} //原索引
else{} //原索引+oldCap

此外，JDK1.7中rehash的時候，舊連結清單遷移新連結清單的時候，如果在新表的數組索引位置相同，則連結清單元素會倒置（采用頭插法），但JDK1.8不會倒置（采用尾插法）。

采用頭插法，高并發容易引起循環連結清單

。

8 JDK1.8中hash()改進

重哈希

在 JDK1.8 中還有個高位參與運算，hashCode() 得到的是一個32位 int 類型的值，通過hashCode()的高16位異或低16位（将高16位滲透到低16位中）實作的：

(h = k.hashCode()) ^ (h >>> 16)

，主要是從速度、功效、品質來考慮的，

這麼做可以在數組table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷

。

key.hashCode()是固定的，JDK1.8的hash()是加工後的key.hashCode()，而JDK1.7的hash()是直接用的 key。

加工過程：key.hashCode() ^ (h >>> 16)

加工後，key.hashCode()的低16位有更好的性能，減少碰撞率。

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}     
i = (table.length - 1) & hash;//這一步是在後面添加元素putVal()方法中進行位置的确定

下面舉例說明一下，n為table的長度：

Java集合源碼解析之——HashMap1 前言2 哈希表3 HashMap4 字段屬性5 構造函數6 擴容機制7 JDK1.8中擴容機制改進8 JDK1.8中hash()改進

Java集合源碼解析之——HashMap1 前言2 哈希表3 HashMap4 字段屬性5 構造函數6 擴容機制7 JDK1.8中擴容機制改進8 JDK1.8中hash()改進

1 前言

2 哈希表

3 HashMap

3.1 HashMap定義

3.2 關于實作 Map 接口

3.3 關于實作Cloneable 及 Serializable 接口

4 字段屬性

4.1 字段屬性講解

5 構造函數

6 擴容機制

7 JDK1.8中擴容機制改進

8 JDK1.8中hash()改進

繼續閱讀

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

JBoss,Geronimo和Glassfish初窺

scala (3) Function 和 Method