Java HashMap 核心源碼解讀

原文出處： geeklu

本篇對HashMap實現的源碼進行簡單的分析。 所使用的HashMap源碼的版本信息如下：

/*


@(#)HashMap.java 1.73 07/03/13
*
Copyright 2006 Sun Microsystems, Inc. All rights reserved.
SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*/</pre> 
一.概述 
在Java中每一個對象都有一個哈希碼，這個值可以通過hashCode()方法獲得。hashCode()的值和對象的equals方法息息相關，是兩個對象的值是否相等的依據，所以當我們覆蓋一個類的equals方法的時候也必須覆蓋hashCode方法。 
例如String的hashCode方法為： 
public int hashCode() {
int h = hash;
if (h == 0) {
int off = offset;
char val[] = value;
int len = count;

for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}</pre> 
可以看得出，一個字符串的哈希值為s[0]31n-1 + s[1]31n-2 + … + s[n-1]，是一個整數。也就是說所有的字符串可以通過hashCode()將其映射到整數的區間中，由于在java中整數的個數是有限的（四個字節有正負，第一位為符號位-231 ~ 231 -1），當s[0]31n-1 + s[1]31n-2 + … + s[n-1]足夠大的時候可能會溢出，導致其變成負值。從上面的情況我們可以看出兩個不同的字符串可能會被映射到同一個整數，發生沖突。因此java的開發人員選擇了31這個乘數因子，盡量使得各個字符串映射的結果在整個java的整數域內均勻分布。 

談完java對象的哈希碼，我們來看看今天的主角HashMap，HashMap可以看作是Java實現的哈希表。HashMap中存放的是key-value對，對應的類型為java.util.HashMap.Entry，所以在HashMap中數據都存放在一個Entry引用類型的數組table中。這里key是一個對象，為了把對象映射到table中的一個位置，我們可以通過求余法來，所以我們可以使用 [key的hashCode % table的長度]來計算位置（當然在實際操作的時候由于需要考慮table上的key的均勻分布可能需要對key的hashCode做一些處理）。 
二.源碼解析 
相關屬性 首先肯定是需要一個數組table，作為數據結構的骨干。 
transient Entry[] table;
 
這邊定義了一個Entry數組的引用。 繼續介紹幾個概念把 
capacity容量 是指數組table的長度

loadFactor 裝載因子，是實際存放量/capacity容量 的一個比值，在代碼中這個屬性是描述了裝載因子的最大值，默認大小為0.75

threshold（閾值）代表hashmap存放內容數量的一個臨界點，當存放量大于這個值的時候，就需要將table進行夸張，也就是新建一個兩倍大的數組，并將老的元素轉移過去。threshold = (int)(capacity * loadFactor); 
put方法詳解 
public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        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;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
 
在HashMap中我們的key可以為null，所以第一步就處理了key為null的情況。

當key為非null的時候，你也許會認為：恩，直接和table長度相除取模吧，但是這里沒有，而是又好像做了一次哈希，這是為什么呢？這個還得先看indexFor(hash, table.length)方法，這個方法是決定存放位置的 
static int indexFor(int h, int length) {
        return h & (length-1);
    }
 
明眼的都可以發現，因為在HashMap中table的長度為2n (我們把運算都換成二進制進行考慮)，所以h & (length-1)就等價于h%length，這也就是說，如果對原本的hashCode不做變換的話，其除去低length-1位后的部分不會對key在table中的位置產生任何影響，這樣只要保持低length-1位不變，不管高位如何都會沖突，所以就想辦法使得高位對其結果也產生影響，于是就對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);
    }
 
當找到key所對應的位置的時候，對對應位置的Entry的鏈表進行遍歷，如果以及存在key的話，就更新對應的value，并返回老的value。如果是新的key的話，就將其增加進去。modCount是用來記錄hashmap結構變化的次數的，這個在hashmap的fail-fast機制中需要使用（當某一個線程獲取了map的游標之后，另一個線程對map做了結構修改的操作，那么原先準備遍歷的線程會拋出異常）。addEntry的方法如下 
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }
 
get方法 
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;
    }
 
get方法其實就是將key以put時相同的方法算出在table的所在位置，然后對所在位置的鏈表進行遍歷，找到hash值和key都相等的Entry并將value返回。