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