Java集合源碼學習（四）HashMap分析

資料結構中有數組和連結清單來實作對資料的存儲，這兩者有不同的應用場景，

數組的特點是：尋址容易，插入和删除困難；連結清單的特點是：尋址困難，插入和删除容易；

哈希表的實作結合了這兩點，哈希表的實作方式有多種，在hashmap中使用的是鍊位址法，也就是拉鍊法。

看下面這張流傳很廣的圖，

拉鍊法實際上是一種連結清單數組的結構，由數組加連結清單組成，在這個長度為16的數組中（hashmap預設初始化大小就是16），每個元素存儲的是一個連結清單的頭結點。

通過元素的key的hash值對數組長度取模，将這個元素插入到數組對應位置的連結清單中。

例如在圖中，337%16=1，353%16=1，于是将其插入到數組位置1的連結清單頭結點中。

繼承abstractmap抽象類，map的一些操作在abstractmap裡已經提供了預設實作，

實作map接口，可以應用map接口定義的一些操作，明确hashmap屬于map體系，

cloneable接口，表明hashmap對象會重寫java.lang.object#clone()方法，hashmap實作的是淺拷貝（shallow copy），

serializable接口，表明hashmap對象可以被序列化

hashmap的實際資料存儲在entry類的數組中，

上面說到hashmap的基礎就是一個線性數組，這個數組就是entry[]。

<code> </code><code>* 内部實際的存儲數組，如果需要調整，容量必須是2的幂</code>

<code> </code><code>transient</code> <code>entry[] table;</code>

再來看一下entry這個内部靜态類，

<code>static</code> <code>class</code> <code>entry<k,v> </code><code>implements</code> <code>map.entry<k,v> {</code>

<code> </code><code>final</code> <code>k key;</code><code>//key-value結構的key</code>

<code> </code><code>v value;</code><code>//存儲值</code>

<code> </code><code>entry<k,v> next;</code><code>//指向下一個連結清單節點</code>

<code> </code><code>final</code> <code>int</code> <code>hash;</code><code>//哈希值</code>

<code> </code><code>* creates new entry.</code>

<code> </code><code>entry(</code><code>int</code> <code>h, k k, v v, entry<k,v> n) {</code>

<code> </code><code>value = v;</code>

hashmap是非同步的，即線程不安全，在多線程條件下，可能出現很多問題，

1.多線程put後可能導緻get死循環，具體表現為cpu使用率100%（put的時候transfer方法循環将舊數組中的連結清單移動到新數組）

2.多線程put的時候可能導緻元素丢失（在addentry方法的new entry<k,v>(hash, key, value, e)，如果兩個線程都同時取得了e,則他們下一個元素都是e，然後指派給table元素的時候有一個成功有一個丢失）

關于hashmap線程安全性更多的了解參考相關的網上資源，這裡不多叙述。

需要線程安全的哈希表結構，可以考慮以下的方式：

使用hashtable 類，hashtable 是線程安全的；

使用并發包下的java.util.concurrent.concurrenthashmap，concurrenthashmap實作了更進階的線程安全；

或者使用synchronizedmap() 同步方法包裝 hashmap object，得到線程安全的map，并在此map上進行操作。

如：

<code>public static <</code><code>k</code><code>,v> map<</code><code>k</code><code>,v> synchronizedmap(map<</code><code>k</code><code>,v> m) {</code>

<code> </code><code>return new synchronizedmap<>(m);</code>

hashmap可以應用所有map接口定義的方法：

<code>public</code> <code>interface</code> <code>map<k,v> {</code>

<code> </code><code>public</code> <code>static</code> <code>interface</code> <code>entry<k,v> {</code>

<code> </code><code>//擷取該entry的key</code>

<code> </code><code>public</code> <code>abstract</code> <code>object getkey();</code>

<code> </code><code>//擷取該entry的value</code>

<code> </code><code>public</code> <code>abstract</code> <code>object getvalue();</code>

<code> </code><code>//設定entry的value </code>

<code> </code><code>public</code> <code>abstract</code> <code>object setvalue(object obj);</code>

<code> </code><code>public</code> <code>abstract</code> <code>boolean</code> <code>equals(object obj);</code>

<code> </code><code>public</code> <code>abstract</code> <code>int</code> <code>hashcode();</code>

<code> </code><code>//傳回鍵值對的數目 </code>

<code> </code><code>//判斷容器是否為空 </code>

<code> </code><code>boolean</code> <code>isempty();</code>

<code> </code><code>//判斷容器是否包含關鍵字key </code>

<code> </code><code>boolean</code> <code>containskey(object key);</code>

<code> </code><code>//判斷容器是否包含值value</code>

<code> </code><code>boolean</code> <code>containsvalue(object value);</code>

<code> </code><code>//根據key擷取value </code>

<code> </code><code>object get(object key);</code>

<code> </code><code>//向容器中加入新的key-value對 </code>

<code> </code><code>object put(object key, object value);</code>

<code> </code><code>//根據key移除相應的鍵值對 </code>

<code> </code><code>object remove(object key);</code>

<code> </code><code>//将另一個map中的所有鍵值對都添加進去 </code>

<code> </code><code>void</code> <code>putall(map<? </code><code>extends</code> <code>k, ? </code><code>extends</code> <code>v> m);</code>

<code> </code><code>//清除容器中的所有鍵值對 </code>

<code> </code><code>void</code> <code>clear();</code>

<code> </code><code>//傳回容器中所有的key組成的set集合 </code>

<code> </code><code>set keyset();</code>

<code> </code><code>//傳回所有的value組成的集合 </code>

<code> </code><code>collection values();</code>

<code> </code><code>//傳回所有的鍵值對 </code>

<code> </code><code>set<map.entry<k, v>> entryset();</code>

<code> </code><code>//繼承自object的方法</code>

<code> </code><code>boolean</code> <code>equals(object obj);</code>

<code> </code><code>int</code> <code>hashcode();</code>

hashmap使用entry[] 數組存儲資料，

另外維護了兩個非常重要的變量：initialcapacity（初始容量）、loadfactor（加載因子）。

初始容量就是初始構造數組的大小，可以指定任何值，

但最後hashmap内部都會将其轉成一個大于指定值的最小的2的幂，比如指定初始容量12，但最後會變成16，指定16，最後就是16。

加載因子是控制數組table的飽和度的，預設的加載因子是0.75，

<code>default_load_factor = </code><code>0</code><code>.75f;</code>

也就是數組達到容量的75%，就會自動的擴容。

另外，hashmap的最大容量是2^30，

static final int maximum_capacity = 1 << 30;

預設的初始化大小是16，

static final int default_initial_capacity = 16;

hashmap提供了四種構造方法，可以使用預設的容量等進行初始化，

也可以顯式制定大小和加載因子，還可以使用另外的map進行構造和初始化。

<code>public</code> <code>hashmap() {</code>

<code> </code><code>this</code><code>.loadfactor = default_load_factor;</code>

<code> </code><code>threshold = (</code><code>int</code><code>)(default_initial_capacity * default_load_factor);</code>

<code> </code><code>table = </code><code>new</code> <code>entry[default_initial_capacity];</code>

<code>public</code> <code>hashmap(map<? </code><code>extends</code> <code>k, ? </code><code>extends</code> <code>v> m) {</code>

<code> </code><code>this</code><code>(math.max((</code><code>int</code><code>) (m.size() / default_load_factor) + </code><code>1</code><code>,</code>

<code> </code><code>default_initial_capacity), default_load_factor);</code>

<code> </code><code>putallforcreate(m);</code>

<code> </code><code>public</code> <code>hashmap(</code><code>int</code> <code>initialcapacity) {</code>

<code> </code><code>this</code><code>(initialcapacity, default_load_factor);</code>

<code> </code><code>public</code> <code>hashmap(</code><code>int</code> <code>initialcapacity, </code><code>float</code> <code>loadfactor) {</code>

理論上哈希函數的輸入域是無限的，優秀的哈希函數可以将沖突減少到最低，但是卻不能避免，下面是一個典型的哈希沖突的例子：

用班級同學做比喻，現有如下同學資料張三，李四，王五，趙剛，吳露..... 假如我們編址規則為取姓氏中姓的開頭字母在字母表的相對位置作為位址，則會産生如下的哈希表位置字母姓名 a b c ... 10 l 李四 w 王五，吳露 .. 25 z 張三，趙剛

常見的辦法開放定址法，再哈希法，鍊位址法以及建立一個公共溢出區等，這裡隻考察鍊位址法。

鍊位址法就是最開始我們提到的連結清單-數組結構，

将所有關鍵字為同義詞的記錄存儲在同一線性連結清單中。

hashmap的存取主要是put和get操作的實作。

執行put方法時根據key的hash值來計算放到table數組的下标，

如果hash到相同的下标，則新put進去的元素放到entry鍊的頭部。

<code>public</code> <code>v put(k key, v value) {</code>

<code> </code><code>return</code> <code>putfornullkey(value);</code>

<code> </code><code>int</code> <code>hash = hash(key.hashcode());</code>

<code> </code><code>int</code> <code>i = indexfor(hash, table.length);</code>

<code> </code><code>for</code> <code>(entry<k,v> e = table[i]; e != </code><code>null</code><code>; e = e.next) {</code>

<code> </code><code>object k;</code>

<code> </code><code>if</code> <code>(e.hash == hash && ((k = e.key) == key || key.equals(k))) {</code>

<code> </code><code>v oldvalue = e.value;</code>

<code> </code><code>e.value = value;</code>

<code> </code><code>e.recordaccess(</code><code>this</code><code>);</code>

<code> </code><code>return</code> <code>oldvalue;</code>

<code> </code><code>modcount++;</code>

<code> </code><code>addentry(hash, key, value, i);</code>

<code> </code><code>return</code> <code>null</code><code>;</code>

　get操作的實作：

<code>public</code> <code>v get(object key) {</code>

<code> </code><code>return</code> <code>getfornullkey();</code>

<code> </code><code>for</code> <code>(entry<k,v> e = table[indexfor(hash, table.length)];e != </code><code>null</code><code>;e = e.next) <br> { object k;</code>

<code> </code><code>if</code> <code>(e.hash == hash && ((k = e.key) == key || key.equals(k)))</code>

<code> </code><code>return</code> <code>e.value;</code>

注意hashmap支援key=null的情況，看這個代碼：

<code>private</code> <code>v putfornullkey(v value) {</code>

<code> </code><code>for</code> <code>(entry<k,v> e = table[</code><code>0</code><code>]; e != </code><code>null</code><code>; e = e.next) {</code>

下面看一下hashmap使用的哈希函數，源碼來自jdk1.6：

<code> </code><code>* 看一下具體的操作，首先對h分别進行無符号右移20位和12位，</code>

<code> </code><code>* 然後對兩個值進行按位異或，最後再與h進行按位異或，</code>

<code> </code><code>* 得到新的h後再進行一次同樣的操作，分别右移7位和4位，具體的哈希函數優劣就不去研究了</code>

<code> </code><code>* 這個方法可以盡量減少碰撞</code>

<code> </code><code>static</code> <code>int</code> <code>hash(</code><code>int</code> <code>h) {</code>

<code> </code><code>return</code> <code>h ^ (h >>> </code><code>7</code><code>) ^ (h >>> </code><code>4</code><code>);</code>

當哈希表的容量超過預設容量時，必須調整table的大小。

當容量已經達到最大可能值時，那麼該方法就将容量調整到integer.max_value傳回，這時，需要建立一個新的table數組，将table數組的元素轉移到新的table數組中。

<code> </code><code>* 再散列過程</code>

<code> </code><code>* rehashes the contents of this map into a new array with a</code>

<code> </code><code>* larger capacity. this method is called automatically when the</code>

<code> </code><code>* number of keys in this map reaches its threshold.</code>

<code> </code><code>void</code> <code>resize(</code><code>int</code> <code>newcapacity) {</code>

<code> </code><code>entry[] oldtable = table;</code>

<code> </code><code>int</code> <code>oldcapacity = oldtable.length;</code>

<code> </code><code>if</code> <code>(oldcapacity == maximum_capacity) {</code>

<code> </code><code>threshold = integer.max_value;</code>

<code> </code><code>return</code><code>;</code>

<code> </code><code>entry[] newtable = </code><code>new</code> <code>entry[newcapacity];</code>

<code> </code><code>transfer(newtable);</code>

<code> </code><code>table = newtable;</code>

<code> </code><code>threshold = (</code><code>int</code><code>)(newcapacity * loadfactor);</code>

<code> </code><code>* 把目前entry[]表的全部元素轉移到新的table中</code>

<code> </code><code>void</code> <code>transfer(entry[] newtable) {</code>

<code> </code><code>entry[] src = table;</code>

<code> </code><code>int</code> <code>newcapacity = newtable.length;</code>

<code> </code><code>entry<k,v> e = src[j];</code>

<code> </code><code>entry<k,v> next = e.next;</code>

<code> </code><code>int</code> <code>i = indexfor(e.hash, newcapacity);</code>

<code> </code><code>e.next = newtable[i];</code>

<code> </code><code>newtable[i] = e;</code>

<code> </code><code>} </code><code>while</code> <code>(e != </code><code>null</code><code>);</code>

Java集合源碼學習（四）HashMap分析

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method