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/licenses/publicdomain
  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.
 109      */
 110 
 111     /* ---------------- Constants -------------- */
 112 
 113     /**
 114      * The default initial capacity for this table,
 115      * used when not otherwise specified in a constructor.
 116      */
 117     static final int DEFAULT_INITIAL_CAPACITY = 16;
 118 
 119     /**
 120      * The default load factor for this table, used when not
 121      * otherwise specified in a constructor.
 122      */
 123     static final float DEFAULT_LOAD_FACTOR = 0.75f;
 124 
 125     /**
 126      * The default concurrency level for this table, used when not
 127      * otherwise specified in a constructor.
 128      */
 129     static final int DEFAULT_CONCURRENCY_LEVEL = 16;
 130 
 131     /**
 132      * The maximum capacity, used if a higher value is implicitly
 133      * specified by either of the constructors with arguments.  MUST
 134      * be a power of two <= 1<<30 to ensure that entries are indexable
 135      * using ints.
 136      */
 137     static final int MAXIMUM_CAPACITY = 1 << 30;
 138 
 139     /**
 140      * The maximum number of segments to allow; used to bound
 141      * constructor arguments.
 142      */
 143     static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
 144 
 145     /**
 146      * Number of unsynchronized retries in size and containsValue
 147      * methods before resorting to locking. This is used to avoid
 148      * unbounded retries if tables undergo continuous modification
 149      * which would make it impossible to obtain an accurate result.
 150      */
 151     static final int RETRIES_BEFORE_LOCK = 2;
 152 
 153     /* ---------------- Fields -------------- */
 154 
 155     /**
 156      * Mask value for indexing into segments. The upper bits of a
 157      * key's hash code are used to choose the segment.
 158      */
 159     final int segmentMask;
 160 
 161     /**
 162      * Shift value for indexing within segments.
 163      */
 164     final int segmentShift;
 165 
 166     /**
 167      * The segments, each of which is a specialized hash table
 168      */
 169     final Segment<K,V>[] segments;
 170 
 171     transient Set<K> keySet;
 172     transient Set<Map.Entry<K,V>> entrySet;
 173     transient Collection<V> values;
 174 
 175     /* ---------------- Small Utilities -------------- */
 176 
 177     /**
 178      * Applies a supplemental hash function to a given hashCode, which
 179      * defends against poor quality hash functions.  This is critical
 180      * because ConcurrentHashMap uses power-of-two length hash tables,
 181      * that otherwise encounter collisions for hashCodes that do not
 182      * differ in lower or upper bits.
 183      */
 184     private static int hash(int h) {
 185         // Spread bits to regularize both segment and index locations,
 186         // using variant of single-word Wang/Jenkins hash.
 187         h += (h <<  15) ^ 0xffffcd7d;
 188         h ^= (h >>> 10);
 189         h += (h <<   3);
 190         h ^= (h >>>  6);
 191         h += (h <<   2) + (h << 14);
 192         return h ^ (h >>> 16);
 193     }
 194 
 195     /**
 196      * Returns the segment that should be used for key with given hash
 197      * @param hash the hash code for the key
 198      * @return the segment
 199      */
 200     final Segment<K,V> segmentFor(int hash) {
 201         return segments[(hash >>> segmentShift) & segmentMask];
 202     }
 203 
 204     /* ---------------- Inner Classes -------------- */
 205 
 206     /**
 207      * ConcurrentHashMap list entry. Note that this is never exported
 208      * out as a user-visible Map.Entry.
 209      *
 210      * Because the value field is volatile, not final, it is legal wrt
 211      * the Java Memory Model for an unsynchronized reader to see null
 212      * instead of initial value when read via a data race.  Although a
 213      * reordering leading to this is not likely to ever actually
 214      * occur, the Segment.readValueUnderLock method is used as a
 215      * backup in case a null (pre-initialized) value is ever seen in
 216      * an unsynchronized access method.
 217      */
 218     static final class HashEntry<K,V> {
 219         final K key;
 220         final int hash;
 221         volatile V value;
 222         final HashEntry<K,V> next;
 223 
 224         HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
 225             this.key = key;
 226             this.hash = hash;
 227             this.next = next;
 228             this.value = value;
 229         }
 230 
 231         @SuppressWarnings("unchecked")
 232         static final <K,V> HashEntry<K,V>[] newArray(int i) {
 233             return new HashEntry[i];
 234         }
 235     }
 236 
 237     /**
 238      * Segments are specialized versions of hash tables.  This
 239      * subclasses from ReentrantLock opportunistically, just to
 240      * simplify some locking and avoid separate construction.
 241      */
 242     static final class Segment<K,V> extends ReentrantLock implements Serializable {
 243         /*
 244          * Segments maintain a table of entry lists that are ALWAYS
 245          * kept in a consistent state, so can be read without locking.
 246          * Next fields of nodes are immutable (final).  All list
 247          * additions are performed at the front of each bin. This
 248          * makes it easy to check changes, and also fast to traverse.
 249          * When nodes would otherwise be changed, new nodes are
 250          * created to replace them. This works well for hash tables
 251          * since the bin lists tend to be short. (The average length
 252          * is less than two for the default load factor threshold.)
 253          *
 254          * Read operations can thus proceed without locking, but rely
 255          * on selected uses of volatiles to ensure that completed
 256          * write operations performed by other threads are
 257          * noticed. For most purposes, the "count" field, tracking the
 258          * number of elements, serves as that volatile variable
 259          * ensuring visibility.  This is convenient because this field
 260          * needs to be read in many read operations anyway:
 261          *
 262          *   - All (unsynchronized) read operations must first read the
 263          *     "count" field, and should not look at table entries if
 264          *     it is 0.
 265          *
 266          *   - All (synchronized) write operations should write to
 267          *     the "count" field after structurally changing any bin.
 268          *     The operations must not take any action that could even
 269          *     momentarily cause a concurrent read operation to see
 270          *     inconsistent data. This is made easier by the nature of
 271          *     the read operations in Map. For example, no operation
 272          *     can reveal that the table has grown but the threshold
 273          *     has not yet been updated, so there are no atomicity
 274          *     requirements for this with respect to reads.
 275          *
 276          * As a guide, all critical volatile reads and writes to the
 277          * count field are marked in code comments.
 278          */
 279 
 280         private static final long serialVersionUID = 2249069246763182397L;
 281 
 282         /**
 283          * The number of elements in this segment's region.
 284          */
 285         transient volatile int count;
 286 
 287         /**
 288          * Number of updates that alter the size of the table. This is
 289          * used during bulk-read methods to make sure they see a
 290          * consistent snapshot: If modCounts change during a traversal
 291          * of segments computing size or checking containsValue, then
 292          * we might have an inconsistent view of state so (usually)
 293          * must retry.
 294          */
 295         transient int modCount;
 296 
 297         /**
 298          * The table is rehashed when its size exceeds this threshold.
 299          * (The value of this field is always <tt>(int)(capacity *
 300          * loadFactor)</tt>.)
 301          */
 302         transient int threshold;
 303 
 304         /**
 305          * The per-segment table.
 306          */
 307         transient volatile HashEntry<K,V>[] table;
 308 
 309         /**
 310          * The load factor for the hash table.  Even though this value
 311          * is same for all segments, it is replicated to avoid needing
 312          * links to outer object.
 313          * @serial
 314          */
 315         final float loadFactor;
 316 
 317         Segment(int initialCapacity, float lf) {
 318             loadFactor = lf;
 319             setTable(HashEntry.<K,V>newArray(initialCapacity));
 320         }
 321 
 322         @SuppressWarnings("unchecked")
 323         static final <K,V> Segment<K,V>[] newArray(int i) {
 324             return new Segment[i];
 325         }
 326 
 327         /**
 328          * Sets table to new HashEntry array.
 329          * Call only while holding lock or in constructor.
 330          */
 331         void setTable(HashEntry<K,V>[] newTable) {
 332             threshold = (int)(newTable.length * loadFactor);
 333             table = newTable;
 334         }
 335 
 336         /**
 337          * Returns properly casted first entry of bin for given hash.
 338          */
 339         HashEntry<K,V> getFirst(int hash) {
 340             HashEntry<K,V>[] tab = table;
 341             return tab[hash & (tab.length - 1)];
 342         }
 343 
 344         /**
 345          * Reads value field of an entry under lock. Called if value
 346          * field ever appears to be null. This is possible only if a
 347          * compiler happens to reorder a HashEntry initialization with
 348          * its table assignment, which is legal under memory model
 349          * but is not known to ever occur.
 350          */
 351         V readValueUnderLock(HashEntry<K,V> e) {
 352             lock();
 353             try {
 354                 return e.value;
 355             } finally {
 356                 unlock();
 357             }
 358         }
 359 
 360         /* Specialized implementations of map methods */
 361 
 362         V get(Object key, int hash) {
 363             if (count != 0) { // read-volatile
 364                 HashEntry<K,V> e = getFirst(hash);
 365                 while (e != null) {
 366                     if (e.hash == hash && key.equals(e.key)) {
 367                         V v = e.value;
 368                         if (v != null)
 369                             return v;
 370                         return readValueUnderLock(e); // recheck
 371                     }
 372                     e = e.next;
 373                 }
 374             }
 375             return null;
 376         }
 377 
 378         boolean containsKey(Object key, int hash) {
 379             if (count != 0) { // read-volatile
 380                 HashEntry<K,V> e = getFirst(hash);
 381                 while (e != null) {
 382                     if (e.hash == hash && key.equals(e.key))
 383                         return true;
 384                     e = e.next;
 385                 }
 386             }
 387             return false;
 388         }
 389 
 390         boolean containsValue(Object value) {
 391             if (count != 0) { // read-volatile
 392                 HashEntry<K,V>[] tab = table;
 393                 int len = tab.length;
 394                 for (int i = 0 ; i < len; i++) {
 395                     for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
 396                         V v = e.value;
 397                         if (v == null) // recheck
 398                             v = readValueUnderLock(e);
 399                         if (value.equals(v))
 400                             return true;
 401                     }
 402                 }
 403             }
 404             return false;
 405         }
 406 
 407         boolean replace(K key, int hash, V oldValue, V newValue) {
 408             lock();
 409             try {
 410                 HashEntry<K,V> e = getFirst(hash);
 411                 while (e != null && (e.hash != hash || !key.equals(e.key)))
 412                     e = e.next;
 413 
 414                 boolean replaced = false;
 415                 if (e != null && oldValue.equals(e.value)) {
 416                     replaced = true;
 417                     e.value = newValue;
 418                 }
 419                 return replaced;
 420             } finally {
 421                 unlock();
 422             }
 423         }
 424 
 425         V replace(K key, int hash, V newValue) {
 426             lock();
 427             try {
 428                 HashEntry<K,V> e = getFirst(hash);
 429                 while (e != null && (e.hash != hash || !key.equals(e.key)))
 430                     e = e.next;
 431 
 432                 V oldValue = null;
 433                 if (e != null) {
 434                     oldValue = e.value;
 435                     e.value = newValue;
 436                 }
 437                 return oldValue;
 438             } finally {
 439                 unlock();
 440             }
 441         }
 442 
 443 
 444         V put(K key, int hash, V value, boolean onlyIfAbsent) {
 445             lock();
 446             try {
 447                 int c = count;
 448                 if (c++ > threshold) // ensure capacity
 449                     rehash();
 450                 HashEntry<K,V>[] tab = table;
 451                 int index = hash & (tab.length - 1);
 452                 HashEntry<K,V> first = tab[index];
 453                 HashEntry<K,V> e = first;
 454                 while (e != null && (e.hash != hash || !key.equals(e.key)))
 455                     e = e.next;
 456 
 457                 V oldValue;
 458                 if (e != null) {
 459                     oldValue = e.value;
 460                     if (!onlyIfAbsent)
 461                         e.value = value;
 462                 }
 463                 else {
 464                     oldValue = null;
 465                     ++modCount;
 466                     tab[index] = new HashEntry<K,V>(key, hash, first, value);
 467                     count = c; // write-volatile
 468                 }
 469                 return oldValue;
 470             } finally {
 471                 unlock();
 472             }
 473         }
 474 
 475         void rehash() {
 476             HashEntry<K,V>[] oldTable = table;
 477             int oldCapacity = oldTable.length;
 478             if (oldCapacity >= MAXIMUM_CAPACITY)
 479                 return;
 480 
 481             /*
 482              * Reclassify nodes in each list to new Map.  Because we are
 483              * using power-of-two expansion, the elements from each bin
 484              * must either stay at same index, or move with a power of two
 485              * offset. We eliminate unnecessary node creation by catching
 486              * cases where old nodes can be reused because their next
 487              * fields won't change. Statistically, at the default
 488              * threshold, only about one-sixth of them need cloning when
 489              * a table doubles. The nodes they replace will be garbage
 490              * collectable as soon as they are no longer referenced by any
 491              * reader thread that may be in the midst of traversing table
 492              * right now.
 493              */
 494 
 495             HashEntry<K,V>[] newTable = HashEntry.newArray(oldCapacity<<1);
 496             threshold = (int)(newTable.length * loadFactor);
 497             int sizeMask = newTable.length - 1;
 498             for (int i = 0; i < oldCapacity ; i++) {
 499                 // We need to guarantee that any existing reads of old Map can
 500                 //  proceed. So we cannot yet null out each bin.
 501                 HashEntry<K,V> e = oldTable[i];
 502 
 503                 if (e != null) {
 504                     HashEntry<K,V> next = e.next;
 505                     int idx = e.hash & sizeMask;
 506 
 507                     //  Single node on list
 508                     if (next == null)
 509                         newTable[idx] = e;
 510 
 511                     else {
 512                         // Reuse trailing consecutive sequence at same slot
 513                         HashEntry<K,V> lastRun = e;
 514                         int lastIdx = idx;
 515                         for (HashEntry<K,V> last = next;
 516                              last != null;
 517                              last = last.next) {
 518                             int k = last.hash & sizeMask;
 519                             if (k != lastIdx) {
 520                                 lastIdx = k;
 521                                 lastRun = last;
 522                             }
 523                         }
 524                         newTable[lastIdx] = lastRun;
 525 
 526                         // Clone all remaining nodes
 527                         for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
 528                             int k = p.hash & sizeMask;
 529                             HashEntry<K,V> n = newTable[k];
 530                             newTable[k] = new HashEntry<K,V>(p.key, p.hash,
 531                                                              n, p.value);
 532                         }
 533                     }
 534                 }
 535             }
 536             table = newTable;
 537         }
 538 
 539         /**
 540          * Remove; match on key only if value null, else match both.
 541          */
 542         V remove(Object key, int hash, Object value) {
 543             lock();
 544             try {
 545                 int c = count - 1;
 546                 HashEntry<K,V>[] tab = table;
 547                 int index = hash & (tab.length - 1);
 548                 HashEntry<K,V> first = tab[index];
 549                 HashEntry<K,V> e = first;
 550                 while (e != null && (e.hash != hash || !key.equals(e.key)))
 551                     e = e.next;
 552 
 553                 V oldValue = null;
 554                 if (e != null) {
 555                     V v = e.value;
 556                     if (value == null || value.equals(v)) {
 557                         oldValue = v;
 558                         // All entries following removed node can stay
 559                         // in list, but all preceding ones need to be
 560                         // cloned.
 561                         ++modCount;
 562                         HashEntry<K,V> newFirst = e.next;
 563                         for (HashEntry<K,V> p = first; p != e; p = p.next)
 564                             newFirst = new HashEntry<K,V>(p.key, p.hash,
 565                                                           newFirst, p.value);
 566                         tab[index] = newFirst;
 567                         count = c; // write-volatile
 568                     }
 569                 }
 570                 return oldValue;
 571             } finally {
 572                 unlock();
 573             }
 574         }
 575 
 576         void clear() {
 577             if (count != 0) {
 578                 lock();
 579                 try {
 580                     HashEntry<K,V>[] tab = table;
 581                     for (int i = 0; i < tab.length ; i++)
 582                         tab[i] = null;
 583                     ++modCount;
 584                     count = 0; // write-volatile
 585                 } finally {
 586                     unlock();
 587                 }
 588             }
 589         }
 590     }
 591 
 592 
 593 
 594     /* ---------------- Public operations -------------- */
 595 
 596     /**
 597      * Creates a new, empty map with the specified initial
 598      * capacity, load factor and concurrency level.
 599      *
 600      * @param initialCapacity the initial capacity. The implementation
 601      * performs internal sizing to accommodate this many elements.
 602      * @param loadFactor  the load factor threshold, used to control resizing.
 603      * Resizing may be performed when the average number of elements per
 604      * bin exceeds this threshold.
 605      * @param concurrencyLevel the estimated number of concurrently
 606      * updating threads. The implementation performs internal sizing
 607      * to try to accommodate this many threads.
 608      * @throws IllegalArgumentException if the initial capacity is
 609      * negative or the load factor or concurrencyLevel are
 610      * nonpositive.
 611      */
 612     public ConcurrentHashMap(int initialCapacity,
 613                              float loadFactor, int concurrencyLevel) {
 614         if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
 615             throw new IllegalArgumentException();
 616 
 617         if (concurrencyLevel > MAX_SEGMENTS)
 618             concurrencyLevel = MAX_SEGMENTS;
 619 
 620         // Find power-of-two sizes best matching arguments
 621         int sshift = 0;
 622         int ssize = 1;
 623         while (ssize < concurrencyLevel) {
 624             ++sshift;
 625             ssize <<= 1;
 626         }
 627         segmentShift = 32 - sshift;
 628         segmentMask = ssize - 1;
 629         this.segments = Segment.newArray(ssize);
 630 
 631         if (initialCapacity > MAXIMUM_CAPACITY)
 632             initialCapacity = MAXIMUM_CAPACITY;
 633         int c = initialCapacity / ssize;
 634         if (c * ssize < initialCapacity)
 635             ++c;
 636         int cap = 1;
 637         while (cap < c)
 638             cap <<= 1;
 639 
 640         for (int i = 0; i < this.segments.length; ++i)
 641             this.segments[i] = new Segment<K,V>(cap, loadFactor);
 642     }
 643 
 644     /**
 645      * Creates a new, empty map with the specified initial capacity
 646      * and load factor and with the default concurrencyLevel (16).
 647      *
 648      * @param initialCapacity The implementation performs internal
 649      * sizing to accommodate this many elements.
 650      * @param loadFactor  the load factor threshold, used to control resizing.
 651      * Resizing may be performed when the average number of elements per
 652      * bin exceeds this threshold.
 653      * @throws IllegalArgumentException if the initial capacity of
 654      * elements is negative or the load factor is nonpositive
 655      *
 656      * @since 1.6
 657      */
 658     public ConcurrentHashMap(int initialCapacity, float loadFactor) {
 659         this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
 660     }
 661 
 662     /**
 663      * Creates a new, empty map with the specified initial capacity,
 664      * and with default load factor (0.75) and concurrencyLevel (16).
 665      *
 666      * @param initialCapacity the initial capacity. The implementation
 667      * performs internal sizing to accommodate this many elements.
 668      * @throws IllegalArgumentException if the initial capacity of
 669      * elements is negative.
 670      */
 671     public ConcurrentHashMap(int initialCapacity) {
 672         this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
 673     }
 674 
 675     /**
 676      * Creates a new, empty map with a default initial capacity (16),
 677      * load factor (0.75) and concurrencyLevel (16).
 678      */
 679     public ConcurrentHashMap() {
 680         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
 681     }
 682 
 683     /**
 684      * Creates a new map with the same mappings as the given map.
 685      * The map is created with a capacity of 1.5 times the number
 686      * of mappings in the given map or 16 (whichever is greater),
 687      * and a default load factor (0.75) and concurrencyLevel (16).
 688      *
 689      * @param m the map
 690      */
 691     public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
 692         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
 693                       DEFAULT_INITIAL_CAPACITY),
 694              DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
 695         putAll(m);
 696     }
 697 
 698     /**
 699      * Returns <tt>true</tt> if this map contains no key-value mappings.
 700      *
 701      * @return <tt>true</tt> if this map contains no key-value mappings
 702      */
 703     public boolean isEmpty() {
 704         final Segment<K,V>[] segments = this.segments;
 705         /*
 706          * We keep track of per-segment modCounts to avoid ABA
 707          * problems in which an element in one segment was added and
 708          * in another removed during traversal, in which case the
 709          * table was never actually empty at any point. Note the
 710          * similar use of modCounts in the size() and containsValue()
 711          * methods, which are the only other methods also susceptible
 712          * to ABA problems.
 713          */
 714         int[] mc = new int[segments.length];
 715         int mcsum = 0;
 716         for (int i = 0; i < segments.length; ++i) {
 717             if (segments[i].count != 0)
 718                 return false;
 719             else
 720                 mcsum += mc[i] = segments[i].modCount;
 721         }
 722         // If mcsum happens to be zero, then we know we got a snapshot
 723         // before any modifications at all were made.  This is
 724         // probably common enough to bother tracking.
 725         if (mcsum != 0) {
 726             for (int i = 0; i < segments.length; ++i) {
 727                 if (segments[i].count != 0 ||
 728                     mc[i] != segments[i].modCount)
 729                     return false;
 730             }
 731         }
 732         return true;
 733     }
 734 
 735     /**
 736      * Returns the number of key-value mappings in this map.  If the
 737      * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
 738      * <tt>Integer.MAX_VALUE</tt>.
 739      *
 740      * @return the number of key-value mappings in this map
 741      */
 742     public int size() {
 743         final Segment<K,V>[] segments = this.segments;
 744         long sum = 0;
 745         long check = 0;
 746         int[] mc = new int[segments.length];
 747         // Try a few times to get accurate count. On failure due to
 748         // continuous async changes in table, resort to locking.
 749         for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
 750             check = 0;
 751             sum = 0;
 752             int mcsum = 0;
 753             for (int i = 0; i < segments.length; ++i) {
 754                 sum += segments[i].count;
 755                 mcsum += mc[i] = segments[i].modCount;
 756             }
 757             if (mcsum != 0) {
 758                 for (int i = 0; i < segments.length; ++i) {
 759                     check += segments[i].count;
 760                     if (mc[i] != segments[i].modCount) {
 761                         check = -1; // force retry
 762                         break;
 763                     }
 764                 }
 765             }
 766             if (check == sum)
 767                 break;
 768         }
 769         if (check != sum) { // Resort to locking all segments
 770             sum = 0;
 771             for (int i = 0; i < segments.length; ++i)
 772                 segments[i].lock();
 773             for (int i = 0; i < segments.length; ++i)
 774                 sum += segments[i].count;
 775             for (int i = 0; i < segments.length; ++i)
 776                 segments[i].unlock();
 777         }
 778         if (sum > Integer.MAX_VALUE)
 779             return Integer.MAX_VALUE;
 780         else
 781             return (int)sum;
 782     }
 783 
 784     /**
 785      * Returns the value to which the specified key is mapped,
 786      * or {@code null} if this map contains no mapping for the key.
 787      *
 788      * <p>More formally, if this map contains a mapping from a key
 789      * {@code k} to a value {@code v} such that {@code key.equals(k)},
 790      * then this method returns {@code v}; otherwise it returns
 791      * {@code null}.  (There can be at most one such mapping.)
 792      *
 793      * @throws NullPointerException if the specified key is null
 794      */
 795     public V get(Object key) {
 796         int hash = hash(key.hashCode());
 797         return segmentFor(hash).get(key, hash);
 798     }
 799 
 800     /**
 801      * Tests if the specified object is a key in this table.
 802      *
 803      * @param  key   possible key
 804      * @return <tt>true</tt> if and only if the specified object
 805      *         is a key in this table, as determined by the
 806      *         <tt>equals</tt> method; <tt>false</tt> otherwise.
 807      * @throws NullPointerException if the specified key is null
 808      */
 809     public boolean containsKey(Object key) {
 810         int hash = hash(key.hashCode());
 811         return segmentFor(hash).containsKey(key, hash);
 812     }
 813 
 814     /**
 815      * Returns <tt>true</tt> if this map maps one or more keys to the
 816      * specified value. Note: This method requires a full internal
 817      * traversal of the hash table, and so is much slower than
 818      * method <tt>containsKey</tt>.
 819      *
 820      * @param value value whose presence in this map is to be tested
 821      * @return <tt>true</tt> if this map maps one or more keys to the
 822      *         specified value
 823      * @throws NullPointerException if the specified value is null
 824      */
 825     public boolean containsValue(Object value) {
 826         if (value == null)
 827             throw new NullPointerException();
 828 
 829         // See explanation of modCount use above
 830 
 831         final Segment<K,V>[] segments = this.segments;
 832         int[] mc = new int[segments.length];
 833 
 834         // Try a few times without locking
 835         for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
 836             int sum = 0;
 837             int mcsum = 0;
 838             for (int i = 0; i < segments.length; ++i) {
 839                 int c = segments[i].count;
 840                 mcsum += mc[i] = segments[i].modCount;
 841                 if (segments[i].containsValue(value))
 842                     return true;
 843             }
 844             boolean cleanSweep = true;
 845             if (mcsum != 0) {
 846                 for (int i = 0; i < segments.length; ++i) {
 847                     int c = segments[i].count;
 848                     if (mc[i] != segments[i].modCount) {
 849                         cleanSweep = false;
 850                         break;
 851                     }
 852                 }
 853             }
 854             if (cleanSweep)
 855                 return false;
 856         }
 857         // Resort to locking all segments
 858         for (int i = 0; i < segments.length; ++i)
 859             segments[i].lock();
 860         boolean found = false;
 861         try {
 862             for (int i = 0; i < segments.length; ++i) {
 863                 if (segments[i].containsValue(value)) {
 864                     found = true;
 865                     break;
 866                 }
 867             }
 868         } finally {
 869             for (int i = 0; i < segments.length; ++i)
 870                 segments[i].unlock();
 871         }
 872         return found;
 873     }
 874 
 875     /**
 876      * Legacy method testing if some key maps into the specified value
 877      * in this table.  This method is identical in functionality to
 878      * {@link #containsValue}, and exists solely to ensure
 879      * full compatibility with class {@link java.util.Hashtable},
 880      * which supported this method prior to introduction of the
 881      * Java Collections framework.
 882 
 883      * @param  value a value to search for
 884      * @return <tt>true</tt> if and only if some key maps to the
 885      *         <tt>value</tt> argument in this table as
 886      *         determined by the <tt>equals</tt> method;
 887      *         <tt>false</tt> otherwise
 888      * @throws NullPointerException if the specified value is null
 889      */
 890     public boolean contains(Object value) {
 891         return containsValue(value);
 892     }
 893 
 894     /**
 895      * Maps the specified key to the specified value in this table.
 896      * Neither the key nor the value can be null.
 897      *
 898      * <p> The value can be retrieved by calling the <tt>get</tt> method
 899      * with a key that is equal to the original key.
 900      *
 901      * @param key key with which the specified value is to be associated
 902      * @param value value to be associated with the specified key
 903      * @return the previous value associated with <tt>key</tt>, or
 904      *         <tt>null</tt> if there was no mapping for <tt>key</tt>
 905      * @throws NullPointerException if the specified key or value is null
 906      */
 907     public V put(K key, V value) {
 908         if (value == null)
 909             throw new NullPointerException();
 910         int hash = hash(key.hashCode());
 911         return segmentFor(hash).put(key, hash, value, false);
 912     }
 913 
 914     /**
 915      * {@inheritDoc}
 916      *
 917      * @return the previous value associated with the specified key,
 918      *         or <tt>null</tt> if there was no mapping for the key
 919      * @throws NullPointerException if the specified key or value is null
 920      */
 921     public V putIfAbsent(K key, V value) {
 922         if (value == null)
 923             throw new NullPointerException();
 924         int hash = hash(key.hashCode());
 925         return segmentFor(hash).put(key, hash, value, true);
 926     }
 927 
 928     /**
 929      * Copies all of the mappings from the specified map to this one.
 930      * These mappings replace any mappings that this map had for any of the
 931      * keys currently in the specified map.
 932      *
 933      * @param m mappings to be stored in this map
 934      */
 935     public void putAll(Map<? extends K, ? extends V> m) {
 936         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
 937             put(e.getKey(), e.getValue());
 938     }
 939 
 940     /**
 941      * Removes the key (and its corresponding value) from this map.
 942      * This method does nothing if the key is not in the map.
 943      *
 944      * @param  key the key that needs to be removed
 945      * @return the previous value associated with <tt>key</tt>, or
 946      *         <tt>null</tt> if there was no mapping for <tt>key</tt>
 947      * @throws NullPointerException if the specified key is null
 948      */
 949     public V remove(Object key) {
 950         int hash = hash(key.hashCode());
 951         return segmentFor(hash).remove(key, hash, null);
 952     }
 953 
 954     /**
 955      * {@inheritDoc}
 956      *
 957      * @throws NullPointerException if the specified key is null
 958      */
 959     public boolean remove(Object key, Object value) {
 960         int hash = hash(key.hashCode());
 961         if (value == null)
 962             return false;
 963         return segmentFor(hash).remove(key, hash, value) != null;
 964     }
 965 
 966     /**
 967      * {@inheritDoc}
 968      *
 969      * @throws NullPointerException if any of the arguments are null
 970      */
 971     public boolean replace(K key, V oldValue, V newValue) {
 972         if (oldValue == null || newValue == null)
 973             throw new NullPointerException();
 974         int hash = hash(key.hashCode());
 975         return segmentFor(hash).replace(key, hash, oldValue, newValue);
 976     }
 977 
 978     /**
 979      * {@inheritDoc}
 980      *
 981      * @return the previous value associated with the specified key,
 982      *         or <tt>null</tt> if there was no mapping for the key
 983      * @throws NullPointerException if the specified key or value is null
 984      */
 985     public V replace(K key, V value) {
 986         if (value == null)
 987             throw new NullPointerException();
 988         int hash = hash(key.hashCode());
 989         return segmentFor(hash).replace(key, hash, value);
 990     }
 991 
 992     /**
 993      * Removes all of the mappings from this map.
 994      */
 995     public void clear() {
 996         for (int i = 0; i < segments.length; ++i)
 997             segments[i].clear();
 998     }
 999 
1000     /**
1001      * Returns a {@link Set} view of the keys contained in this map.
1002      * The set is backed by the map, so changes to the map are
1003      * reflected in the set, and vice-versa.  The set supports element
1004      * removal, which removes the corresponding mapping from this map,
1005      * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1006      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1007      * operations.  It does not support the <tt>add</tt> or
1008      * <tt>addAll</tt> operations.
1009      *
1010      * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1011      * that will never throw {@link ConcurrentModificationException},
1012      * and guarantees to traverse elements as they existed upon
1013      * construction of the iterator, and may (but is not guaranteed to)
1014      * reflect any modifications subsequent to construction.
1015      */
1016     public Set<K> keySet() {
1017         Set<K> ks = keySet;
1018         return (ks != null) ? ks : (keySet = new KeySet());
1019     }
1020 
1021     /**
1022      * Returns a {@link Collection} view of the values contained in this map.
1023      * The collection is backed by the map, so changes to the map are
1024      * reflected in the collection, and vice-versa.  The collection
1025      * supports element removal, which removes the corresponding
1026      * mapping from this map, via the <tt>Iterator.remove</tt>,
1027      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1028      * <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
1029      * support the <tt>add</tt> or <tt>addAll</tt> operations.
1030      *
1031      * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1032      * that will never throw {@link ConcurrentModificationException},
1033      * and guarantees to traverse elements as they existed upon
1034      * construction of the iterator, and may (but is not guaranteed to)
1035      * reflect any modifications subsequent to construction.
1036      */
1037     public Collection<V> values() {
1038         Collection<V> vs = values;
1039         return (vs != null) ? vs : (values = new Values());
1040     }
1041 
1042     /**
1043      * Returns a {@link Set} view of the mappings contained in this map.
1044      * The set is backed by the map, so changes to the map are
1045      * reflected in the set, and vice-versa.  The set supports element
1046      * removal, which removes the corresponding mapping from the map,
1047      * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1048      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1049      * operations.  It does not support the <tt>add</tt> or
1050      * <tt>addAll</tt> operations.
1051      *
1052      * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1053      * that will never throw {@link ConcurrentModificationException},
1054      * and guarantees to traverse elements as they existed upon
1055      * construction of the iterator, and may (but is not guaranteed to)
1056      * reflect any modifications subsequent to construction.
1057      */
1058     public Set<Map.Entry<K,V>> entrySet() {
1059         Set<Map.Entry<K,V>> es = entrySet;
1060         return (es != null) ? es : (entrySet = new EntrySet());
1061     }
1062 
1063     /**
1064      * Returns an enumeration of the keys in this table.
1065      *
1066      * @return an enumeration of the keys in this table
1067      * @see #keySet()
1068      */
1069     public Enumeration<K> keys() {
1070         return new KeyIterator();
1071     }
1072 
1073     /**
1074      * Returns an enumeration of the values in this table.
1075      *
1076      * @return an enumeration of the values in this table
1077      * @see #values()
1078      */
1079     public Enumeration<V> elements() {
1080         return new ValueIterator();
1081     }
1082 
1083     /* ---------------- Iterator Support -------------- */
1084 
1085     abstract class HashIterator {
1086         int nextSegmentIndex;
1087         int nextTableIndex;
1088         HashEntry<K,V>[] currentTable;
1089         HashEntry<K, V> nextEntry;
1090         HashEntry<K, V> lastReturned;
1091 
1092         HashIterator() {
1093             nextSegmentIndex = segments.length - 1;
1094             nextTableIndex = -1;
1095             advance();
1096         }
1097 
1098         public boolean hasMoreElements() { return hasNext(); }
1099 
1100         final void advance() {
1101             if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1102                 return;
1103 
1104             while (nextTableIndex >= 0) {
1105                 if ( (nextEntry = currentTable[nextTableIndex--]) != null)
1106                     return;
1107             }
1108 
1109             while (nextSegmentIndex >= 0) {
1110                 Segment<K,V> seg = segments[nextSegmentIndex--];
1111                 if (seg.count != 0) {
1112                     currentTable = seg.table;
1113                     for (int j = currentTable.length - 1; j >= 0; --j) {
1114                         if ( (nextEntry = currentTable[j]) != null) {
1115                             nextTableIndex = j - 1;
1116                             return;
1117                         }
1118                     }
1119                 }
1120             }
1121         }
1122 
1123         public boolean hasNext() { return nextEntry != null; }
1124 
1125         HashEntry<K,V> nextEntry() {
1126             if (nextEntry == null)
1127                 throw new NoSuchElementException();
1128             lastReturned = nextEntry;
1129             advance();
1130             return lastReturned;
1131         }
1132 
1133         public void remove() {
1134             if (lastReturned == null)
1135                 throw new IllegalStateException();
1136             ConcurrentHashMap.this.remove(lastReturned.key);
1137             lastReturned = null;
1138         }
1139     }
1140 
1141     final class KeyIterator
1142         extends HashIterator
1143         implements Iterator<K>, Enumeration<K>
1144     {
1145         public K next()        { return super.nextEntry().key; }
1146         public K nextElement() { return super.nextEntry().key; }
1147     }
1148 
1149     final class ValueIterator
1150         extends HashIterator
1151         implements Iterator<V>, Enumeration<V>
1152     {
1153         public V next()        { return super.nextEntry().value; }
1154         public V nextElement() { return super.nextEntry().value; }
1155     }
1156 
1157     /**
1158      * Custom Entry class used by EntryIterator.next(), that relays
1159      * setValue changes to the underlying map.
1160      */
1161     final class WriteThroughEntry
1162         extends AbstractMap.SimpleEntry<K,V>
1163     {
1164         WriteThroughEntry(K k, V v) {
1165             super(k,v);
1166         }
1167 
1168         /**
1169          * Set our entry's value and write through to the map. The
1170          * value to return is somewhat arbitrary here. Since a
1171          * WriteThroughEntry does not necessarily track asynchronous
1172          * changes, the most recent "previous" value could be
1173          * different from what we return (or could even have been
1174          * removed in which case the put will re-establish). We do not
1175          * and cannot guarantee more.
1176          */
1177         public V setValue(V value) {
1178             if (value == null) throw new NullPointerException();
1179             V v = super.setValue(value);
1180             ConcurrentHashMap.this.put(getKey(), value);
1181             return v;
1182         }
1183     }
1184 
1185     final class EntryIterator
1186         extends HashIterator
1187         implements Iterator<Entry<K,V>>
1188     {
1189         public Map.Entry<K,V> next() {
1190             HashEntry<K,V> e = super.nextEntry();
1191             return new WriteThroughEntry(e.key, e.value);
1192         }
1193     }
1194 
1195     final class KeySet extends AbstractSet<K> {
1196         public Iterator<K> iterator() {
1197             return new KeyIterator();
1198         }
1199         public int size() {
1200             return ConcurrentHashMap.this.size();
1201         }
1202         public boolean isEmpty() {
1203             return ConcurrentHashMap.this.isEmpty();
1204         }
1205         public boolean contains(Object o) {
1206             return ConcurrentHashMap.this.containsKey(o);
1207         }
1208         public boolean remove(Object o) {
1209             return ConcurrentHashMap.this.remove(o) != null;
1210         }
1211         public void clear() {
1212             ConcurrentHashMap.this.clear();
1213         }
1214     }
1215 
1216     final class Values extends AbstractCollection<V> {
1217         public Iterator<V> iterator() {
1218             return new ValueIterator();
1219         }
1220         public int size() {
1221             return ConcurrentHashMap.this.size();
1222         }
1223         public boolean isEmpty() {
1224             return ConcurrentHashMap.this.isEmpty();
1225         }
1226         public boolean contains(Object o) {
1227             return ConcurrentHashMap.this.containsValue(o);
1228         }
1229         public void clear() {
1230             ConcurrentHashMap.this.clear();
1231         }
1232     }
1233 
1234     final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1235         public Iterator<Map.Entry<K,V>> iterator() {
1236             return new EntryIterator();
1237         }
1238         public boolean contains(Object o) {
1239             if (!(o instanceof Map.Entry))
1240                 return false;
1241             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1242             V v = ConcurrentHashMap.this.get(e.getKey());
1243             return v != null && v.equals(e.getValue());
1244         }
1245         public boolean remove(Object o) {
1246             if (!(o instanceof Map.Entry))
1247                 return false;
1248             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1249             return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1250         }
1251         public int size() {
1252             return ConcurrentHashMap.this.size();
1253         }
1254         public boolean isEmpty() {
1255             return ConcurrentHashMap.this.isEmpty();
1256         }
1257         public void clear() {
1258             ConcurrentHashMap.this.clear();
1259         }
1260     }
1261 
1262     /* ---------------- Serialization Support -------------- */
1263 
1264     /**
1265      * Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1266      * stream (i.e., serialize it).
1267      * @param s the stream
1268      * @serialData
1269      * the key (Object) and value (Object)
1270      * for each key-value mapping, followed by a null pair.
1271      * The key-value mappings are emitted in no particular order.
1272      */
1273     private void writeObject(java.io.ObjectOutputStream s) throws IOException {
1274         s.defaultWriteObject();
1275 
1276         for (int k = 0; k < segments.length; ++k) {
1277             Segment<K,V> seg = segments[k];
1278             seg.lock();
1279             try {
1280                 HashEntry<K,V>[] tab = seg.table;
1281                 for (int i = 0; i < tab.length; ++i) {
1282                     for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
1283                         s.writeObject(e.key);
1284                         s.writeObject(e.value);
1285                     }
1286                 }
1287             } finally {
1288                 seg.unlock();
1289             }
1290         }
1291         s.writeObject(null);
1292         s.writeObject(null);
1293     }
1294 
1295     /**
1296      * Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1297      * stream (i.e., deserialize it).
1298      * @param s the stream
1299      */
1300     private void readObject(java.io.ObjectInputStream s)
1301         throws IOException, ClassNotFoundException {
1302         s.defaultReadObject();
1303 
1304         // Initialize each segment to be minimally sized, and let grow.
1305         for (int i = 0; i < segments.length; ++i) {
1306             segments[i].setTable(new HashEntry[1]);
1307         }
1308 
1309         // Read the keys and values, and put the mappings in the table
1310         for (;;) {
1311             K key = (K) s.readObject();
1312             V value = (V) s.readObject();
1313             if (key == null)
1314                 break;
1315             put(key, value);
1316         }
1317     }
1318 }