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