原文地址：http://ajax-xu.iteye.com/blog/1104649
ConcurrentHashMap是Java 5中支持高并發(fā)、高吞吐量的線程安全HashMap實現。在這之前我對ConcurrentHashMap只有一些膚淺的理解，僅知道它采用了多個鎖，大概也足夠了。但是在經過一次慘痛的面試經歷之后，我覺得必須深入研究它的實現。面試中被問到讀是否要加鎖，因為讀寫會發(fā)生沖突，我說必須要加鎖，我和面試官也因此發(fā)生了沖突，結果可想而知。還是閑話少說，通過仔細閱讀源代碼，現在總算理解ConcurrentHashMap實現機制了，其實現之精巧，令人嘆服，與大家共享之。?
Java代碼??
final?Segment<K,V>[]?segments;???? ???
Java代碼??
static?final?class?HashEntry<K,V>?{???? ????final?K?key;???? ????final?int?hash;???? ????volatile?V?value;???? ????final?HashEntry<K,V>?next;???? }????
Java代碼??
private?static?int?hash(int?h)?{???? ???? ???? ????h?+=?(h?<<??15)?^?0xffffcd7d;???? ????h?^=?(h?>>>?10);???? ????h?+=?(h?<<???3);???? ????h?^=?(h?>>>??6);???? ????h?+=?(h?<<???2)?+?(h?<<?14);???? ????return?h?^?(h?>>>?16);???? }???? ???
Java代碼??
final?Segment<K,V>?segmentFor(int?hash)?{???? ????return?segments[(hash?>>>?segmentShift)?&?segmentMask];???? }???? ???
Java代碼??
public?class?ConcurrentHashMap<K,?V>?extends?AbstractMap<K,?V>???? ????????implements?ConcurrentMap<K,?V>,?Serializable?{???? ???? ????final?int?segmentMask;???? ???? ???? ????final?int?segmentShift;???? ???? ???? ????final?Segment<K,V>[]?segments;???? }????
Java代碼??
???static?final?class?Segment<K,V>?extends?ReentrantLock?implements?Serializable?{???? private?static?final?long?serialVersionUID?=?2249069246763182397L;???? ???????? ????????transient?volatile?int?count;???? ???? ???????? ????????transient?int?modCount;???? ???? ???????? ????????transient?int?threshold;???? ???? ???????? ????????transient?volatile?HashEntry<K,V>[]?table;???? ???? ???????? ????????final?float?loadFactor;???? }???
Java代碼??
public?V?remove(Object?key)?{???? ?hash?=?hash(key.hashCode());???? ????return?segmentFor(hash).remove(key,?hash,?null);???? }????
Java代碼??
V?remove(Object?key,?int?hash,?Object?value)?{???? ????lock();???? ????try?{???? ????????int?c?=?count?-?1;???? ????????HashEntry<K,V>[]?tab?=?table;???? ????????int?index?=?hash?&?(tab.length?-?1);???? ????????HashEntry<K,V>?first?=?tab[index];???? ????????HashEntry<K,V>?e?=?first;???? ????????while?(e?!=?null?&&?(e.hash?!=?hash?||?!key.equals(e.key)))???? ????????????e?=?e.next;???? ???? ????????V?oldValue?=?null;???? ????????if?(e?!=?null)?{???? ????????????V?v?=?e.value;???? ????????????if?(value?==?null?||?value.equals(v))?{???? ????????????????oldValue?=?v;???? ???????????????? ???????????????? ???????????????? ????????????????++modCount;???? ????????????????HashEntry<K,V>?newFirst?=?e.next;???? ????????????????for?(HashEntry<K,V>?p?=?first;?p?!=?e;?p?=?p.next)???? ????????????????????newFirst?=?new?HashEntry<K,V>(p.key,?p.hash,???? ??????????????????????????????????????????????????newFirst,?p.value);???? ????????????????tab[index]?=?newFirst;???? ????????????????count?=?c;? ????????????}???? ????????}???? ????????return?oldValue;???? ????}?finally?{???? ????????unlock();???? ????}???? }???
Java代碼??
V?put(K?key,?int?hash,?V?value,?boolean?onlyIfAbsent)?{???? ????lock();???? ????try?{???? ????????int?c?=?count;???? ????????if?(c++?>?threshold)? ????????????rehash();???? ????????HashEntry<K,V>[]?tab?=?table;???? ????????int?index?=?hash?&?(tab.length?-?1);???? ????????HashEntry<K,V>?first?=?tab[index];???? ????????HashEntry<K,V>?e?=?first;???? ????????while?(e?!=?null?&&?(e.hash?!=?hash?||?!key.equals(e.key)))???? ????????????e?=?e.next;???? ???? ????????V?oldValue;???? ????????if?(e?!=?null)?{???? ????????????oldValue?=?e.value;???? ????????????if?(!onlyIfAbsent)???? ????????????????e.value?=?value;???? ????????}???? ????????else?{???? ????????????oldValue?=?null;???? ????????????++modCount;???? ????????????tab[index]?=?new?HashEntry<K,V>(key,?hash,?first,?value);???? ????????????count?=?c;? ????????}???? ????????return?oldValue;???? ????}?finally?{???? ????????unlock();???? ????}???? }?? ??
Java代碼??
V?get(Object?key,?int?hash)?{???? ????if?(count?!=?0)?{? ????????HashEntry<K,V>?e?=?getFirst(hash);???? ????????while?(e?!=?null)?{???? ????????????if?(e.hash?==?hash?&&?key.equals(e.key))?{???? ????????????????V?v?=?e.value;???? ????????????????if?(v?!=?null)???? ????????????????????return?v;???? ????????????????return?readValueUnderLock(e);? ????????????}???? ????????????e?=?e.next;???? ????????}???? ????}???? ????return?null;???? }???
Java代碼??
V?readValueUnderLock(HashEntry<K,V>?e)?{???? ????lock();???? ????try?{???? ????????return?e.value;???? ????}?finally?{???? ????????unlock();???? ????}???? }???? ???
Java代碼??
boolean?containsKey(Object?key,?int?hash)?{???? ????if?(count?!=?0)?{? ????????HashEntry<K,V>?e?=?getFirst(hash);???? ????????while?(e?!=?null)?{???? ????????????if?(e.hash?==?hash?&&?key.equals(e.key))???? ????????????????return?true;???? ????????????e?=?e.next;???? ????????}???? ????}???? ????return?false;???? }????
Java代碼??
public?int?size()?{???? ????final?Segment<K,V>[]?segments?=?this.segments;???? ????long?sum?=?0;???? ????long?check?=?0;???? ????int[]?mc?=?new?int[segments.length];???? ???? ???? ????for?(int?k?=?0;?k?<?RETRIES_BEFORE_LOCK;?++k)?{???? ????????check?=?0;???? ????????sum?=?0;???? ????????int?mcsum?=?0;???? ????????for?(int?i?=?0;?i?<?segments.length;?++i)?{???? ????????????sum?+=?segments[i].count;???? ????????????mcsum?+=?mc[i]?=?segments[i].modCount;???? ????????}???? ????????if?(mcsum?!=?0)?{???? ????????????for?(int?i?=?0;?i?<?segments.length;?++i)?{???? ????????????????check?+=?segments[i].count;???? ????????????????if?(mc[i]?!=?segments[i].modCount)?{???? ????????????????????check?=?-1;? ????????????????????break;???? ????????????????}???? ????????????}???? ????????}???? ????????if?(check?==?sum)???? ????????????break;???? ????}???? ????if?(check?!=?sum)?{? ????????sum?=?0;???? ????????for?(int?i?=?0;?i?<?segments.length;?++i)???? ????????????segments[i].lock();???? ????????for?(int?i?=?0;?i?<?segments.length;?++i)???? ????????????sum?+=?segments[i].count;???? ????????for?(int?i?=?0;?i?<?segments.length;?++i)???? ????????????segments[i].unlock();???? ????}???? ????if?(sum?>?Integer.MAX_VALUE)???? ????????return?Integer.MAX_VALUE;???? ????else???? ????????return?(int)sum;???? }???? ???
Java代碼??
public?boolean?containsValue(Object?value)?{???? ????if?(value?==?null)???? ????????throw?new?NullPointerException();???? ???? ???? ???? ????final?Segment<K,V>[]?segments?=?this.segments;???? ????int[]?mc?=?new?int[segments.length];???? ???? ???? ????for?(int?k?=?0;?k?<?RETRIES_BEFORE_LOCK;?++k)?{???? ????????int?sum?=?0;???? ????????int?mcsum?=?0;???? ????????for?(int?i?=?0;?i?<?segments.length;?++i)?{???? ????????????int?c?=?segments[i].count;???? ????????????mcsum?+=?mc[i]?=?segments[i].modCount;???? ????????????if?(segments[i].containsValue(value))???? ????????????????return?true;???? ????????}???? ????????boolean?cleanSweep?=?true;???? ????????if?(mcsum?!=?0)?{???? ????????????for?(int?i?=?0;?i?<?segments.length;?++i)?{???? ????????????????int?c?=?segments[i].count;???? ????????????????if?(mc[i]?!=?segments[i].modCount)?{???? ????????????????????cleanSweep?=?false;???? ????????????????????break;???? ????????????????}???? ????????????}???? ????????}???? ????????if?(cleanSweep)???? ????????????return?false;???? ????}???? ???? ????for?(int?i?=?0;?i?<?segments.length;?++i)???? ????????segments[i].lock();???? ????boolean?found?=?false;???? ????try?{???? ????????for?(int?i?=?0;?i?<?segments.length;?++i)?{???? ????????????if?(segments[i].containsValue(value))?{???? ????????????????found?=?true;???? ????????????????break;???? ????????????}???? ????????}???? ????}?finally?{???? ????????for?(int?i?=?0;?i?<?segments.length;?++i)???? ????????????segments[i].unlock();???? ????}???? ????return?found;???? }????
Java代碼??
abstract?class?Hash_Iterator{???? ????int?nextSegmentIndex;???? ????int?nextTableIndex;???? ????HashEntry<K,V>[]?currentTable;???? ????HashEntry<K,?V>?nextEntry;???? ????HashEntry<K,?V>?lastReturned;???? }???? ???
Java代碼??
final?void?advance()?{???? ????if?(nextEntry?!=?null?&&?(nextEntry?=?nextEntry.next)?!=?null)???? ????????return;???? ???? ????while?(nextTableIndex?>=?0)?{???? ????????if?(?(nextEntry?=?currentTable[nextTableIndex--])?!=?null)???? ????????????return;???? ????}???? ???? ????while?(nextSegmentIndex?>=?0)?{???? ????????Segment<K,V>?seg?=?segments[nextSegmentIndex--];???? ????????if?(seg.count?!=?0)?{???? ????????????currentTable?=?seg.table;???? ????????????for?(int?j?=?currentTable.length?-?1;?j?>=?0;?--j)?{???? ????????????????if?(?(nextEntry?=?currentTable[j])?!=?null)?{???? ????????????????????nextTableIndex?=?j?-?1;???? ????????????????????return;???? ????????????????}???? ????????????}???? ????????}???? ????}???? }????
http://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/
轉載于:https://www.cnblogs.com/davidwang456/p/4666238.html
《新程序員》：云原生和全面數字化實踐 50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀
總結
以上是生活随笔 為你收集整理的ConcurrentHashMap实现原理--转载 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
