從本文開始，介紹一下最常用的一個集合對象HashMap，HashMap存儲的是鍵值對，本文采用的基于JDK11的源碼實現(xiàn)。 一般大家都知道HashMap是通過put操作把一組鍵值對（key和value）存儲到HashMap中，然后可以通過get(key)去獲取key對應(yīng)的value。而最重要的這兩個過程是怎么實現(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就是實際存儲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操作也可以認為是O(1)（ 這個地方先暫時理解為O(1),具體原因見后面）。

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

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

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

下面看一下，hash(key)的實現(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進行無符號右移16位
• 把h與h右移后的值進行異或操作最后得到key的hash值。
  

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

假設(shè) table的大小是16，key1和Key2調(diào)用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中索引的計算過程與結(jié)果
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中索引的計算過程與結(jié)果
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

根據(jù)上面計算結(jié)果可知，雖然key1和key2值不同，但是最后得到的table的索引都是1，這樣就會出現(xiàn)了沖突。主要原因是在與n-1進行&操作的時候，通常n的值比較小，因此高16位都是0，這樣0和任何數(shù)&結(jié)果都是0。通常key的hashCode取值很不固定。從最高位到最低位都會出現(xiàn)1的可能。比如key1和key2，他們的區(qū)別恰恰是出現(xiàn)在自己的hashCode的高16位，因此key1和key2與n-1進行&操作的結(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的二進制
-----------------------------------------------
  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的二進制
-----------------------------------------------
  0000 0000 0000 0000 0000 0000 0000 1110 #得到的table索引是14

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

以上就是Java HashMap實現(xiàn)原理分析（一）的詳細內(nèi)容，更多關(guān)于Java HashMap原理的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論