/* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation.  Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ /* * This file is available under and governed by the GNU General Public * License version 2 only, as published by the Free Software Foundation. * However, the following notice accompanied the original version of this * file: * * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at * http://creativecommons.org/publicdomain/zero/1.0/ */ package java.util.concurrent;import java.util.concurrent.locks.*;import java.util.*;import java.io.Serializable;import java.io.IOException;import java.io.ObjectInputStream;import java.io.ObjectOutputStream; /** * 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 * at some point at or since the creation of the iterator/enumeration. * 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 * constructors. * * <p>This class and its views and iterators implement all of the * <em>optional</em> methods of the {@link Map} and {@link Iterator} * interfaces. * * <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 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> * Java Collections Framework</a>. * * @since 1.5 * @author Doug Lea * @param <K> the type of keys maintained by this map * @param <V> the type of mapped values */public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>        implements ConcurrentMap<K, V>, Serializable {    private static final long serialVersionUID = 7249069246763182397L;     /*     * 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     * of table updates.     *     * 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.     */    static final int DEFAULT_INITIAL_CAPACITY = 16;     /**     * The default load factor for this table, used when not     * otherwise specified in a constructor.     */    static final float DEFAULT_LOAD_FACTOR = 0.75f;     /**     * The default concurrency level for this table, used when not     * otherwise specified in a constructor.     */    static final int DEFAULT_CONCURRENCY_LEVEL = 16;     /**     * 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     * using ints.     */    static final int MAXIMUM_CAPACITY = 1 << 30;     /**     * 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.     */    static final int MIN_SEGMENT_TABLE_CAPACITY = 2;     /**     * 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.     */    static final int RETRIES_BEFORE_LOCK = 2;     /* ---------------- Fields -------------- */     /**     * Mask value for indexing into segments. The upper bits of a     * key's hash code are used to choose the segment.     */    final int segmentMask;     /**     * Shift value for indexing within segments.     */    final int segmentShift;     /**     * The segments, each of which is a specialized hash table.     */    final Segment<K,V>[] segments;     transient Set<K> keySet;    transient Set<Map.Entry<K,V>> entrySet;    transient Collection<V> values;     /**     * ConcurrentHashMap list entry. Note that this is never exported     * out as a user-visible Map.Entry.     */    static final class HashEntry<K,V> {        final int hash;        final K key;        volatile V value;        volatile HashEntry<K,V> next;         HashEntry(int hash, K key, V value, HashEntry<K,V> next) {            this.hash = hash;            this.key = key;            this.value = value;            this.next = next;        }         /**         * Sets next field with volatile write semantics.  (See above         * about use of putOrderedObject.)         */        final void setNext(HashEntry<K,V> n) {            UNSAFE.putOrderedObject(this, nextOffset, n);        }         // Unsafe mechanics        static final sun.misc.Unsafe UNSAFE;        static final long nextOffset;        static {            try {                UNSAFE = sun.misc.Unsafe.getUnsafe();                Class k = HashEntry.class;                nextOffset = UNSAFE.objectFieldOffset                    (k.getDeclaredField("next"));            } catch (Exception e) {                throw new Error(e);            }        }    }     /**     * 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.     */    @SuppressWarnings("unchecked")    static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {        return (tab == null) ? null :            (HashEntry<K,V>) UNSAFE.getObjectVolatile            (tab, ((long)i << TSHIFT) + TBASE);    }     /**     * Sets the ith element of given table, with volatile write     * semantics. (See above about use of putOrderedObject.)     */    static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i,                                       HashEntry<K,V> e) {        UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);    }     /**     * 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.     */    private static int hash(int h) {        // Spread bits to regularize both segment and index locations,        // using variant of single-word Wang/Jenkins hash.        h += (h <<  15) ^ 0xffffcd7d;        h ^= (h >>> 10);        h += (h <<   3);        h ^= (h >>>  6);        h += (h <<   2) + (h << 14);        return h ^ (h >>> 16);    }     /**     * Segments are specialized versions of hash tables.  This     * subclasses from ReentrantLock opportunistically, just to     * simplify some locking and avoid separate construction.     */    static final class Segment<K,V> extends ReentrantLock implements Serializable {        /*         * 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.         */         private static final long serialVersionUID = 2249069246763182397L;         /**         * 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         * nodes.         */        static final int MAX_SCAN_RETRIES =            Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;         /**         * The per-segment table. Elements are accessed via         * entryAt/setEntryAt providing volatile semantics.         */        transient volatile HashEntry<K,V>[] table;         /**         * The number of elements. Accessed only either within locks         * or among other volatile reads that maintain visibility.         */        transient int count;         /**         * 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.         */        transient int modCount;         /**         * The table is rehashed when its size exceeds this threshold.         * (The value of this field is always <tt>(int)(capacity *         * loadFactor)</tt>.)         */        transient int threshold;         /**         * The load factor for the hash table.  Even though this value         * is same for all segments, it is replicated to avoid needing         * links to outer object.         * @serial         */        final float loadFactor;         Segment(float lf, int threshold, HashEntry<K,V>[] tab) {            this.loadFactor = lf;            this.threshold = threshold;            this.table = tab;        }         final V put(K key, int hash, V value, boolean onlyIfAbsent) {            HashEntry<K,V> node = tryLock() ? null :                scanAndLockForPut(key, hash, value);            V oldValue;            try {                HashEntry<K,V>[] tab = table;                int index = (tab.length - 1) & hash;                HashEntry<K,V> first = entryAt(tab, index);                for (HashEntry<K,V> e = first;;) {                    if (e != null) {                        K k;                        if ((k = e.key) == key ||                            (e.hash == hash && key.equals(k))) {                            oldValue = e.value;                            if (!onlyIfAbsent) {                                e.value = value;                                ++modCount;                            }                            break;                        }                        e = e.next;                    }                    else {                        if (node != null)                            node.setNext(first);                        else                            node = new HashEntry<K,V>(hash, key, value, first);                        int c = count + 1;                        if (c > threshold && tab.length < MAXIMUM_CAPACITY)                            rehash(node);                        else                            setEntryAt(tab, index, node);                        ++modCount;                        count = c;                        oldValue = null;                        break;                    }                }            } finally {                unlock();            }            return oldValue;        }         /**         * Doubles size of table and repacks entries, also adding the         * given node to new table         */        @SuppressWarnings("unchecked")        private void rehash(HashEntry<K,V> node) {            /*             * 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             * table write.             */            HashEntry<K,V>[] oldTable = table;            int oldCapacity = oldTable.length;            int newCapacity = oldCapacity << 1;            threshold = (int)(newCapacity * loadFactor);            HashEntry<K,V>[] newTable =                (HashEntry<K,V>[]) new HashEntry[newCapacity];            int sizeMask = newCapacity - 1;            for (int i = 0; i < oldCapacity ; i++) {                HashEntry<K,V> e = oldTable[i];                if (e != null) {                    HashEntry<K,V> next = e.next;                    int idx = e.hash & sizeMask;                    if (next == null)   //  Single node on list                        newTable[idx] = e;                    else { // Reuse consecutive sequence at same slot                        HashEntry<K,V> lastRun = e;                        int lastIdx = idx;                        for (HashEntry<K,V> last = next;                             last != null;                             last = last.next) {                            int k = last.hash & sizeMask;                            if (k != lastIdx) {                                lastIdx = k;                                lastRun = last;                            }                        }                        newTable[lastIdx] = lastRun;                        // Clone remaining nodes                        for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {                            V v = p.value;                            int h = p.hash;                            int k = h & sizeMask;                            HashEntry<K,V> n = newTable[k];                            newTable[k] = new HashEntry<K,V>(h, p.key, v, n);                        }                    }                }            }            int nodeIndex = node.hash & sizeMask; // add the new node            node.setNext(newTable[nodeIndex]);            newTable[nodeIndex] = node;            table = newTable;        }         /**         * 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         */        private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {            HashEntry<K,V> first = entryForHash(this, hash);            HashEntry<K,V> e = first;            HashEntry<K,V> node = null;            int retries = -1; // negative while locating node            while (!tryLock()) {                HashEntry<K,V> f; // to recheck first below                if (retries < 0) {                    if (e == null) {                        if (node == null) // speculatively create node                            node = new HashEntry<K,V>(hash, key, value, null);                        retries = 0;                    }                    else if (key.equals(e.key))                        retries = 0;                    else

Lines 1–500 of 1522. Load more