HashMap可謂是面試中的高頻熱點(diǎn)問(wèn)題了，一般可能也就面試前突擊復(fù)習(xí)下，背些知識(shí)點(diǎn)，面試后可能就忘了，為了做到不遺忘，我們需要徹底弄懂它的機(jī)制。

Hash表介紹

首先我們看一張經(jīng)典的圖：

hash.jpg

HashMap的hash機(jī)制

HashMap的存儲(chǔ)形式

通過(guò)上面hash表的介紹，我們知道了hash表其實(shí)核心存儲(chǔ)還是數(shù)組，HashMap也一樣：

 /**
     * 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;

當(dāng)然，這個(gè)數(shù)組存的不再是上面的整數(shù)那么簡(jiǎn)單，而是一個(gè)對(duì)象結(jié)構(gòu)：

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
       //省略部分代碼
    }

HashMap的散列算法

首先，我們一般是存一個(gè)key-value進(jìn)來(lái)，第一步就是用key 的hash值計(jì)算一個(gè)hashcode出來(lái)（怎么計(jì)算后面再說(shuō)）
那HashMap到底是如何確定將這個(gè)hashcode代表的值放在table[]數(shù)組的哪個(gè)位置呢？計(jì)算方式代碼很簡(jiǎn)單，理解起來(lái)確實(shí)很難：

int n = table.length;
int hash = 通過(guò)key計(jì)算出來(lái)的hash值
int pos = (n-1)&hash

這段神奇的(n-1)&has其實(shí)和hash % n 道理是一樣的，但有些地方不一樣，
要說(shuō)位運(yùn)算效率高，能實(shí)現(xiàn)的黑科技也多，但代碼確實(shí)不好懂，這種計(jì)算方式一般人基本都搞不懂，這里我們重點(diǎn)分析下
以table.length = 16為例，所有的數(shù)據(jù)最終取余后都要分布在16個(gè)位置上，從感性上大家都有一種認(rèn)知：超過(guò)了16后，數(shù)據(jù)太大其實(shí)和分布在0到16之間是一樣的。這種認(rèn)知反應(yīng)在二進(jìn)制上就是：高位基本沒(méi)用，只要低位的信息就可以了。所以如果想要利用位運(yùn)算達(dá)到去余的目的，我們就得需要將hash的高位擦除，保留低位。保留多少位數(shù)肯定由table.length決定。
那么如何擦除數(shù)據(jù)呢？
還是以table.length=16為例，除余的結(jié)果肯定分布在0到15之間，假設(shè)hash值為 10100101 11000100 00100101（二進(jìn)制），那么真正有用的只后面四位（15轉(zhuǎn)換成二進(jìn)制后只有后面4位有效），所以看下這個(gè)運(yùn)算：

      10100101 11000100 00100101
 &    00000000 00000000 00001111
------------------------------------------------
      00000000 00000000 00000101

可以看到hash&（n-1)實(shí)際就是為了保留hash的低位數(shù)據(jù)，擦除高位數(shù)據(jù)，很明顯，想要擦除高位，（n-1）的結(jié)果低位必須是全1，這也就解釋了為什么HashMap的table長(zhǎng)度始終是2的平方，只有這樣，table.length-1才能保證低位結(jié)果是全1。事實(shí)上最終結(jié)果就是數(shù)據(jù)在table數(shù)組中的位置。

HashMap的hash優(yōu)化

從上面我們看到，在確定一個(gè)數(shù)據(jù)的存儲(chǔ)位置時(shí)，HashMap只取了低位數(shù)據(jù)，這樣其實(shí)有一個(gè)缺陷，那就是我們拋棄了高位信息，也就拋棄了數(shù)據(jù)分布的離散性，如果數(shù)據(jù)碰巧有了某種規(guī)律，每一次都會(huì)產(chǎn)生碰撞，這樣就劃不來(lái)了，一個(gè)好的hash散列算法應(yīng)該要盡量降低碰撞，這個(gè)時(shí)候我們可以把高位信息利用起來(lái)。
這也是為什么HashMap不直接使用key的hash值的原因，如果key的hash算法實(shí)現(xiàn)比較糟糕就無(wú)法保證數(shù)據(jù)離散，從而無(wú)法減少hash碰撞了。現(xiàn)在我們看下HashMap是怎么優(yōu)化的：

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

代碼很簡(jiǎn)單，又是一個(gè)位操作，現(xiàn)在我們來(lái)詳細(xì)分析下這樣做的目的，
假設(shè)key.hashCode() = 10100101 11000100 00100101
現(xiàn)在h >>> 16 就是無(wú)符號(hào)右移16位，高位補(bǔ)0
變成了 00000000 00000101 00101100
然后：

   10100101 11000100 00100101
^  00000000 00000101 00101100
------------------------------------------------
   10100101 11000001 00001001

可以看到，這么做后能夠利用高16位信息和低16位信息一起得出一個(gè)新的結(jié)果，這樣新的低位信息其實(shí)是老的高位信息和老的低位信息共同作用的結(jié)果，這樣的話就能減少初始key.hashCode()的碰撞可能性。

總結(jié)

這里只是大致的講解了下HashMap的hash機(jī)制，核心的擴(kuò)容，存儲(chǔ)， 查找，刪除等具體分析還請(qǐng)靜待下一篇文章。

參考資料：
JDK 源碼中 HashMap 的 hash 方法原理是什么？