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