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