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. Sun designates this
7 * particular file as subject to the "Classpath" exception as provided
8 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
21 * CA 95054 USA or visit www.sun.com if you need additional information or
22 * have any 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 }
Save This Page