Source for java.util.concurrent.ConcurrentHashMap

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