HashMap實現原理分析（1）

從本文開始肝劲，介紹一下最常用的一個集合對象HashMap突雪，HashMap存儲的是鍵值對闪唆，本文采用的基于JDK11的源碼實現碧库。一般大家都知道HashMap是通過put操作把一組鍵值對（key和value）存儲到HashMap中柜与，然后可以通過get(key)去獲取key對應的value。而最重要的這兩個過程是怎么實現的呢嵌灰？下面我們就來對put和get這兩個過程做一個分析弄匕。

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;

當用戶調用put方法的時候把key和value放入到HashMap的時候，這個數組table就是實際存儲key和value的地方沽瞭。HashMap把用戶傳入的key和value封裝成一個Node<K,V>對象迁匠，把該Node<K,V>對象放入到table對應的位置。Map執(zhí)行get操作的時候驹溃，并沒有傳入具體的數組的索引位置信息城丧，只是傳入了key，因此這個地方就會涉及到一個key轉索引的一個操作豌鹤，然后根據索引獲取table中對應位置的Node對象亡哄，把value值返回給用戶。由于數組的訪問時間復雜度是O(1)布疙，因此Map的get操作也可以認為是O(1)（這個地方先暫時理解為O(1),具體原因見后面）蚊惯。

簡單來說，在執(zhí)行put方法的時候灵临，Map會根據傳入的key獲取它hashcode值拣挪，然后根據hashcode與table大小進行求模運算，得到的值就是它在table數組索引位置俱诸。實際這個過程又有點復雜，具體下面開始分析赊舶。

HashMap 數組尋址與hash值計算

用戶通過key訪問map獲取value的時候睁搭，原理是用key的hash值來與數組的大小取模獲取數組的索引赶诊。但實際在HashMap實現中，對取模運算進行了一下優(yōu)化园骆，采用了(n-1) & hash(key)的方法獲取數組索引舔痪，這里的n是table的大小，hash(key)表示key的哈希值锌唾，這種方法可以得到與取模運算一樣的效果锄码，但是速度要比取模運算快。

下面看一下晌涕，hash(key)的實現邏輯

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

從上面的源碼看：

調用key的hashCode()方法獲取hashCode值h
把h進行無符號右移16位
把h與h右移后的值進行異或操作最后得到key的hash值滋捶。

這里大家比較好奇，為什么會進行這種復雜操作余黎，他的用意是什么重窟？下面來給大家說一下這個過程。

假設 table的大小是16惧财，key1和Key2調用hashCode方法獲取的值的二進制形式分別是：

1111 1111 1111 1101 0000 0000 0000 0001   # key1
1111 1111 1111 1111 0000 0000 0000 0001   # key2

首先我們直接使用key1和key2的hashCode獲取的值去計算在的table的索引值巡扇。
具體過程是：

# key1在table中索引的計算過程與結果
1111 1111 1111 1101 0000 0000 0000 0001  
0000 0000 0000 0000 0000 0000 0000 1111   &    #n-1的二進制
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0001  # 得到的table索引是1


# key2在table中索引的計算過程與結果
1111 1111 1111 1111 0000 0000 0000 0001  
0000 0000 0000 0000 0000 0000 0000 1111   &   #n-1的二進制
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0001  #得到的table索引是1

根據上面計算結果可知，雖然key1和key2值不同垮衷，但是最后得到的table的索引都是1厅翔，這樣就會出現了沖突。主要原因是在與n-1進行&操作的時候搀突，通常n的值比較小刀闷，因此高16位都是0，這樣0和任何數&結果都是0描姚。通常key的hashCode取值很不固定涩赢。從最高位到最低位都會出現1的可能。比如key1和key2轩勘，他們的區(qū)別恰恰是出現在自己的hashCode的高16位筒扒，因此key1和key2與n-1進行&操作的結果是一樣的。如果key1和key2經過hash()方法處理后呢绊寻，來看看結果：

# key1在table中索引的計算過程與結果
    1111 1111 1111 1101 0000 0000 0000 0001  #key1本身
^   0000 0000 0000 0000 1111 1111 1111 1101  #key1右移16的值
-----------------------------------------------
    1111 1111 1111 1111 1111 1111 1111 1100      # hash(key1)計算后的值
&   0000 0000 0000 0000 0000 0000 0000 1111      #n-1的二進制
-----------------------------------------------
    0000 0000 0000 0000 0000 0000 0000 1100  #得到的table索引是12



# key2在table中索引的計算過程與結果
    1111 1111 1111 1111 0000 0000 0000 0001   #key2本身
^   0000 0000 0000 0000 1111 1111 1111 1111   #key2右移16的值
-----------------------------------------------
    1111 1111 1111 1111 1111 1111 1111 1110     #hash(key1)計算后的值
&   0000 0000 0000 0000 0000 0000 0000 1111     #n-1的二進制
-----------------------------------------------
    0000 0000 0000 0000 0000 0000 0000 1110 #得到的table索引是14

這樣key1和key2不會出現位置沖突花墩。當key和自己的高16位進行異或操作的后的值的低16位中同時保留了原始key低16位和高16位的特征。因此key1和key2再和n-1進行&運算時澄步，減少了出現相同值的可能性冰蘑。明白了這些內容內容，下一篇文章開始結束HashMap的put和get方法的實現原理村缸。