從本文開(kāi)始，介紹一下最常用的一個(gè)集合對(duì)象HashMap，HashMap存儲(chǔ)的是鍵值對(duì)，本文采用的基于JDK11的源碼實(shí)現(xiàn)。 一般大家都知道HashMap是通過(guò)put操作把一組鍵值對(duì)（key和value）存儲(chǔ)到HashMap中，然后可以通過(guò)get(key)去獲取key對(duì)應(yīng)的value。而最重要的這兩個(gè)過(guò)程是怎么實(shí)現(xiàn)的呢？下面我們就來(lái)對(duì)put和get這兩個(gè)過(guò)程做一個(gè)分析。

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

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

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

用戶(hù)通過(guò)key訪問(wèn)map獲取value的時(shí)候，原理是用key的hash值來(lái)與數(shù)組的大小取模獲取數(shù)組的索引。但實(shí)際在HashMap實(shí)現(xiàn)中，對(duì)取模運(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)行無(wú)符號(hào)右移16位
• 把h與h右移后的值進(jìn)行異或操作最后得到key的hash值。
  

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

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

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

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

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

# key1在table中索引的計(jì)算過(guò)程與結(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)計(jì)算后的值
&  0000 0000 0000 0000 0000 0000 0000 1111   #n-1的二進(jìn)制
-----------------------------------------------
  0000 0000 0000 0000 0000 0000 0000 1100 #得到的table索引是12



# key2在table中索引的計(jì)算過(guò)程與結(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)計(jì)算后的值
&  0000 0000 0000 0000 0000 0000 0000 1111   #n-1的二進(jìn)制
-----------------------------------------------
  0000 0000 0000 0000 0000 0000 0000 1110 #得到的table索引是14

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

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

最新評(píng)論