java集合中HashMap原理詳解

來自： http://blog.csdn.net//chenleixing/article/details/42494921

HashMap在Java開發中有著非常重要的角色地位，每一個Java程序員都應該了解HashMap。

主要從源碼角度來解析HashMap的設計思路，并且詳細地闡述HashMap中的幾個概念，并深入探討HashMap的內部結構和實現細節，討論HashMap的性能問題。

1. HashMap設計思路以及內部結構組成

HashMap設計思路 
      Map<K,V>是一種以鍵值對存儲數據的容器，而HashMap則是借助了鍵值Key的hashcode值來組織存儲，使得可以非常快速和高效地地根據鍵值key進行數據的存取。

      對于鍵值對<Key,Value>，HashMap內部會將其封裝成一個對應的Entry<Key,Value>對象，即Entry<Key,Value>對象是鍵值對<Key,Value>的組織形式；

      對于每個對象而言，JVM都會為其生成一個hashcode值。HashMap在存儲鍵值對Entry<Key,Value>的時候，會根據Key的hashcode值，以某種映射關系，決定應當將這對鍵值對Entry<Key,Value>存儲在HashMap中的什么位置上；
      當通過Key值取數據的時候，然后根據Key值的hashcode，以及內部映射條件，直接定位到Key對應的Value值存放在什么位置，可以非常高效地將Value值取出。

為了實現上述的設計思路，在HashMap內部，采用了數組+鏈表的形式來組織鍵值對Entry<Key,Value>。

HashMap內部維護了一個Entry[] table 數組，當我們使用 new HashMap()創建一個HashMap時，Entry[] table 的默認長度為16（參見Java API）。Entry[] table的長度又被稱為這個HashMap的容量（capacity）；

對于Entry[] table的每一個元素而言，或為null，或為由若干個Entry<Key,Value>組成的鏈表。HashMap中Entry<Key,Value>的數目被稱為HashMap的大小(size);

Entry[] table中的某一個元素及其對應的Entry<Key,Value>又被稱為桶(bucket); 

其結構如下圖所示：

HashMap內部組織結構由上圖所示，接下來看一下HashMap的基本工作流程：

HashMap設計的初衷，是為了盡可能地迅速根據Key的hashCode值, 直接就可以定位到對應的Entry<Key,Value>對象，然后得到Value。

考慮這樣一個問題：

當我們使用 HashMap map = new HashMap()語句時，我們會創建一個HashMap對象，它內部的 Entry[] table的大小為 16，我們假定Entry[] table的大小會改變。現在，我們現在向它添加160對Key值完全不同的鍵值對<Key,Value>，那么，該HashMap內部有可能下面這種情況：即對于每一個桶中的由Entry<Key,Value>組成的鏈表的長度會非常地長！我們知道，對于查找鏈表操作的時間復雜度是很高的，為O(n)。這樣的一個HashMap的性能會很低很低，如下圖所示：

現在再來分析一下這個問題，當前的HashMap能夠實現：

 1. 根據Key的hashCode，可以直接定位到存儲這個Entry<Key,Value>的桶所在的位置，這個時間的復雜度為O(1)；

 2. 在桶中查找對應的Entry<Key,Value>對象節點，需要遍歷這個桶的Entry<Key,Value>鏈表，時間復雜度為O(n);

那么，現在，我們應該盡可能地將第2個問題的時間復雜度o(n)降到最低，讀者現在是不是有想法了：我們應該要求桶中的鏈表的長度越短越好！桶中鏈表的長度越短，所消耗的查找時間就越低，最好就是一個桶中就一個Entry<Key,Value>對象節點就好了！

這樣一來，桶中的Entry<Key,Value>對象節點要求盡可能第少，這就要求，HashMap中的桶的數量要多了。

我們知道，HashMap的桶數目，即Entry[] table數組的長度，由于數組是內存中連續的存儲單元，它的空間代價是很大的，但是它的隨機存取的速度是Java集合中最快的。我們增大桶的數量，而減少Entry<Key,Value>鏈表的長度，來提高從HashMap中讀取數據的速度。這是典型的拿空間換時間的策略。

但是我們不能剛開始就給HashMap分配過多的桶(即Entry[] table 數組起始不能太大)，這是因為數組是連續的內存空間，它的創建代價很大，況且我們不能確定給HashMap分配這么大的空間，它實際到底能夠用多少，為了解決這一個問題，HashMap采用了根據實際的情況，動態地分配桶的數量。

HashMap的權衡策略 
     要動態分配桶的數量，這就要求要有一個權衡的策略了，HashMap的權衡策略是這樣的：

             如果   HashMap的大小> HashMap的容量(即Entry[] table的大小)*加載因子(經驗值0.75)

                則   HashMap中的Entry[] table 的容量擴充為當前的一倍；

                      然后重新將以前桶中的Entry<Key,Value>鏈表重新分配到各個桶中

上述的  HashMap的容量(即Entry[] table的大小) * 加載因子(經驗值0.75)就是所謂的閥值(threshold)：

閥值（threshold）=容量（capacity）*加載因子（load factor）
容量（capacity）：是指HashMap內部Entry[] table線性數組的長度
加載因子（load factor）：默認為0.75
閥值（threshold）：當HashMap大小超過了閥值，HashMap將擴充2倍，并且rehash。

最后，看一個實例：

默認創建的HashMap map =new HashMap();map的容量是 16，那么，當我們往 map中添加第幾個完全不同的鍵值對<Key,Value>時，HashMap的容量會擴充呢？

很簡單的計算：由于默認的加載因子是0.75 ，那么，此時map的閥值是 16*0.75 = 12，即添加第13 個鍵值對<Key,Value>的時候，map的容量會擴充一倍。

這時候可能會有疑問：本來Entry[] table的容量是16，當放入12個鍵值對<Key,Value>后，不是至少還剩下4個Entry[] table 元素沒有被使用到嗎？這不是浪費了寶貴的空間了嗎？！   確實如此，但是為了盡可能第減少桶中的Entry<Key,Value>鏈表的長度，以提高HashMap的存取性能，確定的這個經驗值。如果你對存取效率要求的不是太高，想省點空間的話，你可以new HashMap(int initialCapacity, float loadFactor)構造方法將這個因子設置得大一些也無妨。

2. HashMap的算法實現解析

HashMap的算法實現最重要的兩個是put() 和get() 兩個方法，下面我將分析這兩個方法：

public V put(K key, V value); 
public V get(Object key);

另外，HashMap支持Key值為null 的情況，接下來也將做討論。

1. 向HashMap中存儲一對鍵值對<Key,Value>流程---put()方法實現：

put()方法-向HashMap存儲鍵值對<Key,Value>

a.  獲取這個Key的hashcode值，根據此值確定應該將這一對鍵值對存放在哪一個桶中，即確定要存放桶的索引；

b.  遍歷所在桶中的Entry<Key,Value>鏈表，查找其中是否已經有了以Key值為Key存儲的Entry<Key,Value>對象，

c1. 若已存在，定位到對應的Entry<Key,Value>,其中的Value值更新為新的Value值；返回舊值；

c2. 若不存在，則根據鍵值對<Key,Value> 創建一個新的Entry<Key,Value>對象，然后添加到這個桶的Entry<Key,Value>鏈表的頭部。

d.  當前的HashMap的大小(即Entry<key,Value>節點的數目)是否超過了閥值，若超過了閥值(threshold)，則增大HashMap的容量(即Entry[] table 的大小)，并且重新組織內部各個Entry<Key,Value>排列。

詳細流程如下列的代碼所示：

/**
     * 將<Key,Value>鍵值對存到HashMap中，如果Key在HashMap中已經存在，那么最終返回被替換掉的Value值。
     * Key 和Value允許為空
     */
    public V put(K key, V value) {

        //1.如果key為null，那么將此value放置到table[0],即第一個桶中
        if (key == null)
            return putForNullKey(value);
        //2.重新計算hashcode值，
        int hash = hash(key.hashCode());
        //3.計算當前hashcode值應當被分配到哪一個桶中，獲取桶的索引
        int i = indexFor(hash, table.length);
        //4.循環遍歷該桶中的Entry列表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //5. 查找Entry<Key,Value>鏈表中是否已經有了以Key值為Key存儲的Entry<Key,Value>對象,
            //已經存在,則將Value值覆蓋到對應的Entry<Key,Value>對象節點上
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//請讀者注意這個判定條件，非常重要！！！
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        //6不存在，則根據鍵值對<Key,Value> 創建一個新的Entry<Key,Value>對象，然后添加到這個桶的Entry<Key,Value>鏈表的頭部。
        addEntry(hash, key, value, i);
        return null;
    }


    /**
     * Key 為null,則將Entry<null,Value>放置到第一桶table[0]中
     */
    private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

/**
     * 根據特定的hashcode 重新計算hash值，
     * 由于JVM生成的的hashcode的低字節(lower bits)沖突概率大，（JDK只是這么一說，至于為什么我也不清楚）
     * 為了提高性能，HashMap對Key的hashcode再加工，取Key的hashcode的高字節參與運算
     */
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }


    /**
     * 返回此hashcode應當分配到的桶的索引
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

當HashMap的大小大于閥值時，HashMap容量的擴充算法

當當前的HashMap的大小大于閥值時，HashMap會對此HashMap的容量進行擴充，即對內部的Entry[] table 數組進行擴充。

HashMap對容量（Entry[] table數組長度） 有兩點要求：

1. 容量的大小應當是 2的N次冪；

2. 當容量大小超過閥值時，容量擴充為當前的一倍；

這里第2點很重要,如果當前的HashMap的容量為16，需要擴充時，容量就要變成16*2 = 32,接著就是32*2=64、64*2=128、128*2=256.........可以看出，容量擴充的大小是呈指數級的級別遞增的。

這里容量擴充的操作可以分為以下幾個步驟：

1. 申請一個新的、大小為當前容量兩倍的數組；

2. 將舊數組的Entry[] table中的鏈表重新計算hash值，然后重新均勻地放置到新的擴充數組中；

3.  釋放舊的數組；

由上述的容量擴充的步驟來看，一次容量擴充的代價非常大，所以在容量擴充時，擴充的比例為當前的一倍，這樣做是盡量減少容量擴充的次數。

為了提高HashMap的性能：

1.在使用HashMap的過程中，你比較明確它要容納多少Entry<Key,Value>，你應該在創建HashMap的時候直接指定它的容量；

2. 如果你確定HashMap的使用的過程中，大小會非常大，那么你應該控制好 加載因子的大小，盡量將它設置得大些。避免Entry[] table過大，而利用率覺很低。

/**
     * Rehashes the contents of this map into a new array with a
     * larger capacity.  This method is called automatically when the
     * number of keys in this map reaches its threshold.
     *
     * If current capacity is MAXIMUM_CAPACITY, this method does not
     * resize the map, but sets threshold to Integer.MAX_VALUE.
     * This has the effect of preventing future calls.
     *
     * @param newCapacity the new capacity, MUST be a power of two;
     *        must be greater than current capacity unless current
     *        capacity is MAXIMUM_CAPACITY (in which case value
     *        is irrelevant).
     */
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }


        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

為什么JDK建議我們重寫Object.equals(Object obj)方法時，需要保證對象可以返回相同的hashcode值？

Java程序員都看過JDK的API文檔，該文檔關于Object.equals(Object obj)方法，有這樣的描述：

“注意：當此方法被重寫時，通常有必要重寫hashCode 方法，以維護hashCode 方法的常規協定，該協定聲明相等對象必須具有相等的哈希碼。”

有的人雖然知道這個協定，但是不一定真正知道為什么會有這一個要求，現在，就來看看原因吧。

再注意看一下上述的這個put()方法實現，當遍歷某個桶中的Entry<Key,Value>鏈表來查找Entry實例的過程中所使用的判斷條件：

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //5. 查找Entry<Key,Value>鏈表中是否已經有了以Key值為Key存儲的Entry<Key,Value>對象,
            //已經存在,則將Value值覆蓋到對應的Entry<Key,Value>對象節點上
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }

對于給定的Key,Value，判斷該Key是否與Entry鏈表中有某一個Entry對象的Key值相等使用的是(k==e.key)==key) || key.equals(k)，另外還有一個判斷條件：即Key經過hash函數轉換后的hash值和當前Entry對象的hash屬性值相等（該hash屬性值和Entry內的Key經過hash方法轉換后的hash值相等）。

上述的情況我們可以總結為；HashMap在確定Key是否在HashMap中存在的要求有兩個：

1. Key值是否相等；

2. hashcode是否相等；

所以我們在定義類時，如果重寫了equals()方法，但是hashcode卻沒有保證相等，就會導致當使用該類實例作為Key值放入HashMap中，會出現HashMap“工作異常”的問題，會出現你不希望的情況。下面讓我們通過一個例子來看看這個“工作異常”情況：

例子： 定義一個簡單Employee類，重寫equals方法，而沒有重寫hashCode()方法。然后使用該類創建兩個實例，放置到一個HashMap中：

package com.hash;


/**
 * 簡單Employee Bean，重寫equals方法,未重寫hashCode()方法
 * @author louluan
 */
public class Employee {

    private String employeeCode;
    private String name;

    public Employee(String employeeCode, String name) {
        this.employeeCode = employeeCode;
        this.name = name;
    }

    public String getEmployeeCode() {
        return employeeCode;
    }
    public String getName() {
        return name;
    }

    @Override
    public boolean equals(Object o)
    {
        if(o instanceof Employee)
        {
            Employee e = (Employee)o;
            if(this.employeeCode.equals(e.getEmployeeCode()) && name.equals(e.getName()))
            {
                return true;
            }
        }
        return false;
    }
}

package com.hash;
import java.util.HashMap;


public class Test {

    public static void main(String[] args) {
        Employee em1= new Employee("123","anndy");
        Employee em2= new Employee("123","anndy");
        boolean equals= em1.equals(em2);
        System.out.println("em1 equals em2 ? " +equals);

        HashMap map = new HashMap();
        map.put(em1, "test1");
        map.put(em2, "test2");
        System.out.println("map size:"+map.size());
    }
}
<em><u><span style="font-family:Courier New;color:#000000;background-color: rgb(240, 240, 240);">
</span></u></em>

運行結果：

em1 equals em2 ? true
map size:2

結果分析：

上述的例子中，我們使用了new Employee("123","anndy"); 語句創建了兩個完全一樣的對象em1,em2，對我們來說，它們就是相同的對象，然后，我們將這兩個我們認為相等的對象作為Key值放入HashMap中，我們想要的結果是：HashMap中的Entry<Key,Value>鍵值對數目應該就一個，并且Entry對象的Value值應該是由"test1" 替換成"test2",但是實際的結果是：HashMap的大小為2，即HashMap中有兩個Entry<Key,Value>鍵值對！！！

原因現在清晰了：因為em1和em2對象的hashCode()繼承自Object，它們返回兩個不同的值，即em1 和em2的hashcode值不相同。

從上面的這個例子可以看出：

我們重寫Object.equals(Object obj)方法時，需要保證對象可以返回相同的hashcode。否則，HashMap工作的時候會有不可控的異常情況出現。

 2. get() 方法的實現：

根據特定的Key值從HashMap中取Value的結果就比較簡單了：

get()方法-根據Key從HashMap中取Value

a.  獲取這個Key的hashcode值，根據此hashcode值決定應該從哪一個桶中查找；

b.  遍歷所在桶中的Entry<Key,Value>鏈表，查找其中是否已經有了以Key值為Key存儲的Entry<Key,Value>對象；

c1. 若已存在，定位到對應的Entry<Key,Value>,返回value；

c2. 若不存在，返回null；

具體算法如下：

/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *  返回key對應的Value值，如果HashMap中沒有，則返回null；
     *  支持Key為null情況
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    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;
    }

3.HashMap對Key為null情況的支持

HashMap允許Key以null的形式存取，Hashmap會將Key為null組成的Entry<null,Value>放置到table[0],即第一個桶中，在put()和get()操作時，會先對Key 為null的值特殊處理：

/**
     * Offloaded version of get() to look up null keys.  Null keys map
     * to index 0.  This null case is split out into separate methods
     * for the sake of performance in the two most commonly used
     * operations (get and put), but incorporated with conditionals in
     * others.
     * get ??????
     */
    private V getForNullKey() {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

/**
     * Key 為null,則將Entry<null,Value>放置到第一桶table[0]中
     */
    private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

4. 鍵值對Entry<Key,Value>的移除----remove(key)方法的實現

根據key值移除鍵值對的操作也比較簡單，內部關鍵的流程分為兩個：

1. 根據Key的hashcode 值和Key定位到Entry<key,Value> 對象在HashMap中的位置；

2. 由于Entry<Key,Value>是一個鏈表元素，之后便是鏈表刪除節點的操作了；

/**
     * Removes the mapping for the specified key from this map if present.
     *
     * @param  key key whose mapping is to be removed from the map
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }


    /**
     * Removes and returns the entry associated with the specified key
     * in the HashMap.  Returns null if the HashMap contains no mapping
     * for this key.
     */
    final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;


        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }


        return e;
    }

3、HashMap的特點總結：

1. HashMap是線程不安全的，如果想使用線程安全的,可以使用Hashtable；它提供的功能和Hashmap基本一致。HashMap實際上是一個Hashtable的輕量級實現；

2. 允許以Key為null的形式存儲<null,Value>鍵值對；

3. HashMap的查找效率非常高，因為它使用Hash表對進行查找，可直接定位到Key值所在的桶中；

4. 使用HashMap時，要注意HashMap容量和加載因子的關系，這將直接影響到HashMap的性能問題。加載因子過小，會提高HashMap的查找效率，但同時也消耗了大量的內存空間，加載因子過大，節省了空間，但是會導致HashMap的查找效率降低。