Java > Open Source Codes > EDU > oswego > cs > dl > util > concurrent > ConcurrentHashMap


1 /*
2   File: ConcurrentHashMap
3
4   Written by Doug Lea. Adapted and released, under explicit
5   permission, from JDK1.2 HashMap.java and Hashtable.java which
6   carries the following copyright:
7
8      * Copyright 1997 by Sun Microsystems, Inc.,
9      * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
10      * All rights reserved.
11      *
12      * This software is the confidential and proprietary information
13      * of Sun Microsystems, Inc. ("Confidential Information"). You
14      * shall not disclose such Confidential Information and shall use
15      * it only in accordance with the terms of the license agreement
16      * you entered into with Sun.
17
18   History:
19   Date Who What
20   26nov2000 dl Created, based on ConcurrentReaderHashMap
21   12jan2001 dl public release
22   17nov2001 dl Minor tunings
23   24oct2003 dl Segment implements Serializable
24 */
25
26 package EDU.oswego.cs.dl.util.concurrent;
27
28 import java.util.Map ;
29 import java.util.AbstractMap ;
30 import java.util.AbstractSet ;
31 import java.util.AbstractCollection ;
32 import java.util.Collection ;
33 import java.util.Set ;
34 import java.util.Iterator ;
35 import java.util.Enumeration ;
36 import java.util.NoSuchElementException ;
37
38 import java.io.Serializable ;
39 import java.io.IOException ;
40 import java.io.ObjectInputStream ;
41 import java.io.ObjectOutputStream ;
42
43
44 /**
45  * A version of Hashtable supporting
46  * concurrency for both retrievals and updates:
47  *
48  * <dl>
49  * <dt> Retrievals
50  *
51  * <dd> Retrievals may overlap updates. (This is the same policy as
52  * ConcurrentReaderHashMap.) Successful retrievals using get(key) and
53  * containsKey(key) usually run without locking. Unsuccessful
54  * retrievals (i.e., when the key is not present) do involve brief
55  * synchronization (locking). Because retrieval operations can
56  * ordinarily overlap with update operations (i.e., put, remove, and
57  * their derivatives), retrievals can only be guaranteed to return the
58  * results of the most recently <em>completed</em> operations holding
59  * upon their onset. Retrieval operations may or may not return
60  * results reflecting in-progress writing operations. However, the
61  * retrieval operations do always return consistent results -- either
62  * those holding before any single modification or after it, but never
63  * a nonsense result. For aggregate operations such as putAll and
64  * clear, concurrent reads may reflect insertion or removal of only
65  * some entries.
66  * <p>
67  *
68  * Iterators and Enumerations (i.e., those returned by
69  * keySet().iterator(), entrySet().iterator(), values().iterator(),
70  * keys(), and elements()) return elements reflecting the state of the
71  * hash table at some point at or since the creation of the
72  * iterator/enumeration. They will return at most one instance of
73  * each element (via next()/nextElement()), but might or might not
74  * reflect puts and removes that have been processed since they were
75  * created. They do <em>not</em> throw ConcurrentModificationException.
76  * However, these iterators are designed to be used by only one
77  * thread at a time. Passing an iterator across multiple threads may
78  * lead to unpredictable results if the table is being concurrently
79  * modified. <p>
80  *
81  *
82  * <dt> Updates
83  *
84  * <dd> This class supports a hard-wired preset <em>concurrency
85  * level</em> of 32. This allows a maximum of 32 put and/or remove
86  * operations to proceed concurrently. This level is an upper bound on
87  * concurrency, not a guarantee, since it interacts with how
88  * well-strewn elements are across bins of the table. (The preset
89  * value in part reflects the fact that even on large multiprocessors,
90  * factors other than synchronization tend to be bottlenecks when more
91  * than 32 threads concurrently attempt updates.)
92  * Additionally, operations triggering internal resizing and clearing
93  * do not execute concurrently with any operation.
94  * <p>
95  *
96  * There is <em>NOT</em> any support for locking the entire table to
97  * prevent updates. This makes it imposssible, for example, to
98  * add an element only if it is not already present, since another
99  * thread may be in the process of doing the same thing.
100  * If you need such capabilities, consider instead using the
101  * ConcurrentReaderHashMap class.
102  *
103  * </dl>
104  *
105  * Because of how concurrency control is split up, the
106  * size() and isEmpty() methods require accumulations across 32
107  * control segments, and so might be slightly slower than you expect.
108  * <p>
109  *
110  * This class may be used as a direct replacement for
111  * java.util.Hashtable in any application that does not rely
112  * on the ability to lock the entire table to prevent updates.
113  * As of this writing, it performs much faster than Hashtable in
114  * typical multi-threaded applications with multiple readers and writers.
115  * Like Hashtable but unlike java.util.HashMap,
116  * this class does NOT allow <tt>null</tt> to be used as a key or
117  * value.
118  * <p>
119  *
120  * Implementation note: A slightly
121  * faster implementation of this class will be possible once planned
122  * Java Memory Model revisions are in place.
123  *
124  * <p>[<a HREF="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
125
126  **/
127
128
129 public class ConcurrentHashMap
130   extends AbstractMap
131   implements Map , Cloneable , Serializable {
132
133   /*
134     The basic strategy is an optimistic-style scheme based on
135     the guarantee that the hash table and its lists are always
136     kept in a consistent enough state to be read without locking:
137
138     * Read operations first proceed without locking, by traversing the
139        apparently correct list of the apparently correct bin. If an
140        entry is found, but not invalidated (value field null), it is
141        returned. If not found, operations must recheck (after a memory
142        barrier) to make sure they are using both the right list and
143        the right table (which can change under resizes). If
144        invalidated, reads must acquire main update lock to wait out
145        the update, and then re-traverse.
146
147     * All list additions are at the front of each bin, making it easy
148        to check changes, and also fast to traverse. Entry next
149        pointers are never assigned. Remove() builds new nodes when
150        necessary to preserve this.
151
152     * Remove() (also clear()) invalidates removed nodes to alert read
153        operations that they must wait out the full modifications.
154
155     * Locking for puts, removes (and, when necessary gets, etc)
156       is controlled by Segments, each covering a portion of the
157       table. During operations requiring global exclusivity (mainly
158       resize and clear), ALL of these locks are acquired at once.
159       Note that these segments are NOT contiguous -- they are based
160       on the least 5 bits of hashcodes. This ensures that the same
161       segment controls the same slots before and after resizing, which
162       is necessary for supporting concurrent retrievals. This
163       comes at the price of a mismatch of logical vs physical locality,
164       but this seems not to be a performance problem in practice.
165  
166   */
167
168   /**
169    * The hash table data.
170    */
171   protected transient Entry[] table;
172
173
174   /**
175    * The number of concurrency control segments.
176    * The value can be at most 32 since ints are used
177    * as bitsets over segments. Emprically, it doesn't
178    * seem to pay to decrease it either, so the value should be at least 32.
179    * In other words, do not redefine this :-)
180    **/
181
182   protected static final int CONCURRENCY_LEVEL = 32;
183
184   /**
185    * Mask value for indexing into segments
186    **/
187
188   protected static final int SEGMENT_MASK = CONCURRENCY_LEVEL - 1;
189
190   /**
191    * Bookkeeping for each concurrency control segment.
192    * Each segment contains a local count of the number of
193    * elements in its region.
194    * However, the main use of a Segment is for its lock.
195    **/
196   protected final static class Segment implements Serializable {
197     /**
198      * The number of elements in this segment's region.
199      * It is always updated within synchronized blocks.
200      **/
201     protected int count;
202
203     /**
204      * Get the count under synch.
205      **/
206     protected synchronized int getCount() { return count; }
207
208     /**
209      * Force a synchronization
210      **/
211     protected synchronized void synch() {}
212   }
213
214   /**
215    * The array of concurrency control segments.
216    **/
217
218   protected final Segment[] segments = new Segment[CONCURRENCY_LEVEL];
219
220
221   /**
222    * The default initial number of table slots for this table (32).
223    * Used when not otherwise specified in constructor.
224    **/
225   public static int DEFAULT_INITIAL_CAPACITY = 32;
226
227
228   /**
229    * The minimum capacity, used if a lower value is implicitly specified
230    * by either of the constructors with arguments.
231    * MUST be a power of two.
232    */
233   private static final int MINIMUM_CAPACITY = 32;
234   
235   /**
236    * The maximum capacity, used if a higher value is implicitly specified
237    * by either of the constructors with arguments.
238    * MUST be a power of two <= 1<<30.
239    */
240   private static final int MAXIMUM_CAPACITY = 1 << 30;
241   
242   /**
243    * The default load factor for this table (0.75)
244    * Used when not otherwise specified in constructor.
245    **/
246
247   public static final float DEFAULT_LOAD_FACTOR = 0.75f;
248
249   /**
250    * The load factor for the hash table.
251    *
252    * @serial
253    */
254   protected final float loadFactor;
255
256   /**
257    * Per-segment resize threshold.
258    *
259    * @serial
260    */
261   protected int threshold;
262
263
264   /**
265    * Number of segments voting for resize. The table is
266    * doubled when 1/4 of the segments reach threshold.
267    * Volatile but updated without synch since this is just a heuristic.
268    **/
269
270   protected transient volatile int votesForResize;
271
272
273   /**
274    * Return the number of set bits in w.
275    * For a derivation of this algorithm, see
276    * "Algorithms and data structures with applications to
277    * graphics and geometry", by Jurg Nievergelt and Klaus Hinrichs,
278    * Prentice Hall, 1993.
279    * See also notes by Torsten Sillke at
280    * http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/bitcount
281    **/
282   protected static int bitcount(int w) {
283     w -= (0xaaaaaaaa & w) >>> 1;
284     w = (w & 0x33333333) + ((w >>> 2) & 0x33333333);
285     w = (w + (w >>> 4)) & 0x0f0f0f0f;
286     w += w >>> 8;
287     w += w >>> 16;
288     return w & 0xff;
289   }
290
291   /**
292    * Returns the appropriate capacity (power of two) for the specified
293    * initial capacity argument.
294    */
295   private int p2capacity(int initialCapacity) {
296     int cap = initialCapacity;
297     
298     // Compute the appropriate capacity
299 int result;
300     if (cap > MAXIMUM_CAPACITY || cap < 0) {
301       result = MAXIMUM_CAPACITY;
302     } else {
303       result = MINIMUM_CAPACITY;
304       while (result < cap)
305         result <<= 1;
306     }
307     return result;
308   }
309
310   /**
311    * Return hash code for Object x. Since we are using power-of-two
312    * tables, it is worth the effort to improve hashcode via
313    * the same multiplicative scheme as used in IdentityHashMap.
314    */
315   protected static int hash(Object x) {
316     int h = x.hashCode();
317     // Multiply by 127 (quickly, via shifts), and mix in some high
318 // bits to help guard against bunching of codes that are
319 // consecutive or equally spaced.
320 return ((h << 7) - h + (h >>> 9) + (h >>> 17));
321   }
322
323
324   /**
325    * Check for equality of non-null references x and y.
326    **/
327   protected boolean eq(Object x, Object y) {
328     return x == y || x.equals(y);
329   }
330
331   /** Create table array and set the per-segment threshold **/
332   protected Entry[] newTable(int capacity) {
333     threshold = (int)(capacity * loadFactor / CONCURRENCY_LEVEL) + 1;
334     return new Entry[capacity];
335   }
336
337   /**
338    * Constructs a new, empty map with the specified initial
339    * capacity and the specified load factor.
340    *
341    * @param initialCapacity the initial capacity.
342    * The actual initial capacity is rounded to the nearest power of two.
343    * @param loadFactor the load factor threshold, used to control resizing.
344    * This value is used in an approximate way: When at least
345    * a quarter of the segments of the table reach per-segment threshold, or
346    * one of the segments itself exceeds overall threshold,
347    * the table is doubled.
348    * This will on average cause resizing when the table-wide
349    * load factor is slightly less than the threshold. If you'd like
350    * to avoid resizing, you can set this to a ridiculously large
351    * value.
352    * @throws IllegalArgumentException if the load factor is nonpositive.
353    */
354   public ConcurrentHashMap(int initialCapacity,
355                            float loadFactor) {
356     if (!(loadFactor > 0))
357       throw new IllegalArgumentException ("Illegal Load factor: "+
358                                          loadFactor);
359     this.loadFactor = loadFactor;
360     for (int i = 0; i < segments.length; ++i)
361       segments[i] = new Segment();
362     int cap = p2capacity(initialCapacity);
363     table = newTable(cap);
364   }
365
366   /**
367    * Constructs a new, empty map with the specified initial
368    * capacity and default load factor.
369    *
370    * @param initialCapacity the initial capacity of the
371    * ConcurrentHashMap.
372    * @throws IllegalArgumentException if the initial maximum number
373    * of elements is less
374    * than zero.
375    */
376   public ConcurrentHashMap(int initialCapacity) {
377     this(initialCapacity, DEFAULT_LOAD_FACTOR);
378   }
379
380   /**
381    * Constructs a new, empty map with a default initial capacity
382    * and default load factor.
383    */
384   public ConcurrentHashMap() {
385     this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
386   }
387
388   /**
389    * Constructs a new map with the same mappings as the given map. The
390    * map is created with a capacity of twice the number of mappings in
391    * the given map or 32 (whichever is greater), and a default load factor.
392    */
393   public ConcurrentHashMap(Map t) {
394     this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
395                   MINIMUM_CAPACITY),
396          DEFAULT_LOAD_FACTOR);
397     putAll(t);
398   }
399
400   /**
401    * Returns the number of key-value mappings in this map.
402    *
403    * @return the number of key-value mappings in this map.
404    */
405   public int size() {
406     int c = 0;
407     for (int i = 0; i < segments.length; ++i)
408       c += segments[i].getCount();
409     return c;
410   }
411
412   /**
413    * Returns <tt>true</tt> if this map contains no key-value mappings.
414    *
415    * @return <tt>true</tt> if this map contains no key-value mappings.
416    */
417   public boolean isEmpty() {
418     for (int i = 0; i < segments.length; ++i)
419       if (segments[i].getCount() != 0)
420         return false;
421     return true;
422   }
423
424
425   /**
426    * Returns the value to which the specified key is mapped in this table.
427    *
428    * @param key a key in the table.
429    * @return the value to which the key is mapped in this table;
430    * <code>null</code> if the key is not mapped to any value in
431    * this table.
432    * @exception NullPointerException if the key is
433    * <code>null</code>.
434    * @see #put(Object, Object)
435    */
436   public Object get(Object key) {
437     int hash = hash(key); // throws null pointer exception if key null
438
439     // Try first without locking...
440 Entry[] tab = table;
441     int index = hash & (tab.length - 1);
442     Entry first = tab[index];
443     Entry e;
444
445     for (e = first; e != null; e = e.next) {
446       if (e.hash == hash && eq(key, e.key)) {
447         Object value = e.value;
448         if (value != null)
449           return value;
450         else
451           break;
452       }
453     }
454
455     // Recheck under synch if key apparently not there or interference
456 Segment seg = segments[hash & SEGMENT_MASK];
457     synchronized(seg) {
458       tab = table;
459       index = hash & (tab.length - 1);
460       Entry newFirst = tab[index];
461       if (e != null || first != newFirst) {
462         for (e = newFirst; e != null; e = e.next) {
463           if (e.hash == hash && eq(key, e.key))
464             return e.value;
465         }
466       }
467       return null;
468     }
469   }
470
471   /**
472    * Tests if the specified object is a key in this table.
473    *
474    * @param key possible key.
475    * @return <code>true</code> if and only if the specified object
476    * is a key in this table, as determined by the
477    * <tt>equals</tt> method; <code>false</code> otherwise.
478    * @exception NullPointerException if the key is
479    * <code>null</code>.
480    * @see #contains(Object)
481    */
482
483   public boolean containsKey(Object key) {
484     return get(key) != null;
485   }
486   
487
488   /**
489    * Maps the specified <code>key</code> to the specified
490    * <code>value</code> in this table. Neither the key nor the
491    * value can be <code>null</code>. (Note that this policy is
492    * the same as for java.util.Hashtable, but unlike java.util.HashMap,
493    * which does accept nulls as valid keys and values.)<p>
494    *
495    * The value can be retrieved by calling the <code>get</code> method
496    * with a key that is equal to the original key.
497    *
498    * @param key the table key.
499    * @param value the value.
500    * @return the previous value of the specified key in this table,
501    * or <code>null</code> if it did not have one.
502    * @exception NullPointerException if the key or value is
503    * <code>null</code>.
504    * @see Object#equals(Object)
505    * @see #get(Object)
506    */
507   public Object put(Object key, Object value) {
508     if (value == null)
509       throw new NullPointerException ();
510     
511     int hash = hash(key);
512     Segment seg = segments[hash & SEGMENT_MASK];
513     int segcount;
514     Entry[] tab;
515     int votes;
516
517     synchronized(seg) {
518       tab = table;
519       int index = hash & (tab.length-1);
520       Entry first = tab[index];
521
522       for (Entry e = first; e != null; e = e.next) {
523         if (e.hash == hash && eq(key, e.key)) {
524           Object oldValue = e.value;
525           e.value = value;
526           return oldValue;
527         }
528       }
529
530       // Add to front of list
531 Entry newEntry = new Entry(hash, key, value, first);
532       tab[index] = newEntry;
533
534       if ((segcount = ++seg.count) < threshold)
535         return null;
536
537       int bit = (1 << (hash & SEGMENT_MASK));
538       votes = votesForResize;
539       if ((votes & bit) == 0)
540         votes = votesForResize |= bit;
541     }
542
543     // Attempt resize if 1/4 segs vote,
544 // or if this seg itself reaches the overall threshold.
545 // (The latter check is just a safeguard to avoid pathological cases.)
546 if (bitcount(votes) >= CONCURRENCY_LEVEL / 4 ||
547         segcount > (threshold * CONCURRENCY_LEVEL))
548       resize(0, tab);
549
550     return null;
551   }
552
553   /**
554    * Gather all locks in order to call rehash, by
555    * recursing within synch blocks for each segment index.
556    * @param index the current segment. initially call value must be 0
557    * @param assumedTab the state of table on first call to resize. If
558    * this changes on any call, the attempt is aborted because the
559    * table has already been resized by another thread.
560    */
561
562   protected void resize(int index, Entry[] assumedTab) {
563     Segment seg = segments[index];
564     synchronized(seg) {
565       if (assumedTab == table) {
566         int next = index+1;
567         if (next < segments.length)
568           resize(next, assumedTab);
569         else
570           rehash();
571       }
572     }
573   }
574
575   /**
576    * Rehashes the contents of this map into a new table
577    * with a larger capacity.
578    */
579   protected void rehash() {
580     votesForResize = 0; // reset
581
582     Entry[] oldTable = table;
583     int oldCapacity = oldTable.length;
584
585     if (oldCapacity >= MAXIMUM_CAPACITY) {
586       threshold = Integer.MAX_VALUE; // avoid retriggering
587 return;
588     }
589     
590     int newCapacity = oldCapacity << 1;
591     Entry[] newTable = newTable(newCapacity);
592     int mask = newCapacity - 1;
593
594     /*
595      * Reclassify nodes in each list to new Map. Because we are
596      * using power-of-two expansion, the elements from each bin
597      * must either stay at same index, or move to
598      * oldCapacity+index. We also eliminate unnecessary node
599      * creation by catching cases where old nodes can be reused
600      * because their next fields won't change. Statistically, at
601      * the default threshhold, only about one-sixth of them need
602      * cloning. (The nodes they replace will be garbage
603      * collectable as soon as they are no longer referenced by any
604      * reader thread that may be in the midst of traversing table
605      * right now.)
606      */
607     
608     for (int i = 0; i < oldCapacity ; i++) {
609       // We need to guarantee that any existing reads of old Map can
610 // proceed. So we cannot yet null out each bin.
611 Entry e = oldTable[i];
612       
613       if (e != null) {
614         int idx = e.hash & mask;
615         Entry next = e.next;
616         
617         // Single node on list
618 if (next == null)
619           newTable[idx] = e;
620         
621         else {
622           // Reuse trailing consecutive sequence of all same bit
623 Entry lastRun = e;
624           int lastIdx = idx;
625           for (Entry last = next; last != null; last = last.next) {
626             int k = last.hash & mask;
627             if (k != lastIdx) {
628               lastIdx = k;
629               lastRun = last;
630             }
631           }
632           newTable[lastIdx] = lastRun;
633           
634           // Clone all remaining nodes
635 for (Entry p = e; p != lastRun; p = p.next) {
636             int k = p.hash & mask;
637             newTable[k] = new Entry(p.hash, p.key,
638                                     p.value, newTable[k]);
639           }
640         }
641       }
642     }
643     
644     table = newTable;
645   }
646
647
648   /**
649    * Removes the key (and its corresponding value) from this
650    * table. This method does nothing if the key is not in the table.
651    *
652    * @param key the key that needs to be removed.
653    * @return the value to which the key had been mapped in this table,
654    * or <code>null</code> if the key did not have a mapping.
655    * @exception NullPointerException if the key is
656    * <code>null</code>.
657    */
658   public Object remove(Object key) {
659     return remove(key, null);
660   }
661
662
663   /**
664    * Removes the (key, value) pair from this
665    * table. This method does nothing if the key is not in the table,
666    * or if the key is associated with a different value. This method
667    * is needed by EntrySet.
668    *
669    * @param key the key that needs to be removed.
670    * @param value the associated value. If the value is null,
671    * it means "any value".
672    * @return the value to which the key had been mapped in this table,
673    * or <code>null</code> if the key did not have a mapping.
674    * @exception NullPointerException if the key is
675    * <code>null</code>.
676    */
677
678   protected Object remove(Object key, Object value) {
679     /*
680       Find the entry, then
681         1. Set value field to null, to force get() to retry
682         2. Rebuild the list without this entry.
683            All entries following removed node can stay in list, but
684            all preceeding ones need to be cloned. Traversals rely
685            on this strategy to ensure that elements will not be
686           repeated during iteration.
687     */
688
689     int hash = hash(key);
690     Segment seg = segments[hash & SEGMENT_MASK];
691
692     synchronized(seg) {
693       Entry[] tab = table;
694       int index = hash & (tab.length-1);
695       Entry first = tab[index];
696       Entry e = first;
697
698       for (;;) {
699         if (e == null)
700           return null;
701         if (e.hash == hash && eq(key, e.key))
702           break;
703         e = e.next;
704       }
705
706       Object oldValue = e.value;
707       if (value != null && !value.equals(oldValue))
708         return null;
709      
710       e.value = null;
711
712       Entry head = e.next;
713       for (Entry p = first; p != e; p = p.next)
714         head = new Entry(p.hash, p.key, p.value, head);
715       tab[index] = head;
716       seg.count--;
717       return oldValue;
718     }
719   }
720
721
722   /**
723    * Returns <tt>true</tt> if this map maps one or more keys to the
724    * specified value. Note: This method requires a full internal
725    * traversal of the hash table, and so is much slower than
726    * method <tt>containsKey</tt>.
727    *
728    * @param value value whose presence in this map is to be tested.
729    * @return <tt>true</tt> if this map maps one or more keys to the
730    * specified value.
731    * @exception NullPointerException if the value is <code>null</code>.
732    */
733   public boolean containsValue(Object value) {
734
735     if (value == null) throw new NullPointerException ();
736
737     for (int s = 0; s < segments.length; ++s) {
738       Segment seg = segments[s];
739       Entry[] tab;
740       synchronized(seg) { tab = table; }
741       for (int i = s; i < tab.length; i+= segments.length) {
742         for (Entry e = tab[i]; e != null; e = e.next)
743           if (value.equals(e.value))
744             return true;
745       }
746     }
747     return false;
748   }
749
750   /**
751    * Tests if some key maps into the specified value in this table.
752    * This operation is more expensive than the <code>containsKey</code>
753    * method.<p>
754    *
755    * Note that this method is identical in functionality to containsValue,
756    * (which is part of the Map interface in the collections framework).
757    *
758    * @param value a value to search for.
759    * @return <code>true</code> if and only if some key maps to the
760    * <code>value</code> argument in this table as
761    * determined by the <tt>equals</tt> method;
762    * <code>false</code> otherwise.
763    * @exception NullPointerException if the value is <code>null</code>.
764    * @see #containsKey(Object)
765    * @see #containsValue(Object)
766    * @see Map
767    */
768
769   public boolean contains(Object value) {
770     return containsValue(value);
771   }
772
773   /**
774    * Copies all of the mappings from the specified map to this one.
775    *
776    * These mappings replace any mappings that this map had for any of the
777    * keys currently in the specified Map.
778    *
779    * @param t Mappings to be stored in this map.
780    */
781
782   public void putAll(Map t) {
783     int n = t.size();
784     if (n == 0)
785       return;
786
787     // Expand enough to hold at least n elements without resizing.
788 // We can only resize table by factor of two at a time.
789 // It is faster to rehash with fewer elements, so do it now.
790 for(;;) {
791       Entry[] tab;
792       int max;
793       synchronized(segments[0]) { // must synch on some segment. pick 0.
794 tab = table;
795         max = threshold * CONCURRENCY_LEVEL;
796       }
797       if (n < max)
798         break;
799       resize(0, tab);
800     }
801
802     for (Iterator it = t.entrySet().iterator(); it.hasNext();) {
803       Map.Entry entry = (Map.Entry ) it.next();
804       put(entry.getKey(), entry.getValue());
805     }
806   }
807
808   /**
809    * Removes all mappings from this map.
810    */
811
812   public void clear() {
813     // We don't need all locks at once so long as locks
814 // are obtained in low to high order
815 for (int s = 0; s < segments.length; ++s) {
816       Segment seg = segments[s];
817       synchronized(seg) {
818         Entry[] tab = table;
819         for (int i = s; i < tab.length; i+= segments.length) {
820           for (Entry e = tab[i]; e != null; e = e.next)
821             e.value = null;
822           tab[i] = null;
823           seg.count = 0;
824         }
825       }
826     }
827   }
828
829   /**
830    * Returns a shallow copy of this
831    * <tt>ConcurrentHashMap</tt> instance: the keys and
832    * values themselves are not cloned.
833    *
834    * @return a shallow copy of this map.
835    */
836
837   public Object clone() {
838     // We cannot call super.clone, since it would share final segments array,
839 // and there's no way to reassign finals.
840 return new ConcurrentHashMap(this);
841   }
842
843   // Views
844
845   protected transient Set keySet = null;
846   protected transient Set entrySet = null;
847   protected transient Collection values = null;
848
849   /**
850    * Returns a set view of the keys contained in this map. The set is
851    * backed by the map, so changes to the map are reflected in the set, and
852    * vice-versa. The set supports element removal, which removes the
853    * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
854    * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
855    * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
856    * <tt>addAll</tt> operations.
857    *
858    * @return a set view of the keys contained in this map.
859    */
860   
861   public Set keySet() {
862     Set ks = keySet;
863     return (ks != null)? ks : (keySet = new KeySet());
864   }
865   
866   private class KeySet extends AbstractSet {
867     public Iterator iterator() {
868       return new KeyIterator();
869     }
870     public int size() {
871       return ConcurrentHashMap.this.size();
872     }
873     public boolean contains(Object o) {
874       return ConcurrentHashMap.this.containsKey(o);
875     }
876     public boolean remove(Object o) {
877       return ConcurrentHashMap.this.remove(o) != null;
878     }
879     public void clear() {
880       ConcurrentHashMap.this.clear();
881     }
882   }
883
884   /**
885    * Returns a collection view of the values contained in this map. The
886    * collection is backed by the map, so changes to the map are reflected in
887    * the collection, and vice-versa. The collection supports element
888    * removal, which removes the corresponding mapping from this map, via the
889    * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
890    * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
891    * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
892    *
893    * @return a collection view of the values contained in this map.
894    */
895   
896   public Collection values() {
897     Collection vs = values;
898     return (vs != null)? vs : (values = new Values());
899   }
900   
901   private class Values extends AbstractCollection {
902     public Iterator iterator() {
903       return new ValueIterator();
904     }
905     public int size() {
906       return ConcurrentHashMap.this.size();
907     }
908     public boolean contains(Object o) {
909       return ConcurrentHashMap.this.containsValue(o);
910     }
911     public void clear() {
912       ConcurrentHashMap.this.clear();
913     }
914   }
915
916   /**
917    * Returns a collection view of the mappings contained in this map. Each
918    * element in the returned collection is a <tt>Map.Entry</tt>. The
919    * collection is backed by the map, so changes to the map are reflected in
920    * the collection, and vice-versa. The collection supports element
921    * removal, which removes the corresponding mapping from the map, via the
922    * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
923    * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
924    * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
925    *
926    * @return a collection view of the mappings contained in this map.
927    */
928   
929   public Set entrySet() {
930     Set es = entrySet;
931     return (es != null) ? es : (entrySet = new EntrySet());
932   }
933
934   private class EntrySet extends AbstractSet {
935     public Iterator iterator() {
936       return new HashIterator();
937     }
938     public boolean contains(Object o) {
939       if (!(o instanceof Map.Entry ))
940         return false;
941       Map.Entry entry = (Map.Entry )o;
942       Object v = ConcurrentHashMap.this.get(entry.getKey());
943       return v != null && v.equals(entry.getValue());
944     }
945     public boolean remove(Object o) {
946       if (!(o instanceof Map.Entry ))
947         return false;
948       Map.Entry e = (Map.Entry )o;
949       return ConcurrentHashMap.this.remove(e.getKey(), e.getValue()) != null;
950     }
951     public int size() {
952       return ConcurrentHashMap.this.size();
953     }
954     public void clear() {
955       ConcurrentHashMap.this.clear();
956     }
957   }
958
959   /**
960    * Returns an enumeration of the keys in this table.
961    *
962    * @return an enumeration of the keys in this table.
963    * @see Enumeration
964    * @see #elements()
965    * @see #keySet()
966    * @see Map
967    */
968   public Enumeration keys() {
969     return new KeyIterator();
970   }
971
972   /**
973    * Returns an enumeration of the values in this table.
974    * Use the Enumeration methods on the returned object to fetch the elements
975    * sequentially.
976    *
977    * @return an enumeration of the values in this table.
978    * @see java.util.Enumeration
979    * @see #keys()
980    * @see #values()
981    * @see Map
982    */
983   
984   public Enumeration elements() {
985     return new ValueIterator();
986   }
987
988   /**
989    * ConcurrentHashMap collision list entry.
990    */
991
992   protected static class Entry implements Map.Entry {
993     /*
994        The use of volatile for value field ensures that
995        we can detect status changes without synchronization.
996        The other fields are never changed, and are
997        marked as final.
998     */
999
1000    protected final Object key;
1001    protected volatile Object value;
1002    protected final int hash;
1003    protected final Entry next;
1004
1005    Entry(int hash, Object key, Object value, Entry next) {
1006      this.value = value;
1007      this.hash = hash;
1008      this.key = key;
1009      this.next = next;
1010    }
1011
1012    // Map.Entry Ops
1013
1014    public Object getKey() {
1015      return key;
1016    }
1017
1018    /**
1019     * Get the value. Note: In an entrySet or entrySet.iterator,
1020     * unless you can guarantee lack of concurrent modification,
1021     * <tt>getValue</tt> <em>might</em> return null, reflecting the
1022     * fact that the entry has been concurrently removed. However,
1023     * there are no assurances that concurrent removals will be
1024     * reflected using this method.
1025     *
1026     * @return the current value, or null if the entry has been
1027     * detectably removed.
1028     **/
1029    public Object getValue() {
1030      return value;
1031    }
1032
1033    /**
1034     * Set the value of this entry. Note: In an entrySet or
1035     * entrySet.iterator), unless you can guarantee lack of concurrent
1036     * modification, <tt>setValue</tt> is not strictly guaranteed to
1037     * actually replace the value field obtained via the <tt>get</tt>
1038     * operation of the underlying hash table in multithreaded
1039     * applications. If iterator-wide synchronization is not used,
1040     * and any other concurrent <tt>put</tt> or <tt>remove</tt>
1041     * operations occur, sometimes even to <em>other</em> entries,
1042     * then this change is not guaranteed to be reflected in the hash
1043     * table. (It might, or it might not. There are no assurances
1044     * either way.)
1045     *
1046     * @param value the new value.
1047     * @return the previous value, or null if entry has been detectably
1048     * removed.
1049     * @exception NullPointerException if the value is <code>null</code>.
1050     *
1051     **/
1052
1053    public Object setValue(Object value) {
1054      if (value == null)
1055        throw new NullPointerException ();
1056      Object oldValue = this.value;
1057      this.value = value;
1058      return oldValue;
1059    }
1060
1061    public boolean equals(Object o) {
1062      if (!(o instanceof Map.Entry ))
1063        return false;
1064      Map.Entry e = (Map.Entry )o;
1065      return (key.equals(e.getKey()) && value.equals(e.getValue()));
1066    }
1067    
1068    public int hashCode() {
1069      return key.hashCode() ^ value.hashCode();
1070    }
1071    
1072    public String toString() {
1073      return key + "=" + value;
1074    }
1075
1076  }
1077
1078  protected class HashIterator implements Iterator , Enumeration {
1079    protected final Entry[] tab; // snapshot of table
1080 protected int index; // current slot
1081 protected Entry entry = null; // current node of slot
1082 protected Object currentKey; // key for current node
1083 protected Object currentValue; // value for current node
1084 protected Entry lastReturned = null; // last node returned by next
1085
1086    protected HashIterator() {
1087      // force all segments to synch
1088 synchronized(segments[0]) { tab = table; }
1089      for (int i = 1; i < segments.length; ++i) segments[i].synch();
1090      index = tab.length - 1;
1091    }
1092
1093    public boolean hasMoreElements() { return hasNext(); }
1094    public Object nextElement() { return next(); }
1095
1096    public boolean hasNext() {
1097      /*
1098        currentkey and currentValue are set here to ensure that next()
1099        returns normally if hasNext() returns true. This avoids
1100        surprises especially when final element is removed during
1101        traversal -- instead, we just ignore the removal during
1102        current traversal.
1103      */
1104
1105      for (;;) {
1106        if (entry != null) {
1107          Object v = entry.value;
1108          if (v != null) {
1109            currentKey = entry.key;
1110            currentValue = v;
1111            return true;
1112          }
1113          else
1114            entry = entry.next;
1115        }
1116
1117        while (entry == null && index >= 0)
1118          entry = tab[index--];
1119
1120        if (entry == null) {
1121          currentKey = currentValue = null;
1122          return false;
1123        }
1124      }
1125    }
1126
1127    protected Object returnValueOfNext() { return entry; }
1128
1129    public Object next() {
1130      if (currentKey == null && !hasNext())
1131        throw new NoSuchElementException ();
1132
1133      Object result = returnValueOfNext();
1134      lastReturned = entry;
1135      currentKey = currentValue = null;
1136      entry = entry.next;
1137      return result;
1138    }
1139
1140    public void remove() {
1141      if (lastReturned == null)
1142        throw new IllegalStateException ();
1143      ConcurrentHashMap.this.remove(lastReturned.key);
1144      lastReturned = null;
1145    }
1146
1147  }
1148
1149  protected class KeyIterator extends HashIterator {
1150    protected Object returnValueOfNext() { return currentKey; }
1151  }
1152  
1153  protected class ValueIterator extends HashIterator {
1154    protected Object returnValueOfNext() { return currentValue; }
1155  }
1156  
1157  /**
1158   * Save the state of the <tt>ConcurrentHashMap</tt>
1159   * instance to a stream (i.e.,
1160   * serialize it).
1161   *
1162   * @serialData
1163   * An estimate of the table size, followed by
1164   * the key (Object) and value (Object)
1165   * for each key-value mapping, followed by a null pair.
1166   * The key-value mappings are emitted in no particular order.
1167   */
1168
1169  private void writeObject(java.io.ObjectOutputStream s)
1170    throws IOException {
1171    // Write out the loadfactor, and any hidden stuff
1172 s.defaultWriteObject();
1173
1174    // Write out capacity estimate. It is OK if this
1175 // changes during the write, since it is only used by
1176 // readObject to set initial capacity, to avoid needless resizings.
1177
1178    int cap;
1179    synchronized(segments[0]) { cap = table.length; }
1180    s.writeInt(cap);
1181
1182    // Write out keys and values (alternating)
1183 for (int k = 0; k < segments.length; ++k) {
1184      Segment seg = segments[k];
1185      Entry[] tab;
1186      synchronized(seg) { tab = table; }
1187      for (int i = k; i < tab.length; i+= segments.length) {
1188        for (Entry e = tab[i]; e != null; e = e.next) {
1189          s.writeObject(e.key);
1190          s.writeObject(e.value);
1191        }
1192      }
1193    }
1194
1195    s.writeObject(null);
1196    s.writeObject(null);
1197  }
1198
1199  /**
1200   * Reconstitute the <tt>ConcurrentHashMap</tt>
1201   * instance from a stream (i.e.,
1202   * deserialize it).
1203   */
1204  private void readObject(java.io.ObjectInputStream s)
1205    throws IOException , ClassNotFoundException {
1206    // Read in the threshold, loadfactor, and any hidden stuff
1207 s.defaultReadObject();
1208
1209    int cap = s.readInt();
1210    table = newTable(cap);
1211    for (int i = 0; i < segments.length; ++i)
1212      segments[i] = new Segment();
1213
1214
1215    // Read the keys and values, and put the mappings in the table
1216 for (;;) {
1217      Object key = s.readObject();
1218      Object value = s.readObject();
1219      if (key == null)
1220        break;
1221      put(key, value);
1222    }
1223  }
1224}
1225

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags