av一区二区在线观看_亚洲男人的天堂网站_日韩亚洲视频_在线成人免费_欧美日韩精品免费观看视频_久草视

您的位置:首頁技術文章
文章詳情頁

Java HashMap實現原理分析(一)

瀏覽:3日期:2022-08-25 17:40:57

從本文開始,介紹一下最常用的一個集合對象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執行get操作的時候,并沒有傳入具體的數組的索引位置信息,只是傳入了key,因此這個地方就會涉及到一個key轉索引的一個操作,然后根據索引獲取table中對應位置的Node對象,把value值返回給用戶。由于數組的訪問時間復雜度是O(1),因此Map的get操作也可以認為是O(1)( 這個地方先暫時理解為O(1),具體原因見后面)。

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

HashMap 數組尋址與hash值計算

用戶通過key訪問map獲取value的時候,原理是用key的hash值來與數組的大小取模獲取數組的索引。但實際在HashMap實現中,對取模運算進行了一下優化,采用了(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 # key11111 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,他們的區別恰恰是出現在自己的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方法的實現原理。

以上就是Java HashMap實現原理分析(一)的詳細內容,更多關于Java HashMap原理的資料請關注好吧啦網其它相關文章!

標簽: Java
相關文章:
主站蜘蛛池模板: 国产区一区 | 日韩a视频 | 久久精品久久久 | 日韩欧美国产一区二区三区 | 成人影院在线视频 | 日本电影韩国电影免费观看 | 久久久国产精品一区 | 91久久久精品国产一区二区蜜臀 | 日韩在线不卡 | 日韩在线视频免费观看 | 国产免费av网 | 亚洲一区二区三区桃乃木香奈 | 久久久91 | 欧美在线一区二区三区 | 亚洲视频免费在线 | 成人久久18免费网站图片 | www.国产.com| 国产精品高潮呻吟久久 | 蜜桃在线视频 | 亚洲国产精品久久久久婷婷老年 | 久久久久久久久毛片 | 日韩中文在线视频 | 国产欧美视频一区二区 | 成人区一区二区三区 | 久久亚洲一区二区三区四区 | 欧美精品一区二区三区蜜桃视频 | 国产91综合 | 精品久久影院 | 一区二区三区四区免费视频 | av在线天堂 | 久久国产综合 | av免费看在线 | 久久男人 | japanhd美女动| 精品9999| aa级毛片毛片免费观看久 | 欧美一区免费 | 91精品一区 | 精品粉嫩aⅴ一区二区三区四区 | 国产欧美一区二区精品忘忧草 | 神马九九|