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