0001 /*
0002 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0003 *
0004 * This code is free software; you can redistribute it and/or modify it
0005 * under the terms of the GNU General Public License version 2 only, as
0006 * published by the Free Software Foundation. Sun designates this
0007 * particular file as subject to the "Classpath" exception as provided
0008 * by Sun in the LICENSE file that accompanied this code.
0009 *
0010 * This code is distributed in the hope that it will be useful, but WITHOUT
0011 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0012 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0013 * version 2 for more details (a copy is included in the LICENSE file that
0014 * accompanied this code).
0015 *
0016 * You should have received a copy of the GNU General Public License version
0017 * 2 along with this work; if not, write to the Free Software Foundation,
0018 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0019 *
0020 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0021 * CA 95054 USA or visit www.sun.com if you need additional information or
0022 * have any questions.
0023 */
0024
0025 /*
0026 * This file is available under and governed by the GNU General Public
0027 * License version 2 only, as published by the Free Software Foundation.
0028 * However, the following notice accompanied the original version of this
0029 * file:
0030 *
0031 * Written by Doug Lea with assistance from members of JCP JSR-166
0032 * Expert Group and released to the public domain, as explained at
0033 * http://creativecommons.org/licenses/publicdomain
0034 */
0035
0036 package java.util.concurrent;
0037
0038 import java.util.concurrent.locks.*;
0039 import java.util.*;
0040 import java.io.Serializable;
0041 import java.io.IOException;
0042 import java.io.ObjectInputStream;
0043 import java.io.ObjectOutputStream;
0044
0045 /**
0046 * A hash table supporting full concurrency of retrievals and
0047 * adjustable expected concurrency for updates. This class obeys the
0048 * same functional specification as {@link java.util.Hashtable}, and
0049 * includes versions of methods corresponding to each method of
0050 * <tt>Hashtable</tt>. However, even though all operations are
0051 * thread-safe, retrieval operations do <em>not</em> entail locking,
0052 * and there is <em>not</em> any support for locking the entire table
0053 * in a way that prevents all access. This class is fully
0054 * interoperable with <tt>Hashtable</tt> in programs that rely on its
0055 * thread safety but not on its synchronization details.
0056 *
0057 * <p> Retrieval operations (including <tt>get</tt>) generally do not
0058 * block, so may overlap with update operations (including
0059 * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
0060 * of the most recently <em>completed</em> update operations holding
0061 * upon their onset. For aggregate operations such as <tt>putAll</tt>
0062 * and <tt>clear</tt>, concurrent retrievals may reflect insertion or
0063 * removal of only some entries. Similarly, Iterators and
0064 * Enumerations return elements reflecting the state of the hash table
0065 * at some point at or since the creation of the iterator/enumeration.
0066 * They do <em>not</em> throw {@link ConcurrentModificationException}.
0067 * However, iterators are designed to be used by only one thread at a time.
0068 *
0069 * <p> The allowed concurrency among update operations is guided by
0070 * the optional <tt>concurrencyLevel</tt> constructor argument
0071 * (default <tt>16</tt>), which is used as a hint for internal sizing. The
0072 * table is internally partitioned to try to permit the indicated
0073 * number of concurrent updates without contention. Because placement
0074 * in hash tables is essentially random, the actual concurrency will
0075 * vary. Ideally, you should choose a value to accommodate as many
0076 * threads as will ever concurrently modify the table. Using a
0077 * significantly higher value than you need can waste space and time,
0078 * and a significantly lower value can lead to thread contention. But
0079 * overestimates and underestimates within an order of magnitude do
0080 * not usually have much noticeable impact. A value of one is
0081 * appropriate when it is known that only one thread will modify and
0082 * all others will only read. Also, resizing this or any other kind of
0083 * hash table is a relatively slow operation, so, when possible, it is
0084 * a good idea to provide estimates of expected table sizes in
0085 * constructors.
0086 *
0087 * <p>This class and its views and iterators implement all of the
0088 * <em>optional</em> methods of the {@link Map} and {@link Iterator}
0089 * interfaces.
0090 *
0091 * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class
0092 * does <em>not</em> allow <tt>null</tt> to be used as a key or value.
0093 *
0094 * <p>This class is a member of the
0095 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
0096 * Java Collections Framework</a>.
0097 *
0098 * @since 1.5
0099 * @author Doug Lea
0100 * @param <K> the type of keys maintained by this map
0101 * @param <V> the type of mapped values
0102 */
0103 public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
0104 implements ConcurrentMap<K, V>, Serializable {
0105 private static final long serialVersionUID = 7249069246763182397L;
0106
0107 /*
0108 * The basic strategy is to subdivide the table among Segments,
0109 * each of which itself is a concurrently readable hash table.
0110 */
0111
0112 /* ---------------- Constants -------------- */
0113
0114 /**
0115 * The default initial capacity for this table,
0116 * used when not otherwise specified in a constructor.
0117 */
0118 static final int DEFAULT_INITIAL_CAPACITY = 16;
0119
0120 /**
0121 * The default load factor for this table, used when not
0122 * otherwise specified in a constructor.
0123 */
0124 static final float DEFAULT_LOAD_FACTOR = 0.75f;
0125
0126 /**
0127 * The default concurrency level for this table, used when not
0128 * otherwise specified in a constructor.
0129 */
0130 static final int DEFAULT_CONCURRENCY_LEVEL = 16;
0131
0132 /**
0133 * The maximum capacity, used if a higher value is implicitly
0134 * specified by either of the constructors with arguments. MUST
0135 * be a power of two <= 1<<30 to ensure that entries are indexable
0136 * using ints.
0137 */
0138 static final int MAXIMUM_CAPACITY = 1 << 30;
0139
0140 /**
0141 * The maximum number of segments to allow; used to bound
0142 * constructor arguments.
0143 */
0144 static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
0145
0146 /**
0147 * Number of unsynchronized retries in size and containsValue
0148 * methods before resorting to locking. This is used to avoid
0149 * unbounded retries if tables undergo continuous modification
0150 * which would make it impossible to obtain an accurate result.
0151 */
0152 static final int RETRIES_BEFORE_LOCK = 2;
0153
0154 /* ---------------- Fields -------------- */
0155
0156 /**
0157 * Mask value for indexing into segments. The upper bits of a
0158 * key's hash code are used to choose the segment.
0159 */
0160 final int segmentMask;
0161
0162 /**
0163 * Shift value for indexing within segments.
0164 */
0165 final int segmentShift;
0166
0167 /**
0168 * The segments, each of which is a specialized hash table
0169 */
0170 final Segment<K, V>[] segments;
0171
0172 transient Set<K> keySet;
0173 transient Set<Map.Entry<K, V>> entrySet;
0174 transient Collection<V> values;
0175
0176 /* ---------------- Small Utilities -------------- */
0177
0178 /**
0179 * Applies a supplemental hash function to a given hashCode, which
0180 * defends against poor quality hash functions. This is critical
0181 * because ConcurrentHashMap uses power-of-two length hash tables,
0182 * that otherwise encounter collisions for hashCodes that do not
0183 * differ in lower or upper bits.
0184 */
0185 private static int hash(int h) {
0186 // Spread bits to regularize both segment and index locations,
0187 // using variant of single-word Wang/Jenkins hash.
0188 h += (h << 15) ^ 0xffffcd7d;
0189 h ^= (h >>> 10);
0190 h += (h << 3);
0191 h ^= (h >>> 6);
0192 h += (h << 2) + (h << 14);
0193 return h ^ (h >>> 16);
0194 }
0195
0196 /**
0197 * Returns the segment that should be used for key with given hash
0198 * @param hash the hash code for the key
0199 * @return the segment
0200 */
0201 final Segment<K, V> segmentFor(int hash) {
0202 return segments[(hash >>> segmentShift) & segmentMask];
0203 }
0204
0205 /* ---------------- Inner Classes -------------- */
0206
0207 /**
0208 * ConcurrentHashMap list entry. Note that this is never exported
0209 * out as a user-visible Map.Entry.
0210 *
0211 * Because the value field is volatile, not final, it is legal wrt
0212 * the Java Memory Model for an unsynchronized reader to see null
0213 * instead of initial value when read via a data race. Although a
0214 * reordering leading to this is not likely to ever actually
0215 * occur, the Segment.readValueUnderLock method is used as a
0216 * backup in case a null (pre-initialized) value is ever seen in
0217 * an unsynchronized access method.
0218 */
0219 static final class HashEntry<K, V> {
0220 final K key;
0221 final int hash;
0222 volatile V value;
0223 final HashEntry<K, V> next;
0224
0225 HashEntry(K key, int hash, HashEntry<K, V> next, V value) {
0226 this .key = key;
0227 this .hash = hash;
0228 this .next = next;
0229 this .value = value;
0230 }
0231
0232 @SuppressWarnings("unchecked")
0233 static final <K, V> HashEntry<K, V>[] newArray(int i) {
0234 return new HashEntry[i];
0235 }
0236 }
0237
0238 /**
0239 * Segments are specialized versions of hash tables. This
0240 * subclasses from ReentrantLock opportunistically, just to
0241 * simplify some locking and avoid separate construction.
0242 */
0243 static final class Segment<K, V> extends ReentrantLock implements
0244 Serializable {
0245 /*
0246 * Segments maintain a table of entry lists that are ALWAYS
0247 * kept in a consistent state, so can be read without locking.
0248 * Next fields of nodes are immutable (final). All list
0249 * additions are performed at the front of each bin. This
0250 * makes it easy to check changes, and also fast to traverse.
0251 * When nodes would otherwise be changed, new nodes are
0252 * created to replace them. This works well for hash tables
0253 * since the bin lists tend to be short. (The average length
0254 * is less than two for the default load factor threshold.)
0255 *
0256 * Read operations can thus proceed without locking, but rely
0257 * on selected uses of volatiles to ensure that completed
0258 * write operations performed by other threads are
0259 * noticed. For most purposes, the "count" field, tracking the
0260 * number of elements, serves as that volatile variable
0261 * ensuring visibility. This is convenient because this field
0262 * needs to be read in many read operations anyway:
0263 *
0264 * - All (unsynchronized) read operations must first read the
0265 * "count" field, and should not look at table entries if
0266 * it is 0.
0267 *
0268 * - All (synchronized) write operations should write to
0269 * the "count" field after structurally changing any bin.
0270 * The operations must not take any action that could even
0271 * momentarily cause a concurrent read operation to see
0272 * inconsistent data. This is made easier by the nature of
0273 * the read operations in Map. For example, no operation
0274 * can reveal that the table has grown but the threshold
0275 * has not yet been updated, so there are no atomicity
0276 * requirements for this with respect to reads.
0277 *
0278 * As a guide, all critical volatile reads and writes to the
0279 * count field are marked in code comments.
0280 */
0281
0282 private static final long serialVersionUID = 2249069246763182397L;
0283
0284 /**
0285 * The number of elements in this segment's region.
0286 */
0287 transient volatile int count;
0288
0289 /**
0290 * Number of updates that alter the size of the table. This is
0291 * used during bulk-read methods to make sure they see a
0292 * consistent snapshot: If modCounts change during a traversal
0293 * of segments computing size or checking containsValue, then
0294 * we might have an inconsistent view of state so (usually)
0295 * must retry.
0296 */
0297 transient int modCount;
0298
0299 /**
0300 * The table is rehashed when its size exceeds this threshold.
0301 * (The value of this field is always <tt>(int)(capacity *
0302 * loadFactor)</tt>.)
0303 */
0304 transient int threshold;
0305
0306 /**
0307 * The per-segment table.
0308 */
0309 transient volatile HashEntry<K, V>[] table;
0310
0311 /**
0312 * The load factor for the hash table. Even though this value
0313 * is same for all segments, it is replicated to avoid needing
0314 * links to outer object.
0315 * @serial
0316 */
0317 final float loadFactor;
0318
0319 Segment(int initialCapacity, float lf) {
0320 loadFactor = lf;
0321 setTable(HashEntry.<K, V> newArray(initialCapacity));
0322 }
0323
0324 @SuppressWarnings("unchecked")
0325 static final <K, V> Segment<K, V>[] newArray(int i) {
0326 return new Segment[i];
0327 }
0328
0329 /**
0330 * Sets table to new HashEntry array.
0331 * Call only while holding lock or in constructor.
0332 */
0333 void setTable(HashEntry<K, V>[] newTable) {
0334 threshold = (int) (newTable.length * loadFactor);
0335 table = newTable;
0336 }
0337
0338 /**
0339 * Returns properly casted first entry of bin for given hash.
0340 */
0341 HashEntry<K, V> getFirst(int hash) {
0342 HashEntry<K, V>[] tab = table;
0343 return tab[hash & (tab.length - 1)];
0344 }
0345
0346 /**
0347 * Reads value field of an entry under lock. Called if value
0348 * field ever appears to be null. This is possible only if a
0349 * compiler happens to reorder a HashEntry initialization with
0350 * its table assignment, which is legal under memory model
0351 * but is not known to ever occur.
0352 */
0353 V readValueUnderLock(HashEntry<K, V> e) {
0354 lock();
0355 try {
0356 return e.value;
0357 } finally {
0358 unlock();
0359 }
0360 }
0361
0362 /* Specialized implementations of map methods */
0363
0364 V get(Object key, int hash) {
0365 if (count != 0) { // read-volatile
0366 HashEntry<K, V> e = getFirst(hash);
0367 while (e != null) {
0368 if (e.hash == hash && key.equals(e.key)) {
0369 V v = e.value;
0370 if (v != null)
0371 return v;
0372 return readValueUnderLock(e); // recheck
0373 }
0374 e = e.next;
0375 }
0376 }
0377 return null;
0378 }
0379
0380 boolean containsKey(Object key, int hash) {
0381 if (count != 0) { // read-volatile
0382 HashEntry<K, V> e = getFirst(hash);
0383 while (e != null) {
0384 if (e.hash == hash && key.equals(e.key))
0385 return true;
0386 e = e.next;
0387 }
0388 }
0389 return false;
0390 }
0391
0392 boolean containsValue(Object value) {
0393 if (count != 0) { // read-volatile
0394 HashEntry<K, V>[] tab = table;
0395 int len = tab.length;
0396 for (int i = 0; i < len; i++) {
0397 for (HashEntry<K, V> e = tab[i]; e != null; e = e.next) {
0398 V v = e.value;
0399 if (v == null) // recheck
0400 v = readValueUnderLock(e);
0401 if (value.equals(v))
0402 return true;
0403 }
0404 }
0405 }
0406 return false;
0407 }
0408
0409 boolean replace(K key, int hash, V oldValue, V newValue) {
0410 lock();
0411 try {
0412 HashEntry<K, V> e = getFirst(hash);
0413 while (e != null
0414 && (e.hash != hash || !key.equals(e.key)))
0415 e = e.next;
0416
0417 boolean replaced = false;
0418 if (e != null && oldValue.equals(e.value)) {
0419 replaced = true;
0420 e.value = newValue;
0421 }
0422 return replaced;
0423 } finally {
0424 unlock();
0425 }
0426 }
0427
0428 V replace(K key, int hash, V newValue) {
0429 lock();
0430 try {
0431 HashEntry<K, V> e = getFirst(hash);
0432 while (e != null
0433 && (e.hash != hash || !key.equals(e.key)))
0434 e = e.next;
0435
0436 V oldValue = null;
0437 if (e != null) {
0438 oldValue = e.value;
0439 e.value = newValue;
0440 }
0441 return oldValue;
0442 } finally {
0443 unlock();
0444 }
0445 }
0446
0447 V put(K key, int hash, V value, boolean onlyIfAbsent) {
0448 lock();
0449 try {
0450 int c = count;
0451 if (c++ > threshold) // ensure capacity
0452 rehash();
0453 HashEntry<K, V>[] tab = table;
0454 int index = hash & (tab.length - 1);
0455 HashEntry<K, V> first = tab[index];
0456 HashEntry<K, V> e = first;
0457 while (e != null
0458 && (e.hash != hash || !key.equals(e.key)))
0459 e = e.next;
0460
0461 V oldValue;
0462 if (e != null) {
0463 oldValue = e.value;
0464 if (!onlyIfAbsent)
0465 e.value = value;
0466 } else {
0467 oldValue = null;
0468 ++modCount;
0469 tab[index] = new HashEntry<K, V>(key, hash, first,
0470 value);
0471 count = c; // write-volatile
0472 }
0473 return oldValue;
0474 } finally {
0475 unlock();
0476 }
0477 }
0478
0479 void rehash() {
0480 HashEntry<K, V>[] oldTable = table;
0481 int oldCapacity = oldTable.length;
0482 if (oldCapacity >= MAXIMUM_CAPACITY)
0483 return;
0484
0485 /*
0486 * Reclassify nodes in each list to new Map. Because we are
0487 * using power-of-two expansion, the elements from each bin
0488 * must either stay at same index, or move with a power of two
0489 * offset. We eliminate unnecessary node creation by catching
0490 * cases where old nodes can be reused because their next
0491 * fields won't change. Statistically, at the default
0492 * threshold, only about one-sixth of them need cloning when
0493 * a table doubles. The nodes they replace will be garbage
0494 * collectable as soon as they are no longer referenced by any
0495 * reader thread that may be in the midst of traversing table
0496 * right now.
0497 */
0498
0499 HashEntry<K, V>[] newTable = HashEntry
0500 .newArray(oldCapacity << 1);
0501 threshold = (int) (newTable.length * loadFactor);
0502 int sizeMask = newTable.length - 1;
0503 for (int i = 0; i < oldCapacity; i++) {
0504 // We need to guarantee that any existing reads of old Map can
0505 // proceed. So we cannot yet null out each bin.
0506 HashEntry<K, V> e = oldTable[i];
0507
0508 if (e != null) {
0509 HashEntry<K, V> next = e.next;
0510 int idx = e.hash & sizeMask;
0511
0512 // Single node on list
0513 if (next == null)
0514 newTable[idx] = e;
0515
0516 else {
0517 // Reuse trailing consecutive sequence at same slot
0518 HashEntry<K, V> lastRun = e;
0519 int lastIdx = idx;
0520 for (HashEntry<K, V> last = next; last != null; last = last.next) {
0521 int k = last.hash & sizeMask;
0522 if (k != lastIdx) {
0523 lastIdx = k;
0524 lastRun = last;
0525 }
0526 }
0527 newTable[lastIdx] = lastRun;
0528
0529 // Clone all remaining nodes
0530 for (HashEntry<K, V> p = e; p != lastRun; p = p.next) {
0531 int k = p.hash & sizeMask;
0532 HashEntry<K, V> n = newTable[k];
0533 newTable[k] = new HashEntry<K, V>(p.key,
0534 p.hash, n, p.value);
0535 }
0536 }
0537 }
0538 }
0539 table = newTable;
0540 }
0541
0542 /**
0543 * Remove; match on key only if value null, else match both.
0544 */
0545 V remove(Object key, int hash, Object value) {
0546 lock();
0547 try {
0548 int c = count - 1;
0549 HashEntry<K, V>[] tab = table;
0550 int index = hash & (tab.length - 1);
0551 HashEntry<K, V> first = tab[index];
0552 HashEntry<K, V> e = first;
0553 while (e != null
0554 && (e.hash != hash || !key.equals(e.key)))
0555 e = e.next;
0556
0557 V oldValue = null;
0558 if (e != null) {
0559 V v = e.value;
0560 if (value == null || value.equals(v)) {
0561 oldValue = v;
0562 // All entries following removed node can stay
0563 // in list, but all preceding ones need to be
0564 // cloned.
0565 ++modCount;
0566 HashEntry<K, V> newFirst = e.next;
0567 for (HashEntry<K, V> p = first; p != e; p = p.next)
0568 newFirst = new HashEntry<K, V>(p.key,
0569 p.hash, newFirst, p.value);
0570 tab[index] = newFirst;
0571 count = c; // write-volatile
0572 }
0573 }
0574 return oldValue;
0575 } finally {
0576 unlock();
0577 }
0578 }
0579
0580 void clear() {
0581 if (count != 0) {
0582 lock();
0583 try {
0584 HashEntry<K, V>[] tab = table;
0585 for (int i = 0; i < tab.length; i++)
0586 tab[i] = null;
0587 ++modCount;
0588 count = 0; // write-volatile
0589 } finally {
0590 unlock();
0591 }
0592 }
0593 }
0594 }
0595
0596 /* ---------------- Public operations -------------- */
0597
0598 /**
0599 * Creates a new, empty map with the specified initial
0600 * capacity, load factor and concurrency level.
0601 *
0602 * @param initialCapacity the initial capacity. The implementation
0603 * performs internal sizing to accommodate this many elements.
0604 * @param loadFactor the load factor threshold, used to control resizing.
0605 * Resizing may be performed when the average number of elements per
0606 * bin exceeds this threshold.
0607 * @param concurrencyLevel the estimated number of concurrently
0608 * updating threads. The implementation performs internal sizing
0609 * to try to accommodate this many threads.
0610 * @throws IllegalArgumentException if the initial capacity is
0611 * negative or the load factor or concurrencyLevel are
0612 * nonpositive.
0613 */
0614 public ConcurrentHashMap(int initialCapacity, float loadFactor,
0615 int concurrencyLevel) {
0616 if (!(loadFactor > 0) || initialCapacity < 0
0617 || concurrencyLevel <= 0)
0618 throw new IllegalArgumentException();
0619
0620 if (concurrencyLevel > MAX_SEGMENTS)
0621 concurrencyLevel = MAX_SEGMENTS;
0622
0623 // Find power-of-two sizes best matching arguments
0624 int sshift = 0;
0625 int ssize = 1;
0626 while (ssize < concurrencyLevel) {
0627 ++sshift;
0628 ssize <<= 1;
0629 }
0630 segmentShift = 32 - sshift;
0631 segmentMask = ssize - 1;
0632 this .segments = Segment.newArray(ssize);
0633
0634 if (initialCapacity > MAXIMUM_CAPACITY)
0635 initialCapacity = MAXIMUM_CAPACITY;
0636 int c = initialCapacity / ssize;
0637 if (c * ssize < initialCapacity)
0638 ++c;
0639 int cap = 1;
0640 while (cap < c)
0641 cap <<= 1;
0642
0643 for (int i = 0; i < this .segments.length; ++i)
0644 this .segments[i] = new Segment<K, V>(cap, loadFactor);
0645 }
0646
0647 /**
0648 * Creates a new, empty map with the specified initial capacity
0649 * and load factor and with the default concurrencyLevel (16).
0650 *
0651 * @param initialCapacity The implementation performs internal
0652 * sizing to accommodate this many elements.
0653 * @param loadFactor the load factor threshold, used to control resizing.
0654 * Resizing may be performed when the average number of elements per
0655 * bin exceeds this threshold.
0656 * @throws IllegalArgumentException if the initial capacity of
0657 * elements is negative or the load factor is nonpositive
0658 *
0659 * @since 1.6
0660 */
0661 public ConcurrentHashMap(int initialCapacity, float loadFactor) {
0662 this (initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
0663 }
0664
0665 /**
0666 * Creates a new, empty map with the specified initial capacity,
0667 * and with default load factor (0.75) and concurrencyLevel (16).
0668 *
0669 * @param initialCapacity the initial capacity. The implementation
0670 * performs internal sizing to accommodate this many elements.
0671 * @throws IllegalArgumentException if the initial capacity of
0672 * elements is negative.
0673 */
0674 public ConcurrentHashMap(int initialCapacity) {
0675 this (initialCapacity, DEFAULT_LOAD_FACTOR,
0676 DEFAULT_CONCURRENCY_LEVEL);
0677 }
0678
0679 /**
0680 * Creates a new, empty map with a default initial capacity (16),
0681 * load factor (0.75) and concurrencyLevel (16).
0682 */
0683 public ConcurrentHashMap() {
0684 this (DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR,
0685 DEFAULT_CONCURRENCY_LEVEL);
0686 }
0687
0688 /**
0689 * Creates a new map with the same mappings as the given map.
0690 * The map is created with a capacity of 1.5 times the number
0691 * of mappings in the given map or 16 (whichever is greater),
0692 * and a default load factor (0.75) and concurrencyLevel (16).
0693 *
0694 * @param m the map
0695 */
0696 public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
0697 this (Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
0698 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR,
0699 DEFAULT_CONCURRENCY_LEVEL);
0700 putAll(m);
0701 }
0702
0703 /**
0704 * Returns <tt>true</tt> if this map contains no key-value mappings.
0705 *
0706 * @return <tt>true</tt> if this map contains no key-value mappings
0707 */
0708 public boolean isEmpty() {
0709 final Segment<K, V>[] segments = this .segments;
0710 /*
0711 * We keep track of per-segment modCounts to avoid ABA
0712 * problems in which an element in one segment was added and
0713 * in another removed during traversal, in which case the
0714 * table was never actually empty at any point. Note the
0715 * similar use of modCounts in the size() and containsValue()
0716 * methods, which are the only other methods also susceptible
0717 * to ABA problems.
0718 */
0719 int[] mc = new int[segments.length];
0720 int mcsum = 0;
0721 for (int i = 0; i < segments.length; ++i) {
0722 if (segments[i].count != 0)
0723 return false;
0724 else
0725 mcsum += mc[i] = segments[i].modCount;
0726 }
0727 // If mcsum happens to be zero, then we know we got a snapshot
0728 // before any modifications at all were made. This is
0729 // probably common enough to bother tracking.
0730 if (mcsum != 0) {
0731 for (int i = 0; i < segments.length; ++i) {
0732 if (segments[i].count != 0
0733 || mc[i] != segments[i].modCount)
0734 return false;
0735 }
0736 }
0737 return true;
0738 }
0739
0740 /**
0741 * Returns the number of key-value mappings in this map. If the
0742 * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
0743 * <tt>Integer.MAX_VALUE</tt>.
0744 *
0745 * @return the number of key-value mappings in this map
0746 */
0747 public int size() {
0748 final Segment<K, V>[] segments = this .segments;
0749 long sum = 0;
0750 long check = 0;
0751 int[] mc = new int[segments.length];
0752 // Try a few times to get accurate count. On failure due to
0753 // continuous async changes in table, resort to locking.
0754 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
0755 check = 0;
0756 sum = 0;
0757 int mcsum = 0;
0758 for (int i = 0; i < segments.length; ++i) {
0759 sum += segments[i].count;
0760 mcsum += mc[i] = segments[i].modCount;
0761 }
0762 if (mcsum != 0) {
0763 for (int i = 0; i < segments.length; ++i) {
0764 check += segments[i].count;
0765 if (mc[i] != segments[i].modCount) {
0766 check = -1; // force retry
0767 break;
0768 }
0769 }
0770 }
0771 if (check == sum)
0772 break;
0773 }
0774 if (check != sum) { // Resort to locking all segments
0775 sum = 0;
0776 for (int i = 0; i < segments.length; ++i)
0777 segments[i].lock();
0778 for (int i = 0; i < segments.length; ++i)
0779 sum += segments[i].count;
0780 for (int i = 0; i < segments.length; ++i)
0781 segments[i].unlock();
0782 }
0783 if (sum > Integer.MAX_VALUE)
0784 return Integer.MAX_VALUE;
0785 else
0786 return (int) sum;
0787 }
0788
0789 /**
0790 * Returns the value to which the specified key is mapped,
0791 * or {@code null} if this map contains no mapping for the key.
0792 *
0793 * <p>More formally, if this map contains a mapping from a key
0794 * {@code k} to a value {@code v} such that {@code key.equals(k)},
0795 * then this method returns {@code v}; otherwise it returns
0796 * {@code null}. (There can be at most one such mapping.)
0797 *
0798 * @throws NullPointerException if the specified key is null
0799 */
0800 public V get(Object key) {
0801 int hash = hash(key.hashCode());
0802 return segmentFor(hash).get(key, hash);
0803 }
0804
0805 /**
0806 * Tests if the specified object is a key in this table.
0807 *
0808 * @param key possible key
0809 * @return <tt>true</tt> if and only if the specified object
0810 * is a key in this table, as determined by the
0811 * <tt>equals</tt> method; <tt>false</tt> otherwise.
0812 * @throws NullPointerException if the specified key is null
0813 */
0814 public boolean containsKey(Object key) {
0815 int hash = hash(key.hashCode());
0816 return segmentFor(hash).containsKey(key, hash);
0817 }
0818
0819 /**
0820 * Returns <tt>true</tt> if this map maps one or more keys to the
0821 * specified value. Note: This method requires a full internal
0822 * traversal of the hash table, and so is much slower than
0823 * method <tt>containsKey</tt>.
0824 *
0825 * @param value value whose presence in this map is to be tested
0826 * @return <tt>true</tt> if this map maps one or more keys to the
0827 * specified value
0828 * @throws NullPointerException if the specified value is null
0829 */
0830 public boolean containsValue(Object value) {
0831 if (value == null)
0832 throw new NullPointerException();
0833
0834 // See explanation of modCount use above
0835
0836 final Segment<K, V>[] segments = this .segments;
0837 int[] mc = new int[segments.length];
0838
0839 // Try a few times without locking
0840 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
0841 int sum = 0;
0842 int mcsum = 0;
0843 for (int i = 0; i < segments.length; ++i) {
0844 int c = segments[i].count;
0845 mcsum += mc[i] = segments[i].modCount;
0846 if (segments[i].containsValue(value))
0847 return true;
0848 }
0849 boolean cleanSweep = true;
0850 if (mcsum != 0) {
0851 for (int i = 0; i < segments.length; ++i) {
0852 int c = segments[i].count;
0853 if (mc[i] != segments[i].modCount) {
0854 cleanSweep = false;
0855 break;
0856 }
0857 }
0858 }
0859 if (cleanSweep)
0860 return false;
0861 }
0862 // Resort to locking all segments
0863 for (int i = 0; i < segments.length; ++i)
0864 segments[i].lock();
0865 boolean found = false;
0866 try {
0867 for (int i = 0; i < segments.length; ++i) {
0868 if (segments[i].containsValue(value)) {
0869 found = true;
0870 break;
0871 }
0872 }
0873 } finally {
0874 for (int i = 0; i < segments.length; ++i)
0875 segments[i].unlock();
0876 }
0877 return found;
0878 }
0879
0880 /**
0881 * Legacy method testing if some key maps into the specified value
0882 * in this table. This method is identical in functionality to
0883 * {@link #containsValue}, and exists solely to ensure
0884 * full compatibility with class {@link java.util.Hashtable},
0885 * which supported this method prior to introduction of the
0886 * Java Collections framework.
0887
0888 * @param value a value to search for
0889 * @return <tt>true</tt> if and only if some key maps to the
0890 * <tt>value</tt> argument in this table as
0891 * determined by the <tt>equals</tt> method;
0892 * <tt>false</tt> otherwise
0893 * @throws NullPointerException if the specified value is null
0894 */
0895 public boolean contains(Object value) {
0896 return containsValue(value);
0897 }
0898
0899 /**
0900 * Maps the specified key to the specified value in this table.
0901 * Neither the key nor the value can be null.
0902 *
0903 * <p> The value can be retrieved by calling the <tt>get</tt> method
0904 * with a key that is equal to the original key.
0905 *
0906 * @param key key with which the specified value is to be associated
0907 * @param value value to be associated with the specified key
0908 * @return the previous value associated with <tt>key</tt>, or
0909 * <tt>null</tt> if there was no mapping for <tt>key</tt>
0910 * @throws NullPointerException if the specified key or value is null
0911 */
0912 public V put(K key, V value) {
0913 if (value == null)
0914 throw new NullPointerException();
0915 int hash = hash(key.hashCode());
0916 return segmentFor(hash).put(key, hash, value, false);
0917 }
0918
0919 /**
0920 * {@inheritDoc}
0921 *
0922 * @return the previous value associated with the specified key,
0923 * or <tt>null</tt> if there was no mapping for the key
0924 * @throws NullPointerException if the specified key or value is null
0925 */
0926 public V putIfAbsent(K key, V value) {
0927 if (value == null)
0928 throw new NullPointerException();
0929 int hash = hash(key.hashCode());
0930 return segmentFor(hash).put(key, hash, value, true);
0931 }
0932
0933 /**
0934 * Copies all of the mappings from the specified map to this one.
0935 * These mappings replace any mappings that this map had for any of the
0936 * keys currently in the specified map.
0937 *
0938 * @param m mappings to be stored in this map
0939 */
0940 public void putAll(Map<? extends K, ? extends V> m) {
0941 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
0942 put(e.getKey(), e.getValue());
0943 }
0944
0945 /**
0946 * Removes the key (and its corresponding value) from this map.
0947 * This method does nothing if the key is not in the map.
0948 *
0949 * @param key the key that needs to be removed
0950 * @return the previous value associated with <tt>key</tt>, or
0951 * <tt>null</tt> if there was no mapping for <tt>key</tt>
0952 * @throws NullPointerException if the specified key is null
0953 */
0954 public V remove(Object key) {
0955 int hash = hash(key.hashCode());
0956 return segmentFor(hash).remove(key, hash, null);
0957 }
0958
0959 /**
0960 * {@inheritDoc}
0961 *
0962 * @throws NullPointerException if the specified key is null
0963 */
0964 public boolean remove(Object key, Object value) {
0965 int hash = hash(key.hashCode());
0966 if (value == null)
0967 return false;
0968 return segmentFor(hash).remove(key, hash, value) != null;
0969 }
0970
0971 /**
0972 * {@inheritDoc}
0973 *
0974 * @throws NullPointerException if any of the arguments are null
0975 */
0976 public boolean replace(K key, V oldValue, V newValue) {
0977 if (oldValue == null || newValue == null)
0978 throw new NullPointerException();
0979 int hash = hash(key.hashCode());
0980 return segmentFor(hash).replace(key, hash, oldValue, newValue);
0981 }
0982
0983 /**
0984 * {@inheritDoc}
0985 *
0986 * @return the previous value associated with the specified key,
0987 * or <tt>null</tt> if there was no mapping for the key
0988 * @throws NullPointerException if the specified key or value is null
0989 */
0990 public V replace(K key, V value) {
0991 if (value == null)
0992 throw new NullPointerException();
0993 int hash = hash(key.hashCode());
0994 return segmentFor(hash).replace(key, hash, value);
0995 }
0996
0997 /**
0998 * Removes all of the mappings from this map.
0999 */
1000 public void clear() {
1001 for (int i = 0; i < segments.length; ++i)
1002 segments[i].clear();
1003 }
1004
1005 /**
1006 * Returns a {@link Set} view of the keys contained in this map.
1007 * The set is backed by the map, so changes to the map are
1008 * reflected in the set, and vice-versa. The set supports element
1009 * removal, which removes the corresponding mapping from this map,
1010 * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1011 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1012 * operations. It does not support the <tt>add</tt> or
1013 * <tt>addAll</tt> operations.
1014 *
1015 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1016 * that will never throw {@link 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 public Set<K> keySet() {
1022 Set<K> ks = keySet;
1023 return (ks != null) ? ks : (keySet = new KeySet());
1024 }
1025
1026 /**
1027 * Returns a {@link Collection} view of the values contained in this map.
1028 * The collection is backed by the map, so changes to the map are
1029 * reflected in the collection, and vice-versa. The collection
1030 * supports element removal, which removes the corresponding
1031 * mapping from this map, via the <tt>Iterator.remove</tt>,
1032 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1033 * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not
1034 * support the <tt>add</tt> or <tt>addAll</tt> operations.
1035 *
1036 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1037 * that will never throw {@link ConcurrentModificationException},
1038 * and guarantees to traverse elements as they existed upon
1039 * construction of the iterator, and may (but is not guaranteed to)
1040 * reflect any modifications subsequent to construction.
1041 */
1042 public Collection<V> values() {
1043 Collection<V> vs = values;
1044 return (vs != null) ? vs : (values = new Values());
1045 }
1046
1047 /**
1048 * Returns a {@link Set} view of the mappings contained in this map.
1049 * The set is backed by the map, so changes to the map are
1050 * reflected in the set, and vice-versa. The set supports element
1051 * removal, which removes the corresponding mapping from the map,
1052 * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1053 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1054 * operations. It does not support the <tt>add</tt> or
1055 * <tt>addAll</tt> operations.
1056 *
1057 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1058 * that will never throw {@link ConcurrentModificationException},
1059 * and guarantees to traverse elements as they existed upon
1060 * construction of the iterator, and may (but is not guaranteed to)
1061 * reflect any modifications subsequent to construction.
1062 */
1063 public Set<Map.Entry<K, V>> entrySet() {
1064 Set<Map.Entry<K, V>> es = entrySet;
1065 return (es != null) ? es : (entrySet = new EntrySet());
1066 }
1067
1068 /**
1069 * Returns an enumeration of the keys in this table.
1070 *
1071 * @return an enumeration of the keys in this table
1072 * @see #keySet()
1073 */
1074 public Enumeration<K> keys() {
1075 return new KeyIterator();
1076 }
1077
1078 /**
1079 * Returns an enumeration of the values in this table.
1080 *
1081 * @return an enumeration of the values in this table
1082 * @see #values()
1083 */
1084 public Enumeration<V> elements() {
1085 return new ValueIterator();
1086 }
1087
1088 /* ---------------- Iterator Support -------------- */
1089
1090 abstract class HashIterator {
1091 int nextSegmentIndex;
1092 int nextTableIndex;
1093 HashEntry<K, V>[] currentTable;
1094 HashEntry<K, V> nextEntry;
1095 HashEntry<K, V> lastReturned;
1096
1097 HashIterator() {
1098 nextSegmentIndex = segments.length - 1;
1099 nextTableIndex = -1;
1100 advance();
1101 }
1102
1103 public boolean hasMoreElements() {
1104 return hasNext();
1105 }
1106
1107 final void advance() {
1108 if (nextEntry != null
1109 && (nextEntry = nextEntry.next) != null)
1110 return;
1111
1112 while (nextTableIndex >= 0) {
1113 if ((nextEntry = currentTable[nextTableIndex--]) != null)
1114 return;
1115 }
1116
1117 while (nextSegmentIndex >= 0) {
1118 Segment<K, V> seg = segments[nextSegmentIndex--];
1119 if (seg.count != 0) {
1120 currentTable = seg.table;
1121 for (int j = currentTable.length - 1; j >= 0; --j) {
1122 if ((nextEntry = currentTable[j]) != null) {
1123 nextTableIndex = j - 1;
1124 return;
1125 }
1126 }
1127 }
1128 }
1129 }
1130
1131 public boolean hasNext() {
1132 return nextEntry != null;
1133 }
1134
1135 HashEntry<K, V> nextEntry() {
1136 if (nextEntry == null)
1137 throw new NoSuchElementException();
1138 lastReturned = nextEntry;
1139 advance();
1140 return lastReturned;
1141 }
1142
1143 public void remove() {
1144 if (lastReturned == null)
1145 throw new IllegalStateException();
1146 ConcurrentHashMap.this .remove(lastReturned.key);
1147 lastReturned = null;
1148 }
1149 }
1150
1151 final class KeyIterator extends HashIterator implements
1152 Iterator<K>, Enumeration<K> {
1153 public K next() {
1154 return super .nextEntry().key;
1155 }
1156
1157 public K nextElement() {
1158 return super .nextEntry().key;
1159 }
1160 }
1161
1162 final class ValueIterator extends HashIterator implements
1163 Iterator<V>, Enumeration<V> {
1164 public V next() {
1165 return super .nextEntry().value;
1166 }
1167
1168 public V nextElement() {
1169 return super .nextEntry().value;
1170 }
1171 }
1172
1173 /**
1174 * Custom Entry class used by EntryIterator.next(), that relays
1175 * setValue changes to the underlying map.
1176 */
1177 final class WriteThroughEntry extends AbstractMap.SimpleEntry<K, V> {
1178 WriteThroughEntry(K k, V v) {
1179 super (k, v);
1180 }
1181
1182 /**
1183 * Set our entry's value and write through to the map. The
1184 * value to return is somewhat arbitrary here. Since a
1185 * WriteThroughEntry does not necessarily track asynchronous
1186 * changes, the most recent "previous" value could be
1187 * different from what we return (or could even have been
1188 * removed in which case the put will re-establish). We do not
1189 * and cannot guarantee more.
1190 */
1191 public V setValue(V value) {
1192 if (value == null)
1193 throw new NullPointerException();
1194 V v = super .setValue(value);
1195 ConcurrentHashMap.this .put(getKey(), value);
1196 return v;
1197 }
1198 }
1199
1200 final class EntryIterator extends HashIterator implements
1201 Iterator<Entry<K, V>> {
1202 public Map.Entry<K, V> next() {
1203 HashEntry<K, V> e = super .nextEntry();
1204 return new WriteThroughEntry(e.key, e.value);
1205 }
1206 }
1207
1208 final class KeySet extends AbstractSet<K> {
1209 public Iterator<K> iterator() {
1210 return new KeyIterator();
1211 }
1212
1213 public int size() {
1214 return ConcurrentHashMap.this .size();
1215 }
1216
1217 public boolean isEmpty() {
1218 return ConcurrentHashMap.this .isEmpty();
1219 }
1220
1221 public boolean contains(Object o) {
1222 return ConcurrentHashMap.this .containsKey(o);
1223 }
1224
1225 public boolean remove(Object o) {
1226 return ConcurrentHashMap.this .remove(o) != null;
1227 }
1228
1229 public void clear() {
1230 ConcurrentHashMap.this .clear();
1231 }
1232 }
1233
1234 final class Values extends AbstractCollection<V> {
1235 public Iterator<V> iterator() {
1236 return new ValueIterator();
1237 }
1238
1239 public int size() {
1240 return ConcurrentHashMap.this .size();
1241 }
1242
1243 public boolean isEmpty() {
1244 return ConcurrentHashMap.this .isEmpty();
1245 }
1246
1247 public boolean contains(Object o) {
1248 return ConcurrentHashMap.this .containsValue(o);
1249 }
1250
1251 public void clear() {
1252 ConcurrentHashMap.this .clear();
1253 }
1254 }
1255
1256 final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
1257 public Iterator<Map.Entry<K, V>> iterator() {
1258 return new EntryIterator();
1259 }
1260
1261 public boolean contains(Object o) {
1262 if (!(o instanceof Map.Entry))
1263 return false;
1264 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
1265 V v = ConcurrentHashMap.this .get(e.getKey());
1266 return v != null && v.equals(e.getValue());
1267 }
1268
1269 public boolean remove(Object o) {
1270 if (!(o instanceof Map.Entry))
1271 return false;
1272 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
1273 return ConcurrentHashMap.this .remove(e.getKey(), e
1274 .getValue());
1275 }
1276
1277 public int size() {
1278 return ConcurrentHashMap.this .size();
1279 }
1280
1281 public boolean isEmpty() {
1282 return ConcurrentHashMap.this .isEmpty();
1283 }
1284
1285 public void clear() {
1286 ConcurrentHashMap.this .clear();
1287 }
1288 }
1289
1290 /* ---------------- Serialization Support -------------- */
1291
1292 /**
1293 * Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1294 * stream (i.e., serialize it).
1295 * @param s the stream
1296 * @serialData
1297 * the key (Object) and value (Object)
1298 * for each key-value mapping, followed by a null pair.
1299 * The key-value mappings are emitted in no particular order.
1300 */
1301 private void writeObject(java.io.ObjectOutputStream s)
1302 throws IOException {
1303 s.defaultWriteObject();
1304
1305 for (int k = 0; k < segments.length; ++k) {
1306 Segment<K, V> seg = segments[k];
1307 seg.lock();
1308 try {
1309 HashEntry<K, V>[] tab = seg.table;
1310 for (int i = 0; i < tab.length; ++i) {
1311 for (HashEntry<K, V> e = tab[i]; e != null; e = e.next) {
1312 s.writeObject(e.key);
1313 s.writeObject(e.value);
1314 }
1315 }
1316 } finally {
1317 seg.unlock();
1318 }
1319 }
1320 s.writeObject(null);
1321 s.writeObject(null);
1322 }
1323
1324 /**
1325 * Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1326 * stream (i.e., deserialize it).
1327 * @param s the stream
1328 */
1329 private void readObject(java.io.ObjectInputStream s)
1330 throws IOException, ClassNotFoundException {
1331 s.defaultReadObject();
1332
1333 // Initialize each segment to be minimally sized, and let grow.
1334 for (int i = 0; i < segments.length; ++i) {
1335 segments[i].setTable(new HashEntry[1]);
1336 }
1337
1338 // Read the keys and values, and put the mappings in the table
1339 for (;;) {
1340 K key = (K) s.readObject();
1341 V value = (V) s.readObject();
1342 if (key == null)
1343 break;
1344 put(key, value);
1345 }
1346 }
1347 }
|