xylz,imxylz

本來想比較全面和深入的談談ConcurrentHashMap的，發(fā)現(xiàn)網(wǎng)上有很多對HashMap和ConcurrentHashMap分析的文章，因此本小節(jié)盡可能的分析其中的細節(jié)，少一點理論的東西，多談談內部設計的原理和思想。

要談ConcurrentHashMap的構造，就不得不談HashMap的構造，因此先從HashMap開始簡單介紹。

HashMap原理

我們從頭開始設想。要將對象存放在一起，如何設計這個容器。目前只有兩條路可以走，一種是采用分格技術，每一個對象存放于一個格子中，這樣通過對格子的編號就能取到或者遍歷對象；另一種技術就是采用串聯(lián)的方式，將各個對象串聯(lián)起來，這需要各個對象至少帶有下一個對象的索引（或者指針）。顯然第一種就是數(shù)組的概念，第二種就是鏈表的概念。所有的容器的實現(xiàn)其實都是基于這兩種方式的，不管是數(shù)組還是鏈表，或者二者俱有。HashMap采用的就是數(shù)組的方式。

有了存取對象的容器后還需要以下兩個條件才能完成Map所需要的條件。

• 能夠快速定位元素：Map的需求就是能夠根據(jù)一個查詢條件快速得到需要的結果，所以這個過程需要的就是盡可能的快。
• 能夠自動擴充容量：顯然對于容器而然，不需要人工的去控制容器的容量是最好的，這樣對于外部使用者來說越少知道底部細節(jié)越好，不僅使用方便，也越安全。

首先條件1，快速定位元素。快速定位元素屬于算法和數(shù)據(jù)結構的范疇，通常情況下哈希（Hash）算法是一種簡單可行的算法。所謂哈希算法，是將任意長度的二進制值映射為固定長度的較小二進制值。常見的MD2,MD4,MD5，SHA-1等都屬于Hash算法的范疇。具體的算法原理和介紹可以參考相應的算法和數(shù)據(jù)結構的書籍，但是這里特別提醒一句，由于將一個較大的集合映射到一個較小的集合上，所以必然就存在多個元素映射到同一個元素上的結果，這個叫“碰撞”，后面會用到此知識，暫且不表。

條件2，如果滿足了條件1，一個元素映射到了某個位置，現(xiàn)在一旦擴充了容量，也就意味著元素映射的位置需要變化。因為對于Hash算法來說，調整了映射的小集合，那么原來映射的路徑肯定就不復存在，那么就需要對現(xiàn)有重新計算映射路徑，也就是所謂的rehash過程。

好了有了上面的理論知識后來看HashMap是如何實現(xiàn)的。

在HashMap中首先由一個對象數(shù)組table是不可避免的，修飾符transient只是表示序列號的時候不被存儲而已。size描述的是Map中元素的大小，threshold描述的是達到指定元素個數(shù)后需要擴容，loadFactor是擴容因子(loadFactor>0)，也就是計算threshold的。那么元素的容量就是table.length，也就是數(shù)組的大小。換句話說，如果存取的元素大小達到了整個容量(table.length)的loadFactor倍（也就是table.length*loadFactor個），那么就需要擴充容量了。在HashMap中每次擴容就是將擴大數(shù)組的一倍，使數(shù)組大小為原來的兩倍。

然后接下來看如何將一個元素映射到數(shù)組table中。顯然要映射的key是一個無盡的超大集合，而table是一個較小的有限集合，那么一種方式就是將key編碼后的hashCode值取模映射到table上，這樣看起來不錯。但是在Java中采用了一種更高效的辦法。由于與(&)是比取模(%)更高效的操作，因此Java中采用hash值與數(shù)組大小-1后取與來確定數(shù)組索引的。為什么這樣做是更有效的？參考資料7對這一塊進行非常詳細的分析，這篇文章的作者非常認真，也非常仔細的分析了里面包含的思想。

清單1 indexFor片段

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

前面說明，既然是大集合映射到小集合上，那么就必然存在“碰撞”，也就是不同的key映射到了相同的元素上。那么HashMap是怎么解決這個問題的？

在HashMap中采用了下面方式，解決了此問題。

1. 同一個索引的數(shù)組元素組成一個鏈表，查找允許時循環(huán)鏈表找到需要的元素。
2. 盡可能的將元素均勻的分布在數(shù)組上。

對于問題1，HashMap采用了上圖的一種數(shù)據(jù)結構。table中每一個元素是一個Map.Entry，其中Entry包含了四個數(shù)據(jù)，key,value,hash,next。key和value是存儲的數(shù)據(jù)；hash是元素key的Hash后的表現(xiàn)形式（最終要映射到數(shù)組上），這里鏈表上所有元素的hash經過清單1 的indexFor后將得到相同的數(shù)組索引；next是指向下一個元素的索引，同一個鏈表上的元素就是通過next串聯(lián)起來的。

再來看問題2 盡可能的將元素均勻的分布在數(shù)組上這個問題是怎么解決的。首先清單2 是將key的hashCode經過一系列的變換，使之更符合小數(shù)據(jù)集合的散列模型。

清單2 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);
}

至于清單2 為什么這樣散列我沒有找到依據(jù)，也沒有什么好的參考資料。參考資料1 分析了此過程，認為是一種比較有效的方式，有興趣的可以研究下。

第二點就是在清單1 的描述中，盡可能的與數(shù)組的長度減1的數(shù)與操作，使之分布均勻。這在參考資料7 中有介紹。

第三點就是構造數(shù)組時數(shù)組的長度是2的倍數(shù)。清單3 反映了這個過程。為什么要是2的倍數(shù)？在參考資料7 中分析說是使元素盡可能的分布均勻。

清單3 HashMap 構造數(shù)組

// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
    capacity <<= 1;

this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];

另外loadFactor的默認值0.75和capacity的默認值16是經過大量的統(tǒng)計分析得出的，很久以前我見過相關的數(shù)據(jù)分析，現(xiàn)在找不到了，有興趣的可以查詢相關資料。這里不再敘述了。

有了上述原理后再來分析HashMap的各種方法就不是什么問題的。

清單4 HashMap的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;
}

清單4 描述的是HashMap的get操作，在這個操作中首先判斷key是否為空，因為為空的話總是映射到table的第0個元素上（可以看上面的清單2和清單1）。然后就需要查找table的索引。一旦找到對應的Map.Entry元素后就開始遍歷此鏈表。由于不同的hash可能映射到同一個table[index]上，而相同的key卻同時映射到相同的hash上，所以一個key和Entry對應的條件就是hash(key)==e.hash 并且key.equals(e.key)。從這里我們看到，Object.hashCode()只是為了將相同的元素映射到相同的鏈表上（Map.Entry)，而Object.equals()才是比較兩個元素是否相同的關鍵！這就是為什么總是成對覆蓋hashCode()和equals()的原因。

清單5 HashMap的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;
}
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);
}

清單5 描述的是HashMap的put操作。對比get操作，可以發(fā)現(xiàn)，put實際上是先查找，一旦找到key對應的Entry就直接修改Entry的value值，否則就增加一個元素。增加的元素是在鏈表的頭部，也就是占據(jù)table中的元素，如果table中對應索引原來有元素的話就將整個鏈表添加到新增加的元素的后面。也就是說新增加的元素再次查找的話是優(yōu)于在它之前添加的同一個鏈表上的元素。這里涉及到就是擴容，也就是一旦元素的個數(shù)達到了擴容因子規(guī)定的數(shù)量(threhold=table.length*loadFactor)，就將數(shù)組擴大一倍。

清單6 HashMap擴容過程

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);
}

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);
        }
    }
}

清單6 描述的是HashMap擴容的過程。可以看到擴充過程會導致元素數(shù)據(jù)的所有元素進行重新hash計算，這個過程也叫rehash。顯然這是一個非常耗時的過程，否則擴容都會導致所有元素重新計算hash。因此盡可能的選擇合適的初始化大小是有效提高HashMap效率的關鍵。太大了會導致過多的浪費空間，太小了就可能會導致繁重的rehash過程。在這個過程中l(wèi)oadFactor也可以考慮。

舉個例子來說，如果要存儲1000個元素，采用默認擴容因子0.75，那么1024顯然是不夠的，因為1000>0.75*1024了，所以選擇2048是必須的，顯然浪費了1048個空間。如果確定最多只有1000個元素，那么擴容因子為1，那么1024是不錯的選擇。另外需要強調的一點是擴容因此越大，從統(tǒng)計學角度講意味著鏈表的長度就也大，也就是在查找元素的時候就需要更多次的循環(huán)。所以凡事必然是一個平衡的過程。

這里可能有人要問題，一旦我將Map的容量擴大后（也就是數(shù)組的大小），這個容量還能減小么？比如說剛開始Map中可能有10000個元素，運行一旦時間以后Map的大小永遠不會超過10個，那么Map的容量能減小到10個或者16個么？答案就是不能，這個capacity一旦擴大后就不能減小了，只能通過構造一個新的Map來控制capacity了。

HashMap的幾個內部迭代器也是非常重要的，這里限于篇幅就不再展開了，有興趣的可以自己研究下。

Hashtable的原理和HashMap的原理幾乎一樣，所以就不討論了。另外LinkedHashMap是在Map.Entry的基礎上增加了before/after兩個雙向索引，用來將所有Map.Entry串聯(lián)起來，這樣就可以遍歷或者做LRU Cache等。這里也不再展開討論了。

memcached 內部數(shù)據(jù)結構就是采用了HashMap類似的思想來實現(xiàn)的，有興趣的可以參考資料8,9，10。

為了不使這篇文章過長，因此將ConcurrentHashMap的原理放到下篇講。需要說明的是，盡管ConcurrentHashMap與HashMap的名稱有些淵源，而且實現(xiàn)原理有些相似，但是為了更好的支持并發(fā)，ConcurrentHashMap在內部也有一些比較大的調整，這個在下篇會具體介紹。

參考資料：

1. HashMap hash方法分析
2. 通過分析 JDK 源代碼研究 Hash 存儲機制
3. Java 理論與實踐: 哈希
4. Java 理論與實踐: 構建一個更好的 HashMap
5. jdk1.6 ConcurrentHashMap
6. ConcurrentHashMap之實現(xiàn)細節(jié)
7. 深入理解HashMap
8. memcached-數(shù)據(jù)結構
9. memcached存儲管理 數(shù)據(jù)結構
10. memcached