摘要：當(dāng)哈希表中鍵值對(duì)的數(shù)量超過(guò)當(dāng)前容量和裝載因子的乘積后，哈希表重新散列也就是內(nèi)部的數(shù)據(jù)結(jié)構(gòu)重建了，并且哈希表的容量大約變?yōu)樵瓉?lái)的兩倍。下面的是根據(jù)哈希值得到元素在哈希表中的下標(biāo)。一般在哈希表中是用哈希值對(duì)表長(zhǎng)取模得到。

HashMap是Map接口下比較常用的一個(gè)類，我們都知道它存儲(chǔ)的是鍵值對(duì)(key-value)，可以高效地插入和刪除。這篇文章分析一下它內(nèi)部的實(shí)現(xiàn)，由于源碼比較長(zhǎng)，只看一些重要的。

首先，HashMap是基于哈希表存儲(chǔ)的。它內(nèi)部有一個(gè)數(shù)組，當(dāng)元素要存儲(chǔ)的時(shí)候，先計(jì)算其key的哈希值，根據(jù)哈希值找到元素在數(shù)組中對(duì)應(yīng)的下標(biāo)。如果這個(gè)位置沒(méi)有元素，就直接把當(dāng)前元素放進(jìn)去，如果有元素了(這里記為A)，就把當(dāng)前元素鏈接到元素A的前面，然后把當(dāng)前元素放入數(shù)組中。所以在Hashmap中，數(shù)組其實(shí)保存的是鏈表的首節(jié)點(diǎn)。下面是百度百科的一張圖：

如上圖，每個(gè)元素是一個(gè)Entry對(duì)象，在其中保存了元素的key和value，還有一個(gè)指針可用于指向下一個(gè)對(duì)象。所有哈希值相同的key(也就是沖突了)用鏈表把它們串起來(lái)，這是拉鏈法。

//默認(rèn)初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)裝載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//哈希表
transient Entry[] table;
//鍵值對(duì)的數(shù)量
transient int size;
//擴(kuò)容的閾值
int threshold;
//哈希數(shù)組的裝載因子
final float loadFactor;

在上面的變量中，capacity是指哈希表的長(zhǎng)度，也就是table的大小，默認(rèn)為16。裝載因子loadFactor是哈希表的“裝滿程度”，JDK的文檔是這樣說(shuō)的：

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

大體意思是：裝載因子是哈希表在擴(kuò)容之前能裝多滿的度量值。當(dāng)哈希表中“鍵值對(duì)”的數(shù)量超過(guò)當(dāng)前容量(capacity)和裝載因子的乘積后，哈希表重新散列(也就是內(nèi)部的數(shù)據(jù)結(jié)構(gòu)重建了)，并且哈希表的容量大約變?yōu)樵瓉?lái)的兩倍。

從上面的變量定義可以看出，默認(rèn)的裝載因子DEFAULT_LOAD_FACTOR 是0.75。這個(gè)值越大，空間利用率越高，但查詢速度(包括get和put)操作會(huì)變慢。明白了裝載因子之后，threshold也就能理解了，它其實(shí)等于容量*裝載因子。

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)  //計(jì)算出大于指定容量的最小的2的冪
        capacity <<= 1;

    this.loadFactor = loadFactor;
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];   //給哈希表分配空間
    useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    init();
}

構(gòu)造器有好幾個(gè)，最終都會(huì)調(diào)用上面的這個(gè)。它接受兩個(gè)參數(shù)，一個(gè)是初始容量，還有一個(gè)是裝載因子。剛開(kāi)始先判斷值合不合法，有問(wèn)題的話會(huì)拋出異常。重要的是下面的capacity的計(jì)算，它的邏輯是計(jì)算出大于initialCapacity的最小的2的冪。其實(shí)目的就是要讓容量能大于等于指定的初始容量，但這個(gè)值還得是2的指數(shù)倍，這是一個(gè)關(guān)鍵的問(wèn)題。這么做的原因主要是為了哈希值的映射。先來(lái)看一下HashMap中有關(guān)哈希的方法：

final int hash(Object k) {
    int h = 0;
    if (useAltHashing) {
        if (k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h = hashSeed;
    }
    h ^= k.hashCode();
    // 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);
}
static int indexFor(int h, int length) {
    return h & (length-1);
}

hash()方法重新計(jì)算了key的哈希值，用了比較復(fù)雜的位運(yùn)算，具體邏輯我也不清楚，反正肯定是比較好的方法，能減少?zèng)_突什么的。

下面的indexFor()是根據(jù)哈希值得到元素在哈希表中的下標(biāo)。一般在哈希表中是用哈希值對(duì)表長(zhǎng)取模得到。當(dāng)length(也就是capacity)為2的冪時(shí)，h & (length-1)是同樣的效果。并且，2的冪一定是偶數(shù)，那么減1之后就是奇數(shù)，二進(jìn)制的最后一位一定是1。那么h & (length-1)的最后一位可能是1，也可能是0，可以均勻地散列。如果length是奇數(shù)，那么length-1就是偶數(shù)，最后一位是0。此時(shí)h & (length-1)的最后一位只可能是0，所有得到的下標(biāo)都是偶數(shù)，那么哈希表就浪費(fèi)了一半的空間。所以HashMap中的容量(capacity)一定要是2的冪?？梢钥吹侥J(rèn)的DEFAULT_INITIAL_CAPACITY=16和MAXIMUM_CAPACITY=1<<30都是這樣的。

HashMap中的鍵值對(duì)被封裝成Entry對(duì)象，這是HashMap中的一個(gè)內(nèi)部類，看一下它的實(shí)現(xiàn)：

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

    Entry(int h, K k, V v, Entry n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry)o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
            Object v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                return true;
        }
        return false;
    }

    public final int hashCode() {
        return (key==null   ? 0 : key.hashCode()) ^
               (value==null ? 0 : value.hashCode());
    }

    public final String toString() {
        return getKey() + "=" + getValue();
    }
    void recordAccess(HashMap m) {
    }
    void recordRemoval(HashMap m) {
    }
}

這個(gè)類的實(shí)現(xiàn)還是簡(jiǎn)潔易懂的。提供了getKey()、getValue()等方法供調(diào)用，判斷相等是要求key和value均相等。

先put了才能get，所以先看一下put()方法：

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry 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;
}

在這個(gè)方法中，先判斷key是否為null，是的話調(diào)用putForNullKey()方法，這說(shuō)明HashMap允許key為null(其實(shí)value可以)。如果不是null，計(jì)算哈希值并且得到在表中的下標(biāo)。然后到對(duì)應(yīng)的鏈表中查詢是否已經(jīng)存在相同的key，如果已經(jīng)存在就直接更新值(value)。否則，調(diào)用addEntry()方法進(jìn)行插入。

看一下putForNullKey()方法：

private V putForNullKey(V value) {
    for (Entry 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;
}

可以看到，key為null時(shí)直接在下標(biāo)0處插入，同樣是存在就更新值，否則調(diào)用addEntry()插入。

下面是addEntry()方法的實(shí)現(xiàn)：

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

首先判斷是否要擴(kuò)容(擴(kuò)容會(huì)重新計(jì)算下標(biāo)值，并且復(fù)制元素)，然后計(jì)算數(shù)組下標(biāo)，最后在createEntry()中使用頭插法插入元素。

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
    for (Entry e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}
final Entry getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key);
    for (Entry e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

這個(gè)比put()簡(jiǎn)單一些，同樣要判斷key是不是null，然后就是鏈表的遍歷查詢。

HashMap的基本實(shí)現(xiàn)就如上面所分析的，最后做下總結(jié)：

HashMap內(nèi)部用Entry對(duì)象保存鍵值對(duì)，基于哈希表存儲(chǔ)，用拉鏈法解決沖突。

HashMap的默認(rèn)容量大小為16，默認(rèn)裝載因子為0.75?？梢灾付ㄈ萘看笮。萘孔罱K一定會(huì)被設(shè)置為2的冪，這是為了均勻地散列。

HashMap的key和value都可以是null，當(dāng)然只能有一個(gè)key是null，value可以有多個(gè)。

HashMap的鍵值對(duì)數(shù)量超過(guò)容量*裝載因子時(shí)會(huì)擴(kuò)容，擴(kuò)容后的容量大約是原來(lái)的兩倍。擴(kuò)容會(huì)重新散列，所以元素的位置可能發(fā)生會(huì)變化，而且這是一個(gè)耗時(shí)操作。

HashMap是線程不安全的。