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 }