讓我們先來看看HashMap有哪些知識點：

• hashing的概念
• HashMap中解決碰撞的方法
• equals()和hashCode()的應(yīng)用，以及它們在HashMap中的重要性
• 不可變對象的好處
• HashMap多線程的條件競爭
• 重新調(diào)整HashMap的大小

HashMap概述

HashMap是基于哈希表的Map接口的非同步實現(xiàn)。此實現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。

HashMap的數(shù)據(jù)結(jié)構(gòu)

在Java編程語言中，最基本的結(jié)構(gòu)就是兩種，一個是數(shù)組，另外一個是模擬指針（引用），所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個基本結(jié)構(gòu)來構(gòu)造的，HashMap也不例外。HashMap實際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。

從上圖中可以看出，HashMap底層就是一個數(shù)組結(jié)構(gòu)，數(shù)組中的每一項又是一個鏈表。當新建一個HashMap的時候，就會初始化一個數(shù)組。

/**
* The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry[] table;
 
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
    ……
}

可以看出，Entry就是數(shù)組中的元素，每個 Map.Entry 其實就是一個key-value對，它持有一個指向下一個元素的引用，這就構(gòu)成了鏈表。

HashMap的存取實現(xiàn)

存儲

public V put(K key, V value) {
    // HashMap允許存放null鍵和null值。
    // 當key為null時，調(diào)用putForNullKey方法，將value放置在數(shù)組第一個位置。  
    if (key == null)
        return putForNullKey(value);
    // 根據(jù)key的keyCode重新計算hash值。
    int hash = hash(key.hashCode());
    // 搜索指定hash值在對應(yīng)table中的索引。
    int i = indexFor(hash, table.length);
    // 如果 i 索引處的 Entry 不為 null，通過循環(huán)不斷遍歷 e 元素的下一個元素。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 如果i索引處的Entry為null，表明此處還沒有Entry。
    modCount++;
    // 將key、value添加到i索引處。
    addEntry(hash, key, value, i);
    return null;
}

從上面的源代碼中可以看出：當我們往HashMap中put元素的時候，先根據(jù)key的hashCode重新計算hash值，根據(jù)hash值得到這個元素在數(shù)組中的位置（即下標）， 如果數(shù)組該位置上已經(jīng)存放有其他元素了，那么在這個位置上的元素將以鏈表的形式存放，新加入的放在鏈頭，最先加入的放在鏈尾。如果數(shù)組該位置上沒有元素，就直接將該元素放到此數(shù)組中的該位置上。

addEntry(hash, key, value, i)方法根據(jù)計算出的hash值，將key-value對放在數(shù)組table的i索引處。addEntry 是 HashMap 提供的一個包訪問權(quán)限的方法，代碼如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 獲取指定 bucketIndex 索引處的 Entry  
    Entry<K,V> e = table[bucketIndex];
    // 將新創(chuàng)建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry  
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    // 如果 Map 中的 key-value 對的數(shù)量超過了極限
    if (size++ >= threshold)
    // 把 table 對象的長度擴充到原來的2倍。
        resize(2 * table.length);
}

當系統(tǒng)決定存儲HashMap中的key-value對時，完全沒有考慮Entry中的value，僅僅只是根據(jù)key來計算并決定每個Entry的存儲位置。我們完全可以把 Map 集合中的 value 當成 key 的附屬，當系統(tǒng)決定了 key 的存儲位置之后，value 隨之保存在那里即可。

hash(int h)方法根據(jù)key的hashCode重新計算一次散列。此算法加入了高位計算，防止低位不變，高位變化時，造成的hash沖突。

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);  
}

我們可以看到在HashMap中要找到某個元素，需要根據(jù)key的hash值來求得對應(yīng)數(shù)組中的位置。如何計算這個位置就是hash算法。前面說過HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，所以我們當然希望這個HashMap里面的 元素位置盡量的分布均勻些，盡量使得每個位置上的元素數(shù)量只有一個，那么當我們用hash算法求得這個位置的時候，馬上就可以知道對應(yīng)位置的元素就是我們要的，而不用再去遍歷鏈表，這樣就大大優(yōu)化了查詢的效率。

對于任意給定的對象，只要它的 hashCode() 返回值相同，那么程序調(diào)用 hash(int h) 方法所計算得到的 hash 碼值總是相同的。我們首先想到的就是把hash值對數(shù)組長度取模運算，這樣一來，元素的分布相對來說是比較均勻的。但是，“模”運算的消耗還是比較大的，在HashMap中是這樣做的：調(diào)用 indexFor(int h, int length) 方法來計算該對象應(yīng)該保存在 table 數(shù)組的哪個索引處。indexFor(int h, int length) 方法的代碼如下：

static int indexFor(int h, int length) {  
    return h & (length-1);
}

這個方法非常巧妙，它通過 h & (table.length -1) 來得到該對象的保存位，而HashMap底層數(shù)組的長度總是 2 的 n 次方，這是HashMap在速度上的優(yōu)化。在 HashMap 構(gòu)造器中有如下代碼：

int capacity = 1;
    while (capacity < initialCapacity)  
        capacity <<= 1;

這段代碼保證初始化時HashMap的容量總是2的n次方，即底層數(shù)組的長度總是為2的n次方。

當length總是 2 的n次方時，h& (length-1)運算等價于對length取模，也就是h%length，但是&比%具有更高的效率。

這看上去很簡單，其實比較有玄機的，我們舉個例子來說明：

假設(shè)數(shù)組長度分別為15和16，優(yōu)化后的hash碼分別為8和9，那么&運算后的結(jié)果如下：

h & (table.length-1)    hash        table.length-1  
8 & (15-1)： 0100    &   1110    = 0100
9 & (15-1)： 0101    &   1110    = 0100
8 & (16-1)： 0100    &   1111    = 0100
9 & (16-1)： 0101    &   1111    = 0101

從上面的例子中可以看出：當它們和15-1（1110）“與”的時候，產(chǎn)生了相同的結(jié)果，也就是說它們會定位到數(shù)組中的同一個位置上去，這就產(chǎn)生了碰撞，8和9會被放到數(shù)組中的同一個位置上形成鏈表，那么查詢的時候就需要遍歷這個鏈 表，得到8或者9，這樣就降低了查詢的效率。同時，我們也可以發(fā)現(xiàn)，當數(shù)組長度為15的時候，hash值會與15-1（1110）進行“與”，那么最后一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，數(shù)組可以使用的位置比數(shù)組長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率！而當數(shù)組長度為16時，即為2的n次方時，2n-1得到的二進制數(shù)的每個位上的值都為1，這使得在低位上&時，得到的和原h(huán)ash的低位相同，加之hash(int h)方法對key的hashCode的進一步優(yōu)化，加入了高位計算，就使得只有相同的hash值的兩個值才會被放到數(shù)組中的同一個位置上形成鏈表。

所以說，當數(shù)組長度為2的n次冪的時候，不同的key算得得index相同的幾率較小，那么數(shù)據(jù)在數(shù)組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了。

根據(jù)上面 put 方法的源代碼可以看出，當程序試圖將一個key-value對放入HashMap中時，程序首先根據(jù)該 key 的 hashCode() 返回值決定該 Entry 的存儲位置：如果兩個 Entry 的 key 的 hashCode() 返回值相同，那它們的存儲位置相同。如果這兩個 Entry 的 key 通過 equals 比較返回 true，新添加 Entry 的 value 將覆蓋集合中原有 Entry 的 value，但key不會覆蓋。如果這兩個 Entry 的 key 通過 equals 比較返回 false，新添加的 Entry 將與集合中原有 Entry 形成 Entry 鏈，而且新添加的 Entry 位于 Entry 鏈的頭部——具體說明繼續(xù)看 addEntry() 方法的說明。

讀取

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
        e != null;
        e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
            return e.value;
    }
    return null;
}

有了上面存儲時的hash算法作為基礎(chǔ)，理解起來這段代碼就很容易了。從上面的源代碼中可以看出：從HashMap中g(shù)et元素時，首先計算key的hashCode，找到數(shù)組中對應(yīng)位置的某一元素，然后通過key的equals方法在對應(yīng)位置的鏈表中找到需要的元素。

歸納
簡單地說，HashMap 在底層將 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象。HashMap 底層采用一個 Entry[] 數(shù)組來保存所有的 key-value 對，當需要存儲一個 Entry 對象時，會根據(jù)hash算法來決定其在數(shù)組中的存儲位置，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置；當需要取出一個Entry時，
也會根據(jù)hash算法找到其在數(shù)組中的存儲位置，再根據(jù)equals方法從該位置上的鏈表中取出該Entry。

HashMap的resize（rehash）

當HashMap中的元素越來越多的時候，hash沖突的幾率也就越來越高，因為數(shù)組的長度是固定的。所以為了提高查詢的效率，就要對HashMap的數(shù)組進行擴容，數(shù)組擴容這個操作也會出現(xiàn)在ArrayList中，這是一個常用的操作，而在HashMap數(shù)組擴容之后，最消耗性能的點就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計算其在新數(shù)組中的位置，并放進去，這就是resize。

那么HashMap什么時候進行擴容呢？當HashMap中的元素個數(shù)超過數(shù)組大小loadFactor時，就會進行數(shù)組擴容，loadFactor的默認值為0.75，這是一個折中的取值。也就是說，默認情況下，數(shù)組大小為16，那么當HashMap中元素個數(shù)超過160.75=12的時候，就把數(shù)組的大小擴展為 2*16=32，即擴大一倍，然后重新計算每個元素在數(shù)組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經(jīng)預知HashMap中元素的個數(shù)，那么預設(shè)元素的個數(shù)能夠有效的提高HashMap的性能。

HashMap的性能參數(shù)

HashMap 包含如下幾個構(gòu)造器：

HashMap()：構(gòu)建一個初始容量為 16，負載因子為 0.75 的 HashMap。
ashMap(int initialCapacity)：構(gòu)建一個初始容量為 initialCapacity，負載因子為 0.75 的 HashMap。
HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的負載因子創(chuàng)建一個 HashMap。
HashMap的基礎(chǔ)構(gòu)造器HashMap(int initialCapacity, float loadFactor)帶有兩個參數(shù)，它們是初始容量initialCapacity和負載因子loadFactor。

負載因子loadFactor衡量的是一個散列表的空間的使用程度，負載因子越大表示散列表的裝填程度越高，反之愈小。對于使用鏈表法的散列表來說，查找一個元素的平均時間是O(1+a)，因此如果負載因子越大，對空間的利用更充分，然而后果是查找效率的降低；如果負載因子太小，那么散列表的數(shù)據(jù)將過于稀疏，對空間造成嚴重浪費。

HashMap的實現(xiàn)中，通過threshold字段來判斷HashMap的最大容量：

threshold = (int)(capacity * loadFactor);

結(jié)合負載因子的定義公式可知，threshold就是在此loadFactor和capacity對應(yīng)下允許的最大元素數(shù)目，超過這個數(shù)目就重新resize，以降低實際的負載因子。默認的的負載因子0.75是對空間和時間效率的一個平衡選擇。當容量超出此最大容量時， resize后的HashMap容量是容量的兩倍：

Fail-Fast機制

我們知道java.util.HashMap不是線程安全的，因此如果在使用迭代器的過程中有其他線程修改了map，那么將拋出ConcurrentModificationException，這就是所謂fail-fast策略。

這一策略在源碼中的實現(xiàn)是通過modCount域，modCount顧名思義就是修改次數(shù)，對HashMap內(nèi)容的修改都將增加這個值，那么在迭代器初始化過程中會將這個值賦給迭代器的expectedModCount。

HashIterator() {
    expectedModCount = modCount;
    if (size > 0) { // advance to first entry
    Entry[] t = table;
    while (index < t.length && (next = t[index++]) == null)  
        ;
    }
}

在迭代過程中，判斷modCount跟expectedModCount是否相等，如果不相等就表示已經(jīng)有其他線程修改了Map：

注意到modCount聲明為volatile，保證線程之間修改的可見性。

final Entry<K,V> nextEntry() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();

在HashMap的API中指出：

由所有HashMap類的“collection 視圖方法”所返回的迭代器都是快速失敗的：在迭代器創(chuàng)建之后，如果從結(jié)構(gòu)上對映射進行修改，除非通過迭代器本身的 remove 方法，其他任何時間任何方式的修改，迭代器都將拋出 ConcurrentModificationException。因此，面對并發(fā)的修改，迭代器很快就會完全失敗，而不冒在將來不確定的時間發(fā)生任意不確定行為的風險。

注意，迭代器的快速失敗行為不能得到保證，一般來說，存在非同步的并發(fā)修改時，不可能作出任何堅決的保證?？焖偈〉鞅M最大努力拋出ConcurrentModificationException。因此，編寫依賴于此異常的程序的做法是錯誤的，正確做法是：迭代器的快速失敗行為應(yīng)該僅用于檢測程序錯誤。

HashMap的兩種遍歷方式

第一種

Map map = new HashMap();
　　Iterator iter = map.entrySet().iterator();
　　while (iter.hasNext()) {
　　Map.Entry entry = (Map.Entry) iter.next();
　　Object key = entry.getKey();
　　Object val = entry.getValue();
　　}

效率高,以后一定要使用此種方式！

第二種

Map map = new HashMap();
　　Iterator iter = map.keySet().iterator();
　　while (iter.hasNext()) {
　　Object key = iter.next();
　　Object val = map.get(key);
　　}

效率低,以后盡量少使用！

面試常見問題總結(jié)

“你用過HashMap嗎？” “什么是HashMap？你為什么用到它？”

幾乎每個人都會回答“是的”，然后回答HashMap的一些特性，譬如HashMap可以接受null鍵值和值，而Hashtable則不能；HashMap是非synchronized;HashMap很快；以及HashMap儲存的是鍵值對等等。這顯示出你已經(jīng)用過HashMap，而且對它相當?shù)氖煜?。但是面試官來個急轉(zhuǎn)直下，從此刻開始問出一些刁鉆的問題，關(guān)于HashMap的更多基礎(chǔ)的細節(jié)。面試官可能會問出下面的問題：

“你知道HashMap的工作原理嗎？” “你知道HashMap的get()方法的工作原理嗎？”

你也許會回答“我沒有詳查標準的Java API，你可以看看Java源代碼或者Open JDK?！薄拔铱梢杂肎oogle找到答案?！?/p>

但一些面試者可能可以給出答案，“HashMap是基于hashing的原理，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象。當我們給put()方法傳遞鍵和值時，我們先對鍵調(diào)用hashCode()方法，返回的hashCode用于找到bucket位置來儲存Entry對象。”這里關(guān)鍵點在于指出，HashMap是在bucket中儲存鍵對象和值對象，作為Map.Entry。這一點有助于理解獲取對象的邏輯。如果你沒有意識到這一點，或者錯誤的認為僅僅只在bucket中存儲值的話，你將不會回答如何從HashMap中獲取對象的邏輯。這個答案相當?shù)恼_，也顯示出面試者確實知道hashing以及HashMap的工作原理。但是這僅僅是故事的開始，當面試官加入一些Java程序員每天要碰到的實際場景的時候，錯誤的答案頻現(xiàn)。下個問題可能是關(guān)于HashMap中的碰撞探測(collision detection)以及碰撞的解決方法：

“當兩個對象的hashcode相同會發(fā)生什么？” 從這里開始，真正的困惑開始了，一些面試者會回答因為hashcode相同，所以兩個對象是相等的，HashMap將會拋出異常，或者不會存儲它們。然后面試官可能會提醒他們有equals()和hashCode()兩個方法，并告訴他們兩個對象就算hashcode相同，但是它們可能并不相等。一些面試者可能就此放棄，而另外一些還能繼續(xù)挺進，他們回答“因為hashcode相同，所以它們的bucket位置相同，‘碰撞’會發(fā)生。因為HashMap使用鏈表存儲對象，這個Entry(包含有鍵值對的Map.Entry對象)會存儲在鏈表中?！边@個答案非常的合理，雖然有很多種處理碰撞的方法，這種方法是最簡單的，也正是HashMap的處理方法。但故事還沒有完結(jié)，面試官會繼續(xù)問：

“如果兩個鍵的hashcode相同，你如何獲取值對象？” 面試者會回答：當我們調(diào)用get()方法，HashMap會使用鍵對象的hashcode找到bucket位置，然后獲取值對象。面試官提醒他如果有兩個值對象儲存在同一個bucket，他給出答案:將會遍歷鏈表直到找到值對象。面試官會問因為你并沒有值對象去比較，你是如何確定確定找到值對象的？除非面試者直到HashMap在鏈表中存儲的是鍵值對，否則他們不可能回答出這一題。

其中一些記得這個重要知識點的面試者會說，找到bucket位置之后，會調(diào)用keys.equals()方法去找到鏈表中正確的節(jié)點，最終找到要找的值對象。完美的答案！

許多情況下，面試者會在這個環(huán)節(jié)中出錯，因為他們混淆了hashCode()和equals()方法。因為在此之前hashCode()屢屢出現(xiàn)，而equals()方法僅僅在獲取值對象的時候才出現(xiàn)。一些優(yōu)秀的開發(fā)者會指出使用不可變的、聲明作final的對象，并且采用合適的equals()和hashCode()方法的話，將會減少碰撞的發(fā)生，提高效率。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個獲取對象的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇。

如果你認為到這里已經(jīng)完結(jié)了，那么聽到下面這個問題的時候，你會大吃一驚。“如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦？”除非你真正知道HashMap的工作原理，否則你將回答不出這道題。默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組，來重新調(diào)整map的大小，并將原來的對象放入新的bucket數(shù)組中。這個過程叫作rehashing，因為它調(diào)用hash方法找到新的bucket位置。

如果你能夠回答這道問題，下面的問題來了：“你了解重新調(diào)整HashMap大小存在什么問題嗎？”你可能回答不上來，這時面試官會提醒你當多線程的情況下，可能產(chǎn)生條件競爭(race condition)。

當重新調(diào)整HashMap大小的時候，確實存在條件競爭，因為如果兩個線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了，它們會同時試著調(diào)整大小。在調(diào)整大小的過程中，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發(fā)生了，那么就死循環(huán)了。這個時候，你可以質(zhì)問面試官，為什么這么奇怪，要在多線程的環(huán)境下使用HashMap呢？：）

為什么String, Interger這樣的wrapper類適合作為鍵？

String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因為String是不可變的，也是final的，而且已經(jīng)重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優(yōu)點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。

我們可以使用自定義的對象作為鍵嗎？

這是前一個問題的延伸。當然你可能使用任何對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規(guī)則，并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的，那么它已經(jīng)滿足了作為鍵的條件，因為當它創(chuàng)建之后就已經(jīng)不能改變了。

我們可以使用CocurrentHashMap來代替Hashtable嗎？

這是另外一個很熱門的面試題，因為ConcurrentHashMap越來越多人用了。我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據(jù)同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的線程安全性。

總結(jié)

HashMap的工作原理

HashMap基于hashing原理，我們通過put()和get()方法儲存和獲取對象。當我們將鍵值對傳遞給put()方法時，它調(diào)用鍵對象的hashCode()方法來計算hashcode，讓后找到bucket位置來儲存值對象。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。HashMap使用鏈表來解決碰撞問題，當發(fā)生碰撞了，對象將會儲存在鏈表的下一個節(jié)點中。 HashMap在每個鏈表節(jié)點中儲存鍵值對對象。

當兩個不同的鍵對象的hashcode相同時會發(fā)生什么？ 它們會儲存在同一個bucket位置的鏈表中。鍵對象的equals()方法用來找到鍵值對。

因為HashMap的好處非常多，我曾經(jīng)在電子商務(wù)的應(yīng)用中使用HashMap作為緩存。因為金融領(lǐng)域非常多的運用Java，也出于性能的考慮，我們會經(jīng)常用到HashMap和ConcurrentHashMap。

參考文章：

http://www.importnew.com/7099.html
http://www.importnew.com/16301.html