ConcurrentHashMap （jdk1.7）源碼學習
一.介紹
1.Segment(分段鎖)
1.1 Segment
- 容器里有多把鎖，每一把鎖用於鎖容器其中一部分數據，那麼當多執行緒訪問容器里不同數據段的數據時，執行緒間就不會存在鎖競爭，從而可以有效的提高並發訪問效率，這就是ConcurrentHashMap所使用的鎖分段技術
- 分段鎖其實是一種鎖的設計，並不是具體的一種鎖，對於ConcurrentHashMap而言，其並發的實現就是通過分段鎖的形式來實現高效的並發操作。
- Segment 類繼承於 ReentrantLock 類
-
如圖，ConcurrentHashMap定位一個元素的過程需要進行兩次Hash操作。
第一次Hash定位到Segment，第二次Hash定位到元素所在的鏈表的頭部-
壞處
這一種結構的帶來的副作用是Hash的過程要比普通的HashMap要
-
好處
寫操作的時候可以只對元素所在的Segment進行加鎖即可，不會影響到其他的Segment，這樣，在最理想的情況下，ConcurrentHashMap可以最高同時支援Segment數量大小的寫操作（剛好這些寫操作都非常平均地分布在所有的Segment上）。
-
-
註：
- 當需要put元素的時候,並不是對整個hashmap進行加鎖,而是先通過hashcode來知道他要放哪一個分段中,然後對分段加鎖,所以當多執行緒put的時候,只要不是放在一個分段這種,就實現了真正的並行插入
-
但是，在統計size的時候，可就是獲取hashmap全局資訊的時候，就可能需要獲取所有的分段鎖才能統計。
- 其中並發級別控制了Segment的個數，在一個ConcurrentHashMap創建後Segment的個數是不能變的，擴容過程過改變的是每個Segment的大小。
1.2 ReentrantLock
-
lock拿不到鎖會一直等待。tryLock是去嘗試，拿不到就返回false，拿到返回true。
tryLock是可以被打斷的，被中斷 的，lock是不可以。
2.數據結構
在JDK1.7版本中，ConcurrentHashMap的數據結構是由一個Segment數組和多個HashEntry組成，如1.中圖所示
3.CocurrentHashMap和HashMap異同
3.1 相同點：
- 都實現了 Map 介面，繼承了 AbstractMap 抽象類
- jdk1.7都是數組 + 鏈表 ，1.8變成了數組 + 鏈表 + 紅黑樹
3.2 不同點
- HashMap不支援並發操作，沒有同步方法
4.CocurrentHashMap和HashTable的對比
-
Hashtable它把所有方法都加上
synchronized關鍵字來實現執行緒安全。所有的方法都同步這樣造成多個執行緒訪問效率特別低。 -
HashTable的鎖加在整個Hash表上，而ConcurrentHashMap將鎖加在segment上（每個段上）
二.源碼部分
1.基本屬性
AbstractMap是 Map 介面的的實現類之一，也是 HashMap, TreeMap, ConcurrentHashMap 等類的父類。
ConcurrentMap它是一個介面，是一個能夠支援並發訪問的java.util.map集合
Serializable:一個對象序列化的介面，一個類只有實現了Serializable介面，它的對象才能被序列化
1.1常用常量
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
implements ConcurrentMap<K, V>, Serializable {
//serialVersionUID 用來表明實現序列化類的不同版本間的兼容性
private static final long serialVersionUID = 7249069246763182397L;
/**
* The default initial capacity for this table,該表的默認初始容量
* used when not otherwise specified in a constructor.在構造函數中未指定時使用
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* The default load factor for this table, used when not otherwise specified in a constructor.
* 該表的默認載入因子，在構造函數中未指定時使用。
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The default concurrency level for this table, used when not otherwise specified in a constructor.
* 此表的默認並發級別，在構造函數中未指定時使用。
*/
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
/**
* The maximum capacity, used if a higher value is implicitly specified by either of the constructors with arguments. MUST
* be a power of two <= 1<<30 to ensure that entries are indexable
* using ints.
* 最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The minimum capacity for per-segment tables. Must be a power
* of two, at least two to avoid immediate resizing on next use
* after lazy construction.
* 每個段表的最小容量。必須是2的冪，至少為2，以避免在延遲構造後再次使用時立即調整大小。
*/
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
/**
* The maximum number of segments to allow; used to bound
* constructor arguments. Must be power of two less than 1 << 24.
* 允許的最大段數;用於綁定構造函數參數。
*/
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
/**
* Number of unsynchronized retries in size and containsValue
* methods before resorting to locking. This is used to avoid
* unbounded retries if tables undergo continuous modification
* which would make it impossible to obtain an accurate result.
* 在使用鎖定之前，在size和containsValue方法上的未同步重試次數。如果表經歷了連續的修改，從而無法獲得準確的結果，這可以用來避免無邊界重試。
* 在size方法和containsValue方法，會優先採用樂觀的方式不加鎖，直到重試次數達到2，才會對所有Segment加鎖
* 這個值的設定，是為了避免無限次的重試。後邊size方法會詳講怎麼實現樂觀機制的。
*/
static final int RETRIES_BEFORE_LOCK = 2;
/**
* Mask value for indexing into segments. The upper bits of a key's hash code are used to choose the segment.
* 用於索引段的掩碼值，用於根據元素的hash值定位所在的 Segment 下標
*/
final int segmentMask;
/**
* Shift value for indexing within segments.
* 在段內索引的移位值
*/
final int segmentShift;
/**
* The segments, each of which is a specialized hash table.
* Segment 組成的數組，每一個 Segment 都可以看做是一個特殊的 HashMap
*/
final Segment<K,V>[] segments;
1.2內部類
/**
* ConcurrentHashMap list entry. Note that this is never exported out as a user-visible Map.Entry.
* ConcurrentHashMap列表條目。注意，這永遠不會導出為用戶可見的Map.Entry。
* HashEntry，存在於每個Segment中，它就類似於HashMap中的Node，用於存儲鍵值對的具體數據和維護單向鏈表的關係
*/
static final class HashEntry<K,V> {
final int hash;
final K key;
//value和next都用 volatile 修飾，用於保證記憶體可見性和禁止指令重排序
volatile V value;
volatile HashEntry<K,V> next;
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
/**
* The maximum number of times to tryLock in a prescan before possibly blocking on acquire in preparation for a locked
* segment operation. On multiprocessors, using a bounded
* number of retries maintains cache acquired while locating
* nodes.
* 在為鎖定段操作做準備而可能阻塞之前，在預掃描中嘗試lock的最大次數。在多處理器上，使用有限的重試次數來維護在定位節點時獲取的快取。
*/
static final int MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
/**
* The per-segment table. Elements are accessed via
* entryAt/setEntryAt providing volatile semantics.
* 每個segment中的鍵值對數組
*/
transient volatile HashEntry<K,V>[] table;
/**
* The number of elements. Accessed only either within locks
* or among other volatile reads that maintain visibility.
* Segment中的元素個數
*/
transient int count;
/**
* The total number of mutative operations in this segment.
* Even though this may overflows 32 bits, it provides
* sufficient accuracy for stability checks in CHM isEmpty()
* and size() methods. Accessed only either within locks or
* among other volatile reads that maintain visibility.
* 每次 table 結構修改時，modCount增加1
*/
transient int modCount;
/**
* The table is rehashed when its size exceeds this threshold.
* 當表的大小超過這個閾值時，表將被重新散列。
* (The value of this field is always <tt>(int)(capacity *
* loadFactor)</tt>.)
* segment擴容的閾值
*/
transient int threshold;
/**
* The load factor for the hash table. Even though this value
* is same for all segments, it is replicated to avoid needing
* links to outer object.
* @serial
* 載入因子
*/
final float loadFactor;
//構造函數
Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
this.loadFactor = lf;
this.threshold = threshold;
this.table = tab;
}
2.構造函數
/**
* Creates a new, empty map with a default initial capacity (16),
* load factor (0.75) and concurrencyLevel (16).
* 創建一個新的空映射，具有默認的初始容量(16)，負載因子(0.75)和並發級別(16)。
*/
public ConcurrentHashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}
/**
* Creates a new, empty map with the specified initial capacity,
* and with default load factor (0.75) and concurrencyLevel (16).
* 使用指定的初始容量創建一個新的空映射，以及默認的負載因子(0.75)和並發級別(16)。
* @param initialCapacity the initial capacity. The implementation
* performs internal sizing to accommodate this many elements.
* @throws IllegalArgumentException if the initial capacity of
* elements is negative.
*/
public ConcurrentHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}
/**
* Creates a new, empty map with the specified initial capacity
* and load factor and with the default concurrencyLevel (16).
* 使用指定的初始容量，負載因子和默認的concurrencyLevel (16)創建一個新的空映射
* @param initialCapacity The implementation performs internal
* sizing to accommodate this many elements.
* @param loadFactor the load factor threshold, used to control resizing.
* Resizing may be performed when the average number of elements per
* bin exceeds this threshold.
* @throws IllegalArgumentException if the initial capacity of
* elements is negative or the load factor is nonpositive
*
* @since 1.6
*/
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
}
/**
* Creates a new map with the same mappings as the given map.
* 使用與給定映射相同的映射創建一個新映射。
* The map is created with a capacity of 1.5 times the number
* of mappings in the given map or 16 (whichever is greater),
* and a default load factor (0.75) and concurrencyLevel (16).
* 容量為原map * 1.5倍 和 16 中大的那個，載入因子為0.75，concurrencyLevel為16
* @param m the map
*/
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
//構建新的table
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY),
DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
//將原映射put進去
putAll(m);
}
/**
* Creates a new, empty map with the specified initial capacity, load factor and concurrency level.
* 使用指定的初始容量、負載因子和並發級別創建一個新的空映射。
* 所有的構造函數最終都會調用這個構造函數
* @param initialCapacity the initial capacity. The implementation
* performs internal sizing to accommodate this many elements.
* @param loadFactor the load factor threshold, used to control resizing.
* Resizing may be performed when the average number of elements per
* bin exceeds this threshold.
* @param concurrencyLevel the estimated number of concurrently
* updating threads. The implementation performs internal sizing
* to try to accommodate this many threads.
* @throws IllegalArgumentException if the initial capacity is
* negative or the load factor or concurrencyLevel are
* nonpositive.
*/
@SuppressWarnings("unchecked")
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
//如果載入因子<=0,初始容量為負，並發級別<=0，則拋出異常
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
//並發級別不能大於16
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// Find power-of-two sizes best matching arguments 找到2次冪大小的最佳匹配參數
//偏移量
//默認concurrencyLevel = 16, 所以ssize在默認情況下也是16,此時 sshift = 4
int sshift = 0;
//segmen的大小
int ssize = 1;
//找到>concurrencyLevel的最小2次冪
//sshift相當於ssize從1向左移的次數
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
//段偏移量，默認值28
this.segmentShift = 32 - sshift;
//掩碼
this.segmentMask = ssize - 1;
//對初始容量再進行判斷
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//計算一個segment中數組的數量
int c = initialCapacity / ssize;
//向上取整
if (c * ssize < initialCapacity)
++c;
//最小分段為2
int cap = MIN_SEGMENT_TABLE_CAPACITY;
//同樣地，將segment容量取到大於實際需要的最小2次冪
while (cap < c)
cap <<= 1;
// create segments and segments[0]
//創建segment數組，並初始化segmen[0]
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
//創建ssize大小的數組
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
//將obj對象的偏移量為offset的位置修改為value，因為Java中沒有記憶體操作，而Unsafe的這個操作正好補充了記憶體操作的不足。也可以用於數組操作，比如ConcurrentHashMap中就大量用到了該操作
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
3. put（）
/**
* Maps the specified key to the specified value in this table.
* 將指定的鍵映射到該表中的指定值。
* Neither the key nor the value can be null.
* 鍵和值都不能為空。
* <p> The value can be retrieved by calling the <tt>get</tt> method
* with a key that is equal to the original key.
* 可以通過調用get方法檢索該值，該方法具有與原始鍵相等的鍵
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>
* @throws NullPointerException if the specified key or value is null
*/
//告訴編譯器忽略警告。不用在編譯完成後出現警告
@SuppressWarnings("unchecked")
public V put(K key, V value) {
Segment<K,V> s;
//如果指定的值為空,拋出異常
if (value == null)
throw new NullPointerException();
int hash = hash(key);
//一個鍵值對在Segment數組中下標
int j = (hash >>> segmentShift) & segmentMask;
//這裡是用Unsafe類的原子操作找到Segment數組中j下標的 Segment 對象
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
//返回segment類型，如果不存在則初始化
s = ensureSegment(j);
//將鍵值對通過segment中put方法put，返回值為：
return s.put(key, hash, value, false);
}
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//這裡通過tryLock嘗試加鎖，如果加鎖成功，返回null，否則執行 scanAndLockForPut方法
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
//保存舊value
V oldValue;
try {
HashEntry<K,V>[] tab = table;
//二次哈希計算，求hashentry數組下標
int index = (tab.length - 1) & hash;
//找到下標的頭結點
HashEntry<K,V> first = entryAt(tab, index);
//遍歷操作
for (HashEntry<K,V> e = first;;) {
//當首結點不為空的時候
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
//當首結點為空，或者遍歷晚時,以下
//node值不為空時，說明調用scanAndLockForPut()方法時，遍歷沒有找到該節點，創建了新結點給node，「預熱」
if (node != null)
//直接頭插法
node.setNext(first);
else
//新建結點，頭插法
node = new HashEntry<K,V>(hash, key, value, first);
count加1
int c = count + 1;
//當c大於閾值且table長度沒達到最大值的時候擴容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
//否則，將結點插到數組下標為index的位置
setEntryAt(tab, index, node);
//增加修改次數
++modCount;
//count也++
count = c;
//因為沒有舊的value所以設置為null
oldValue = null;
break;
}
}
} finally {
unlock();
}
//返回oldvalue
return oldValue;
}
4.get（）
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
* 返回指定鍵映射到的值，或是null
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code key.equals(k)},
* then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* @throws NullPointerException if the specified key is null
*/
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead 手動集成訪問方法以減少開銷
HashEntry<K,V>[] tab;
//計算hash值
int h = hash(key);
//從主存中取出最新的結點
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
//如果若Segment不為空，且鏈表也不為空，則遍歷查找節點
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
//找到結點，返回value
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
//無，返回空
return null;
}
5. ensureSegment（）
/**
* Returns the segment for the given index, creating it and recording in segment table (via CAS) if not already present.
* 返回給定索引的段，創建它並(通過CAS)在段表中記錄(如果不存在)。
* @param k the index
* @return the segment
*/
@SuppressWarnings("unchecked")
////k為 (hash >>> segmentShift) & segmentMask 計算出的segment下標
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments;
////u代表 k 的偏移量，用於通過 UNSAFE 獲取主記憶體最新的實際 K 值
long u = (k << SSHIFT) + SBASE; // raw offset
Segment<K,V> seg;
//從記憶體中取到最新的下標位置的 Segment 對象，判斷是否為空
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
//如果為空，則按照ss[0]為原型來建造segment
Segment<K,V> proto = ss[0]; // use segment 0 as prototype
//容量為ss[0]的長度
int cap = proto.table.length;
//載入因子也為ss[0]的
float lf = proto.loadFactor;
//算出閾值
int threshold = (int)(cap * lf);
//再創建Segment 對應的 HashEntry 數組
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) { // recheck 再次從記憶體中取到最新的下標位置的 Segment 對象，判斷是否為空
//創建segment對象
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
//循環檢查 u下標位置的 Segment 是否為空
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
//不為空，說明有其他執行緒已經創建對象，則用seg保存
//若為空，則當前下標的Segment對象為空，就把它替換為最新創建出來的 s 對象
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
//返回segment
return seg;
}
6.scanAndLockForPut（）
/**
* Scans for a node containing given key while trying to
* acquire lock, creating and returning one if not found. Upon
* return, guarantees that lock is held. UNlike in most
* methods, calls to method equals are not screened: Since
* traversal speed doesn't matter, we might as well help warm
* up the associated code and accesses as well.
* put()方法第一步搶鎖失敗之後，就會執行此方法
* @return a new node if key not found, else null
*/
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
//找到HashEntry數組的下標的首結點
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node = null;
//初始化重試次數，為-1
int retries = -1; // negative while locating node
//一直嘗試搶鎖
while (!tryLock()) {
HashEntry<K,V> f; // to recheck first below
//
if (retries < 0) {
//首結點為空，預先創建一個新的結點，在hashentry數組上，retries++
if (e == null) {
if (node == null) // speculatively create node
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0;
}
//如果first有值，並且相對應，則也把retries = 0
else if (key.equals(e.key))
retries = 0;
else
//不對應的話，就從判斷語句開始
//同樣的如果空，就新建結點，否則找到該結點，最後retries = 0
e = e.next;
}
else if (++retries > MAX_SCAN_RETRIES) {
//lock拿不到鎖會一直等待。tryLock是去嘗試，拿不到就返回false，拿到返回true。
lock();
break;
}
//retries為偶數的時候&1為0，檢查在這段時間內first結點是否有改變
else if ((retries & 1) == 0 &&
(f = entryForHash(this, hash)) != first) {
e = first = f; // re-traverse if entry changed如果條目改變了，重新遍歷
retries = -1;
}
}
return node;
}
- scanAndLockForPut 這個方法可以確保返回時，當前執行緒一定是獲取到鎖的狀態。
7.rehash（）
-
當 put 方法時，發現元素個數超過了閾值，則會擴容
-
但是segment互相之間並不影響
/**
* Doubles size of table and repacks entries, also adding the given node to new table
* 將表的大小增加一倍並重新打包條目，還將給定節點添加到新表中
*/
@SuppressWarnings("unchecked")
private void rehash(HashEntry<K,V> node) {
/*
* Reclassify nodes in each list to new table. Because we
* are using power-of-two expansion, the elements from
* each bin must either stay at same index, or move with a
* power of two offset. We eliminate unnecessary node
* creation by catching cases where old nodes can be
* reused because their next fields won't change.
* Statistically, at the default threshold, only about
* one-sixth of them need cloning when a table
* doubles. The nodes they replace will be garbage
* collectable as soon as they are no longer referenced by
* any reader thread that may be in the midst of
* concurrently traversing table. Entry accesses use plain
* array indexing because they are followed by volatile
* table write.
*/
HashEntry<K,V>[] oldTable = table;
//oldCapacity為原表的長度
int oldCapacity = oldTable.length;
//新容量為原來的2倍
int newCapacity = oldCapacity << 1;
//再計算新的閾值
threshold = (int)(newCapacity * loadFactor);
//創建新容量的hashentry
HashEntry<K,V>[] newTable =
(HashEntry<K,V>[]) new HashEntry[newCapacity];
//哈希表大小掩碼 用於計算索引值
int sizeMask = newCapacity - 1;
//遍歷原表
for (int i = 0; i < oldCapacity ; i++) {
//// e 為鏈表的第一個結點
HashEntry<K,V> e = oldTable[i];
//如果首結點不為空
if (e != null) {
//保存e的next結點
HashEntry<K,V> next = e.next;
//重新計算e的index
int idx = e.hash & sizeMask;
//如果next為null，說明此位置沒發生哈希衝突，直接將e插入
if (next == null) // Single node on list
newTable[idx] = e;
else { // Reuse consecutive sequence at same slot 重複使用同一槽位的連續序列
HashEntry<K,V> lastRun = e;
int lastIdx = idx;
//遍歷列表
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
//計算當前遍歷到的節點的新下標
int k = last.hash & sizeMask;
//若 k 不等於 lastIdx，則把last更新
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
//新表的lastidx位置放入和lastrun index相同的結點
newTable[lastIdx] = lastRun;
// Clone remaining nodes 克隆剩餘節點
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
//通過遍歷建立新結點的方式
V v = p.value;
int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
}
}
}
}
//添加新節點,put方法傳入的結點
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
8.remove（）
/**
* Remove; match on key only if value null, else match both.
*/
final V remove(Object key, int hash, Object value) {
//搶鎖
if (!tryLock())
scanAndLock(key, hash);
V oldValue = null;
try {
HashEntry<K,V>[] tab = table;
//找到哈希表對應下標的頭結點
int index = (tab.length - 1) & hash;
HashEntry<K,V> e = entryAt(tab, index);
HashEntry<K,V> pred = null;
//如果首結點不為null
while (e != null) {
K k;
//記錄next
HashEntry<K,V> next = e.next;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
V v = e.value;
if (value == null || value == v || value.equals(v)) {
if (pred == null)
/**
* static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i,
* HashEntry<K,V> e) {
* UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);
* putOrderedObject: 將這個方法名拆成 put ordered Object
*/
setEntryAt(tab, index, next);
else
pred.setNext(next);
++modCount;
--count;
oldValue = v;
}
break;
//用的Unsafe的方法直接替換數組對應的值（此時的數組對應的空，所以可以直接插入），然後就是解鎖，返回舊的值了。
}
pred = e;
e = next;
}
} finally {
unlock();
}
return oldValue;
}
9.size（）
/**
* Returns the number of key-value mappings in this map.
* 返回此映射中的鍵-值映射的數量。
* If the map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
* <tt>Integer.MAX_VALUE</tt>.
*
* @return the number of key-value mappings in this map
*/
public int size() {
// Try a few times to get accurate count. On failure due to
// continuous async changes in table, resort to locking.
//試幾次，得到準確的數字。如果由於表中的連續非同步更改而導致失敗，則使用鎖定。
final Segment<K,V>[] segments = this.segments;
int size;
boolean overflow; // true if size overflows 32 bits
long sum; // sum of modCounts 的和
long last = 0L; // previous sum
int retries = -1; // first iteration isn't retry 重試次數
try {
for (;;) {
//如果超過重試次數，則不再重試，而是把所有Segment都加鎖，再統計 size
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
//遍歷所有Segment
//先不都鎖上，每個段統計count，並記錄modcount
//最後如果modcount不相等，則重新循環，直到超出最大重試次數
//則強制鎖上所有segment，然後統計次數返回
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
sum += seg.modCount;
int c = seg.count;
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
if (sum == last)
break;
last = sum;
}
} finally {
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
return overflow ? Integer.MAX_VALUE : size;
}
三.總結
1. ConcurrentHashMap中變數使用final和volatile修飾有什麼用呢？
-
final：HashEntry裡面除了value值不是final修飾的，其他都被final修飾了，所以在HashEntry鏈表裡面添加HashEntry的時候，只能添加到頭節點，不能添加到尾節點，因為HashEntry裡面的next值是被final修飾的，不能修改。 -
volatile:來保證某個變數記憶體的改變對其他執行緒即時可見，在配合CAS可以實現不加鎖對並發操作的支援。如：get操作可以無鎖是由於Node的元素val和指針next是用volatile修飾的，在多執行緒環境下執行緒A修改結點的val或者新增節點的時候是對執行緒B可見的
2. 什麼是哈希演算法？
- 是一種將任意內容的輸入轉換成相同長度輸出的加密方式，其輸出被稱為哈希值。
3. 為什麼用兩次hash？
- 構造分離鎖，操作的時候不會鎖住整個表，提高並發能力
4. hashmap在多執行緒下的隱患是什麼？可以用用什麼代替
-
jdk1.7版本存在put操作時存在丟失數據的情況
jdk1.8版本雖然解決了死循環問題，但是也有數據覆蓋問題
-
可用ConcurrentHashMap代替HashMap
5. 並發問題分析
ConcurrentHashMap的get操作時候，新增，修改，刪除都是要考慮並發問題的
。。。
6. segmentShift、segmentMask、sshift、ssize和SBASE關係
-
一個鍵值對在Segment數組中下標為：
(hash >>> segmentShift) & segmentMask -
其中，
- segmentShift = 32 – sshift
- segmentMask = ssize – 1
- 其中，
- 2^sshif=ssize
- ssize為concurrencyLevel的最小2次冪
