ConcurrentHashMap深入剖析（基於JDK1.7）
2022-06-28 15:02:28
最近有點時間，翻了翻ConcurrentHashMap的原始碼學習了一下，對我自己認為比較重要的一些方法進行了學習，新增了一些必要的註釋，拿出來與園子的小夥伴分享一下，有說的不對的地方，還請各位批評指正，歡迎交流。
話不多說，上原始碼：
1 package cn.com.pep.concurrent; 2 3 import java.util.concurrent.ConcurrentMap; 4 import java.util.concurrent.locks.*; 5 6 import java.util.*; 7 import java.io.Serializable; 8 import java.io.IOException; 9 10 /** 11 * A hash table supporting full concurrency of retrievals and adjustable 12 * expected concurrency for updates. This class obeys the same functional 13 * specification as {@link java.util.Hashtable}, and includes versions of 14 * methods corresponding to each method of <tt>Hashtable</tt>. However, even 15 * though all operations are thread-safe, retrieval operations do <em>not</em> 16 * entail locking, and there is <em>not</em> any support for locking the entire 17 * table in a way that prevents all access. This class is fully interoperable 18 * with <tt>Hashtable</tt> in programs that rely on its thread safety but not on 19 * its synchronization details. 20 * 21 * <p> 22 * Retrieval operations (including <tt>get</tt>) generally do not block, so may 23 * overlap with update operations (including <tt>put</tt> and <tt>remove</tt>). 24 * Retrievals reflect the results of the most recently <em>completed</em> update 25 * operations holding upon their onset. For aggregate operations such as 26 * <tt>putAll</tt> and <tt>clear</tt>, concurrent retrievals may reflect 27 * insertion or removal of only some entries. Similarly, Iterators and 28 * Enumerations return elements reflecting the state of the hash table at some 29 * point at or since the creation of the iterator/enumeration. They do 30 * <em>not</em> throw {@link ConcurrentModificationException}. However, 31 * iterators are designed to be used by only one thread at a time. 32 * 33 * <p> 34 * The allowed concurrency among update operations is guided by the optional 35 * <tt>concurrencyLevel</tt> constructor argument (default <tt>16</tt>), which 36 * is used as a hint for internal sizing. The table is internally partitioned to 37 * try to permit the indicated number of concurrent updates without contention. 38 * Because placement in hash tables is essentially random, the actual 39 * concurrency will vary. Ideally, you should choose a value to accommodate as 40 * many threads as will ever concurrently modify the table. Using a 41 * significantly higher value than you need can waste space and time, and a 42 * significantly lower value can lead to thread contention. But overestimates 43 * and underestimates within an order of magnitude do not usually have much 44 * noticeable impact. A value of one is appropriate when it is known that only 45 * one thread will modify and all others will only read. Also, resizing this or 46 * any other kind of hash table is a relatively slow operation, so, when 47 * possible, it is a good idea to provide estimates of expected table sizes in 48 * constructors. 49 * 50 * <p> 51 * This class and its views and iterators implement all of the <em>optional</em> 52 * methods of the {@link Map} and {@link Iterator} interfaces. 53 * 54 * <p> 55 * Like {@link Hashtable} but unlike {@link HashMap}, this class does 56 * <em>not</em> allow <tt>null</tt> to be used as a key or value. 57 * 58 * <p> 59 * This class is a member of the 60 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> Java 61 * Collections Framework</a>. 62 * 63 * @since 1.5 64 * @author Doug Lea 65 * @param <K> the type of keys maintained by this map 66 * @param <V> the type of mapped values 67 */ 68 public class ConcurrentHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>, Serializable { 69 private static final long serialVersionUID = 7249069246763182397L; 70 71 /* 72 * The basic strategy is to subdivide the table among Segments, each of which 73 * itself is a concurrently readable hash table. To reduce footprint, all but 74 * one segments are constructed only when first needed (see ensureSegment). To 75 * maintain visibility in the presence of lazy construction, accesses to 76 * segments as well as elements of segment's table must use volatile access, 77 * which is done via Unsafe within methods segmentAt etc below. These provide 78 * the functionality of AtomicReferenceArrays but reduce the levels of 79 * indirection. Additionally, volatile-writes of table elements and entry "next" 80 * fields within locked operations use the cheaper "lazySet" forms of writes 81 * (via putOrderedObject) because these writes are always followed by lock 82 * releases that maintain sequential consistency of table updates. 83 * 84 * Historical note: The previous version of this class relied heavily on "final" 85 * fields, which avoided some volatile reads at the expense of a large initial 86 * footprint. Some remnants of that design (including forced construction of 87 * segment 0) exist to ensure serialization compatibility. 88 */ 89 90 /* ---------------- Constants -------------- */ 91 92 /** 93 * The default initial capacity for this table, used when not otherwise 94 * specified in a constructor. 95 */ 96 static final int DEFAULT_INITIAL_CAPACITY = 16; 97 98 /** 99 * The default load factor for this table, used when not otherwise specified in 100 * a constructor. 101 */ 102 static final float DEFAULT_LOAD_FACTOR = 0.75f; 103 104 /** 105 * The default concurrency level for this table, used when not otherwise 106 * specified in a constructor. 107 */ 108 static final int DEFAULT_CONCURRENCY_LEVEL = 16; 109 110 /** 111 * The maximum capacity, used if a higher value is implicitly specified by 112 * either of the constructors with arguments. MUST be a power of two <= 1<<30 to 113 * ensure that entries are indexable using ints. 114 */ 115 static final int MAXIMUM_CAPACITY = 1 << 30; 116 117 /** 118 * The minimum capacity for per-segment tables. Must be a power of two, at least 119 * two to avoid immediate resizing on next use after lazy construction. 120 */ 121 static final int MIN_SEGMENT_TABLE_CAPACITY = 2; 122 123 /** 124 * The maximum number of segments to allow; used to bound constructor arguments. 125 * Must be power of two less than 1 << 24. 126 */ 127 static final int MAX_SEGMENTS = 1 << 16; // slightly conservative 128 129 /** 130 * Number of unsynchronized retries in size and containsValue methods before 131 * resorting to locking. This is used to avoid unbounded retries if tables 132 * undergo continuous modification which would make it impossible to obtain an 133 * accurate result. 134 */ 135 static final int RETRIES_BEFORE_LOCK = 2; 136 137 /* ---------------- Fields -------------- */ 138 139 /** 140 * holds values which can't be initialized until after VM is booted. 141 */ 142 private static class Holder { 143 144 /** 145 * Enable alternative hashing of String keys? 146 * 147 * <p> 148 * Unlike the other hash map implementations we do not implement a threshold for 149 * regulating whether alternative hashing is used for String keys. Alternative 150 * hashing is either enabled for all instances or disabled for all instances. 151 */ 152 static final boolean ALTERNATIVE_HASHING; 153 154 static { 155 // Use the "threshold" system property even though our threshold 156 // behaviour is "ON" or "OFF". 157 String altThreshold = java.security.AccessController 158 .doPrivileged(new sun.security.action.GetPropertyAction("jdk.map.althashing.threshold")); 159 160 int threshold; 161 try { 162 threshold = (null != altThreshold) ? Integer.parseInt(altThreshold) : Integer.MAX_VALUE; 163 164 // disable alternative hashing if -1 165 if (threshold == -1) { 166 threshold = Integer.MAX_VALUE; 167 } 168 169 if (threshold < 0) { 170 throw new IllegalArgumentException("value must be positive integer."); 171 } 172 } catch (IllegalArgumentException failed) { 173 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed); 174 } 175 ALTERNATIVE_HASHING = threshold <= MAXIMUM_CAPACITY; 176 } 177 } 178 179 /** 180 * A randomizing value associated with this instance that is applied to hash 181 * code of keys to make hash collisions harder to find. 182 */ 183 private transient final int hashSeed = randomHashSeed(this); 184 185 private static int randomHashSeed(ConcurrentHashMap instance) { 186 if (sun.misc.VM.isBooted() && Holder.ALTERNATIVE_HASHING) { 187 return sun.misc.Hashing.randomHashSeed(instance); 188 } 189 190 return 0; 191 } 192 193 /** 194 * Mask value for indexing into segments. The upper bits of a key's hash code 195 * are used to choose the segment. 196 */ 197 final int segmentMask; 198 199 /** 200 * Shift value for indexing within segments. 201 */ 202 final int segmentShift; 203 204 /** 205 * The segments, each of which is a specialized hash table. 206 */ 207 final Segment<K, V>[] segments; 208 209 transient Set<K> keySet; 210 transient Set<Map.Entry<K, V>> entrySet; 211 transient Collection<V> values; 212 213 /** 214 * ConcurrentHashMap list entry. Note that this is never exported out as a 215 * user-visible Map.Entry. 216 */ 217 static final class HashEntry<K, V> { 218 final int hash; 219 final K key; 220 volatile V value; 221 volatile HashEntry<K, V> next; 222 223 HashEntry(int hash, K key, V value, HashEntry<K, V> next) { 224 this.hash = hash; 225 this.key = key; 226 this.value = value; 227 this.next = next; 228 } 229 230 /** 231 * Sets next field with volatile write semantics. (See above about use of 232 * putOrderedObject.) 233 */ 234 final void setNext(HashEntry<K, V> n) { 235 UNSAFE.putOrderedObject(this, nextOffset, n); 236 } 237 238 // Unsafe mechanics 239 static final sun.misc.Unsafe UNSAFE; 240 static final long nextOffset; 241 static { 242 try { 243 UNSAFE = sun.misc.Unsafe.getUnsafe(); 244 Class k = HashEntry.class; 245 nextOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("next")); 246 } catch (Exception e) { 247 throw new Error(e); 248 } 249 } 250 } 251 252 /** 253 * Gets the ith element of given table (if nonnull) with volatile read 254 * semantics. Note: This is manually integrated into a few performance-sensitive 255 * methods to reduce call overhead. 256 */ 257 @SuppressWarnings("unchecked") 258 static final <K, V> HashEntry<K, V> entryAt(HashEntry<K, V>[] tab, int i) { 259 /* 獲取HashEntry陣列中，指定下標的頭結點 */ 260 return (HashEntry<K, V>) (tab == null ? null : UNSAFE.getObjectVolatile(tab, i << TSHIFT + TBASE)); 261 } 262 263 /** 264 * Sets the ith element of given table, with volatile write semantics. (See 265 * above about use of putOrderedObject.) 266 */ 267 static final <K, V> void setEntryAt(HashEntry<K, V>[] tab, int i, HashEntry<K, V> e) { 268 UNSAFE.putOrderedObject(tab, (i << TSHIFT) + TBASE, e); 269 } 270 271 /** 272 * Applies a supplemental hash function to a given hashCode, which defends 273 * against poor quality hash functions. This is critical because 274 * ConcurrentHashMap uses power-of-two length hash tables, that otherwise 275 * encounter collisions for hashCodes that do not differ in lower or upper bits. 276 */ 277 private int hash(Object k) { 278 int h = hashSeed; 279 280 if ((0 != h) && (k instanceof String)) { 281 return sun.misc.Hashing.stringHash32((String) k); 282 } 283 284 h ^= k.hashCode(); 285 286 // Spread bits to regularize both segment and index locations, 287 // using variant of single-word Wang/Jenkins hash. 288 h += (h << 15) ^ 0xffffcd7d; 289 h ^= (h >>> 10); 290 h += (h << 3); 291 h ^= (h >>> 6); 292 h += (h << 2) + (h << 14); 293 return h ^ (h >>> 16); 294 } 295 296 /** 297 * Segments are specialized versions of hash tables. This subclasses from 298 * ReentrantLock opportunistically, just to simplify some locking and avoid 299 * separate construction. 300 */ 301 static final class Segment<K, V> extends ReentrantLock implements Serializable { 302 /* 303 * Segments maintain a table of entry lists that are always kept in a consistent 304 * state, so can be read (via volatile reads of segments and tables) without 305 * locking. This requires replicating nodes when necessary during table 306 * resizing, so the old lists can be traversed by readers still using old 307 * version of table. 308 * 309 * This class defines only mutative methods requiring locking. Except as noted, 310 * the methods of this class perform the per-segment versions of 311 * ConcurrentHashMap methods. (Other methods are integrated directly into 312 * ConcurrentHashMap methods.) These mutative methods use a form of controlled 313 * spinning on contention via methods scanAndLock and scanAndLockForPut. These 314 * intersperse tryLocks with traversals to locate nodes. The main benefit is to 315 * absorb cache misses (which are very common for hash tables) while obtaining 316 * locks so that traversal is faster once acquired. We do not actually use the 317 * found nodes since they must be re-acquired under lock anyway to ensure 318 * sequential consistency of updates (and in any case may be undetectably 319 * stale), but they will normally be much faster to re-locate. Also, 320 * scanAndLockForPut speculatively creates a fresh node to use in put if no node 321 * is found. 322 */ 323 324 private static final long serialVersionUID = 2249069246763182397L; 325 326 /** 327 * The maximum number of times to tryLock in a prescan before possibly blocking 328 * on acquire in preparation for a locked segment operation. On multiprocessors, 329 * using a bounded number of retries maintains cache acquired while locating 330 * nodes. 331 */ 332 static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1; 333 334 /** 335 * The per-segment table. Elements are accessed via entryAt/setEntryAt providing 336 * volatile semantics. 337 */ 338 transient volatile HashEntry<K, V>[] table; 339 340 /** 341 * The number of elements. Accessed only either within locks or among other 342 * volatile reads that maintain visibility. 343 */ 344 transient int count;//當前segment中包含節點元素的數量 345 346 /** 347 * The total number of mutative operations in this segment. Even though this may 348 * overflows 32 bits, it provides sufficient accuracy for stability checks in 349 * CHM isEmpty() and size() methods. Accessed only either within locks or among 350 * other volatile reads that maintain visibility. 351 */ 352 transient int modCount;//發生寫操作的次數 353 354 /** 355 * The table is rehashed when its size exceeds this threshold. (The value of 356 * this field is always <tt>(int)(capacity * 357 * loadFactor)</tt>.) 358 */ 359 transient int threshold;//進行擴容的閾值 360 361 /** 362 * The load factor for the hash table. Even though this value is same for all 363 * segments, it is replicated to avoid needing links to outer object. 364 * 365 * @serial 366 */ 367 final float loadFactor;//載入因子 368 369 Segment(float lf, int threshold, HashEntry<K, V>[] tab) { 370 this.loadFactor = lf; 371 this.threshold = threshold; 372 this.table = tab; 373 } 374 375 final V put(K key, int hash, V value, boolean onlyIfAbsent) { 376 /* Try get lock for synchronized */ 377 HashEntry<K, V> node = tryLock() ? null : scanAndLockForPut(key, hash, value); 378 V oldValue = null; 379 try { 380 HashEntry<K, V>[] tab = table; 381 int index = (tab.length - 1) & hash; 382 /* 獲取頭結點 */ 383 HashEntry<K, V> first = entryAt(tab, index); 384 for (HashEntry<K, V> e = first;;) { 385 if (e != null) { 386 K k; 387 if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { 388 oldValue = e.value; 389 if (!onlyIfAbsent) { 390 e.value = value; 391 ++modCount; 392 } 393 break; 394 } 395 e = e.next; 396 } else { 397 /* 獲取鎖的過程中,建立了node節點,將node直接連結到當前這條鏈的頭結點,作為新的頭結點 */ 398 if (node != null) { 399 node.next = first; 400 } else { 401 /* 否則，建立新的頭結點 */ 402 node = new HashEntry<K, V>(hash, key, value, first); 403 } 404 405 int c = count + 1; 406 /* 判斷是否需要重新當前Segment中的陣列是否需要重新hash */ 407 if (c > threshold && tab.length < MAXIMUM_CAPACITY) { 408 rehash(node); 409 } else { 410 setEntryAt(tab, index, node); 411 } 412 ++modCount; 413 count = c; 414 oldValue = null; 415 break; 416 } 417 } 418 } finally { 419 unlock(); 420 } 421 422 return oldValue; 423 } 424 425 /** 426 * Doubles size of table and repacks entries, also adding the given node to new 427 * table 428 */ 429 @SuppressWarnings("unchecked") 430 private void rehash(HashEntry<K, V> node) { 431 HashEntry<K, V>[] oldTable = table; 432 int oldCapacity = oldTable.length; 433 int newCapacity = oldCapacity << 1; 434 threshold = (int) (newCapacity * loadFactor); 435 HashEntry<K, V>[] newTable = new HashEntry[newCapacity]; 436 int sizeMask = newCapacity - 1; 437 for (int i = 0; i < oldCapacity; i++) { 438 HashEntry<K, V> e = oldTable[i]; 439 if (e != null) { 440 HashEntry<K, V> next = e.next; 441 int idx = e.hash & sizeMask; 442 /* 說明這條鏈上有且僅有一個結點 */ 443 if (next == null) { 444 newTable[idx] = e; 445 } else { 446 HashEntry<K, V> lastRun = e; 447 int lastIdx = idx; 448 /*尋找擴容之後，不再原來這條鏈上的最後一個節點lastRun，這個節點之後的所有元素也必定不再原來鏈上，也必須轉移到新的鏈上*/ 449 for (HashEntry<K, V> last = next; last != null; last = last.next) { 450 int k = last.hash & sizeMask; 451 if (k != lastIdx) { 452 lastIdx = k; 453 lastRun = last; 454 } 455 } 456 457 /*遍歷完成之後這個lastIdx就是新鏈在HashEntry中的下標*/ 458 459 /* 460 * 重點注意： 461 * 1、因為HashEntry[]的擴容是倍增的，始終是2的冪次方，計算某個HashEntry所在HashEntry[]陣列中下標的演演算法為：i = (e.hash >> segmentShift) & segmentMask; 462 * 2、假設擴容之前HashEntry[]的長度為2的k次方，要確定某個hashEntry在HashEntry[]中的下標m，按照上面演演算法，m只與hash值的後k位有關; 463 * 3、擴容之後HashEntry[]的長度變為了2的k+1次方，又因為hash、segmentShift、SegmentMask均為final，所以計算的新下標n只與hash值的後k+1位有關； 464 * 4、第2步和第3步的的後k位和後k+1位，差異只在第k+1位，這位要麼為0，要麼為1，所以擴容前後，節點的所在陣列中的下標有如下關係：m == n 或者 m+(k<<1) = n; 465 * 5、根據第4步得出的結論，擴容之前每一條鏈上的HashEntry節點擴容之後只可能有兩種分佈情況：a、還分佈在原來的下標為m鏈上；b、分佈在新的m+(k<<1)這條鏈上，k不等於0; 466 */ 467 468 /*根據最上面第5步得出的結論，擴容之前不同的鏈上的元素擴容之後是不可能分佈在同一條鏈上的，所以就有如下賦值操作 ,將lastRun之後的所有元素賦值到新的鏈上，也有可能舊鏈*/ 469 newTable[lastIdx] = lastRun; 470 /* 將lastRun之前的節點採用頭插法插入到連結串列的頭部 */ 471 for (HashEntry<K, V> p = e; p != lastRun; p = p.next) { 472 V v = p.value; 473 int h = p.hash; 474 int k = h & sizeMask; 475 HashEntry<K, V> n = newTable[k]; 476 newTable[k] = new HashEntry<K, V>(h, p.key, v, n); 477 } 478 } 479 } 480 } 481 /* 重置這條鏈的頭結點 */ 482 int nodeIndex = node.hash & sizeMask; 483 node.setNext(newTable[nodeIndex]); 484 newTable[nodeIndex] = node; 485 table = newTable; 486 } 487 488 /** 489 * Scans for a node containing given key while trying to acquire lock, creating 490 * and returning one if not found. Upon return, guarantees that lock is held. 491 * UNlike in most methods, calls to method equals are not screened: Since 492 * traversal speed doesn't matter, we might as well help warm up the associated 493 * code and accesses as well. 494 * 495 * @return a new node if key not found, else null 496 */ 497 private HashEntry<K, V> scanAndLockForPut(K key, int hash, V value) { 498 /* 自旋的過程中嘗試獲取這個節點 */ 499 HashEntry<K, V> first = entryForHash(this, hash); 500 HashEntry<K, V> e = first; 501 HashEntry<K, V> node = null; 502 int retries = -1; 503 while (!tryLock()) { 504 HashEntry<K, V> f; 505 if (retries < 0) { 506 if (e == null) { 507 /* 在自旋嘗試的過程中,當前這條hashEntry鏈遍歷完成了,但是沒有找到這個節點就新建一個結點 */ 508 if (node == null) { 509 node = new HashEntry<K, V>(hash, key, value, null); 510 retries = 0; 511 } 512 } else if (key.equals(e.key)) { 513 retries = 0; 514 } else { 515 e = e.next; 516 } 517 } else if (++retries > RETRIES_BEFORE_LOCK) { 518 /* 自旋達到了最大次數，則不再自旋獲取，阻塞等待 */ 519 lock(); 520 break; 521 } else if (((retries & 1) == 0) && (f = entryForHash(this, hash)) != first) { 522 /* 自旋的過程中，頭結點發生了變化，說明發生了並行的寫操作，重新嘗試 */ 523 e = first = f; 524 retries = -1; 525 } 526 } 527 528 /* 第一次嘗試就獲取到了鎖,或者這條鏈還沒遍歷完就獲取到了鎖則node為空 */ 529 return node; 530 } 531 532 /** 533 * Scans for a node containing the given key while trying to acquire lock for a 534 * remove or replace operation. Upon return, guarantees that lock is held. Note 535 * that we must lock even if the key is not found, to ensure sequential 536 * consistency of updates. 537 */ 538 private void scanAndLock(Object key, int hash) { 539 // similar to but simpler than scanAndLockForPut 540 HashEntry<K, V> first = entryForHash(this, hash); 541 HashEntry<K, V> e = first; 542 int retries = -1; 543 /* 自旋的時候做一些遍歷操作，降低cpu的使用率 */ 544 while (!tryLock()) { 545 HashEntry<K, V> f; 546 if (retries < 0) { 547 if (e == null || key.equals(e.key)) { 548 retries = 0; 549 } 550 e = e.next; 551 } else if (++retries > MAX_SCAN_RETRIES) { 552 lock(); 553 break; 554 } else if (((retries & 1) == 0) && ((f = entryForHash(this, hash)) != first)) { 555 /* 嘗試獲取鎖的過程中 */ 556 e = first = f; 557 retries = -1; 558 } 559 } 560 } 561 562 /** 563 * Remove; match on key only if value null, else match both. 564 */ 565 final V remove(Object key, int hash, Object value) { 566 V oldValue = null; 567 if (!tryLock()) { 568 scanAndLock(key, hash); 569 } 570 try { 571 HashEntry<K, V>[] tab = table; 572 int index = (tab.length - 1) & hash; 573 /* current node */ 574 HashEntry<K, V> e = entryAt(tab, index); 575 /* previous node before current node */ 576 HashEntry<K, V> prev = null; 577 while (e != null) { 578 K k; 579 HashEntry<K, V> next = e.next; 580 if ((k = e.key) == key || ((e.hash == hash) && k.equals(key))) { 581 V v = e.value; 582 /* Value為null的時候只匹配key,否則key和value都需要匹配 */ 583 if (value == null || value == v || value.equals(value)) { 584 if (prev == null) { 585 setEntryAt(tab, index, next); 586 } else { 587 prev.setNext(next); 588 } 589 modCount++; 590 count--; 591 oldValue = v; 592 } 593 break; 594 } 595 prev = e; 596 e = next; 597 } 598 } finally { 599 unlock(); 600 } 601 return oldValue; 602 } 603 604 final boolean replace(K key, int hash, V oldValue, V newValue) { 605 boolean repalced = false; 606 if (!tryLock()) { 607 /* 獲取鎖失敗,進行一定次數的自旋獲取,還未成功則阻塞獲取 */ 608 scanAndLock(key, hash); 609 } 610 611 try { 612 for (HashEntry<K, V> e = entryForHash(this, hash); e != null; e = e.next) { 613 K k; 614 if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { 615 /* key相等，並且oldValue值等於原來位置的值才進行替換操作 */ 616 if (oldValue.equals(e.value)) { 617 e.value = newValue; 618 ++modCount; 619 repalced = true; 620 } 621 break; 622 } 623 } 624 } finally { 625 unlock(); 626 } 627 return repalced; 628 } 629 630 final V replace(K key, int hash, V value) { 631 V oldValue = null; 632 if (!tryLock()) { 633 scanAndLock(key, hash); 634 } 635 636 try { 637 HashEntry<K, V> e; 638 for (e = entryForHash(this, hash); e != null; e = e.next) { 639 K k; 640 if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { 641 oldValue = e.value; 642 e.value = value; 643 ++modCount; 644 break; 645 } 646 } 647 } finally { 648 unlock(); 649 } 650 return oldValue; 651 } 652 653 final void clear() { 654 lock(); 655 try { 656 HashEntry<K, V>[] tab = table; 657 for (int i = 0; i < tab.length; i++) 658 setEntryAt(tab, i, null); 659 ++modCount; 660 count = 0; 661 } finally { 662 unlock(); 663 } 664 } 665 } 666 667 // Accessing segments 668 669 /** 670 * Gets the jth element of given segment array (if nonnull) with volatile 671 * element access semantics via Unsafe. (The null check can trigger harmlessly 672 * only during deserialization.) Note: because each element of segments array is 673 * set only once (using fully ordered writes), some performance-sensitive 674 * methods rely on this method only as a recheck upon null reads. 675 */ 676 @SuppressWarnings("unchecked") 677 static final <K, V> Segment<K, V> segmentAt(Segment<K, V>[] ss, int j) { 678 long u = (j << SSHIFT) + SBASE; 679 return ss == null ? null : (Segment<K, V>) UNSAFE.getObjectVolatile(ss, u); 680 } 681 682 /** 683 * Returns the segment for the given index, creating it and recording in segment 684 * table (via CAS) if not already present. 685 * 686 * @param k the index 687 * @return the segment 688 */ 689 @SuppressWarnings("unchecked") 690 private Segment<K, V> ensureSegment(int k) { 691 /* 給當前位置建立一個新的segment */ 692 Segment<K, V>[] ss = this.segments; 693 long u = (k << SSHIFT) + SBASE; 694 Segment<K, V> seg; 695 if ((seg = (Segment<K, V>) UNSAFE.getObjectVolatile(ss, u)) == null) { 696 /* 以segment[0]作為原型來初始化當前位置的segment */ 697 Segment<K, V> proto = ss[0]; 698 int len = proto.table.length; 699 float lf = proto.loadFactor; 700 int threshold = (int) (len * lf); 701 HashEntry<K, V>[] tab = new HashEntry[len]; 702 if ((seg = (Segment<K, V>) UNSAFE.getObjectVolatile(ss, u)) == null) { 703 Segment<K, V> segment = new Segment<>(lf, threshold, tab); 704 while ((seg = (Segment<K, V>) UNSAFE.getObjectVolatile(ss, u)) == null) { 705 if (UNSAFE.compareAndSwapObject(ss, u, null, seg = segment)) { 706 break; 707 } 708 } 709 } 710 } 711 return seg; 712 } 713 714 // Hash-based segment and entry accesses 715 716 /** 717 * Get the segment for the given hash 718 */ 719 @SuppressWarnings("unchecked") 720 private Segment<K, V> segmentForHash(int h) { 721 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; 722 return (Segment<K, V>) UNSAFE.getObjectVolatile(segments, u); 723 } 724 725 /** 726 * Gets the table entry for the given segment and hash 727 */ 728 @SuppressWarnings("unchecked") 729 static final <K, V> HashEntry<K, V> entryForHash(Segment<K, V> seg, int h) { 730 /* 根據hash值獲取當前segment中，維護的HashEntry陣列中的某一條鏈的頭結點 */ 731 HashEntry<K, V>[] tab; 732 return (HashEntry<K, V>) ((seg == null || (tab = seg.table) == null) ? null 733 : UNSAFE.getObjectVolatile(seg, (((tab.length - 1) & h) << TSHIFT) + TBASE)); 734 } 735 736 /* ---------------- Public operations -------------- */ 737 738 /** 739 * Creates a new, empty map with the specified initial capacity, load factor and 740 * concurrency level. 741 * 742 * @param initialCapacity the initial capacity. The implementation performs 743 * internal sizing to accommodate this many elements. 744 * @param loadFactor the load factor threshold, used to control resizing. 745 * Resizing may be performed when the average number of 746 * elements per bin exceeds this threshold. 747 * @param concurrencyLevel the estimated number of concurrently updating 748 * threads. The implementation performs internal sizing 749 * to try to accommodate this many threads. 750 * @throws IllegalArgumentException if the initial capacity is negative or the 751 * load factor or concurrencyLevel are 752 * nonpositive. 753 */ 754 @SuppressWarnings("unchecked") 755 public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { 756 if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) 757 throw new IllegalArgumentException(); 758 if (concurrencyLevel > MAX_SEGMENTS) 759 concurrencyLevel = MAX_SEGMENTS; 760 // Find power-of-two sizes best matching arguments 761 int sshift = 0; 762 int ssize = 1; 763 while (ssize < concurrencyLevel) { 764 ++sshift; 765 ssize <<= 1; 766 } 767 this.segmentShift = 32 - sshift; 768 this.segmentMask = ssize - 1; 769 if (initialCapacity > MAXIMUM_CAPACITY) 770 initialCapacity = MAXIMUM_CAPACITY; 771 int c = initialCapacity / ssize; 772 if (c * ssize < initialCapacity) 773 ++c; 774 int cap = MIN_SEGMENT_TABLE_CAPACITY; 775 while (cap < c) 776 cap <<= 1; 777 // create segments and segments[0] 778 Segment<K, V> s0 = new Segment<K, V>(loadFactor, (int) (cap * loadFactor), 779 (HashEntry<K, V>[]) new HashEntry[cap]); 780 Segment<K, V>[] ss = (Segment<K, V>[]) new Segment[ssize]; 781 UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0] 782 this.segments = ss; 783 } 784 785 /** 786 * Creates a new, empty map with the specified initial capacity and load factor 787 * and with the default concurrencyLevel (16). 788 * 789 * @param initialCapacity The implementation performs internal sizing to 790 * accommodate this many elements. 791 * @param loadFactor the load factor threshold, used to control resizing. 792 * Resizing may be performed when the average number of 793 * elements per bin exceeds this threshold. 794 * @throws IllegalArgumentException if the initial capacity of elements is 795 * negative or the load factor is nonpositive 796 * 797 * @since 1.6 798 */ 799 public ConcurrentHashMap(int initialCapacity, float loadFactor) { 800 this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL); 801 } 802 803 /** 804 * Creates a new, empty map with the specified initial capacity, and with 805 * default load factor (0.75) and concurrencyLevel (16). 806 * 807 * @param initialCapacity the initial capacity. The implementation performs 808 * internal sizing to accommodate this many elements. 809 * @throws IllegalArgumentException if the initial capacity of elements is 810 * negative. 811 */ 812 public ConcurrentHashMap(int initialCapacity) { 813 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); 814 } 815 816 /** 817 * Creates a new, empty map with a default initial capacity (16), load factor 818 * (0.75) and concurrencyLevel (16). 819 */ 820 public ConcurrentHashMap() { 821 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); 822 } 823 824 /** 825 * Creates a new map with the same mappings as the given map. The map is created 826 * with a capacity of 1.5 times the number of mappings in the given map or 16 827 * (whichever is greater), and a default load factor (0.75) and concurrencyLevel 828 * (16). 829 * 830 * @param m the map 831 */ 832 public ConcurrentHashMap(Map<? extends K, ? extends V> m) { 833 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR, 834 DEFAULT_CONCURRENCY_LEVEL); 835 putAll(m); 836 } 837 838 /** 839 * Returns <tt>true</tt> if this map contains no key-value mappings. 840 * 841 * @return <tt>true</tt> if this map contains no key-value mappings 842 */ 843 public boolean isEmpty() { 844 /* 845 * Sum per-segment modCounts to avoid mis-reporting when elements are 846 * concurrently added and removed in one segment while checking another, in 847 * which case the table was never actually empty at any point. (The sum ensures 848 * accuracy up through at least 1<<31 per-segment modifications before recheck.) 849 * Methods size() and containsValue() use similar constructions for stability 850 * checks. 851 */ 852 /* 853 * 總體思路是遍歷兩次segment[]陣列，不加鎖操作 第一次遍歷， 854 * 在遍歷的過程中有任何一個segment中元素數量不為空，就立即返回false,否則就累加每個segment中寫操作的次數modCount; 855 * 第一次遍歷結束，如果累加的寫操作的次數為0，直接返回true，說明segment[]陣列中沒有任何元素，否則再進行第二次遍歷，任何一個segment不為空 856 * ，則返回false, 否則就進行第一次計算的累計寫操作次數sum的減法操作，直到遍歷完所有的segment,遍歷結束之後，sum不等於0就說明， 857 * 在這兩次遍歷的過程中發生了一次寫操作，所以必定不為空。 858 */ 859 long sum = 0L; 860 final Segment<K, V>[] segments = this.segments; 861 for (int i = 0; i < segments.length; i++) { 862 Segment<K, V> seg = segmentAt(segments, i); 863 if (seg != null) { 864 if (seg.count != 0) { 865 return false; 866 } 867 sum += seg.modCount; 868 } 869 } 870 871 if (sum != 0L) { 872 for (int i = 0; i < segments.length; i++) { 873 Segment<K, V> seg = segmentAt(segments, i); 874 if (seg != null) { 875 if (seg.count != 0) { 876 return false; 877 } 878 sum -= seg.modCount; 879 } 880 } 881 882 if (sum != 0) { 883 return false; 884 } 885 } 886 return true; 887 } 888 889 /** 890 * Returns the number of key-value mappings in this map. If the map contains 891 * more than <tt>Integer.MAX_VALUE</tt> elements, returns 892 * <tt>Integer.MAX_VALUE</tt>. 893 * 894 * @return the number of key-value mappings in this map 895 */ 896 public int size() { 897 /* 統計size的過程中可以不同的segment中有並行的寫操作，所以只能相對的統計某一個時間範圍內的size大小 */ 898 final Segment<K, V>[] segments = this.segments; 899 int size;// 計算的大小 900 long sum;// 本輪計算的累計並行次數 901 long last = 0L;// 上一次計算的累計並行次數 902 int retries = -1;// 初始重試次數 903 boolean overflow;// size是否溢位 904 try { 905 /* 906 * 總體思路：不加鎖先嚐試計算size,最大重試3次，要是在這個最大重試次數的範圍內，segment[]中沒有發生並行寫操作，則結束， 907 * 否則對所有的segment進行加鎖再統計size 908 */ 909 for (;;) { 910 /* 重試次數達到了閾值,則對所有的段進行加鎖計算 */ 911 if (retries++ == RETRIES_BEFORE_LOCK) { 912 for (int i = 0; i < segments.length; i++) { 913 segmentAt(segments, i).lock(); 914 } 915 } 916 917 sum = 0L; 918 size = 0; 919 overflow = false; 920 for (int i = 0; i < segments.length; i++) { 921 Segment<K, V> seg = segmentAt(segments, i); 922 if (seg != null) { 923 sum += seg.modCount; 924 int c = seg.count; 925 /* 發生了長度溢位 */ 926 if (c < 0 || (size += c) < 0) { 927 overflow = true; 928 } 929 } 930 } 931 932 /* 兩次並行修改的次數一樣說明這段時間的size是穩定的，則統計size結束，否則繼續重試，達到閾值，仍不穩定，則對所有segment加鎖，然後再計算 */ 933 if (sum == last) { 934 break; 935 } 936 last = sum; 937 } 938 } finally { 939 if (retries > RETRIES_BEFORE_LOCK) { 940 for (int i = 0; i < segments.length; i++) { 941 segmentAt(segments, i).unlock(); 942 } 943 } 944 } 945 return overflow ? Integer.MAX_VALUE : size; 946 } 947 948 /** 949 * Returns the value to which the specified key is mapped, or {@code null} if 950 * this map contains no mapping for the key. 951 * 952 * <p> 953 * More formally, if this map contains a mapping from a key {@code k} to a value 954 * {@code v} such that {@code key.equals(k)}, then this method returns 955 * {@code v}; otherwise it returns {@code null}. (There can be at most one such 956 * mapping.) 957 * 958 * @throws NullPointerException if the specified key is null 959 */ 960 @SuppressWarnings("unchecked") 961 public V get(Object key) { 962 Segment<K, V> seg; 963 HashEntry<K, V>[] tab; 964 int h = hash(key); 965 /* 根據key定位到其所在的segment[]陣列中下標，在記憶體中所對應的地址 */ 966 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; 967 if ((seg = (Segment<K, V>) UNSAFE.getObjectVolatile(segments, u)) != null && (tab = seg.table) != null) { 968 for (HashEntry<K, V> e = (HashEntry<K, V>) UNSAFE.getObjectVolatile(seg, 969 (((tab.length - 1) & h) << TSHIFT) + TBASE); e != null; e = e.next) { 970 K k; 971 if ((k = e.key) == key || (e.hash == h && key.equals(k))) { 972 return e.value; 973 } 974 } 975 } 976 return null; 977 } 978 979 /** 980 * Tests if the specified object is a key in this table. 981 * 982 * @param key possible key 983 * @return <tt>true</tt> if and only if the specified object is a key in this 984 * table, as determined by the <tt>equals</tt> method; <tt>false</tt> 985 * otherwise. 986 * @throws NullPointerException if the specified key is null 987 */ 988 @SuppressWarnings("unchecked") 989 public boolean containsKey(Object key) { 990 Segment<K, V> seg; 991 HashEntry<K, V>[] tab; 992 int h = hash(key); 993 long u = (((h >> segmentShift) & segmentMask) << SSHIFT) + SBASE; 994 if ((seg = (Segment<K, V>) UNSAFE.getObjectVolatile(segments, u)) != null && (tab = seg.table) != null) { 995 long ut = (((tab.length - 1) & h) << TSHIFT) + TBASE; 996 for (HashEntry<K, V> e = (HashEntry<K, V>) UNSAFE.getObjectVolatile(tab, ut); e != null; e = e.next) { 997 K k; 998 if ((k = e.key) == key || (e.hash == h && key.equals(k))) { 999 return true; 1000 } 1001 } 1002 } 1003 1004 return false; 1005 } 1006 1007 /** 1008 * Returns <tt>true</tt> if this map maps one or more keys to the specified 1009 * value. Note: This method requires a full internal traversal of the hash 1010 * table, and so is much slower than method <tt>containsKey</tt>. 1011 * 1012 * @param value value whose presence in this map is to be tested 1013 * @return <tt>true</tt> if this map maps one or more keys to the specified 1014 * value 1015 * @throws NullPointerException if the specified value is null 1016 */ 1017 public boolean containsValue(Object value) { 1018 /* 總體和計算size方法思路一致,參見size註釋 */ 1019 if (value == null) { 1020 throw new NullPointerException(); 1021 } 1022 1023 final Segment<K, V>[] segments = this.segments; 1024 boolean found = false; 1025 long last = 0; 1026 int retries = -1; 1027 try { 1028 /* 找到了直接跳出到這裡 */ 1029 outer: for (;;) { 1030 if (retries++ == RETRIES_BEFORE_LOCK) { 1031 for (int i = 0; i < segments.length; i++) { 1032 segmentAt(segments, i).lock(); 1033 } 1034 } 1035 1036 /* 用來統計並行的操作次數 */ 1037 long sum = 0L; 1038 for (int i = 0; i < segments.length; i++) { 1039 Segment<K, V> seg = segmentAt(segments, i); 1040 HashEntry<K, V>[] tab; 1041 if (seg != null && (tab = seg.table) != null) { 1042 for (int j = 0; j < tab.length; j++) { 1043 HashEntry<K, V> e; 1044 for (e = entryAt(tab, j); e != null; e = e.next) { 1045 V v = e.value; 1046 if (v != null && value.equals(v)) { 1047 found = true; 1048 /* 找到了匹配的value，則跳出到最外層的迴圈 */ 1049 break outer; 1050 } 1051 } 1052 } 1053 } 1054 sum += seg.modCount; 1055 } 1056 1057 if (retries > 0 && sum == last) { 1058 break; 1059 } 1060 last = sum; 1061 } 1062 } finally { 1063 if (retries > RETRIES_BEFORE_LOCK) { 1064 for (int i = 0; i < segments.length; i++) { 1065 segmentAt(segments, i).unlock(); 1066 } 1067 } 1068 } 1069 return found; 1070 } 1071 1072 /** 1073 * Legacy method testing if some key maps into the specified value in this 1074 * table. This method is identical in functionality to {@link #containsValue}, 1075 * and exists solely to ensure full compatibility with class 1076 * {@link java.util.Hashtable}, which supported this method prior to 1077 * introduction of the Java Collections framework. 1078 * 1079 * @param value a value to search for 1080 * @return <tt>true</tt> if and only if some key maps to the <tt>value</tt> 1081 * argument in this table as determined by the <tt>equals</tt> method; 1082 * <tt>false</tt> otherwise 1083 * @throws NullPointerException if the specified value is null 1084 */ 1085 public boolean contains(Object value) { 1086 return containsValue(value); 1087 } 1088 1089 /** 1090 * Maps the specified key to the specified value in this table. Neither the key 1091 * nor the value can be null. 1092 * 1093 * <p> 1094 * The value can be retrieved by calling the <tt>get</tt> method with a key that 1095 * is equal to the original key. 1096 * 1097 * @param key key with which the specified value is to be associated 1098 * @param value value to be associated with the specified key 1099 * @return the previous value associated with <tt>key</tt>, or <tt>null</tt> if 1100 * there was no mapping for <tt>key</tt> 1101 * @throws NullPointerException if the specified key or value is null 1102 */ 1103 @SuppressWarnings("unchecked") 1104 public V put(K key, V value) { 1105 Segment<K, V> s; 1106 if (value == null) { 1107 throw new NullPointerException(); 1108 } 1109 int hash = hash(key); 1110 int j = (hash >>> segmentShift) & segmentMask; 1111 /* 如果當前的segment為空，則建立一個 */ 1112 if ((s = (Segment<K, V>) UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) { 1113 s = ensureSegment(j); 1114 } 1115 return s.put(key, hash, value, false); 1116 } 1117 1118 /** 1119 * {@inheritDoc} 1120 * 1121 * @return the previous value associated with the specified key, or 1122 * <tt>null</tt> if there was no mapping for the key 1123 * @throws NullPointerException if the specified key or value is null 1124 */ 1125 @SuppressWarnings("unchecked") 1126 public V putIfAbsent(K key, V value) { 1127 Segment<K, V> s; 1128 if (value == null) 1129 throw new NullPointerException(); 1130 int hash = hash(key); 1131 int j = (hash >>> segmentShift) & segmentMask; 1132 if ((s = (Segment<K, V>) UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) 1133 s = ensureSegment(j); 1134 return s.put(key, hash, value, true); 1135 } 1136 1137 /** 1138 * Copies all of the mappings from the specified map to this one. These mappings 1139 * replace any mappings that this map had for any of the keys currently in the 1140 * specified map. 1141 * 1142 * @param m mappings to be stored in this map 1143 */ 1144 public void putAll(Map<? extends K, ? extends V> m) { 1145 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) 1146 put(e.getKey(), e.getValue()); 1147 } 1148 1149 /** 1150 * Removes the key (and its corresponding value) from this map. This method does 1151 * nothing if the key is not in the map. 1152 * 1153 * @param key the key that needs to be removed 1154 * @return the previous value associated with <tt>key</tt>, or <tt>null</tt> if 1155 * there was no mapping for <tt>key</tt> 1156 * @throws NullPointerException if the specified key is null 1157 */ 1158 public V remove(Object key) { 1159 int hash = hash(key); 1160 Segment<K, V> s = segmentForHash(hash); 1161 return s == null ? null : s.remove(key, hash, null); 1162 } 1163 1164 /** 1165 * {@inheritDoc} 1166 * 1167 * @throws NullPointerException if the specified key is null 1168 */ 1169 public boolean remove(Object key, Object value) { 1170 int hash = hash(key); 1171 Segment<K, V> s; 1172 return value != null && (s = segmentForHash(hash)) != null && s.remove(key, hash, value) != null; 1173 } 1174 1175 /** 1176 * {@inheritDoc} 1177 * 1178 * @throws NullPointerException if any of the arguments are null 1179 */ 1180 public boolean replace(K key, V oldValue, V newValue) { 1181 int hash = hash(key); 1182 if (oldValue == null || newValue == null) 1183 throw new NullPointerException(); 1184 Segment<K, V> s = segmentForHash(hash); 1185 return s != null && s.replace(key, hash, oldValue, newValue); 1186 } 1187 1188 /** 1189 * {@inheritDoc} 1190 * 1191 * @return the previous value associated with the specified key, or 1192 * <tt>null</tt> if there was no mapping for the key 1193 * @throws NullPointerException if the specified key or value is null 1194 */ 1195 public V replace(K key, V value) { 1196 int hash = hash(key); 1197 if (value == null) { 1198 throw new NullPointerException(); 1199 } 1200 Segment<K, V> seg = segmentForHash(hash); 1201 return seg == null ? null : seg.replace(key, hash, value); 1202 } 1203 1204 /** 1205 * Removes all of the mappings from this map. 1206 */ 1207 public void clear() { 1208 final Segment<K, V>[] segments = this.segments; 1209 for (int j = 0; j < segments.length; ++j) { 1210 Segment<K, V> s = segmentAt(segments, j); 1211 if (s != null) 1212 s.clear(); 1213 } 1214 } 1215 1216 /** 1217 * Returns a {@link Set} view of the keys contained in this map. The set is 1218 * backed by the map, so changes to the map are reflected in the set, and 1219 * vice-versa. The set supports element removal, which removes the corresponding 1220 * mapping from this map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 1221 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. It 1222 * does not support the <tt>add</tt> or <tt>addAll</tt> operations. 1223 * 1224 * <p> 1225 * The view's <tt>iterator</tt> is a "weakly consistent" iterator that will 1226 * never throw {@link ConcurrentModificationException}, and guarantees to 1227 * traverse elements as they existed upon construction of the iterator, and may 1228 * (but is not guaranteed to) reflect any modifications subsequent to 1229 * construction. 1230 */ 1231 public Set<K> keySet() { 1232 Set<K> ks = keySet; 1233 return (ks != null) ? ks : (keySet = new KeySet()); 1234 } 1235 1236 /** 1237 * Returns a {@link Collection} view of the values contained in this map. The 1238 * collection is backed by the map, so changes to the map are reflected in the 1239 * collection, and vice-versa. The collection supports element removal, which 1240 * removes the corresponding mapping from this map, via the 1241 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, <tt>removeAll</tt>, 1242 * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support the 1243 * <tt>add</tt> or <tt>addAll</tt> operations. 1244 * 1245 * <p> 1246 * The view's <tt>iterator</tt> is a "weakly consistent" iterator that will 1247 * never throw {@link ConcurrentModificationException}, and guarantees to 1248 * traverse elements as they existed upon construction of the iterator, and may 1249 * (but is not guaranteed to) reflect any modifications subsequent to 1250 * construction. 1251 */ 1252 public Collection<V> values() { 1253 Collection<V> vs = values; 1254 return (vs != null) ? vs : (values = new Values()); 1255 } 1256 1257 /** 1258 * Returns a {@link Set} view of the mappings contained in this map. The set is 1259 * backed by the map, so changes to the map are reflected in the set, and 1260 * vice-versa. The set supports element removal, which removes the corresponding 1261 * mapping from the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 1262 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. It 1263 * does not support the <tt>add</tt> or <tt>addAll</tt> operations. 1264 * 1265 * <p> 1266 * The view's <tt>iterator</tt> is a "weakly consistent" iterator that will 1267 * never throw {@link ConcurrentModificationException}, and guarantees to 1268 * traverse elements as they existed upon construction of the iterator, and may 1269 * (but is not guaranteed to) reflect any modifications subsequent to 1270 * construction. 1271 */ 1272 public Set<Map.Entry<K, V>> entrySet() { 1273 Set<Map.Entry<K, V>> es = entrySet; 1274 return (es != null) ? es : (entrySet = new EntrySet()); 1275 } 1276 1277 /** 1278 * Returns an enumeration of the keys in this table. 1279 * 1280 * @return an enumeration of the keys in this table 1281 * @see #keySet() 1282 */ 1283 public Enumeration<K> keys() { 1284 return new KeyIterator(); 1285 } 1286 1287 /** 1288 * Returns an enumeration of the values in this table. 1289 * 1290 * @return an enumeration of the values in this table 1291 * @see #values() 1292 */ 1293 public Enumeration<V> elements() { 1294 return new ValueIterator(); 1295 } 1296 1297 /* ---------------- Iterator Support -------------- */ 1298 1299 abstract class HashIterator { 1300 int nextSegmentIndex; 1301 int nextTableIndex; 1302 HashEntry<K, V>[] currentTable; 1303 HashEntry<K, V> nextEntry; 1304 HashEntry<K, V> lastReturned; 1305 1306 HashIterator() { 1307 nextSegmentIndex = segments.length - 1; 1308 nextTableIndex = -1; 1309 advance(); 1310 } 1311 1312 /** 1313 * Set nextEntry to first node of next non-empty table (in backwards order, to 1314 * simplify checks). 1315 */ 1316 final void advance() { 1317 for (;;) { 1318 if (nextTableIndex >= 0) { 1319 if ((nextEntry = entryAt(currentTable, nextTableIndex--)) != null) 1320 break; 1321 } else if (nextSegmentIndex >= 0) { 1322 Segment<K, V> seg = segmentAt(segments, nextSegmentIndex--); 1323 if (seg != null && (currentTable = seg.table) != null) 1324 nextTableIndex = currentTable.length - 1; 1325 } else 1326 break; 1327 } 1328 } 1329 1330 final HashEntry<K, V> nextEntry() { 1331 HashEntry<K, V> e = nextEntry; 1332 if (e == null) 1333 throw new NoSuchElementException(); 1334 lastReturned = e; // cannot assign until after null check 1335 if ((nextEntry = e.next) == null) 1336 advance(); 1337 return e; 1338 } 1339 1340 public final boolean hasNext() { 1341 return nextEntry != null; 1342 } 1343 1344 public final boolean hasMoreElements() { 1345 return nextEntry != null; 1346 } 1347 1348 public final void remove() { 1349 if (lastReturned == null) 1350 throw new IllegalStateException(); 1351 ConcurrentHashMap.this.remove(lastReturned.key); 1352 lastReturned = null; 1353 } 1354 } 1355 1356 final class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> { 1357 public final K next() { 1358 return super.nextEntry().key; 1359 } 1360 1361 public final K nextElement() { 1362 return super.nextEntry().key; 1363 } 1364 } 1365 1366 final class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> { 1367 public final V next() { 1368 return super.nextEntry().value; 1369 } 1370 1371 public final V nextElement() { 1372 return super.nextEntry().value; 1373 } 1374 } 1375 1376 /** 1377 * Custom Entry class used by EntryIterator.next(), that relays setValue changes 1378 * to the underlying map. 1379 */ 1380 final class WriteThroughEntry extends AbstractMap.SimpleEntry<K, V> { 1381 WriteThroughEntry(K k, V v) { 1382 super(k, v); 1383 } 1384 1385 /** 1386 * Set our entry's value and write through to the map. The value to return is 1387 * somewhat arbitrary here. Since a WriteThroughEntry does not necessarily track 1388 * asynchronous changes, the most recent "previous" value could be different 1389 * from what we return (or could even have been removed in which case the put 1390 * will re-establish). We do not and cannot guarantee more. 1391 */ 1392 public V setValue(V value) { 1393 if (value == null) 1394 throw new NullPointerException(); 1395 V v = super.setValue(value); 1396 ConcurrentHashMap.this.put(getKey(), value); 1397 return v; 1398 } 1399 } 1400 1401 final class EntryIterator extends HashIterator implements Iterator<Entry<K, V>> { 1402 public Map.Entry<K, V> next() { 1403 HashEntry<K, V> e = super.nextEntry(); 1404 return new WriteThroughEntry(e.key, e.value); 1405 } 1406 } 1407 1408 final class KeySet extends AbstractSet<K> { 1409 public Iterator<K> iterator() { 1410 return new KeyIterator(); 1411 } 1412 1413 public int size() { 1414 return ConcurrentHashMap.this.size(); 1415 } 1416 1417 public boolean isEmpty() { 1418 return ConcurrentHashMap.this.isEmpty(); 1419 } 1420 1421 public boolean contains(Object o) { 1422 return ConcurrentHashMap.this.containsKey(o); 1423 } 1424 1425 public boolean remove(Object o) { 1426 return ConcurrentHashMap.this.remove(o) != null; 1427 } 1428 1429 public void clear() { 1430 ConcurrentHashMap.this.clear(); 1431 } 1432 } 1433 1434 final class Values extends AbstractCollection<V> { 1435 public Iterator<V> iterator() { 1436 return new ValueIterator(); 1437 } 1438 1439 public int size() { 1440 return ConcurrentHashMap.this.size(); 1441 } 1442 1443 public boolean isEmpty() { 1444 return ConcurrentHashMap.this.isEmpty(); 1445 } 1446 1447 public boolean contains(Object o) { 1448 return ConcurrentHashMap.this.containsValue(o); 1449 } 1450 1451 public void clear() { 1452 ConcurrentHashMap.this.clear(); 1453 } 1454 } 1455 1456 final class EntrySet extends AbstractSet<Map.Entry<K, V>> { 1457 public Iterator<Map.Entry<K, V>> iterator() { 1458 return new EntryIterator(); 1459 } 1460 1461 public boolean contains(Object o) { 1462 if (!(o instanceof Map.Entry)) 1463 return false; 1464 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; 1465 V v = ConcurrentHashMap.this.get(e.getKey()); 1466 return v != null && v.equals(e.getValue()); 1467 } 1468 1469 public boolean remove(Object o) { 1470 if (!(o instanceof Map.Entry)) 1471 return false; 1472 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; 1473 return ConcurrentHashMap.this.remove(e.getKey(), e.getValue()); 1474 } 1475 1476 public int size() { 1477 return ConcurrentHashMap.this.size(); 1478 } 1479 1480 public boolean isEmpty() { 1481 return ConcurrentHashMap.this.isEmpty(); 1482 } 1483 1484 public void clear() { 1485 ConcurrentHashMap.this.clear(); 1486 } 1487 } 1488 1489 /* ---------------- Serialization Support -------------- */ 1490 1491 /** 1492 * Save the state of the <tt>ConcurrentHashMap</tt> instance to a stream (i.e., 1493 * serialize it). 1494 * 1495 * @param s the stream 1496 * @serialData the key (Object) and value (Object) for each key-value mapping, 1497 * followed by a null pair. The key-value mappings are emitted in no 1498 * particular order. 1499 */ 1500 private void writeObject(java.io.ObjectOutputStream s) throws IOException { 1501 // force all segments for serialization compatibility 1502 for (int k = 0; k < segments.length; ++k) 1503 ensureSegment(k); 1504 s.defaultWriteObject(); 1505 1506 final Segment<K, V>[] segments = this.segments; 1507 for (int k = 0; k < segments.length; ++k) { 1508 Segment<K, V> seg = segmentAt(segments, k); 1509 seg.lock(); 1510 try { 1511 HashEntry<K, V>[] tab = seg.table; 1512 for (int i = 0; i < tab.length; ++i) { 1513 HashEntry<K, V> e; 1514 for (e = entryAt(tab, i); e != null; e = e.next) { 1515 s.writeObject(e.key); 1516 s.writeObject(e.value); 1517 } 1518 } 1519 } finally { 1520 seg.unlock(); 1521 } 1522 } 1523 s.writeObject(null); 1524 s.writeObject(null); 1525 } 1526 1527 /** 1528 * Reconstitute the <tt>ConcurrentHashMap</tt> instance from a stream (i.e., 1529 * deserialize it). 1530 * 1531 * @param s the stream 1532 */ 1533 @SuppressWarnings("unchecked") 1534 private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { 1535 s.defaultReadObject(); 1536 1537 // set hashMask 1538 UNSAFE.putIntVolatile(this, HASHSEED_OFFSET, randomHashSeed(this)); 1539 1540 // Re-initialize segments to be minimally sized, and let grow. 1541 int cap = MIN_SEGMENT_TABLE_CAPACITY; 1542 final Segment<K, V>[] segments = this.segments; 1543 for (int k = 0; k < segments.length; ++k) { 1544 Segment<K, V> seg = segments[k]; 1545 if (seg != null) { 1546 seg.threshold = (int) (cap * seg.loadFactor); 1547 seg.table = (HashEntry<K, V>[]) new HashEntry[cap]; 1548 } 1549 } 1550 1551 // Read the keys and values, and put the mappings in the table 1552 for (;;) { 1553 K key = (K) s.readObject(); 1554 V value = (V) s.readObject(); 1555 if (key == null) 1556 break; 1557 put(key, value); 1558 } 1559 } 1560 1561 // Unsafe mechanics 1562 private static final sun.misc.Unsafe UNSAFE; 1563 private static final long SBASE; 1564 private static final int SSHIFT; 1565 private static final long TBASE; 1566 private static final int TSHIFT; 1567 private static final long HASHSEED_OFFSET; 1568 1569 static { 1570 int ss, ts; 1571 try { 1572 UNSAFE = sun.misc.Unsafe.getUnsafe(); 1573 Class tc = HashEntry[].class; 1574 Class sc = Segment[].class; 1575 /* 獲取陣列中第0個元素在陣列物件中的偏移量 */ 1576 TBASE = UNSAFE.arrayBaseOffset(tc); 1577 SBASE = UNSAFE.arrayBaseOffset(sc); 1578 /* 獲取陣列中每個元素的長度大小 */ 1579 ts = UNSAFE.arrayIndexScale(tc); 1580 ss = UNSAFE.arrayIndexScale(sc); 1581 HASHSEED_OFFSET = UNSAFE.objectFieldOffset(ConcurrentHashMap.class.getDeclaredField("hashSeed")); 1582 } catch (Exception e) { 1583 throw new Error(e); 1584 } 1585 if ((ss & (ss - 1)) != 0 || (ts & (ts - 1)) != 0) 1586 throw new Error("data type scale not a power of two"); 1587 /* 陣列中元素的大小用2的冪次表示，如ss =16,SSHIFT = 4; */ 1588 SSHIFT = 31 - Integer.numberOfLeadingZeros(ss); 1589 TSHIFT = 31 - Integer.numberOfLeadingZeros(ts); 1590 } 1591 1592 }