hashmap 存取原理圖_HashMap底層實現原理

HashMap底層原理總結，幾個Hash集合之間的對比。

HashMap底層存儲結構

HashMap是一個用于存儲Key-Value鍵值對的集合，每一個鍵值對也叫做一個Entry。這些Entry分散存儲在一個數組當中，這個數組就是HashMap的主干。1

7* 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[] table;1

18* Basic hash bin node, used for most entries. (See below for

* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)

static class implements Map.Entry{

final int hash;

final K key;

V value;

Node next;

Node(int hash, K key, V value, Node next) { ... }

public final K getKey(){ return key; }

public final V getValue(){ return value; }

public final String toString(){ return key + "=" + value; }

public final int hashCode(){ return Objects.hashCode(key) ^ Objects.hashCode(value);}

public final V setValue(V newValue){ ... }

public final boolean equals(Object o){ ... }

}

因為table數組的長度是有限的，再好的hash函數也會出現index沖突的情況，所以我們用鏈表來解決這個問題，table數組的每一個元素不只是一個Entry對象，也是一個鏈表的頭節點，每一個Entry對象通過Next指針指向下一個Entry節點。當新來的Entry映射到沖突數組位置時，只需要插入對應的鏈表即可。

需要注意的是：新來的Entry節點插入鏈表時，會插在鏈表的頭部，因為HashMap的發明者認為，后插入的Entry被查找的可能性更大。

HashMap中的table數組如下所示：

所以，HashMap是數組+鏈表+紅黑樹(在Java 8中為了優化Entry的查找性能，新加了紅黑樹部分)實現的。

Put方法原理

調用hashMap.put("str", 1)，將會在HashMap的table數組中插入一個Key為“str”的元素，這時候需要我們用一個hash()函數來確定Entry的插入位置，而每種數據類型有自己的hashCode()函數，比如String類型的hashCode()函數如下所示：1

7public static int hashCode(byte[] value){

int h = 0;

for (byte v : value) {

h = 31 * h + (v & 0xff);

}

return h;

}

所以，put()函數的執行路徑是這樣的：首先put("str", 1)會調用HashMap的hash("str")方法。

在hash()內部，會調用String(Latin1)內部的hashcode()獲取字符串”str”的hashcode。

“str”的hashcode被返回給put()，put()通過一定計算得到最終的插入位置index。

最后將這個Entry插入到table的index位置。

這里就出現了兩個問題，問題1: 在put()里怎樣得到插入位置index？問題2: 為什么會調用HashMap的hash()函數，直接調用String的hashcode()不好嗎？

問題1: 在put()里怎樣得到插入位置index？

對于不同的hash碼我們希望它被插入到不同的位置，所以我們首先會想到對數組長度的取模運算，但是由于取模運算的效率很低，所以HashMap的發明者用位運算替代了取模運算。

在put()里是通過如下的語句得到插入位置的：1index = hash(key) & (Length - 1)

其中Length是table數組的長度。為了實現和取模運算相同的功能，這里要求(Length - 1)這部分的二進制表示全為1，我們用HashMap的默認初始長度16舉例說明：1

5假設"str"的hash嗎為: 1001 0110 1011 1110 1101 0010 1001 0101

Length - 1 = 15 : 1111

hash("str") & (Length - 1) = 0101

如果(Length - 1)這部分不全為1，假如Length是10，那么Length - 1 = 9 ：1001 那么無論再和任何hash碼做與操作，中間兩位數都會是0，這樣就會出現大量不同的hash碼被映射到相同位置的情況。

所以，在HashMap中table數組的默認長度是16，并且要求每次自動擴容或者手動擴容時，長度都必須是2的冪。

問題2: 為什么會調用HashMap的hash()函數，直接調用String的hashcode()不好嗎？

HashMap中的hash()函數如下所示：1

4static final int hash(Object key){

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

HashMap中的hash()函數是將得到hashcode做進一步處理，它將hashcode的高16位和低16位進行異或操作，這樣做的目的是：在table的長度比較小的情況下，也能保證hashcode的高位參與到地址映射的計算當中，同時不會有太大的開銷。

綜上所述：從hashcode計算得到table索引的計算過程如下所示：

put()方法的執行過程如下所示：

HashMap的擴容機制

在HashMap中有一下兩個屬性和擴容相關：1

2int threshold;

final float loadFactor;

其中threshold = Length * loadFactor，Length表示table數組的長度(默認值是16)，loadFactor為負載因子(默認值是0.75)，閥值threshold表示當table數組中存儲的元素超過這個閥值的時候，就需要擴容了。以默認長度16，和默認負載因子0.75為例，threshold = 16 * 0.75 = 12，即當table數組中存儲的元素個數超過12個的時候，table數組就該擴容了。

當然Java中的數組是無法自動擴容的，方法是使用一個新的數組代替已有的容量小的數組，然后將舊數組中的元素經過重新計算放到新數組中，那么怎樣對舊元素進行重新映射呢？

其實很簡單，由于我們在擴容時，是使用2的冪擴展，即數組的長度擴大到原來的2倍, 4倍, 8倍…，因此在resize時(Length - 1)這部分相當于在高位新增一個或多個1bit，我們以擴大到原來的兩倍為例說明：

(a)中n為16，(b)中n擴大到兩倍為32，相當于(n - 1)這部分的高位多了一個1, 然后和原hash碼作與操作，這樣元素在數組中映射的位置要么不變，要不向后移動16個位置：

因此，我們在擴充HashMap的時候，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”，可以看看下圖為16擴充為32的resize示意圖：

這個設計確實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認為是隨機的，因此resize的過程，均勻的把之前的沖突的節點分散到新的bucket了。這一塊就是JDK1.8新增的優化點。有一點注意區別，JDK1.7中resize的時候，舊鏈表遷移新鏈表的時候，如果在新表的數組索引位置相同，則鏈表元素會倒置，但是從上圖可以看出，JDK1.8不會倒置。

HashMap死鎖形成原理

HashMap非線程安全，即任一時刻可以有多個線程同時寫HashMap，可能會導致數據的不一致。如果需要滿足線程安全，可以用 Collections的synchronizedMap方法使HashMap具有線程安全的能力，或者使用線程安全的ConcurrentHashMap。

要理解HashMap死鎖形成的原理，我們要對HashMap的resize里的transfer過程有所了解，transfer過程是將舊數組中的元素復制到新數組中，在Java 8之前，復制過程會導致鏈表倒置，這也是形成死鎖的重要原因(Java 8中已經不會倒置)，transfer的基本過程如下：1

41. 新建節點e指向當前節點，新建節點next指向e.next

2. 將e.next指向新數組中指定位置newTable[i]

3. newTable[i] = e

4. e = next

舉個例子：1

7現在有鏈表1->2->3，要將它復制到新數組的newTable[i]位置

1. Node e = 1, next = e.next;

2. e.next = newTable[i];

3. newTable[i] = e;

4. e = next, next = e.next;

執行完后會得到這樣的結果：

newTable[i]=3->2->1

死鎖會在這種情況產生：兩個線程同時往HashMap里放Entry，同時HashMap正好需要擴容，如果一個線程已經完成了transfer過程，而另一個線程不知道，并且又要進行transfer的時候，死鎖就會形成。1

5現在Thread1已將完成了transfer，newTable[i]=3->2->1

在Thread2中:

Node e = 1, next = e.next;

e.next = newTable[i] : 1 -> newTable[i]=3

newTable[i] = e : newTable[i] = 1->3->2->1 //這時候鏈表換已經形成了

在形成鏈表換以后再對HashMap進行Get操作時，就會形成死循環。

在Java 8中對這里進行了優化，鏈表復制到新數組時并不會倒置，不會因為多個線程put導致死循環，但是還有很多弊端，比如數據丟失等，因此多線程情況下還是建議使用ConcurrentHashMap。

HashMap和Hashtable有什么區別

Java為數據結構中的映射定義了一個接口java.util.Map，此接口主要有四個常用的實現類，分別是HashMap、Hashtable、LinkedHashMap和TreeMap，類繼承關系如下圖所示：

Hashtable：Hashtable是遺留類，很多映射的常用功能與HashMap類似，不同的是它承自Dictionary類，并且是線程安全的，任一時間只有一個線程能寫Hashtable，并發性不如ConcurrentHashMap，因為ConcurrentHashMap引入了分段鎖。Hashtable不建議在新代碼中使用，不需要線程安全的場合可以用HashMap替換，需要線程安全的場合可以用ConcurrentHashMap替換。

總結擴容是一個特別耗性能的操作，所以當程序員在使用HashMap的時候，估算map的大小，初始化的時候給一個大致的數值，避免map進行頻繁的擴容。

負載因子是可以修改的，也可以大于1，但是建議不要輕易修改，除非情況非常特殊。

HashMap是線程不安全的，不要在并發的環境中同時操作HashMap，建議使用ConcurrentHashMap。

JDK1.8引入紅黑樹大程度優化了HashMap的性能。