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