Java > Open Source Codes > java > util > concurrent > ConcurrentHashMap


1 /*
2  * @(#)ConcurrentHashMap.java 1.10 04/07/12
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN 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
38  * {@link ConcurrentModificationException}. However, iterators are
39  * designed to be used by only one thread at a time.
40  *
41  * <p> The allowed concurrency among update operations is guided by
42  * the optional <tt>concurrencyLevel</tt> constructor argument
43  * (default 16), which is used as a hint for internal sizing. The
44  * table is internally partitioned to try to permit the indicated
45  * number of concurrent updates without contention. Because placement
46  * in hash tables is essentially random, the actual concurrency will
47  * vary. Ideally, you should choose a value to accommodate as many
48  * threads as will ever concurrently modify the table. Using a
49  * significantly higher value than you need can waste space and time,
50  * and a significantly lower value can lead to thread contention. But
51  * overestimates and underestimates within an order of magnitude do
52  * not usually have much noticeable impact. A value of one is
53  * appropriate when it is known that only one thread will modify and
54  * all others will only read. Also, resizing this or any other kind of
55  * hash table is a relatively slow operation, so, when possible, it is
56  * a good idea to provide estimates of expected table sizes in
57  * constructors.
58  *
59  * <p>This class and its views and iterators implement all of the
60  * <em>optional</em> methods of the {@link Map} and {@link Iterator}
61  * interfaces.
62  *
63  * <p> Like {@link java.util.Hashtable} but unlike {@link
64  * java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
65  * used as a key or value.
66  *
67  * <p>This class is a member of the
68  * <a HREF="{@docRoot}/../guide/collections/index.html">
69  * Java Collections Framework</a>.
70  *
71  * @since 1.5
72  * @author Doug Lea
73  * @param <K> the type of keys maintained by this map
74  * @param <V> the type of mapped values
75  */
76 public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
77         implements ConcurrentMap <K, V>, Serializable {
78     private static final long serialVersionUID = 7249069246763182397L;
79
80     /*
81      * The basic strategy is to subdivide the table among Segments,
82      * each of which itself is a concurrently readable hash table.
83      */
84
85     /* ---------------- Constants -------------- */
86
87     /**
88      * The default initial number of table slots for this table.
89      * Used when not otherwise specified in constructor.
90      */
91     static int DEFAULT_INITIAL_CAPACITY = 16;
92
93     /**
94      * The maximum capacity, used if a higher value is implicitly
95      * specified by either of the constructors with arguments. MUST
96      * be a power of two <= 1<<30 to ensure that entries are indexible
97      * using ints.
98      */
99     static final int MAXIMUM_CAPACITY = 1 << 30;
100
101     /**
102      * The default load factor for this table. Used when not
103      * otherwise specified in constructor.
104      */
105     static final float DEFAULT_LOAD_FACTOR = 0.75f;
106
107     /**
108      * The default number of concurrency control segments.
109      **/
110     static final int DEFAULT_SEGMENTS = 16;
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
609      * capacity, and with default load factor and concurrencyLevel.
610      *
611      * @param initialCapacity the initial capacity. The implementation
612      * performs internal sizing to accommodate this many elements.
613      * @throws IllegalArgumentException if the initial capacity of
614      * elements is negative.
615      */
616     public ConcurrentHashMap(int initialCapacity) {
617         this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
618     }
619
620     /**
621      * Creates a new, empty map with a default initial capacity,
622      * load factor, and concurrencyLevel.
623      */
624     public ConcurrentHashMap() {
625         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
626     }
627
628     /**
629      * Creates a new map with the same mappings as the given map. The
630      * map is created with a capacity of twice the number of mappings in
631      * the given map or 11 (whichever is greater), and a default load factor
632      * and concurrencyLevel.
633      * @param t the map
634      */
635     public ConcurrentHashMap(Map<? extends K, ? extends V> t) {
636         this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
637                       11),
638              DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
639         putAll(t);
640     }
641
642     // inherit Map javadoc
643 public boolean isEmpty() {
644         final Segment[] segments = this.segments;
645         /*
646          * We keep track of per-segment modCounts to avoid ABA
647          * problems in which an element in one segment was added and
648          * in another removed during traversal, in which case the
649          * table was never actually empty at any point. Note the
650          * similar use of modCounts in the size() and containsValue()
651          * methods, which are the only other methods also susceptible
652          * to ABA problems.
653          */
654         int[] mc = new int[segments.length];
655         int mcsum = 0;
656         for (int i = 0; i < segments.length; ++i) {
657             if (segments[i].count != 0)
658                 return false;
659             else
660                 mcsum += mc[i] = segments[i].modCount;
661         }
662         // If mcsum happens to be zero, then we know we got a snapshot
663 // before any modifications at all were made. This is
664 // probably common enough to bother tracking.
665 if (mcsum != 0) {
666             for (int i = 0; i < segments.length; ++i) {
667                 if (segments[i].count != 0 ||
668                     mc[i] != segments[i].modCount)
669                     return false;
670             }
671         }
672         return true;
673     }
674
675     // inherit Map javadoc
676 public int size() {
677         final Segment[] segments = this.segments;
678         long sum = 0;
679         long check = 0;
680         int[] mc = new int[segments.length];
681         // Try a few times to get accurate count. On failure due to
682 // continuous async changes in table, resort to locking.
683 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
684             check = 0;
685             sum = 0;
686             int mcsum = 0;
687             for (int i = 0; i < segments.length; ++i) {
688                 sum += segments[i].count;
689                 mcsum += mc[i] = segments[i].modCount;
690             }
691             if (mcsum != 0) {
692                 for (int i = 0; i < segments.length; ++i) {
693                     check += segments[i].count;
694                     if (mc[i] != segments[i].modCount) {
695                         check = -1; // force retry
696 break;
697                     }
698                 }
699             }
700             if (check == sum)
701                 break;
702         }
703         if (check != sum) { // Resort to locking all segments
704 sum = 0;
705             for (int i = 0; i < segments.length; ++i)
706                 segments[i].lock();
707             for (int i = 0; i < segments.length; ++i)
708                 sum += segments[i].count;
709             for (int i = 0; i < segments.length; ++i)
710                 segments[i].unlock();
711         }
712         if (sum > Integer.MAX_VALUE)
713             return Integer.MAX_VALUE;
714         else
715             return (int)sum;
716     }
717
718
719     /**
720      * Returns the value to which the specified key is mapped in this table.
721      *
722      * @param key a key in the table.
723      * @return the value to which the key is mapped in this table;
724      * <tt>null</tt> if the key is not mapped to any value in
725      * this table.
726      * @throws NullPointerException if the key is
727      * <tt>null</tt>.
728      */
729     public V get(Object key) {
730         int hash = hash(key); // throws NullPointerException if key null
731 return segmentFor(hash).get(key, hash);
732     }
733
734     /**
735      * Tests if the specified object is a key in this table.
736      *
737      * @param key possible key.
738      * @return <tt>true</tt> if and only if the specified object
739      * is a key in this table, as determined by the
740      * <tt>equals</tt> method; <tt>false</tt> otherwise.
741      * @throws NullPointerException if the key is
742      * <tt>null</tt>.
743      */
744     public boolean containsKey(Object key) {
745         int hash = hash(key); // throws NullPointerException if key null
746 return segmentFor(hash).containsKey(key, hash);
747     }
748
749     /**
750      * Returns <tt>true</tt> if this map maps one or more keys to the
751      * specified value. Note: This method requires a full internal
752      * traversal of the hash table, and so is much slower than
753      * method <tt>containsKey</tt>.
754      *
755      * @param value value whose presence in this map is to be tested.
756      * @return <tt>true</tt> if this map maps one or more keys to the
757      * specified value.
758      * @throws NullPointerException if the value is <tt>null</tt>.
759      */
760     public boolean containsValue(Object value) {
761         if (value == null)
762             throw new NullPointerException ();
763         
764         // See explanation of modCount use above
765
766         final Segment[] segments = this.segments;
767         int[] mc = new int[segments.length];
768
769         // Try a few times without locking
770 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
771             int sum = 0;
772             int mcsum = 0;
773             for (int i = 0; i < segments.length; ++i) {
774                 int c = segments[i].count;
775                 mcsum += mc[i] = segments[i].modCount;
776                 if (segments[i].containsValue(value))
777                     return true;
778             }
779             boolean cleanSweep = true;
780             if (mcsum != 0) {
781                 for (int i = 0; i < segments.length; ++i) {
782                     int c = segments[i].count;
783                     if (mc[i] != segments[i].modCount) {
784                         cleanSweep = false;
785                         break;
786                     }
787                 }
788             }
789             if (cleanSweep)
790                 return false;
791         }
792         // Resort to locking all segments
793 for (int i = 0; i < segments.length; ++i)
794             segments[i].lock();
795         boolean found = false;
796         try {
797             for (int i = 0; i < segments.length; ++i) {
798                 if (segments[i].containsValue(value)) {
799                     found = true;
800                     break;
801                 }
802             }
803         } finally {
804             for (int i = 0; i < segments.length; ++i)
805                 segments[i].unlock();
806         }
807         return found;
808     }
809
810     /**
811      * Legacy method testing if some key maps into the specified value
812      * in this table. This method is identical in functionality to
813      * {@link #containsValue}, and exists solely to ensure
814      * full compatibility with class {@link java.util.Hashtable},
815      * which supported this method prior to introduction of the
816      * Java Collections framework.
817
818      * @param value a value to search for.
819      * @return <tt>true</tt> if and only if some key maps to the
820      * <tt>value</tt> argument in this table as
821      * determined by the <tt>equals</tt> method;
822      * <tt>false</tt> otherwise.
823      * @throws NullPointerException if the value is <tt>null</tt>.
824      */
825     public boolean contains(Object value) {
826         return containsValue(value);
827     }
828
829     /**
830      * Maps the specified <tt>key</tt> to the specified
831      * <tt>value</tt> in this table. Neither the key nor the
832      * value can be <tt>null</tt>.
833      *
834      * <p> The value can be retrieved by calling the <tt>get</tt> method
835      * with a key that is equal to the original key.
836      *
837      * @param key the table key.
838      * @param value the value.
839      * @return the previous value of the specified key in this table,
840      * or <tt>null</tt> if it did not have one.
841      * @throws NullPointerException if the key or value is
842      * <tt>null</tt>.
843      */
844     public V put(K key, V value) {
845         if (value == null)
846             throw new NullPointerException ();
847         int hash = hash(key);
848         return segmentFor(hash).put(key, hash, value, false);
849     }
850
851     /**
852      * If the specified key is not already associated
853      * with a value, associate it with the given value.
854      * This is equivalent to
855      * <pre>
856      * if (!map.containsKey(key))
857      * return map.put(key, value);
858      * else
859      * return map.get(key);
860      * </pre>
861      * Except that the action is performed atomically.
862      * @param key key with which the specified value is to be associated.
863      * @param value value to be associated with the specified key.
864      * @return previous value associated with specified key, or <tt>null</tt>
865      * if there was no mapping for key.
866      * @throws NullPointerException if the specified key or value is
867      * <tt>null</tt>.
868      */
869     public V putIfAbsent(K key, V value) {
870         if (value == null)
871             throw new NullPointerException ();
872         int hash = hash(key);
873         return segmentFor(hash).put(key, hash, value, true);
874     }
875
876
877     /**
878      * Copies all of the mappings from the specified map to this one.
879      *
880      * These mappings replace any mappings that this map had for any of the
881      * keys currently in the specified Map.
882      *
883      * @param t Mappings to be stored in this map.
884      */
885     public void putAll(Map<? extends K, ? extends V> t) {
886         for (Iterator<? extends Map.Entry<? extends K, ? extends V>> it = (Iterator<? extends Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
887             Entry<? extends K, ? extends V> e = it.next();
888             put(e.getKey(), e.getValue());
889         }
890     }
891
892     /**
893      * Removes the key (and its corresponding value) from this
894      * table. This method does nothing if the key is not in the table.
895      *
896      * @param key the key that needs to be removed.
897      * @return the value to which the key had been mapped in this table,
898      * or <tt>null</tt> if the key did not have a mapping.
899      * @throws NullPointerException if the key is
900      * <tt>null</tt>.
901      */
902     public V remove(Object key) {
903         int hash = hash(key);
904         return segmentFor(hash).remove(key, hash, null);
905     }
906
907     /**
908      * Remove entry for key only if currently mapped to given value.
909      * Acts as
910      * <pre>
911      * if (map.get(key).equals(value)) {
912      * map.remove(key);
913      * return true;
914      * } else return false;
915      * </pre>
916      * except that the action is performed atomically.
917      * @param key key with which the specified value is associated.
918      * @param value value associated with the specified key.
919      * @return true if the value was removed
920      * @throws NullPointerException if the specified key is
921      * <tt>null</tt>.
922      */
923     public boolean remove(Object key, Object value) {
924         int hash = hash(key);
925         return segmentFor(hash).remove(key, hash, value) != null;
926     }
927
928
929     /**
930      * Replace entry for key only if currently mapped to given value.
931      * Acts as
932      * <pre>
933      * if (map.get(key).equals(oldValue)) {
934      * map.put(key, newValue);
935      * return true;
936      * } else return false;
937      * </pre>
938      * except that the action is performed atomically.
939      * @param key key with which the specified value is associated.
940      * @param oldValue value expected to be associated with the specified key.
941      * @param newValue value to be associated with the specified key.
942      * @return true if the value was replaced
943      * @throws NullPointerException if the specified key or values are
944      * <tt>null</tt>.
945      */
946     public boolean replace(K key, V oldValue, V newValue) {
947         if (oldValue == null || newValue == null)
948             throw new NullPointerException ();
949         int hash = hash(key);
950         return segmentFor(hash).replace(key, hash, oldValue, newValue);
951     }
952
953     /**
954      * Replace entry for key only if currently mapped to some value.
955      * Acts as
956      * <pre>
957      * if ((map.containsKey(key)) {
958      * return map.put(key, value);
959      * } else return null;
960      * </pre>
961      * except that the action is performed atomically.
962      * @param key key with which the specified value is associated.
963      * @param value value to be associated with the specified key.
964      * @return previous value associated with specified key, or <tt>null</tt>
965      * if there was no mapping for key.
966      * @throws NullPointerException if the specified key or value is
967      * <tt>null</tt>.
968      */
969     public V replace(K key, V value) {
970         if (value == null)
971             throw new NullPointerException ();
972         int hash = hash(key);
973         return segmentFor(hash).replace(key, hash, value);
974     }
975
976
977     /**
978      * Removes all mappings from this map.
979      */
980     public void clear() {
981         for (int i = 0; i < segments.length; ++i)
982             segments[i].clear();
983     }
984
985     /**
986      * Returns a set view of the keys contained in this map. The set is
987      * backed by the map, so changes to the map are reflected in the set, and
988      * vice-versa. The set supports element removal, which removes the
989      * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
990      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
991      * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
992      * <tt>addAll</tt> operations.
993      * The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
994      * will never throw {@link java.util.ConcurrentModificationException},
995      * and guarantees to traverse elements as they existed upon
996      * construction of the iterator, and may (but is not guaranteed to)
997      * reflect any modifications subsequent to construction.
998      *
999      * @return a set view of the keys contained in this map.
1000     */
1001    public Set<K> keySet() {
1002        Set<K> ks = keySet;
1003        return (ks != null) ? ks : (keySet = new KeySet());
1004    }
1005
1006
1007    /**
1008     * Returns a collection view of the values contained in this map. The
1009     * collection is backed by the map, so changes to the map are reflected in
1010     * the collection, and vice-versa. The collection supports element
1011     * removal, which removes the corresponding mapping from this map, via the
1012     * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1013     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1014     * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1015     * The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1016     * will never throw {@link java.util.ConcurrentModificationException},
1017     * and guarantees to traverse elements as they existed upon
1018     * construction of the iterator, and may (but is not guaranteed to)
1019     * reflect any modifications subsequent to construction.
1020     *
1021     * @return a collection view of the values contained in this map.
1022     */
1023    public Collection<V> values() {
1024        Collection<V> vs = values;
1025        return (vs != null) ? vs : (values = new Values());
1026    }
1027
1028
1029    /**
1030     * Returns a collection view of the mappings contained in this map. Each
1031     * element in the returned collection is a <tt>Map.Entry</tt>. The
1032     * collection is backed by the map, so changes to the map are reflected in
1033     * the collection, and vice-versa. The collection supports element
1034     * removal, which removes the corresponding mapping from the map, via the
1035     * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1036     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1037     * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1038     * The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1039     * will never throw {@link java.util.ConcurrentModificationException},
1040     * and guarantees to traverse elements as they existed upon
1041     * construction of the iterator, and may (but is not guaranteed to)
1042     * reflect any modifications subsequent to construction.
1043     *
1044     * @return a collection view of the mappings contained in this map.
1045     */
1046    public Set<Map.Entry<K,V>> entrySet() {
1047        Set<Map.Entry<K,V>> es = entrySet;
1048        return (es != null) ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet());
1049    }
1050
1051
1052    /**
1053     * Returns an enumeration of the keys in this table.
1054     *
1055     * @return an enumeration of the keys in this table.
1056     * @see #keySet
1057     */
1058    public Enumeration<K> keys() {
1059        return new KeyIterator();
1060    }
1061
1062    /**
1063     * Returns an enumeration of the values in this table.
1064     *
1065     * @return an enumeration of the values in this table.
1066     * @see #values
1067     */
1068    public Enumeration<V> elements() {
1069        return new ValueIterator();
1070    }
1071
1072    /* ---------------- Iterator Support -------------- */
1073
1074    abstract class HashIterator {
1075        int nextSegmentIndex;
1076        int nextTableIndex;
1077        HashEntry[] currentTable;
1078        HashEntry<K, V> nextEntry;
1079        HashEntry<K, V> lastReturned;
1080
1081        HashIterator() {
1082            nextSegmentIndex = segments.length - 1;
1083            nextTableIndex = -1;
1084            advance();
1085        }
1086
1087        public boolean hasMoreElements() { return hasNext(); }
1088
1089        final void advance() {
1090            if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1091                return;
1092
1093            while (nextTableIndex >= 0) {
1094                if ( (nextEntry = (HashEntry<K,V>)currentTable[nextTableIndex--]) != null)
1095                    return;
1096            }
1097
1098            while (nextSegmentIndex >= 0) {
1099                Segment<K,V> seg = (Segment<K,V>)segments[nextSegmentIndex--];
1100                if (seg.count != 0) {
1101                    currentTable = seg.table;
1102                    for (int j = currentTable.length - 1; j >= 0; --j) {
1103                        if ( (nextEntry = (HashEntry<K,V>)currentTable[j]) != null) {
1104                            nextTableIndex = j - 1;
1105                            return;
1106                        }
1107                    }
1108                }
1109            }
1110        }
1111
1112        public boolean hasNext() { return nextEntry != null; }
1113
1114        HashEntry<K,V> nextEntry() {
1115            if (nextEntry == null)
1116                throw new NoSuchElementException();
1117            lastReturned = nextEntry;
1118            advance();
1119            return lastReturned;
1120        }
1121
1122        public void remove() {
1123            if (lastReturned == null)
1124                throw new IllegalStateException ();
1125            ConcurrentHashMap.this.remove(lastReturned.key);
1126            lastReturned = null;
1127        }
1128    }
1129
1130    final class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1131        public K next() { return super.nextEntry().key; }
1132        public K nextElement() { return super.nextEntry().key; }
1133    }
1134
1135    final class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1136        public V next() { return super.nextEntry().value; }
1137        public V nextElement() { return super.nextEntry().value; }
1138    }
1139
1140    
1141
1142    /**
1143     * Entry iterator. Exported Entry objects must write-through
1144     * changes in setValue, even if the nodes have been cloned. So we
1145     * cannot return internal HashEntry objects. Instead, the iterator
1146     * itself acts as a forwarding pseudo-entry.
1147     */
1148    final class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
1149        public Map.Entry<K,V> next() {
1150            nextEntry();
1151            return this;
1152        }
1153
1154        public K getKey() {
1155            if (lastReturned == null)
1156                throw new IllegalStateException ("Entry was removed");
1157            return lastReturned.key;
1158        }
1159
1160        public V getValue() {
1161            if (lastReturned == null)
1162                throw new IllegalStateException ("Entry was removed");
1163            return ConcurrentHashMap.this.get(lastReturned.key);
1164        }
1165
1166        public V setValue(V value) {
1167            if (lastReturned == null)
1168                throw new IllegalStateException ("Entry was removed");
1169            return ConcurrentHashMap.this.put(lastReturned.key, value);
1170        }
1171
1172        public boolean equals(Object o) {
1173            // If not acting as entry, just use default.
1174 if (lastReturned == null)
1175                return super.equals(o);
1176            if (!(o instanceof Map.Entry))
1177                return false;
1178            Map.Entry e = (Map.Entry)o;
1179            return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1180        }
1181
1182        public int hashCode() {
1183            // If not acting as entry, just use default.
1184 if (lastReturned == null)
1185                return super.hashCode();
1186
1187            Object k = getKey();
1188            Object v = getValue();
1189            return ((k == null) ? 0 : k.hashCode()) ^
1190                   ((v == null) ? 0 : v.hashCode());
1191        }
1192
1193        public String toString() {
1194            // If not acting as entry, just use default.
1195 if (lastReturned == null)
1196                return super.toString();
1197            else
1198                return getKey() + "=" + getValue();
1199        }
1200
1201        boolean eq(Object o1, Object o2) {
1202            return (o1 == null ? o2 == null : o1.equals(o2));
1203        }
1204
1205    }
1206
1207    final class KeySet extends AbstractSet<K> {
1208        public Iterator<K> iterator() {
1209            return new KeyIterator();
1210        }
1211        public int size() {
1212            return ConcurrentHashMap.this.size();
1213        }
1214        public boolean contains(Object o) {
1215            return ConcurrentHashMap.this.containsKey(o);
1216        }
1217        public boolean remove(Object o) {
1218            return ConcurrentHashMap.this.remove(o) != null;
1219        }
1220        public void clear() {
1221            ConcurrentHashMap.this.clear();
1222        }
1223        public Object [] toArray() {
1224            Collection<K> c = new ArrayList<K>();
1225            for (Iterator<K> i = iterator(); i.hasNext(); )
1226                c.add(i.next());
1227            return c.toArray();
1228        }
1229        public <T> T[] toArray(T[] a) {
1230            Collection<K> c = new ArrayList<K>();
1231            for (Iterator<K> i = iterator(); i.hasNext(); )
1232                c.add(i.next());
1233            return c.toArray(a);
1234        }
1235    }
1236
1237    final class Values extends AbstractCollection<V> {
1238        public Iterator<V> iterator() {
1239            return new ValueIterator();
1240        }
1241        public int size() {
1242            return ConcurrentHashMap.this.size();
1243        }
1244        public boolean contains(Object o) {
1245            return ConcurrentHashMap.this.containsValue(o);
1246        }
1247        public void clear() {
1248            ConcurrentHashMap.this.clear();
1249        }
1250        public Object [] toArray() {
1251            Collection<V> c = new ArrayList<V>();
1252            for (Iterator<V> i = iterator(); i.hasNext(); )
1253                c.add(i.next());
1254            return c.toArray();
1255        }
1256        public <T> T[] toArray(T[] a) {
1257            Collection<V> c = new ArrayList<V>();
1258            for (Iterator<V> i = iterator(); i.hasNext(); )
1259                c.add(i.next());
1260            return c.toArray(a);
1261        }
1262    }
1263
1264    final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1265        public Iterator<Map.Entry<K,V>> iterator() {
1266            return new EntryIterator();
1267        }
1268        public boolean contains(Object o) {
1269            if (!(o instanceof Map.Entry))
1270                return false;
1271            Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1272            V v = ConcurrentHashMap.this.get(e.getKey());
1273            return v != null && v.equals(e.getValue());
1274        }
1275        public boolean remove(Object o) {
1276            if (!(o instanceof Map.Entry))
1277                return false;
1278            Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1279            return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1280        }
1281        public int size() {
1282            return ConcurrentHashMap.this.size();
1283        }
1284        public void clear() {
1285            ConcurrentHashMap.this.clear();
1286        }
1287        public Object [] toArray() {
1288            // Since we don't ordinarily have distinct Entry objects, we
1289 // must pack elements using exportable SimpleEntry
1290 Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1291            for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1292                c.add(new SimpleEntry<K,V>(i.next()));
1293            return c.toArray();
1294        }
1295        public <T> T[] toArray(T[] a) {
1296            Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1297            for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1298                c.add(new SimpleEntry<K,V>(i.next()));
1299            return c.toArray(a);
1300        }
1301
1302    }
1303
1304    /**
1305     * This duplicates java.util.AbstractMap.SimpleEntry until this class
1306     * is made accessible.
1307     */
1308    static final class SimpleEntry<K,V> implements Entry<K,V> {
1309        K key;
1310        V value;
1311
1312        public SimpleEntry(K key, V value) {
1313            this.key = key;
1314            this.value = value;
1315        }
1316
1317        public SimpleEntry(Entry<K,V> e) {
1318            this.key = e.getKey();
1319            this.value = e.getValue();
1320        }
1321
1322        public K getKey() {
1323            return key;
1324        }
1325
1326        public V getValue() {
1327            return value;
1328        }
1329
1330        public V setValue(V value) {
1331            V oldValue = this.value;
1332            this.value = value;
1333            return oldValue;
1334        }
1335
1336        public boolean equals(Object o) {
1337            if (!(o instanceof Map.Entry))
1338                return false;
1339            Map.Entry e = (Map.Entry)o;
1340            return eq(key, e.getKey()) && eq(value, e.getValue());
1341        }
1342
1343        public int hashCode() {
1344            return ((key == null) ? 0 : key.hashCode()) ^
1345                   ((value == null) ? 0 : value.hashCode());
1346        }
1347
1348        public String toString() {
1349            return key + "=" + value;
1350        }
1351
1352        static boolean eq(Object o1, Object o2) {
1353            return (o1 == null ? o2 == null : o1.equals(o2));
1354        }
1355    }
1356
1357    /* ---------------- Serialization Support -------------- */
1358
1359    /**
1360     * Save the state of the <tt>ConcurrentHashMap</tt>
1361     * instance to a stream (i.e.,
1362     * serialize it).
1363     * @param s the stream
1364     * @serialData
1365     * the key (Object) and value (Object)
1366     * for each key-value mapping, followed by a null pair.
1367     * The key-value mappings are emitted in no particular order.
1368     */
1369    private void writeObject(java.io.ObjectOutputStream s) throws IOException {
1370        s.defaultWriteObject();
1371
1372        for (int k = 0; k < segments.length; ++k) {
1373            Segment<K,V> seg = (Segment<K,V>)segments[k];
1374            seg.lock();
1375            try {
1376                HashEntry[] tab = seg.table;
1377                for (int i = 0; i < tab.length; ++i) {
1378                    for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i]; e != null; e = e.next) {
1379                        s.writeObject(e.key);
1380                        s.writeObject(e.value);
1381                    }
1382                }
1383            } finally {
1384                seg.unlock();
1385            }
1386        }
1387        s.writeObject(null);
1388        s.writeObject(null);
1389    }
1390
1391    /**
1392     * Reconstitute the <tt>ConcurrentHashMap</tt>
1393     * instance from a stream (i.e.,
1394     * deserialize it).
1395     * @param s the stream
1396     */
1397    private void readObject(java.io.ObjectInputStream s)
1398        throws IOException , ClassNotFoundException {
1399        s.defaultReadObject();
1400
1401        // Initialize each segment to be minimally sized, and let grow.
1402 for (int i = 0; i < segments.length; ++i) {
1403            segments[i].setTable(new HashEntry[1]);
1404        }
1405
1406        // Read the keys and values, and put the mappings in the table
1407 for (;;) {
1408            K key = (K) s.readObject();
1409            V value = (V) s.readObject();
1410            if (key == null)
1411                break;
1412            put(key, value);
1413        }
1414    }
1415}
1416

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags