一、前言

??Java的容器是面試中的必考點(diǎn)，最近為了準(zhǔn)備春招，我開始閱讀容器的源碼。今天研究了一下HashMap的源碼，頗有心得，所以寫篇博客分享一下HashMap的實(shí)現(xiàn)原理。內(nèi)容主要包括HashMap的底層結(jié)構(gòu)，hash函數(shù)的原理，以及HashMap的容量機(jī)制等內(nèi)容。內(nèi)容很多，但是這些內(nèi)容彼此相輔相成，并不適合分開來(lái)敘述，所以將它們放在一起進(jìn)行講解。相信大家看完這篇博客，將清楚的理解HashMap高效的秘訣。

二、解析

?2.1 什么是Hash

??Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長(zhǎng)度的輸入，通過(guò)散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)散列成相同的輸出，所以不可能從散列值來(lái)唯一的確定輸入值。簡(jiǎn)單的說(shuō)就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)（此處引用其他博客）。簡(jiǎn)單來(lái)說(shuō)，就是將一個(gè)任意類型的數(shù)據(jù)，根據(jù)一定的算法，計(jì)算出一個(gè)標(biāo)識(shí)它的int類型的整數(shù)，或者一個(gè)字符串，也就是hash值。

??注意：根據(jù)同一散列函數(shù)計(jì)算出的散列值如果不同，那么輸入值肯定也不同；但是，根據(jù)同一散列函數(shù)計(jì)算出的散列值如果相同，輸入值不一定相同。兩個(gè)不同的輸入值，根據(jù)同一散列函數(shù)計(jì)算出的散列值相同的現(xiàn)象叫做hash碰撞。

?2.2 HashMap的底層結(jié)構(gòu)

??我們首先來(lái)談一談HashMap的底層結(jié)構(gòu)，即HashMap是如何保存數(shù)據(jù)的，若連這個(gè)都不清楚，那其余的也無(wú)從談起。HashMap的結(jié)構(gòu)概括說(shuō)來(lái)就是：數(shù)組 + 鏈表。

??我們知道，HashMap中的元素都是Key - Value類型的，我們姑且將每一個(gè)元素稱為一個(gè)節(jié)點(diǎn)Node。在HashMap中，所有的Node都是存在一個(gè)數(shù)組中，而這個(gè)數(shù)組的聲明如下：

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;

??可以看到，這個(gè)數(shù)組table的類型是Node類型，其實(shí)就是我們說(shuō)的Key - Value。那當(dāng)我們進(jìn)行put操作時(shí)，元素將如何存入這個(gè)數(shù)組中呢？這時(shí)候就要用到我們前面提到的Hash了。當(dāng)我們往HashMap中存入一個(gè)元素時(shí)，HaspMap底層會(huì)調(diào)用hash函數(shù)，計(jì)算出元素key的hash值，然后再用這個(gè)hash值與HashMap的總?cè)萘窟M(jìn)行求余，得到的余數(shù)就是這個(gè)元素在數(shù)組中存放的下標(biāo)。

??既然如此，那就可能會(huì)出現(xiàn)hash碰撞的情況——即兩個(gè)不同的元素，根據(jù)以上方法求出的下標(biāo)值卻相等。這要如何解決呢？HashMap的做法就是采用 數(shù)組+鏈表 的方式解決：在存儲(chǔ)元素的數(shù)組中，每個(gè)位置并不是存儲(chǔ)一個(gè)單獨(dú)的Node，而是存儲(chǔ)一個(gè)鏈表，而這個(gè)Node就是鏈表中的一個(gè)節(jié)點(diǎn)，當(dāng)一個(gè)元素要放入數(shù)組的某個(gè)位置時(shí)，若這個(gè)位置已經(jīng)有元素了，那就將這個(gè)元素接在最后一個(gè)元素的后面。如下圖所示，數(shù)組下標(biāo)為1的位置有三個(gè)元素，它們共同形成一個(gè)鏈表。

??我們來(lái)看看HashMap中Node的代碼，幫助我們理解數(shù)組+鏈表的結(jié)構(gòu)。通過(guò)下面的代碼可以看到，Node是HashMap的一個(gè)內(nèi)部類，他有四個(gè)成員變量：

• hash：記錄節(jié)點(diǎn)的hash值；
• key：記錄節(jié)點(diǎn)的key值；
• value：記錄節(jié)點(diǎn)的value值；
• next：記錄當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)；

??而鏈表的結(jié)構(gòu)，就是通過(guò)next成員變量來(lái)實(shí)現(xiàn)的。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    
    //其余方法......
}

?2.3 HashMap的容量機(jī)制——高效秘訣

??理解了HashMap的底層結(jié)構(gòu)之后，我們?cè)賮?lái)探索它高效的秘訣。我們知道，HashMap是優(yōu)化了查找速度的一種集合，查詢效率極高。而在HashMap中，查詢一個(gè)元素的步驟如下：

1. 首先通過(guò)向hash函數(shù)傳入需要查找的元素的key值，hash函數(shù)計(jì)算出key的hash值；
2. 將hash值與總?cè)萘窟M(jìn)行取模運(yùn)算，計(jì)算出數(shù)組元素在數(shù)組中的下標(biāo)；
3. 根據(jù)數(shù)組下標(biāo)獲得元素所在的鏈表；
4. 從鏈表的第一個(gè)節(jié)往后依次比較key值；
5. 找到key值相等的節(jié)點(diǎn)返回；

??以上步驟可以歸結(jié)為以下代碼（注意：以下代碼是我從源碼中抽取出來(lái)組合在一起的，實(shí)際上它們并不在一個(gè)方法中）：

Object get(Object key){
    // 1：獲取key的hash值
    int h = hash(key);
    
    // 2-3：從數(shù)組中獲取元素所在的鏈表
    int len = table.length;
    Node n = table[ h & (len - 1) ]; // 重點(diǎn)：這里使用 h&(len-1) 取代了 h%len
    
    // 4-5：遍歷鏈表n，并返回查找結(jié)果（代碼省略）
    ......
}

??上面的代碼只有一個(gè)地方可能讓人疑惑，那就是取模操作%被按位與運(yùn)算&所取代。上面的代碼中，數(shù)組的中括號(hào)中本應(yīng)該是h%len，但是大家去查閱源碼，會(huì)發(fā)現(xiàn)實(shí)際寫的是h & (len-1)。這是什么意思呢，其實(shí)在特殊情況下，這就是取模運(yùn)算。下面我們就來(lái)講解一下滿足 h & (len-1) == h % len的特殊情況。

??這種特殊情況就是：一個(gè)數(shù)對(duì)2^n取模，等價(jià)于這個(gè)數(shù)對(duì)2^n - 1做與運(yùn)算，即num % 2^n == num & (2^n -1)。我們舉個(gè)例子來(lái)說(shuō)明這個(gè)公式的原理：假設(shè)上面的公式中，n==3，即我們要對(duì)2^3，也就是8取模，8轉(zhuǎn)換成二進(jìn)制是1000，而2^3-1 == 7，轉(zhuǎn)換成二進(jìn)制就是0111，然后與一個(gè)數(shù)做與運(yùn)算，即num & (2^3 -1)，結(jié)果將得到num轉(zhuǎn)換成二進(jìn)制后的末尾三位。而我們看num / 8，實(shí)際上就是二進(jìn)制的num向右移動(dòng)三位，移掉掉的那三位就是num / 8的余數(shù)，即num % 8。而移掉的三位數(shù)，不正是我們通過(guò)num & (2^3 -1)獲得的嗎。比方說(shuō)10 % 8 == 2，而10 & (7) = 1010 & 0111 == 0010 == 2。這個(gè)地方需要好好理解一下，如果實(shí)在不理解，那就記住這個(gè)結(jié)論。

??在HashMap中，保證了存儲(chǔ)元素的數(shù)組的大小一定是2^n，所以在內(nèi)部，通過(guò)hash值與數(shù)組容量取余的操作，都用上面說(shuō)的與運(yùn)算取代了。這樣做的好處是，與運(yùn)算直接操作內(nèi)存，效率極高，而在HashMap中，獲取數(shù)組下標(biāo)是一個(gè)非常頻繁的操作，無(wú)論是get還是put都要用上，所以這種優(yōu)化對(duì)HashMap的查詢效率有很多的提升。在HashMap中，有兩個(gè)靜態(tài)變量，分別是默認(rèn)初始容量和最大容量，可以看到，它們都是都是2的n次方，而且沒有直接寫成數(shù)字，而是一個(gè)移位公式，如 1 << 4，就是為了提醒大家HashMap的容量機(jī)制。

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

??說(shuō)到這里，可能有人會(huì)有疑問(wèn)了：HashMap不是有構(gòu)造器，可以指定初始容量嗎，如果我們指定一個(gè)不是2^n的容量，不就破壞了這種機(jī)制嗎？答案當(dāng)然是不會(huì)的，我們雖然可以指定HashMap的初始容量，但是不代表它會(huì)直接使用我們指定的容量。當(dāng)我們?yōu)?code>HashMap指定一個(gè)初始容量時(shí)，它不會(huì)直接使用這個(gè)容量，而是計(jì)算出第一個(gè)大于等于這個(gè)容量的且滿足2^n的數(shù)，若這個(gè)數(shù)大于HashMap運(yùn)行的最大值，則直接使用最大值。而且我們知道，Java中的大多數(shù)容器都有自動(dòng)擴(kuò)容機(jī)制，包括HashMap，而HashMap為了滿足容量一定是2^n，擴(kuò)容時(shí)是在原來(lái)的基礎(chǔ)上乘2，因?yàn)?code>2^n乘以2還是滿足2^n。

??其實(shí)，使用位運(yùn)算代替取模運(yùn)算，除了性能之外，還有一個(gè)好處就是可以很好的解決負(fù)數(shù)的問(wèn)題。因?yàn)槲覀冎溃琱ashcode的結(jié)果是int類型，而int的取值范圍是-2^31 ~ 2^31 - 1，即[ -2147483648, 2147483647]；這里面是包含負(fù)數(shù)的，我們知道，對(duì)于一個(gè)負(fù)數(shù)取模還是有些麻煩的。如果使用二進(jìn)制的位運(yùn)算的話就可以很好的避免這個(gè)問(wèn)題。首先，不管hashcode的值是正數(shù)還是負(fù)數(shù)。length-1這個(gè)值一定是個(gè)正數(shù)。那么，他的二進(jìn)制的第一位一定是0（有符號(hào)數(shù)用最高位作為符號(hào)位，“0”代表“+”，“1”代表“-”），這樣里兩個(gè)數(shù)做按位與運(yùn)算之后，第一位一定是個(gè)0，也就是，得到的結(jié)果一定是個(gè)正數(shù)。（此段引用參考博客）

?2.4 解析hash方法

??接下來(lái)，我們?cè)賮?lái)看看HashMap源碼中的計(jì)算哈希值的hash函數(shù)是如何實(shí)現(xiàn)的：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

??以上是JDK1.8中hash函數(shù)的實(shí)現(xiàn)（其他版本的hash方法有所差異，但是原理是一樣的），簡(jiǎn)介明了：方法接收一個(gè)參數(shù)，也就是Node的key值，然后判斷key值是否為null，若為null，則hash值為0；否則調(diào)用key的hashCode方法獲取hash值，并將hash值右移16位后與原hash值做異或運(yùn)算。這個(gè)方法還是很好理解的，除了一個(gè)地方，就是為什么要將hash值右移16位后做與運(yùn)算呢，調(diào)用hashCode方法獲取的hash值不能直接用嗎？這么做的原因還是為了優(yōu)化。

??我們?nèi)绾味x一個(gè)hash算法的優(yōu)劣？其中的一個(gè)重要因素就是盡量少發(fā)生hash碰撞。大家可以試想一下，HashMap最壞的情況是什么樣子：所有存入其中的元素，通過(guò)hash值計(jì)算出來(lái)的下標(biāo)都是一樣的，都放在數(shù)組的同一個(gè)位置，組成一個(gè)鏈表。這樣的情況下，HashMap便完全失去了意義，和一個(gè)普通的鏈表又有什么區(qū)別。而好的hash函數(shù)，可以使碰撞發(fā)生的概率大大減少，讓元素在數(shù)組中分別均勻，從而提高查找效率。

??而源碼中的異或運(yùn)算，實(shí)際上就是為了降低hash碰撞進(jìn)行的擾動(dòng)計(jì)算。為什么這么說(shuō)呢，舉個(gè)簡(jiǎn)單的例子：

HashMap的容量：8  ->  轉(zhuǎn)換成二進(jìn)制：1000

兩個(gè)要存如HashMap中的元素的hash值如下（下面兩個(gè)hash值只有最后4位完全匹配）：
    1、 0010 1010 0111 1001 0010 0101
    2、 0101 1101 1111 0100 0111 0101

這兩個(gè)hash值與容量8取模后得到：
    1、0101
    2、0101

??可以看到，上面例子中的兩個(gè)hash值差別巨大，但是它們和容量8進(jìn)行取模后的結(jié)果卻是一樣的，結(jié)果發(fā)生了hash碰撞。因?yàn)槿萘繉?duì)于容量8來(lái)說(shuō)，取模的做法是與8-1也就是7做按位與運(yùn)算，而7轉(zhuǎn)換成二進(jìn)制的結(jié)果是0111，也就是說(shuō)，取模的結(jié)果實(shí)際上就是取hash值的后3位，而hash值的前29位無(wú)論怎樣，都不會(huì)影響結(jié)果。所以就是上面兩個(gè)hash值差異巨大，但是后三位相同，導(dǎo)致它們求出的下標(biāo)是相同的。這種情況下，發(fā)生hash碰撞的幾率將會(huì)大大增加。所以，為了充分利用計(jì)算出的hash值的每一位，HashMap的源碼做出了一個(gè)優(yōu)化，將計(jì)算出的hash值向右移動(dòng)16位，讓后讓移動(dòng)后的值與原hash值做與運(yùn)算，計(jì)算出新的值。為什么是16位呢，因?yàn)?code>int是32位的，16位正好是32的一半。這樣，就充分利用了hash值的每一位，減少了hash碰撞的發(fā)生。

?2.5 JDK1.8對(duì)HashMap結(jié)構(gòu)的優(yōu)化——紅黑樹

??其實(shí)從JDK1.8開始，HashMap已經(jīng)不再是簡(jiǎn)單的數(shù)組+鏈表的存儲(chǔ)結(jié)構(gòu)，而是做出了一個(gè)巨大的變動(dòng)，在HashMap的數(shù)據(jù)存儲(chǔ)中引入了紅黑樹，變成了數(shù)組+鏈表+樹的結(jié)構(gòu)。下面我們來(lái)簡(jiǎn)單的談一談這種結(jié)構(gòu)。

??首先我們還是要回歸之前談過(guò)的HashMap最壞情況的問(wèn)題：HashMap中，所有的元素都在數(shù)組的同一個(gè)位置，在一條鏈表上。這時(shí)候，HashMap和一個(gè)鏈表基本上沒什么區(qū)別，之前的那些查詢優(yōu)化也就沒效果了。這時(shí)候查詢一個(gè)元素的時(shí)間復(fù)雜度是多少？當(dāng)然是和遍歷鏈表一樣——O（n）。當(dāng)然，這只是極端的情況，正常情況下不會(huì)出現(xiàn)，但是大部分元素集中在少數(shù)幾條鏈表上這種情況還是很常見的，比如key是自定義類型，而程序員提供了不好的hashCode方法，得到的hash值經(jīng)常發(fā)生碰撞。

??為了當(dāng)發(fā)生以上情況時(shí)效率不至于太慢，JDK1.8改變了HashMap的存儲(chǔ)結(jié)構(gòu)——當(dāng)HashMap中的某一條鏈表元素過(guò)多時(shí)，底層就會(huì)將其轉(zhuǎn)換為一棵紅黑樹。而紅黑樹的查詢時(shí)間復(fù)雜度為O(log n)，相比于鏈表的O（n）來(lái)說(shuō)要快上不少。在HashMap中有下面三個(gè)帶有默認(rèn)值的靜態(tài)變量，用來(lái)控制樹化過(guò)程：

/**
 * 桶的樹化閾值：
 *     即 鏈表轉(zhuǎn)成紅黑樹的閾值，在存儲(chǔ)數(shù)據(jù)時(shí)，
 *     當(dāng)鏈表長(zhǎng)度 > 該值時(shí)，則將鏈表轉(zhuǎn)換成紅黑樹
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 桶的鏈表還原閾值：
 *     即 紅黑樹轉(zhuǎn)為鏈表的閾值，當(dāng)在擴(kuò)容（resize（））時(shí)
 *     （此時(shí)HashMap的數(shù)據(jù)存儲(chǔ)位置會(huì)重新計(jì)算），在重新計(jì)算存儲(chǔ)位置后，
 *     當(dāng)原有的紅黑樹內(nèi)數(shù)量 < 6時(shí)，則將 紅黑樹轉(zhuǎn)換成鏈表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 最小樹形化容量閾值：
 *     即 當(dāng)哈希表中的總?cè)萘?> 該值時(shí)，才允許將鏈表轉(zhuǎn)換成紅黑樹,
 *     否則，當(dāng)元素太多時(shí)，則直接擴(kuò)容，而不是樹形化
 *     為了避免進(jìn)行擴(kuò)容、樹形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD
 */
static final int MIN_TREEIFY_CAPACITY = 64;

三、總結(jié)

??上面的內(nèi)容對(duì)HashMap的底層存儲(chǔ)，效率優(yōu)化機(jī)制做了一個(gè)較為詳細(xì)的介紹，相信看完之后會(huì)對(duì)HashMap有一個(gè)較為深入的理解。但是，這些只是HashMap的一部分，想要真正了解HashMap，還是要自己結(jié)合源碼，仔細(xì)的閱讀。希望我寫的這篇博客能夠?qū)σ恍┤擞兴鶐椭?/p>

四、參考

??以上內(nèi)容大部分參看下面兩篇博客后，根據(jù)自己的理解編寫：

• https://mp.weixin.qq.com/s/qCHkzs4JPOipB-ZzqrfbeQ —— 此篇分析hash函數(shù)
• https://mp.weixin.qq.com/s/8a5BTWomhe3R-jqT1ffwYw —— 此篇分析HashMap容量