Java中的幾個HashMap

一、HashMap，即java.util.HashMap

標准鏈地址法實現。這個不用多解析，下圖十分明了。（圖片來自網絡）

二、Collections.synchronizedMap() 函數返回的線程安全的HashMap

這個的實現比較簡單。

代碼中有：

1. private final Map<K,V> m; // Backing Map
2. final Object mutex;// Object on which to synchronize

基本所有的方法都加上了synchronized(mutex)。

但是這個HashMap不能隨便地進行迭代，因為它只是簡單包裝了HashMap，而回看HashMap的實現，我們可以發現，對於沖突的key，形成一個鏈表，明顯如果有一個線程在歷遍HashMap，另一個線程在做刪除操作，則很有可能出錯。

因此，JDK中給出以下代碼：

1. Map m = Collections.synchronizedMap(new HashMap());
2. ...
3. Set s = m.keySet(); // Needn't be in synchronized block
4. ...
5. synchronized(m) { // Synchronizing on m, not s!
6. Iterator i = s.iterator(); // Must be in synchronized block
7. while (i.hasNext())
8. foo(i.next());
9. }

三、ConcurrentHashMap

對於HashMap，最主要的是以下四種的操作：

1. public V get(Object key)
2. public V put(K key, V value)
3. public V remove(Object key)
4. 迭代

在多線程環境下，get，put，remove都是比較容易實現的（如果不考慮效率，簡單加鎖即可），迭代的操作才是真正的難點。

從Collections.synchronizedMap()的迭代來看，它並不能做到對客戶代碼透明，有點蛋疼。

下面簡單分析ConcurrentHashMap的實現，相當精巧。

默認一個ConcurrentHashMap中有16個子HashMap，所以相當於一個二級哈希。對於所有的操作都是先定位到子HashMap，再作相應的操作。

對於：

public V get(Object key)

先得到 key所在的table，再像HashMap一樣get
中間並不加鎖

public V put(K key, V value)

先得到所屬的table，加鎖
判斷table是否要擴容
如果table要擴容，則產生newTable
hash值相同的slot整體移到newTable
hash值不同的slot，把oldTable中的所有Entry都復制到newTable中
因為有可能其它線程在歷遍這個table，所以不能把原來的鏈表拆斷

public V remove(Object key)

remove操作，如下圖，要刪除Entry3，則先復制Entry1為Entry1*，Entry1*指向Entry4，再復制Entry2為Entry2*，Entry2*指向Entry1*，最終形成一個兩叉的鏈表。原本的Entry1，Entry2，Entry3會被GC自動回收。

迭代操作：

ConcurrentHashMap的歷遍是從後向前歷遍的，因為如果有另一個線程B在執行clear操作時，會把table中的所有slot都置為null，這個操作是從前向後執行
如果線程A在歷遍Map時也是從前向後，則有可能會出現追趕現象。

以下代碼：

1. HashMap<Integer, String> m1 = new HashMap();
2. m1.put(1, "001");
3. m1.put(2, "002");
4. for(Entry<Integer, String> entry : m1.entrySet()){
5. System.out.println("key:" + entry.getKey());
6. }

HashMap輸出的是 key:1 key:2
ConcurrentHashMap輸出的是key:2 key:1

總結：Java中的類庫實在太多了，HashMap還有很多，有空再補充。