當我們享受著jdk帶來的便利時同樣承受它帶來的不幸惡果。通過分析Hashtable就知道,synchronized是針對整張Hash表的,即每次鎖住整張表讓線程獨占,安全的背後是巨大的浪費,而現在的解決方案----ConcurrentHashMap。
ConcurrentHashMap和Hashtable主要區別就是圍繞著鎖的粒度以及如何鎖。如圖 左邊便是Hashtable的實現方式---鎖整個hash表;而右邊則是ConcurrentHashMap的實現方式---鎖桶(或段)。ConcurrentHashMap將hash表分為16個桶(默認值),諸如get,put,remove等常用操作只鎖當前需要用到的桶。試想,原來只能一個線程進入,現在卻能同時16個寫線程進入(寫線程才需要鎖定,而讀線程幾乎不受限制,之後會提到),並發性的提升是顯而易見的。 接下來,讓我們看看ConcurrentHashMap中的幾個重要方法,心裡知道了實現機制後,使用起來就更加有底氣。 ConcurrentHashMap中主要實體類就是三個:ConcurrentHashMap(整個Hash表),Segment(桶),HashEntry(節點),對應上面的圖可以看出之間的關系。 get方法(請注意,這裡分析的方法都是針對桶的,因為ConcurrentHashMap的最大改進就是將粒度細化到了桶上),首先判斷了當前桶的數據個數是否為0,為0自然不可能get到什麼,只有返回null,這樣做避免了不必要的搜索,也用最小的代價避免出錯。然後得到頭節點(方法將在下面涉及)之後就是根據hash和key逐個判斷是否是指定的值,如果是並且值非空就說明找到了,直接返回;程序非常簡單;相對於之前的Hashtable,並發是不可避免的啊!public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; int h = spread(key.hashCode()); if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }
put操作一上來就鎖定了整個segment,這當然是為了並發的安全,修改數據是不能並發進行的,必須得有個判斷是否超限的語句以確保容量不足時能夠rehash,,原來segment裡面才是真正的hashtable,即每個segment是一個傳統意義上的hashtable,如上圖,從兩者的結構就可以看出區別,這裡就是找出需要的entry在table的哪一個位置,之後得到的entry就是這個鏈的第一個節點,如果e!=null,說明找到了,這是就要替換節點的值if(!onlyIfAbsent),否則,我們需要new一個entry,它的後繼是first,而讓tab[index]指向它,什麼意思呢?實際上就是將這個新entry插入到鏈頭,剩下的就非常容易理解了。
public V put(K key, V value) { return putVal(key, value, false); } /** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { V oldVal = null; synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }
remove操作非常類似put,但要注意一點區別,中間那個for循環是做什麼用的呢?從代碼來看,就是將定位之後的所有entry克隆並拼回前面去,但有必要嗎?每次刪除一個元素就要將那之前的元素克隆一遍?這點其實是由entry的不變性來決定的,仔細觀察entry定義,發現除了value,其他所有屬性都是用final來修飾的,這意味著在第一次設置了next域之後便不能再改變它,取而代之的是將它之前的節點全都克隆一次。
public V remove(Object key) { return replaceNode(key, null, null); } /** * Implementation for the four public remove/replace methods: * Replaces node value with v, conditional upon match of cv if * non-null. If resulting value is null, delete. */ final V replaceNode(Object key, V value, Object cv) { int hash = spread(key.hashCode()); for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0 || (f = tabAt(tab, i = (n - 1) & hash)) == null) break; else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { V oldVal = null; boolean validated = false; synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { validated = true; for (Node<K,V> e = f, pred = null;;) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { V ev = e.val; if (cv == null || cv == ev || (ev != null && cv.equals(ev))) { oldVal = ev; if (value != null) e.val = value; else if (pred != null) pred.next = e.next; else setTabAt(tab, i, e.next); } break; } pred = e; if ((e = e.next) == null) break; } } else if (f instanceof TreeBin) { validated = true; TreeBin<K,V> t = (TreeBin<K,V>)f; TreeNode<K,V> r, p; if ((r = t.root) != null && (p = r.findTreeNode(hash, key, null)) != null) { V pv = p.val; if (cv == null || cv == pv || (pv != null && cv.equals(pv))) { oldVal = pv; if (value != null) p.val = value; else if (t.removeTreeNode(p)) setTabAt(tab, i, untreeify(t.first)); } } } } } if (validated) { if (oldVal != null) { if (value == null) addCount(-1L, -1); return oldVal; } break; } } } return null; }