大部分Java開(kāi)發(fā)者都在使用Map，特別是HashMap。HashMap是一種簡(jiǎn)單但強(qiáng)大的方式去存儲(chǔ)和獲取數(shù)據(jù)。但有多少開(kāi)發(fā)者知道HashMap內(nèi)部如何工作呢？幾天前，我閱讀了java.util.HashMap的大量源代碼（包括Java 7 和Java 8），來(lái)深入理解這個(gè)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。在這篇文章中，我會(huì)解釋java.util.HashMap的實(shí)現(xiàn)，描述Java 8實(shí)現(xiàn)中添加的新特性，并討論性能、內(nèi)存以及使用HashMap時(shí)的一些已知問(wèn)題。

內(nèi)部存儲(chǔ)

Java HashMap類(lèi)實(shí)現(xiàn)了Map<K, V>接口。這個(gè)接口中的主要方法包括：

V put(K key, V value)
V get(Object key)
V remove(Object key)
Boolean containsKey(Object key)

HashMap使用了一個(gè)內(nèi)部類(lèi)Entry<K, V>來(lái)存儲(chǔ)數(shù)據(jù)。這個(gè)內(nèi)部類(lèi)是一個(gè)簡(jiǎn)單的鍵值對(duì)，并帶有額外兩個(gè)數(shù)據(jù)：

一個(gè)指向其他入口（譯者注：引用對(duì)象）的引用，這樣HashMap可以存儲(chǔ)類(lèi)似鏈接列表這樣的對(duì)象。
一個(gè)用來(lái)代表鍵的哈希值，存儲(chǔ)這個(gè)值可以避免HashMap在每次需要時(shí)都重新生成鍵所對(duì)應(yīng)的哈希值。
下面是Entry<K, V>在Java 7下的一部分代碼：

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
…
}

HashMap將數(shù)據(jù)存儲(chǔ)到多個(gè)單向Entry鏈表中（有時(shí)也被稱(chēng)為桶bucket或者容器orbins）。所有的列表都被注冊(cè)到一個(gè)Entry數(shù)組中（Entry<K, V>[]數(shù)組），這個(gè)內(nèi)部數(shù)組的默認(rèn)長(zhǎng)度是16。

下面這幅圖描述了一個(gè)HashMap實(shí)例的內(nèi)部存儲(chǔ)，它包含一個(gè)nullable對(duì)象組成的數(shù)組。每個(gè)對(duì)象都連接到另外一個(gè)對(duì)象，這樣就構(gòu)成了一個(gè)鏈表。

所有具有相同哈希值的鍵都會(huì)被放到同一個(gè)鏈表（桶）中。具有不同哈希值的鍵最終可能會(huì)在相同的桶中。

當(dāng)用戶(hù)調(diào)用 put(K key， V value) 或者 get(Object key) 時(shí)，程序會(huì)計(jì)算對(duì)象應(yīng)該在的桶的索引。然后，程序會(huì)迭代遍歷對(duì)應(yīng)的列表，來(lái)尋找具有相同鍵的Entry對(duì)象（使用鍵的equals()方法）。

對(duì)于調(diào)用get()的情況，程序會(huì)返回值所對(duì)應(yīng)的Entry對(duì)象（如果Entry對(duì)象存在）。

對(duì)于調(diào)用put(K key, V value)的情況，如果Entry對(duì)象已經(jīng)存在，那么程序會(huì)將值替換為新值，否則，程序會(huì)在單向鏈表的表頭創(chuàng)建一個(gè)新的Entry（從參數(shù)中的鍵和值）。

桶（鏈表）的索引，是通過(guò)map的3個(gè)步驟生成的：

首先獲取鍵的散列碼。

程序重復(fù)散列碼，來(lái)阻止針對(duì)鍵的糟糕的哈希函數(shù)，因?yàn)檫@有可能會(huì)將所有的數(shù)據(jù)都放到內(nèi)部數(shù)組的相同的索引（桶）上。
程序拿到重復(fù)后的散列碼，并對(duì)其使用數(shù)組長(zhǎng)度（最小是1）的位掩碼（bit-mask）。這個(gè)操作可以保證索引不會(huì)大于數(shù)組的大小。你可以將其看做是一個(gè)經(jīng)過(guò)計(jì)算的優(yōu)化取模函數(shù)。

下面是生成索引的源代碼：

// the "rehash" function in JAVA 7 that takes the hashcode of the key
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// the "rehash" function in JAVA 8 that directly takes the key
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// the function that returns the index from the rehashed hash
static int indexFor(int h, int length) {
return h & (length-1);
}

為了更有效地工作，內(nèi)部數(shù)組的大小必須是2的冪值。讓我們看一下為什么：

假設(shè)數(shù)組的長(zhǎng)度是17，那么掩碼的值就是16（數(shù)組長(zhǎng)度-1）。16的二進(jìn)制表示是0…010000，這樣對(duì)于任何值H來(lái)說(shuō)，“H & 16”的結(jié)果就是16或者0。這意味著長(zhǎng)度為17的數(shù)組只能應(yīng)用到兩個(gè)桶上：一個(gè)是0，另外一個(gè)是16，這樣不是很有效率。但是如果你將數(shù)組的長(zhǎng)度設(shè)置為2的冪值，例如16，那么按位索引的工作變成“H & 15”。15的二進(jìn)制表示是0…001111，索引公式輸出的值可以從0到15，這樣長(zhǎng)度為16的數(shù)組就可以被充分使用了。例如：

如果H = 952，它的二進(jìn)制表示是0..01110111000，對(duì)應(yīng)的索引是0…01000 = 8
如果H = 1576，它的二進(jìn)制表示是0..011000101000，對(duì)應(yīng)的索引是0…01000 = 8
如果H = 12356146，它的二進(jìn)制表示是0..0101111001000101000110010，對(duì)應(yīng)的索引是0…00010 = 2
如果H = 59843，它的二進(jìn)制表示是0..01110100111000011，它對(duì)應(yīng)的索引是0…00011 = 3
這種機(jī)制對(duì)于開(kāi)發(fā)者來(lái)說(shuō)是透明的：如果他選擇一個(gè)長(zhǎng)度為37的HashMap，Map會(huì)自動(dòng)選擇下一個(gè)大于37的2的冪值（64）作為內(nèi)部數(shù)組的長(zhǎng)度。

自動(dòng)調(diào)整大小

在獲取索引后，get()、put()或者remove()方法會(huì)訪問(wèn)對(duì)應(yīng)的鏈表，來(lái)查看針對(duì)指定鍵的Entry對(duì)象是否已經(jīng)存在。在不做修改的情況下，這個(gè)機(jī)制可能會(huì)導(dǎo)致性能問(wèn)題，因?yàn)檫@個(gè)方法需要迭代整個(gè)列表來(lái)查看Entry對(duì)象是否存在。假設(shè)內(nèi)部數(shù)組的長(zhǎng)度采用默認(rèn)值16，而你需要存儲(chǔ)2，000,000條記錄。在最好的情況下，每個(gè)鏈表會(huì)有125,000個(gè)Entry對(duì)象（2,000,000/16）。get()、remove()和put()方法在每一次執(zhí)行時(shí)，都需要進(jìn)行125,000次迭代。為了避免這種情況，HashMap可以增加內(nèi)部數(shù)組的長(zhǎng)度，從而保證鏈表中只保留很少的Entry對(duì)象。

當(dāng)你創(chuàng)建一個(gè)HashMap時(shí)，你可以通過(guò)以下構(gòu)造函數(shù)指定一個(gè)初始長(zhǎng)度，以及一個(gè)loadFactor：

</pre>
public HashMap(int initialCapacity, float loadFactor)
<pre>

如果你不指定參數(shù)，那么默認(rèn)的initialCapacity的值是16， loadFactor的默認(rèn)值是0.75。initialCapacity代表內(nèi)部數(shù)組的鏈表的長(zhǎng)度。

當(dāng)你每次使用put(…)方法向Map中添加一個(gè)新的鍵值對(duì)時(shí)，該方法會(huì)檢查是否需要增加內(nèi)部數(shù)組的長(zhǎng)度。為了實(shí)現(xiàn)這一點(diǎn)，Map存儲(chǔ)了2個(gè)數(shù)據(jù)：

Map的大?。核鞨ashMap中記錄的條數(shù)。我們?cè)谙騂ashMap中插入或者刪除值時(shí)更新它。

閥值：它等于內(nèi)部數(shù)組的長(zhǎng)度*loadFactor，在每次調(diào)整內(nèi)部數(shù)組的長(zhǎng)度時(shí)，該閥值也會(huì)同時(shí)更新。

在添加新的Entry對(duì)象之前，put(…)方法會(huì)檢查當(dāng)前Map的大小是否大于閥值。如果大于閥值，它會(huì)創(chuàng)建一個(gè)新的數(shù)組，數(shù)組長(zhǎng)度是當(dāng)前內(nèi)部數(shù)組的兩倍。因?yàn)樾聰?shù)組的大小已經(jīng)發(fā)生改變，所以索引函數(shù)（就是返回“鍵的哈希值 & (數(shù)組長(zhǎng)度-1)”的位運(yùn)算結(jié)果）也隨之改變。調(diào)整數(shù)組的大小會(huì)創(chuàng)建兩個(gè)新的桶（鏈表），并且將所有現(xiàn)存Entry對(duì)象重新分配到桶上。調(diào)整數(shù)組大小的目標(biāo)在于降低鏈表的大小，從而降低put()、remove()和get()方法的執(zhí)行時(shí)間。對(duì)于具有相同哈希值的鍵所對(duì)應(yīng)的所有Entry對(duì)象來(lái)說(shuō)，它們會(huì)在調(diào)整大小后分配到相同的桶中。但是，如果兩個(gè)Entry對(duì)象的鍵的哈希值不一樣，但它們之前在同一個(gè)桶上，那么在調(diào)整以后，并不能保證它們依然在同一個(gè)桶上。

這幅圖片描述了調(diào)整前和調(diào)整后的內(nèi)部數(shù)組的情況。在調(diào)整數(shù)組長(zhǎng)度之前，為了得到Entry對(duì)象E，Map需要迭代遍歷一個(gè)包含5個(gè)元素的鏈表。在調(diào)整數(shù)組長(zhǎng)度之后，同樣的get()方法則只需要遍歷一個(gè)包含2個(gè)元素的鏈表，這樣get()方法在調(diào)整數(shù)組長(zhǎng)度后的運(yùn)行速度提高了2倍。

線(xiàn)程安全

如果你已經(jīng)非常熟悉HashMap，那么你肯定知道它不是線(xiàn)程安全的，但是為什么呢？例如假設(shè)你有一個(gè)Writer線(xiàn)程，它只會(huì)向Map中插入已經(jīng)存在的數(shù)據(jù)，一個(gè)Reader線(xiàn)程，它會(huì)從Map中讀取數(shù)據(jù)，那么它為什么不工作呢？

因?yàn)樵谧詣?dòng)調(diào)整大小的機(jī)制下，如果線(xiàn)程試著去添加或者獲取一個(gè)對(duì)象，Map可能會(huì)使用舊的索引值，這樣就不會(huì)找到Entry對(duì)象所在的新桶。

在最糟糕的情況下，當(dāng)2個(gè)線(xiàn)程同時(shí)插入數(shù)據(jù)，而2次put()調(diào)用會(huì)同時(shí)出發(fā)數(shù)組自動(dòng)調(diào)整大小。既然兩個(gè)線(xiàn)程在同時(shí)修改鏈表，那么Map有可能在一個(gè)鏈表的內(nèi)部循環(huán)中退出。如果你試著去獲取一個(gè)帶有內(nèi)部循環(huán)的列表中的數(shù)據(jù)，那么get()方法永遠(yuǎn)不會(huì)結(jié)束。

HashTable提供了一個(gè)線(xiàn)程安全的實(shí)現(xiàn)，可以阻止上述情況發(fā)生。但是，既然所有的同步的CRUD操作都非常慢。例如，如果線(xiàn)程1調(diào)用get(key1)，然后線(xiàn)程2調(diào)用get(key2)，線(xiàn)程2調(diào)用get(key3)，那么在指定時(shí)間，只能有1個(gè)線(xiàn)程可以得到它的值，但是3個(gè)線(xiàn)程都可以同時(shí)訪問(wèn)這些數(shù)據(jù)。

從Java 5開(kāi)始，我們就擁有一個(gè)更好的、保證線(xiàn)程安全的HashMap實(shí)現(xiàn)：ConcurrentHashMap。對(duì)于ConcurrentMap來(lái)說(shuō)，只有桶是同步的，這樣如果多個(gè)線(xiàn)程不使用同一個(gè)桶或者調(diào)整內(nèi)部數(shù)組的大小，它們可以同時(shí)調(diào)用get()、remove()或者put()方法。在一個(gè)多線(xiàn)程應(yīng)用程序中，這種方式是更好的選擇。

鍵的不變性

為什么將字符串和整數(shù)作為HashMap的鍵是一種很好的實(shí)現(xiàn)？主要是因?yàn)樗鼈兪遣豢勺兊?！如果你選擇自己創(chuàng)建一個(gè)類(lèi)作為鍵，但不能保證這個(gè)類(lèi)是不可變的，那么你可能會(huì)在HashMap內(nèi)部丟失數(shù)據(jù)。

我們來(lái)看下面的用例：

你有一個(gè)鍵，它的內(nèi)部值是“1”。

你向HashMap中插入一個(gè)對(duì)象，它的鍵就是“1”。

HashMap從鍵（即“1”）的散列碼中生成哈希值。

Map在新創(chuàng)建的記錄中存儲(chǔ)這個(gè)哈希值。

你改動(dòng)鍵的內(nèi)部值，將其變?yōu)椤?”。

鍵的哈希值發(fā)生了改變，但是HashMap并不知道這一點(diǎn)（因?yàn)榇鎯?chǔ)的是舊的哈希值）。

你試著通過(guò)修改后的鍵獲取相應(yīng)的對(duì)象。

Map會(huì)計(jì)算新的鍵（即“2”）的哈希值，從而找到Entry對(duì)象所在的鏈表（桶）。

情況1： 既然你已經(jīng)修改了鍵，Map會(huì)試著在錯(cuò)誤的桶中尋找Entry對(duì)象，沒(méi)有找到。

情況2： 你很幸運(yùn)，修改后的鍵生成的桶和舊鍵生成的桶是同一個(gè)。Map這時(shí)會(huì)在鏈表中進(jìn)行遍歷，已找到具有相同鍵的Entry對(duì)象。但是為了尋找鍵，Map首先會(huì)通過(guò)調(diào)用equals()方法來(lái)比較鍵的哈希值。因?yàn)樾薷暮蟮逆I會(huì)生成不同的哈希值（舊的哈希值被存儲(chǔ)在記錄中），那么Map沒(méi)有辦法在鏈表中找到對(duì)應(yīng)的Entry對(duì)象。

下面是一個(gè)Java示例，我們向Map中插入兩個(gè)鍵值對(duì)，然后我修改第一個(gè)鍵，并試著去獲取這兩個(gè)對(duì)象。你會(huì)發(fā)現(xiàn)從Map中返回的只有第二個(gè)對(duì)象，第一個(gè)對(duì)象已經(jīng)“丟失”在HashMap中：

public class MutableKeyTest {
public static void main(String[] args) {
class MyKey {
Integer i;
public void setI(Integer i) {
this.i = i;
}
public MyKey(Integer i) {
this.i = i;
}
@Override
public int hashCode() {
return i;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof MyKey) {
return i.equals(((MyKey) obj).i);
} else
return false;
}
}
Map<MyKey, String> myMap = new HashMap<>();
MyKey key1 = new MyKey(1);
MyKey key2 = new MyKey(2);
myMap.put(key1, "test " + 1);
myMap.put(key2, "test " + 2);
// modifying key1
key1.setI(3);
String test1 = myMap.get(key1);
String test2 = myMap.get(key2);
System.out.println("test1= " + test1 + " test2=" + test2);
}
}

上述代碼的輸出是“test1=null test2=test 2”。如我們期望的那樣，Map沒(méi)有能力獲取經(jīng)過(guò)修改的鍵 1所對(duì)應(yīng)的字符串1。

Java 8 中的改進(jìn)

在Java 8中，HashMap中的內(nèi)部實(shí)現(xiàn)進(jìn)行了很多修改。的確如此，Java 7使用了1000行代碼來(lái)實(shí)現(xiàn)，而Java 8中使用了2000行代碼。我在前面描述的大部分內(nèi)容在Java 8中依然是對(duì)的，除了使用鏈表來(lái)保存Entry對(duì)象。在Java 8中，我們?nèi)匀皇褂脭?shù)組，但它會(huì)被保存在Node中，Node中包含了和之前Entry對(duì)象一樣的信息，并且也會(huì)使用鏈表：

下面是在Java 8中Node實(shí)現(xiàn)的一部分代碼：

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;

那么和Java 7相比，到底有什么大的區(qū)別呢？好吧，Node可以被擴(kuò)展成TreeNode。TreeNode是一個(gè)紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)，它可以存儲(chǔ)更多的信息，這樣我們可以在O(log(n))的復(fù)雜度下添加、刪除或者獲取一個(gè)元素。下面的示例描述了TreeNode保存的所有信息：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
final int hash; // inherited from Node<K,V>
final K key; // inherited from Node<K,V>
V value; // inherited from Node<K,V>
Node<K,V> next; // inherited from Node<K,V>
Entry<K,V> before, after;// inherited from LinkedHashMap.Entry<K,V>
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red;

紅黑樹(shù)是自平衡的二叉搜索樹(shù)。它的內(nèi)部機(jī)制可以保證它的長(zhǎng)度總是log(n)，不管我們是添加還是刪除節(jié)點(diǎn)。使用這種類(lèi)型的樹(shù)，最主要的好處是針對(duì)內(nèi)部表中許多數(shù)據(jù)都具有相同索引（桶）的情況，這時(shí)對(duì)樹(shù)進(jìn)行搜索的復(fù)雜度是O(log(n))，而對(duì)于鏈表來(lái)說(shuō)，執(zhí)行相同的操作，復(fù)雜度是O(n)。

如你所見(jiàn)，我們?cè)跇?shù)中確實(shí)存儲(chǔ)了比鏈表更多的數(shù)據(jù)。根據(jù)繼承原則，內(nèi)部表中可以包含Node（鏈表）或者TreeNode（紅黑樹(shù)）。Oracle決定根據(jù)下面的規(guī)則來(lái)使用這兩種數(shù)據(jù)結(jié)構(gòu)：

- 對(duì)于內(nèi)部表中的指定索引（桶），如果node的數(shù)目多于8個(gè)，那么鏈表就會(huì)被轉(zhuǎn)換成紅黑樹(shù)。

- 對(duì)于內(nèi)部表中的指定索引（桶），如果node的數(shù)目小于6個(gè)，那么紅黑樹(shù)就會(huì)被轉(zhuǎn)換成鏈表。

這張圖片描述了在Java 8 HashMap中的內(nèi)部數(shù)組，它既包含樹(shù)（桶0），也包含鏈表（桶1，2和3）。桶0是一個(gè)樹(shù)結(jié)構(gòu)是因?yàn)樗墓?jié)點(diǎn)大于8個(gè)。

內(nèi)存開(kāi)銷(xiāo)

JAVA 7

使用HashMap會(huì)消耗一些內(nèi)存。在Java 7中，HashMap將鍵值對(duì)封裝成Entry對(duì)象，一個(gè)Entry對(duì)象包含以下信息：

指向下一個(gè)記錄的引用
一個(gè)預(yù)先計(jì)算的哈希值（整數(shù)）
一個(gè)指向鍵的引用
一個(gè)指向值的引用

此外，Java 7中的HashMap使用了Entry對(duì)象的內(nèi)部數(shù)組。假設(shè)一個(gè)Java 7 HashMap包含N個(gè)元素，它的內(nèi)部數(shù)組的容量是CAPACITY，那么額外的內(nèi)存消耗大約是：

sizeOf(integer)* N + sizeOf(reference)* (3*N+C)

其中：

整數(shù)的大小是4個(gè)字節(jié)

引用的大小依賴(lài)于JVM、操作系統(tǒng)以及處理器，但通常都是4個(gè)字節(jié)。

這就意味著內(nèi)存總開(kāi)銷(xiāo)通常是16 * N + 4 * CAPACITY字節(jié)。

注意：在Map自動(dòng)調(diào)整大小后，CAPACITY的值是下一個(gè)大于N的最小的2的冪值。

注意：從Java 7開(kāi)始，HashMap采用了延遲加載的機(jī)制。這意味著即使你為HashMap指定了大小，在我們第一次使用put()方法之前，記錄使用的內(nèi)部數(shù)組（耗費(fèi)4*CAPACITY字節(jié)）也不會(huì)在內(nèi)存中分配空間。

JAVA 8

在Java 8實(shí)現(xiàn)中，計(jì)算內(nèi)存使用情況變得復(fù)雜一些，因?yàn)镹ode可能會(huì)和Entry存儲(chǔ)相同的數(shù)據(jù)，或者在此基礎(chǔ)上再增加6個(gè)引用和一個(gè)Boolean屬性（指定是否是TreeNode）。

如果所有的節(jié)點(diǎn)都只是Node，那么Java 8 HashMap消耗的內(nèi)存和Java 7 HashMap消耗的內(nèi)存是一樣的。

如果所有的節(jié)點(diǎn)都是TreeNode，那么Java 8 HashMap消耗的內(nèi)存就變成：

N * sizeOf(integer) + N * sizeOf(boolean) + sizeOf(reference)* (9*N+CAPACITY )

在大部分標(biāo)準(zhǔn)JVM中，上述公式的結(jié)果是44 * N + 4 * CAPACITY 字節(jié)。

性能問(wèn)題

非對(duì)稱(chēng)HashMap vs 均衡HashMap

在最好的情況下，get()和put()方法都只有O(1)的復(fù)雜度。但是，如果你不去關(guān)心鍵的哈希函數(shù)，那么你的put()和get()方法可能會(huì)執(zhí)行非常慢。put()和get()方法的高效執(zhí)行，取決于數(shù)據(jù)被分配到內(nèi)部數(shù)組（桶）的不同的索引上。如果鍵的哈希函數(shù)設(shè)計(jì)不合理，你會(huì)得到一個(gè)非對(duì)稱(chēng)的分區(qū)（不管內(nèi)部數(shù)據(jù)的是多大）。所有的put()和get()方法會(huì)使用最大的鏈表，這樣就會(huì)執(zhí)行很慢，因?yàn)樗枰湵碇械娜坑涗洝Ｔ谧顗牡那闆r下（如果大部分?jǐn)?shù)據(jù)都在同一個(gè)桶上），那么你的時(shí)間復(fù)雜度就會(huì)變?yōu)镺(n)。

下面是一個(gè)可視化的示例。第一張圖描述了一個(gè)非對(duì)稱(chēng)HashMap，第二張圖描述了一個(gè)均衡HashMap。

skewedHashmap

在這個(gè)非對(duì)稱(chēng)HashMap中，在桶0上運(yùn)行g(shù)et()和put()方法會(huì)很花費(fèi)時(shí)間。獲取記錄K需要花費(fèi)6次迭代。

在這個(gè)均衡HashMap中，獲取記錄K只需要花費(fèi)3次迭代。這兩個(gè)HashMap存儲(chǔ)了相同數(shù)量的數(shù)據(jù)，并且內(nèi)部數(shù)組的大小一樣。唯一的區(qū)別是鍵的哈希函數(shù)，這個(gè)函數(shù)用來(lái)將記錄分布到不同的桶上。

下面是一個(gè)使用Java編寫(xiě)的極端示例，在這個(gè)示例中，我使用哈希函數(shù)將所有的數(shù)據(jù)放到相同的鏈表（桶），然后我添加了2,000,000條數(shù)據(jù)。

public class Test {
public static void main(String[] args) {
class MyKey {
Integer i;
public MyKey(Integer i){
this.i =i;
}
@Override
public int hashCode() {
return 1;
}
@Override
public boolean equals(Object obj) {
…
}
}
Date begin = new Date();
Map <MyKey,String> myMap= new HashMap<>(2_500_000,1);
for (int i=0;i<2_000_000;i++){
myMap.put( new MyKey(i), "test "+i);
}
Date end = new Date();
System.out.println("Duration (ms) "+ (end.getTime()-begin.getTime()));
}
}

我的機(jī)器配置是core i5-2500k @ 3.6G，在java 8u40下需要花費(fèi)超過(guò)45分鐘的時(shí)間來(lái)運(yùn)行（我在45分鐘后停止了進(jìn)程）。如果我運(yùn)行同樣的代碼， 但是我使用如下的hash函數(shù)：

@Override
public int hashCode() {
int key = 2097152-1;
return key+2097152*i;
}

運(yùn)行它需要花費(fèi)46秒，和之前比，這種方式好很多了！新的hash函數(shù)比舊的hash函數(shù)在處理哈希分區(qū)時(shí)更合理，因此調(diào)用put()方法會(huì)更快一些。如果你現(xiàn)在運(yùn)行相同的代碼，但是使用下面的hash函數(shù)，它提供了更好的哈希分區(qū)：

@Override
public int hashCode() {
return i;
}

現(xiàn)在只需要花費(fèi)2秒！

我希望你能夠意識(shí)到哈希函數(shù)有多重要。如果在Java 7上面運(yùn)行同樣的測(cè)試，第一個(gè)和第二個(gè)的情況會(huì)更糟（因?yàn)镴ava 7中的put()方法復(fù)雜度是O(n)，而Java 8中的復(fù)雜度是O(log(n))。

在使用HashMap時(shí)，你需要針對(duì)鍵找到一種哈希函數(shù)，可以將鍵擴(kuò)散到最可能的桶上。為此，你需要避免哈希沖突。String對(duì)象是一個(gè)非常好的鍵，因?yàn)樗泻芎玫墓：瘮?shù)。Integer也很好，因?yàn)樗墓Ｖ稻褪撬陨淼闹怠?/p>

調(diào)整大小的開(kāi)銷(xiāo)

如果你需要存儲(chǔ)大量數(shù)據(jù)，你應(yīng)該在創(chuàng)建HashMap時(shí)指定一個(gè)初始的容量，這個(gè)容量應(yīng)該接近你期望的大小。

如果你不這樣做，Map會(huì)使用默認(rèn)的大小，即16，factorLoad的值是0.75。前11次調(diào)用put()方法會(huì)非?？?，但是第12次（16*0.75）調(diào)用時(shí)會(huì)創(chuàng)建一個(gè)新的長(zhǎng)度為32的內(nèi)部數(shù)組（以及對(duì)應(yīng)的鏈表/樹(shù)），第13次到第22次調(diào)用put()方法會(huì)很快，但是第23次（32*0.75）調(diào)用時(shí)會(huì)重新創(chuàng)建（再一次）一個(gè)新的內(nèi)部數(shù)組，數(shù)組的長(zhǎng)度翻倍。然后內(nèi)部調(diào)整大小的操作會(huì)在第48次、96次、192次…..調(diào)用put()方法時(shí)觸發(fā)。如果數(shù)據(jù)量不大，重建內(nèi)部數(shù)組的操作會(huì)很快，但是數(shù)據(jù)量很大時(shí)，花費(fèi)的時(shí)間可能會(huì)從秒級(jí)到分鐘級(jí)。通過(guò)初始化時(shí)指定Map期望的大小，你可以避免調(diào)整大小操作帶來(lái)的消耗。

但這里也有一個(gè)缺點(diǎn)：如果你將數(shù)組設(shè)置的非常大，例如2^28，但你只是用了數(shù)組中的2^26個(gè)桶，那么你將會(huì)浪費(fèi)大量的內(nèi)存（在這個(gè)示例中大約是2^30字節(jié)）。

結(jié)論

對(duì)于簡(jiǎn)單的用例，你沒(méi)有必要知道HashMap是如何工作的，因?yàn)槟悴粫?huì)看到O(1)、O(n)以及O(log(n))之間的區(qū)別。但是如果能夠理解這一經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu)背后的機(jī)制，總是有好處的。另外，對(duì)于Java開(kāi)發(fā)者職位來(lái)說(shuō)，這是一道典型的面試問(wèn)題。

對(duì)于大數(shù)據(jù)量的情況，了解HashMap如何工作以及理解鍵的哈希函數(shù)的重要性就變得非常重要。

我希望這篇文章可以幫助你對(duì)HashMap的實(shí)現(xiàn)有一個(gè)深入的理解。

最新評(píng)論