ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java
Revision: 1.57
Committed: Mon Mar 7 23:49:21 2005 UTC (19 years, 2 months ago) by dl
Branch: MAIN
Changes since 1.56: +15 -15 lines
Log Message:
Javadoc improvements

File Contents

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