553N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 0N/A * published by the Free Software Foundation. Oracle designates this 0N/A * particular file as subject to the "Classpath" exception as provided 0N/A * by Oracle in the LICENSE file that accompanied this code. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 553N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 553N/A * or visit www.oracle.com if you need additional information or have any 0N/A * This file is available under and governed by the GNU General Public 0N/A * License version 2 only, as published by the Free Software Foundation. 0N/A * However, the following notice accompanied the original version of this 0N/A * Written by Doug Lea with assistance from members of JCP JSR-166 0N/A * Expert Group and released to the public domain, as explained at * A hash table supporting full concurrency of retrievals and * adjustable expected concurrency for updates. This class obeys the * same functional specification as {@link java.util.Hashtable}, and * includes versions of methods corresponding to each method of * <tt>Hashtable</tt>. However, even though all operations are * thread-safe, retrieval operations do <em>not</em> entail locking, * and there is <em>not</em> any support for locking the entire table * in a way that prevents all access. This class is fully * interoperable with <tt>Hashtable</tt> in programs that rely on its * thread safety but not on its synchronization details. * <p> Retrieval operations (including <tt>get</tt>) generally do not * block, so may overlap with update operations (including * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results * of the most recently <em>completed</em> update operations holding * upon their onset. For aggregate operations such as <tt>putAll</tt> * and <tt>clear</tt>, concurrent retrievals may reflect insertion or * removal of only some entries. Similarly, Iterators and * Enumerations return elements reflecting the state of the hash table * They do <em>not</em> throw {@link ConcurrentModificationException}. * However, iterators are designed to be used by only one thread at a time. * <p> The allowed concurrency among update operations is guided by * the optional <tt>concurrencyLevel</tt> constructor argument * (default <tt>16</tt>), which is used as a hint for internal sizing. The * table is internally partitioned to try to permit the indicated * number of concurrent updates without contention. Because placement * in hash tables is essentially random, the actual concurrency will * vary. Ideally, you should choose a value to accommodate as many * threads as will ever concurrently modify the table. Using a * significantly higher value than you need can waste space and time, * and a significantly lower value can lead to thread contention. But * overestimates and underestimates within an order of magnitude do * not usually have much noticeable impact. A value of one is * appropriate when it is known that only one thread will modify and * all others will only read. Also, resizing this or any other kind of * hash table is a relatively slow operation, so, when possible, it is * a good idea to provide estimates of expected table sizes in * <p>This class and its views and iterators implement all of the * <em>optional</em> methods of the {@link Map} and {@link Iterator} * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class * does <em>not</em> allow <tt>null</tt> to be used as a key or value. * <p>This class is a member of the * Java Collections Framework</a>. * @param <K> the type of keys maintained by this map * @param <V> the type of mapped values * The basic strategy is to subdivide the table among Segments, * each of which itself is a concurrently readable hash table. To * reduce footprint, all but one segments are constructed only * when first needed (see ensureSegment). To maintain visibility * in the presence of lazy construction, accesses to segments as * well as elements of segment's table must use volatile access, * which is done via Unsafe within methods segmentAt etc * below. These provide the functionality of AtomicReferenceArrays * but reduce the levels of indirection. Additionally, * volatile-writes of table elements and entry "next" fields * within locked operations use the cheaper "lazySet" forms of * writes (via putOrderedObject) because these writes are always * followed by lock releases that maintain sequential consistency * Historical note: The previous version of this class relied * heavily on "final" fields, which avoided some volatile reads at * the expense of a large initial footprint. Some remnants of * that design (including forced construction of segment 0) exist * to ensure serialization compatibility. /* ---------------- Constants -------------- */ * The default initial capacity for this table, * used when not otherwise specified in a constructor. * The default load factor for this table, used when not * otherwise specified in a constructor. * The default concurrency level for this table, used when not * otherwise specified in a constructor. * The maximum capacity, used if a higher value is implicitly * specified by either of the constructors with arguments. MUST * be a power of two <= 1<<30 to ensure that entries are indexable * The minimum capacity for per-segment tables. Must be a power * of two, at least two to avoid immediate resizing on next use * after lazy construction. * The maximum number of segments to allow; used to bound * constructor arguments. Must be power of two less than 1 << 24. static final int MAX_SEGMENTS =
1 <<
16;
// slightly conservative * Number of unsynchronized retries in size and containsValue * methods before resorting to locking. This is used to avoid * unbounded retries if tables undergo continuous modification * which would make it impossible to obtain an accurate result. /* ---------------- Fields -------------- */ * holds values which can't be initialized until after VM is booted. * Enable alternative hashing of String keys? * <p>Unlike the other hash map implementations we do not implement a * threshold for regulating whether alternative hashing is used for * String keys. Alternative hashing is either enabled for all instances * or disabled for all instances. // Use the "threshold" system property even though our threshold // behaviour is "ON" or "OFF". "jdk.map.althashing.threshold"));
// disable alternative hashing if -1 throw new Error(
"Illegal value for 'jdk.map.althashing.threshold'",
failed);
* A randomizing value associated with this instance that is applied to * hash code of keys to make hash collisions harder to find. * Mask value for indexing into segments. The upper bits of a * key's hash code are used to choose the segment. * Shift value for indexing within segments. * The segments, each of which is a specialized hash table. * ConcurrentHashMap list entry. Note that this is never exported * out as a user-visible Map.Entry. * Sets next field with volatile write semantics. (See above * about use of putOrderedObject.) * Gets the ith element of given table (if nonnull) with volatile * read semantics. Note: This is manually integrated into a few * performance-sensitive methods to reduce call overhead. * Sets the ith element of given table, with volatile write * semantics. (See above about use of putOrderedObject.) * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because ConcurrentHashMap uses power-of-two length hash tables, * that otherwise encounter collisions for hashCodes that do not * differ in lower or upper bits. if ((
0 != h) && (k
instanceof String)) {
// Spread bits to regularize both segment and index locations, h += (h <<
15) ^
0xffffcd7d;
h += (h <<
2) + (h <<
14);
* Segments are specialized versions of hash tables. This * subclasses from ReentrantLock opportunistically, just to * simplify some locking and avoid separate construction. * Segments maintain a table of entry lists that are always * kept in a consistent state, so can be read (via volatile * reads of segments and tables) without locking. This * requires replicating nodes when necessary during table * resizing, so the old lists can be traversed by readers * still using old version of table. * This class defines only mutative methods requiring locking. * Except as noted, the methods of this class perform the * per-segment versions of ConcurrentHashMap methods. (Other * methods are integrated directly into ConcurrentHashMap * methods.) These mutative methods use a form of controlled * spinning on contention via methods scanAndLock and * scanAndLockForPut. These intersperse tryLocks with * traversals to locate nodes. The main benefit is to absorb * cache misses (which are very common for hash tables) while * obtaining locks so that traversal is faster once * acquired. We do not actually use the found nodes since they * must be re-acquired under lock anyway to ensure sequential * consistency of updates (and in any case may be undetectably * stale), but they will normally be much faster to re-locate. * Also, scanAndLockForPut speculatively creates a fresh node * to use in put if no node is found. * The maximum number of times to tryLock in a prescan before * possibly blocking on acquire in preparation for a locked * segment operation. On multiprocessors, using a bounded * number of retries maintains cache acquired while locating * The per-segment table. Elements are accessed via * The number of elements. Accessed only either within locks * or among other volatile reads that maintain visibility. * The total number of mutative operations in this segment. * Even though this may overflows 32 bits, it provides * sufficient accuracy for stability checks in CHM isEmpty() * and size() methods. Accessed only either within locks or * among other volatile reads that maintain visibility. * The table is rehashed when its size exceeds this threshold. * (The value of this field is always <tt>(int)(capacity * * The load factor for the hash table. Even though this value * is same for all segments, it is replicated to avoid needing * Doubles size of table and repacks entries, also adding the * given node to new table * Reclassify nodes in each list to new table. Because we * are using power-of-two expansion, the elements from * each bin must either stay at same index, or move with a * power of two offset. We eliminate unnecessary node * creation by catching cases where old nodes can be * reused because their next fields won't change. * Statistically, at the default threshold, only about * one-sixth of them need cloning when a table * doubles. The nodes they replace will be garbage * collectable as soon as they are no longer referenced by * any reader thread that may be in the midst of * concurrently traversing table. Entry accesses use plain * array indexing because they are followed by volatile if (
next ==
null)
// Single node on list else {
// Reuse consecutive sequence at same slot * Scans for a node containing given key while trying to * acquire lock, creating and returning one if not found. Upon * return, guarantees that lock is held. UNlike in most * methods, calls to method equals are not screened: Since * traversal speed doesn't matter, we might as well help warm * up the associated code and accesses as well. * @return a new node if key not found, else null int retries = -
1;
// negative while locating node if (
node ==
null)
// speculatively create node e =
first = f;
// re-traverse if entry changed * Scans for a node containing the given key while trying to * acquire lock for a remove or replace operation. Upon * return, guarantees that lock is held. Note that we must * lock even if the key is not found, to ensure sequential * consistency of updates. // similar to but simpler than scanAndLockForPut * Remove; match on key only if value null, else match both. * Gets the jth element of given segment array (if nonnull) with * volatile element access semantics via Unsafe. (The null check * can trigger harmlessly only during deserialization.) Note: * because each element of segments array is set only once (using * fully ordered writes), some performance-sensitive methods rely * on this method only as a recheck upon null reads. * Returns the segment for the given index, creating it and * recording in segment table (via CAS) if not already present. // Hash-based segment and entry accesses * Get the segment for the given hash * Gets the table entry for the given segment and hash /* ---------------- Public operations -------------- */ * Creates a new, empty map with the specified initial * capacity, load factor and concurrency level. * @param initialCapacity the initial capacity. The implementation * performs internal sizing to accommodate this many elements. * @param loadFactor the load factor threshold, used to control resizing. * Resizing may be performed when the average number of elements per * bin exceeds this threshold. * @param concurrencyLevel the estimated number of concurrently * updating threads. The implementation performs internal sizing * to try to accommodate this many threads. * @throws IllegalArgumentException if the initial capacity is * negative or the load factor or concurrencyLevel are // Find power-of-two sizes best matching arguments // create segments and segments[0] * Creates a new, empty map with the specified initial capacity * and load factor and with the default concurrencyLevel (16). * @param initialCapacity The implementation performs internal * sizing to accommodate this many elements. * @param loadFactor the load factor threshold, used to control resizing. * Resizing may be performed when the average number of elements per * bin exceeds this threshold. * @throws IllegalArgumentException if the initial capacity of * elements is negative or the load factor is nonpositive * Creates a new, empty map with the specified initial capacity, * and with default load factor (0.75) and concurrencyLevel (16). * @param initialCapacity the initial capacity. The implementation * performs internal sizing to accommodate this many elements. * @throws IllegalArgumentException if the initial capacity of * Creates a new, empty map with a default initial capacity (16), * load factor (0.75) and concurrencyLevel (16). * Creates a new map with the same mappings as the given map. * The map is created with a capacity of 1.5 times the number * of mappings in the given map or 16 (whichever is greater), * and a default load factor (0.75) and concurrencyLevel (16). * Returns <tt>true</tt> if this map contains no key-value mappings. * @return <tt>true</tt> if this map contains no key-value mappings * Sum per-segment modCounts to avoid mis-reporting when * elements are concurrently added and removed in one segment * while checking another, in which case the table was never * actually empty at any point. (The sum ensures accuracy up * through at least 1<<31 per-segment modifications before * recheck.) Methods size() and containsValue() use similar * constructions for stability checks. if (
sum !=
0L) {
// recheck unless no modifications * Returns the number of key-value mappings in this map. If the * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns * <tt>Integer.MAX_VALUE</tt>. * @return the number of key-value mappings in this map // Try a few times to get accurate count. On failure due to // continuous async changes in table, resort to locking. boolean overflow;
// true if size overflows 32 bits long sum;
// sum of modCounts long last =
0L;
// previous sum int retries = -
1;
// first iteration isn't retry if (c <
0 || (
size += c) <
0)
* Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code key.equals(k)}, * then this method returns {@code v}; otherwise it returns * {@code null}. (There can be at most one such mapping.) * @throws NullPointerException if the specified key is null Segment<K,V> s;
// manually integrate access methods to reduce overhead * Tests if the specified object is a key in this table. * @param key possible key * @return <tt>true</tt> if and only if the specified object * is a key in this table, as determined by the * <tt>equals</tt> method; <tt>false</tt> otherwise. * @throws NullPointerException if the specified key is null Segment<K,V> s;
// same as get() except no need for volatile value read * Returns <tt>true</tt> if this map maps one or more keys to the * specified value. Note: This method requires a full internal * traversal of the hash table, and so is much slower than * method <tt>containsKey</tt>. * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * @throws NullPointerException if the specified value is null * Legacy method testing if some key maps into the specified value * in this table. This method is identical in functionality to * {@link #containsValue}, and exists solely to ensure * full compatibility with class {@link java.util.Hashtable}, * which supported this method prior to introduction of the * Java Collections framework. * @param value a value to search for * @return <tt>true</tt> if and only if some key maps to the * <tt>value</tt> argument in this table as * determined by the <tt>equals</tt> method; * <tt>false</tt> otherwise * @throws NullPointerException if the specified value is null * Maps the specified key to the specified value in this table. * Neither the key nor the value can be null. * <p> The value can be retrieved by calling the <tt>get</tt> method * with a key that is equal to the original key. * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt> * @throws NullPointerException if the specified key or value is null * @return the previous value associated with the specified key, * or <tt>null</tt> if there was no mapping for the key * @throws NullPointerException if the specified key or value is null * Copies all of the mappings from the specified map to this one. * These mappings replace any mappings that this map had for any of the * keys currently in the specified map. * @param m mappings to be stored in this map public void putAll(
Map<?
extends K, ?
extends V> m) {
* Removes the key (and its corresponding value) from this map. * This method does nothing if the key is not in the map. * @param key the key that needs to be removed * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt> * @throws NullPointerException if the specified key is null * @throws NullPointerException if the specified key is null * @throws NullPointerException if any of the arguments are null * @return the previous value associated with the specified key, * or <tt>null</tt> if there was no mapping for the key * @throws NullPointerException if the specified key or value is null * Removes all of the mappings from this map. * Returns a {@link Set} view of the keys contained in this map. * The set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. The set supports element * removal, which removes the corresponding mapping from this map, * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> * operations. It does not support the <tt>add</tt> or * <tt>addAll</tt> operations. * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator * that will never throw {@link ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) * reflect any modifications subsequent to construction. * Returns a {@link Collection} view of the values contained in this map. * The collection is backed by the map, so changes to the map are * reflected in the collection, and vice-versa. The collection * supports element removal, which removes the corresponding * mapping from this map, via the <tt>Iterator.remove</tt>, * <tt>Collection.remove</tt>, <tt>removeAll</tt>, * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not * support the <tt>add</tt> or <tt>addAll</tt> operations. * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator * that will never throw {@link ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) * reflect any modifications subsequent to construction. * Returns a {@link Set} view of the mappings contained in this map. * The set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. The set supports element * removal, which removes the corresponding mapping from the map, * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> * operations. It does not support the <tt>add</tt> or * <tt>addAll</tt> operations. * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator * that will never throw {@link ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) * reflect any modifications subsequent to construction. * Returns an enumeration of the keys in this table. * @return an enumeration of the keys in this table * Returns an enumeration of the values in this table. * @return an enumeration of the values in this table /* ---------------- Iterator Support -------------- */ * Set nextEntry to first node of next non-empty table * (in backwards order, to simplify checks). * Custom Entry class used by EntryIterator.next(), that relays * setValue changes to the underlying map. * Set our entry's value and write through to the map. The * value to return is somewhat arbitrary here. Since a * WriteThroughEntry does not necessarily track asynchronous * changes, the most recent "previous" value could be * different from what we return (or could even have been * removed in which case the put will re-establish). We do not * and cannot guarantee more. /* ---------------- Serialization Support -------------- */ * Save the state of the <tt>ConcurrentHashMap</tt> instance to a * stream (i.e., serialize it). * the key (Object) and value (Object) * for each key-value mapping, followed by a null pair. * The key-value mappings are emitted in no particular order. // force all segments for serialization compatibility * Reconstitute the <tt>ConcurrentHashMap</tt> instance from a * stream (i.e., deserialize it). // Don't call defaultReadObject() || (
ssize & (
ssize-
1)) !=
0 )
// ssize not power of two // Re-initialize segments to be minimally sized, and let grow. // Read the keys and values, and put the mappings in the table private static final long SBASE;
private static final int SSHIFT;
private static final long TBASE;
private static final int TSHIFT;
if ((
ss & (
ss-
1)) !=
0 || (
ts & (
ts-
1)) !=
0)
throw new Error(
"data type scale not a power of two");