從本文開始，介紹一下最常用的一個集合對象HashMap，HashMap存儲的是鍵值對，本文采用的基于JDK11的源碼實(shí)現(xiàn)。 一般大家都知道HashMap是通過put操作把一組鍵值對（key和value）存儲到HashMap中，然后可以通過get(key)去獲取key對應(yīng)的value。而最重要的這兩個過程是怎么實(shí)現(xiàn)的呢？下面我們就來對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;

當(dāng)用戶調(diào)用put方法的時候把key和value放入到HashMap的時候，這個數(shù)組table就是實(shí)際存儲key和value的地方。HashMap把用戶傳入的key和value封裝成一個Node<K,V>對象，把該Node<K,V>對象放入到table對應(yīng)的位置。Map執(zhí)行g(shù)et操作的時候，并沒有傳入具體的數(shù)組的索引位置信息，只是傳入了key，因此這個地方就會涉及到一個key轉(zhuǎn)索引的一個操作，然后根據(jù)索引獲取table中對應(yīng)位置的Node對象，把value值返回給用戶。由于數(shù)組的訪問時間復(fù)雜度是O(1)，因此Map的get操作也可以認(rèn)為是O(1)（ 這個地方先暫時理解為O(1),具體原因見后面）。

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

HashMap 數(shù)組尋址與hash值計算

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

下面看一下，hash(key)的實(shí)現(xiàn)邏輯

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

從上面的源碼看：

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

這里大家比較好奇，為什么會進(jìn)行這種復(fù)雜操作，他的用意是什么？下面來給大家說一下這個過程。

假設(shè) table的大小是16，key1和Key2調(diào)用hashCode方法獲取的值的二進(jìn)制形式分別是：

1111 1111 1111 1101 0000 0000 0000 0001 # key11111 1111 1111 1111 0000 0000 0000 0001 # key2

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

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

根據(jù)上面計算結(jié)果可知，雖然key1和key2值不同，但是最后得到的table的索引都是1，這樣就會出現(xiàn)了沖突。主要原因是在與n-1進(jìn)行&操作的時候，通常n的值比較小，因此高16位都是0，這樣0和任何數(shù)&結(jié)果都是0。通常key的hashCode取值很不固定。從最高位到最低位都會出現(xiàn)1的可能。比如key1和key2，他們的區(qū)別恰恰是出現(xiàn)在自己的hashCode的高16位，因此key1和key2與n-1進(jìn)行&操作的結(jié)果是一樣的。如果key1和key2經(jīng)過hash()方法處理后呢，來看看結(jié)果：

# key1在table中索引的計算過程與結(jié)果 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的二進(jìn)制----------------------------------------------- 0000 0000 0000 0000 0000 0000 0000 1100 #得到的table索引是12# key2在table中索引的計算過程與結(jié)果 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的二進(jìn)制----------------------------------------------- 0000 0000 0000 0000 0000 0000 0000 1110 #得到的table索引是14

這樣key1和key2不會出現(xiàn)位置沖突。當(dāng)key和自己的高16位進(jìn)行異或操作的后的值的低16位中同時保留了原始key低16位和高16位的特征。因此key1和key2再和n-1進(jìn)行&運(yùn)算時，減少了出現(xiàn)相同值的可能性。明白了這些內(nèi)容內(nèi)容，下一篇文章開始結(jié)束HashMap的put和get方法的實(shí)現(xiàn)原理。

以上就是Java HashMap實(shí)現(xiàn)原理分析（一）的詳細(xì)內(nèi)容，更多關(guān)于Java HashMap原理的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章！