/**
 * A Red-Black tree based {@link NavigableMap} implementation.
 * The map is sorted according to the {@linkplain Comparable natural
 * ordering} of its keys, or by a {@link Comparator} provided at map
 * creation time, depending on which constructor is used.
 *
 * <p>This implementation provides guaranteed log(n) time cost for the
 * {@code containsKey}, {@code get}, {@code put} and {@code remove}
 * operations.  Algorithms are adaptations of those in Cormen, Leiserson, and
 * Rivest''s <em>Introduction to Algorithms</em>.
 *
 * <p>Note that the ordering maintained by a tree map, like any sorted map, and
 * whether or not an explicit comparator is provided, must be <em>consistent
 * with {@code equals}</em> if this sorted map is to correctly implement the
 * {@code Map} interface.  (See {@code Comparable} or {@code Comparator} for a
 * precise definition of <em>consistent with equals</em>.)  This is so because
 * the {@code Map} interface is defined in terms of the {@code equals}
 * operation, but a sorted map performs all key comparisons using its {@code
 * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
 * this method are, from the standpoint of the sorted map, equal.  The behavior
 * of a sorted map <em>is</em> well-defined even if its ordering is
 * inconsistent with {@code equals}; it just fails to obey the general contract
 * of the {@code Map} interface.
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a map concurrently, and at least one of the
 * threads modifies the map structurally, it <em>must</em> be synchronized
 * externally.  (A structural modification is any operation that adds or
 * deletes one or more mappings; merely changing the value associated
 * with an existing key is not a structural modification.)  This is
 * typically accomplished by synchronizing on some object that naturally
 * encapsulates the map.
 * If no such object exists, the map should be "wrapped" using the
 * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the map: <pre>
 *   SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
 *
 * <p>The iterators returned by the {@code iterator} method of the collections
 * returned by all of this class''s "collection view methods" are
 * <em>fail-fast</em>: if the map is structurally modified at any time after
 * the iterator is created, in any way except through the iterator''s own
 * {@code remove} method, the iterator will throw a {@link
 * ConcurrentModificationException}.  Thus, in the face of concurrent
 * modification, the iterator fails quickly and cleanly, rather than risking
 * arbitrary, non-deterministic behavior at an undetermined time in the future.
 *
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:   <em>the fail-fast behavior of iterators
 * should be used only to detect bugs.</em>
 *
 * <p>All {@code Map.Entry} pairs returned by methods in this class
 * and its views represent snapshots of mappings at the time they were
 * produced. They do <strong>not</strong> support the {@code Entry.setValue}
 * method. (Note however that it is possible to change mappings in the
 * associated map using {@code put}.)
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 *
 * @author  Josh Bloch and Doug Lea
 * @see Map
 * @see HashMap
 * @see Hashtable
 * @see Comparable
 * @see Comparator
 * @see Collection
 * @since 1.2
 */

 1 import java.util.*;
 2 import java.util.Map.Entry;
 3 public class Solution {
 4     public static void main(String[] args) {
 5         TreeMap<Integer, Integer> map = new TreeMap<>();
 6         map.put(1, 5);
 7         map.put(2, 4);
 8         map.put(3, 3);
 9         map.put(4, 2);
10         map.put(5, 1);
11         
12         for (Entry<Integer, Integer> entry : map.entrySet()) {
13             String s = entry.getKey()+"--"+entry.getValue();
14             System.out.println(s);
15         }
16     }
17 }

 1   public V put(K key, V value) {
 2         Entry<K,V> t = root;
 3         if (t == null) {
 4             compare(key, key); // type (and possibly null) check
 5 
 6             root = new Entry<>(key, value, null);
 7             size = 1;
 8             modCount++;
 9             return null;
10         }
11         int cmp;
12         Entry<K,V> parent;
13         // split comparator and comparable paths
14         Comparator<? super K> cpr = comparator;
15         if (cpr != null) {
16             do {
17                 parent = t;
18                 cmp = cpr.compare(key, t.key);
19                 if (cmp < 0)
20                     t = t.left;
21                 else if (cmp > 0)
22                     t = t.right;
23                 else
24                     return t.setValue(value);
25             } while (t != null);
26         }
27         else {
28             if (key == null)
29                 throw new NullPointerException();
30             @SuppressWarnings("unchecked")
31                 Comparable<? super K> k = (Comparable<? super K>) key;
32             do {
33                 parent = t;
34                 cmp = k.compareTo(t.key);
35                 if (cmp < 0)
36                     t = t.left;
37                 else if (cmp > 0)
38                     t = t.right;
39                 else
40                     return t.setValue(value);
41             } while (t != null);
42         }
43         Entry<K,V> e = new Entry<>(key, value, parent);
44         if (cmp < 0)
45             parent.left = e;
46         else
47             parent.right = e;
48         fixAfterInsertion(e);
49         size++;
50         modCount++;
51         return null;
52     }

1 /**
2      * Compares two keys using the correct comparison method for this TreeMap.
3      */
4     @SuppressWarnings("unchecked")
5     final int compare(Object k1, Object k2) {
6         return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
7             : comparator.compare((K)k1, (K)k2);
8     }

1     public V get(Object key) {
2         Entry<K,V> p = getEntry(key);
3         return (p==null ? null : p.value);
4     }

 1 final Entry<K,V> getEntry(Object key) {
 2         // Offload comparator-based version for sake of performance
 3         if (comparator != null)
 4             return getEntryUsingComparator(key);
 5         if (key == null)
 6             throw new NullPointerException();
 7         @SuppressWarnings("unchecked")
 8             Comparable<? super K> k = (Comparable<? super K>) key;
 9         Entry<K,V> p = root;
10         while (p != null) {
11             int cmp = k.compareTo(p.key);
12             if (cmp < 0)
13                 p = p.left;
14             else if (cmp > 0)
15                 p = p.right;
16             else
17                 return p;
18         }
19         return null;
20     }

 1 final Entry<K,V> getEntryUsingComparator(Object key) {
 2         @SuppressWarnings("unchecked")
 3             K k = (K) key;
 4         Comparator<? super K> cpr = comparator;
 5         if (cpr != null) {
 6             Entry<K,V> p = root;
 7             while (p != null) {
 8                 int cmp = cpr.compare(k, p.key);
 9                 if (cmp < 0)
10                     p = p.left;
11                 else if (cmp > 0)
12                     p = p.right;
13                 else
14                     return p;
15             }
16         }
17         return null;
18     }

1     public V remove(Object key) {
2         Entry<K,V> p = getEntry(key);
3         if (p == null)
4             return null;
5 
6         V oldValue = p.value;
7         deleteEntry(p);
8         return oldValue;
9     }

1     final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
2         EntryIterator(Entry<K,V> first) {
3             super(first);
4         }
5         public Map.Entry<K,V> next() {
6             return nextEntry();
7         }
8     }

 1  abstract class PrivateEntryIterator<T> implements Iterator<T> {
 2         Entry<K,V> next;
 3         Entry<K,V> lastReturned;
 4         int expectedModCount;
 5 
 6         PrivateEntryIterator(Entry<K,V> first) {
 7             expectedModCount = modCount;
 8             lastReturned = null;
 9             next = first;
10         }
11 
12         public final boolean hasNext() {
13             return next != null;
14         }
15 
16         final Entry<K,V> nextEntry() {
17             Entry<K,V> e = next;
18             if (e == null)
19                 throw new NoSuchElementException();
20             if (modCount != expectedModCount)
21                 throw new ConcurrentModificationException();
22             next = successor(e);
23             lastReturned = e;
24             return e;
25         }

 1 static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
 2         if (t == null)
 3             return null;
 4         else if (t.right != null) {
 5             Entry<K,V> p = t.right;
 6             while (p.left != null)
 7                 p = p.left;
 8             return p;
 9         } else {
10             Entry<K,V> p = t.parent;
11             Entry<K,V> ch = t;
12             while (p != null && ch == p.right) {
13                 ch = p;
14                 p = p.parent;
15             }
16             return p;
17         }
18     }

  1 /**
  2  * A hash table supporting full concurrency of retrievals and
  3  * high expected concurrency for updates. This class obeys the
  4  * same functional specification as {@link java.util.Hashtable}, and
  5  * includes versions of methods corresponding to each method of
  6  * {@code Hashtable}. However, even though all operations are
  7  * thread-safe, retrieval operations do <em>not</em> entail locking,
  8  * and there is <em>not</em> any support for locking the entire table
  9  * in a way that prevents all access.  This class is fully
 10  * interoperable with {@code Hashtable} in programs that rely on its
 11  * thread safety but not on its synchronization details.
 12  *
 13  * <p>Retrieval operations (including {@code get}) generally do not
 14  * block, so may overlap with update operations (including {@code put}
 15  * and {@code remove}). Retrievals reflect the results of the most
 16  * recently <em>completed</em> update operations holding upon their
 17  * onset. (More formally, an update operation for a given key bears a
 18  * <em>happens-before</em> relation with any (non-null) retrieval for
 19  * that key reporting the updated value.)  For aggregate operations
 20  * such as {@code putAll} and {@code clear}, concurrent retrievals may
 21  * reflect insertion or removal of only some entries.  Similarly,
 22  * Iterators, Spliterators and Enumerations return elements reflecting the
 23  * state of the hash table at some point at or since the creation of the
 24  * iterator/enumeration.  They do <em>not</em> throw {@link
 25  * java.util.ConcurrentModificationException ConcurrentModificationException}.
 26  * However, iterators are designed to be used by only one thread at a time.
 27  * Bear in mind that the results of aggregate status methods including
 28  * {@code size}, {@code isEmpty}, and {@code containsValue} are typically
 29  * useful only when a map is not undergoing concurrent updates in other threads.
 30  * Otherwise the results of these methods reflect transient states
 31  * that may be adequate for monitoring or estimation purposes, but not
 32  * for program control.
 33  *
 34  * <p>The table is dynamically expanded when there are too many
 35  * collisions (i.e., keys that have distinct hash codes but fall into
 36  * the same slot modulo the table size), with the expected average
 37  * effect of maintaining roughly two bins per mapping (corresponding
 38  * to a 0.75 load factor threshold for resizing). There may be much
 39  * variance around this average as mappings are added and removed, but
 40  * overall, this maintains a commonly accepted time/space tradeoff for
 41  * hash tables.  However, resizing this or any other kind of hash
 42  * table may be a relatively slow operation. When possible, it is a
 43  * good idea to provide a size estimate as an optional {@code
 44  * initialCapacity} constructor argument. An additional optional
 45  * {@code loadFactor} constructor argument provides a further means of
 46  * customizing initial table capacity by specifying the table density
 47  * to be used in calculating the amount of space to allocate for the
 48  * given number of elements.  Also, for compatibility with previous
 49  * versions of this class, constructors may optionally specify an
 50  * expected {@code concurrencyLevel} as an additional hint for
 51  * internal sizing.  Note that using many keys with exactly the same
 52  * {@code hashCode()} is a sure way to slow down performance of any
 53  * hash table. To ameliorate impact, when keys are {@link Comparable},
 54  * this class may use comparison order among keys to help break ties.
 55  *
 56  * <p>A {@link Set} projection of a ConcurrentHashMap may be created
 57  * (using {@link #newKeySet()} or {@link #newKeySet(int)}), or viewed
 58  * (using {@link #keySet(Object)} when only keys are of interest, and the
 59  * mapped values are (perhaps transiently) not used or all take the
 60  * same mapping value.
 61  *
 62  * <p>A ConcurrentHashMap can be used as scalable frequency map (a
 63  * form of histogram or multiset) by using {@link
 64  * java.util.concurrent.atomic.LongAdder} values and initializing via
 65  * {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
 66  * to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
 67  * {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
 68  *
 69  * <p>This class and its views and iterators implement all of the
 70  * <em>optional</em> methods of the {@link Map} and {@link Iterator}
 71  * interfaces.
 72  *
 73  * <p>Like {@link Hashtable} but unlike {@link HashMap}, this class
 74  * does <em>not</em> allow {@code null} to be used as a key or value.
 75  *
 76  * <p>ConcurrentHashMaps support a set of sequential and parallel bulk
 77  * operations that, unlike most {@link Stream} methods, are designed
 78  * to be safely, and often sensibly, applied even with maps that are
 79  * being concurrently updated by other threads; for example, when
 80  * computing a snapshot summary of the values in a shared registry.
 81  * There are three kinds of operation, each with four forms, accepting
 82  * functions with Keys, Values, Entries, and (Key, Value) arguments
 83  * and/or return values. Because the elements of a ConcurrentHashMap
 84  * are not ordered in any particular way, and may be processed in
 85  * different orders in different parallel executions, the correctness
 86  * of supplied functions should not depend on any ordering, or on any
 87  * other objects or values that may transiently change while
 88  * computation is in progress; and except for forEach actions, should
 89  * ideally be side-effect-free. Bulk operations on {@link java.util.Map.Entry}
 90  * objects do not support method {@code setValue}.
 91  *
 92  * <ul>
 93  * <li> forEach: Perform a given action on each element.
 94  * A variant form applies a given transformation on each element
 95  * before performing the action.</li>
 96  *
 97  * <li> search: Return the first available non-null result of
 98  * applying a given function on each element; skipping further
 99  * search when a result is found.</li>
100  *
101  * <li> reduce: Accumulate each element.  The supplied reduction
102  * function cannot rely on ordering (more formally, it should be
103  * both associative and commutative).  There are five variants:
104  *
105  * <ul>
106  *
107  * <li> Plain reductions. (There is not a form of this method for
108  * (key, value) function arguments since there is no corresponding
109  * return type.)</li>
110  *
111  * <li> Mapped reductions that accumulate the results of a given
112  * function applied to each element.</li>
113  *
114  * <li> Reductions to scalar doubles, longs, and ints, using a
115  * given basis value.</li>
116  *
117  * </ul>
118  * </li>
119  * </ul>
120  *
121  * <p>These bulk operations accept a {@code parallelismThreshold}
122  * argument. Methods proceed sequentially if the current map size is
123  * estimated to be less than the given threshold. Using a value of
124  * {@code Long.MAX_VALUE} suppresses all parallelism.  Using a value
125  * of {@code 1} results in maximal parallelism by partitioning into
126  * enough subtasks to fully utilize the {@link
127  * ForkJoinPool#commonPool()} that is used for all parallel
128  * computations. Normally, you would initially choose one of these
129  * extreme values, and then measure performance of using in-between
130  * values that trade off overhead versus throughput.
131  *
132  * <p>The concurrency properties of bulk operations follow
133  * from those of ConcurrentHashMap: Any non-null result returned
134  * from {@code get(key)} and related access methods bears a
135  * happens-before relation with the associated insertion or
136  * update.  The result of any bulk operation reflects the
137  * composition of these per-element relations (but is not
138  * necessarily atomic with respect to the map as a whole unless it
139  * is somehow known to be quiescent).  Conversely, because keys
140  * and values in the map are never null, null serves as a reliable
141  * atomic indicator of the current lack of any result.  To
142  * maintain this property, null serves as an implicit basis for
143  * all non-scalar reduction operations. For the double, long, and
144  * int versions, the basis should be one that, when combined with
145  * any other value, returns that other value (more formally, it
146  * should be the identity element for the reduction). Most common
147  * reductions have these properties; for example, computing a sum
148  * with basis 0 or a minimum with basis MAX_VALUE.
149  *
150  * <p>Search and transformation functions provided as arguments
151  * should similarly return null to indicate the lack of any result
152  * (in which case it is not used). In the case of mapped
153  * reductions, this also enables transformations to serve as
154  * filters, returning null (or, in the case of primitive
155  * specializations, the identity basis) if the element should not
156  * be combined. You can create compound transformations and
157  * filterings by composing them yourself under this "null means
158  * there is nothing there now" rule before using them in search or
159  * reduce operations.
160  *
161  * <p>Methods accepting and/or returning Entry arguments maintain
162  * key-value associations. They may be useful for example when
163  * finding the key for the greatest value. Note that "plain" Entry
164  * arguments can be supplied using {@code new
165  * AbstractMap.SimpleEntry(k,v)}.
166  *
167  * <p>Bulk operations may complete abruptly, throwing an
168  * exception encountered in the application of a supplied
169  * function. Bear in mind when handling such exceptions that other
170  * concurrently executing functions could also have thrown
171  * exceptions, or would have done so if the first exception had
172  * not occurred.
173  *
174  * <p>Speedups for parallel compared to sequential forms are common
175  * but not guaranteed.  Parallel operations involving brief functions
176  * on small maps may execute more slowly than sequential forms if the
177  * underlying work to parallelize the computation is more expensive
178  * than the computation itself.  Similarly, parallelization may not
179  * lead to much actual parallelism if all processors are busy
180  * performing unrelated tasks.
181  *
182  * <p>All arguments to all task methods must be non-null.
183  *
184  * <p>This class is a member of the
185  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
186  * Java Collections Framework</a>.
187  *
188  * @since 1.5
189  * @author Doug Lea
190  * @param <K> the type of keys maintained by this map
191  * @param <V> the type of mapped values
192  */

 1     /* ---------------- Fields -------------- */
 2 
 3     /**
 4      * The array of bins. Lazily initialized upon first insertion.
 5      * Size is always a power of two. Accessed directly by iterators.
 6      */
 7     transient volatile Node<K,V>[] table;
 8 
 9     /**
10      * The next table to use; non-null only while resizing.
11      */
12     private transient volatile Node<K,V>[] nextTable;
13 
14     /**
15      * Base counter value, used mainly when there is no contention,
16      * but also as a fallback during table initialization
17      * races. Updated via CAS.
18      */
19     private transient volatile long baseCount;
20 
21     /**
22      * Table initialization and resizing control.  When negative, the
23      * table is being initialized or resized: -1 for initialization,
24      * else -(1 + the number of active resizing threads).  Otherwise,
25      * when table is null, holds the initial table size to use upon
26      * creation, or 0 for default. After initialization, holds the
27      * next element count value upon which to resize the table.
28      */
29     private transient volatile int sizeCtl;
30 
31     /**
32      * The next table index (plus one) to split while resizing.
33      */
34     private transient volatile int transferIndex;
35 
36     /**
37      * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
38      */
39     private transient volatile int cellsBusy;
40 
41     /**
42      * Table of counter cells. When non-null, size is a power of 2.
43      */
44     private transient volatile CounterCell[] counterCells;
45 
46     // views
47     private transient KeySetView<K,V> keySet;
48     private transient ValuesView<K,V> values;
49     private transient EntrySetView<K,V> entrySet;

 1 public ConcurrentHashMap() {
 2     }
 3 
 4     /**
 5      * Creates a new, empty map with an initial table size
 6      * accommodating the specified number of elements without the need
 7      * to dynamically resize.
 8      *
 9      * @param initialCapacity The implementation performs internal
10      * sizing to accommodate this many elements.
11      * @throws IllegalArgumentException if the initial capacity of
12      * elements is negative
13      */
14     public ConcurrentHashMap(int initialCapacity) {
15         if (initialCapacity < 0)
16             throw new IllegalArgumentException();
17         int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
18                    MAXIMUM_CAPACITY :
19                    tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
20         this.sizeCtl = cap;
21     }
22 
23     /**
24      * Creates a new map with the same mappings as the given map.
25      *
26      * @param m the map
27      */
28     public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
29         this.sizeCtl = DEFAULT_CAPACITY;
30         putAll(m);
31     }
32 
33     /**
34      * Creates a new, empty map with an initial table size based on
35      * the given number of elements ({@code initialCapacity}) and
36      * initial table density ({@code loadFactor}).
37      *
38      * @param initialCapacity the initial capacity. The implementation
39      * performs internal sizing to accommodate this many elements,
40      * given the specified load factor.
41      * @param loadFactor the load factor (table density) for
42      * establishing the initial table size
43      * @throws IllegalArgumentException if the initial capacity of
44      * elements is negative or the load factor is nonpositive
45      *
46      * @since 1.6
47      */
48     public ConcurrentHashMap(int initialCapacity, float loadFactor) {
49         this(initialCapacity, loadFactor, 1);
50     }
51 
52     /**
53      * Creates a new, empty map with an initial table size based on
54      * the given number of elements ({@code initialCapacity}), table
55      * density ({@code loadFactor}), and number of concurrently
56      * updating threads ({@code concurrencyLevel}).
57      *
58      * @param initialCapacity the initial capacity. The implementation
59      * performs internal sizing to accommodate this many elements,
60      * given the specified load factor.
61      * @param loadFactor the load factor (table density) for
62      * establishing the initial table size
63      * @param concurrencyLevel the estimated number of concurrently
64      * updating threads. The implementation may use this value as
65      * a sizing hint.
66      * @throws IllegalArgumentException if the initial capacity is
67      * negative or the load factor or concurrencyLevel are
68      * nonpositive
69      */
70     public ConcurrentHashMap(int initialCapacity,
71                              float loadFactor, int concurrencyLevel) {
72         if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
73             throw new IllegalArgumentException();
74         if (initialCapacity < concurrencyLevel)   // Use at least as many bins
75             initialCapacity = concurrencyLevel;   // as estimated threads
76         long size = (long)(1.0 + (long)initialCapacity / loadFactor);
77         int cap = (size >= (long)MAXIMUM_CAPACITY) ?
78             MAXIMUM_CAPACITY : tableSizeFor((int)size);
79         this.sizeCtl = cap;
80     }

1     private static final int tableSizeFor(int c) {
2         int n = c - 1;
3         n |= n >>> 1;
4         n |= n >>> 2;
5         n |= n >>> 4;
6         n |= n >>> 8;
7         n |= n >>> 16;
8         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
9     }

 1     final V putVal(K key, V value, boolean onlyIfAbsent) {
 2         if (key == null || value == null) throw new NullPointerException();
 3         int hash = spread(key.hashCode());
 4         int binCount = 0;
 5         for (Node<K,V>[] tab = table;;) {
 6             Node<K,V> f; int n, i, fh;
 7             if (tab == null || (n = tab.length) == 0)
 8                 tab = initTable();
 9             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
10                 if (casTabAt(tab, i, null,
11                              new Node<K,V>(hash, key, value, null)))
12                     break;                   // no lock when adding to empty bin
13             }
14             else if ((fh = f.hash) == MOVED)
15                 tab = helpTransfer(tab, f);
16             else {
17                 V oldVal = null;
18                 synchronized (f) {
19                     if (tabAt(tab, i) == f) {
20                         if (fh >= 0) {
21                             binCount = 1;
22                             for (Node<K,V> e = f;; ++binCount) {
23                                 K ek;
24                                 if (e.hash == hash &&
25                                     ((ek = e.key) == key ||
26                                      (ek != null && key.equals(ek)))) {
27                                     oldVal = e.val;
28                                     if (!onlyIfAbsent)
29                                         e.val = value;
30                                     break;
31                                 }
32                                 Node<K,V> pred = e;
33                                 if ((e = e.next) == null) {
34                                     pred.next = new Node<K,V>(hash, key,
35                                                               value, null);
36                                     break;
37                                 }
38                             }
39                         }
40                         else if (f instanceof TreeBin) {
41                             Node<K,V> p;
42                             binCount = 2;
43                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
44                                                            value)) != null) {
45                                 oldVal = p.val;
46                                 if (!onlyIfAbsent)
47                                     p.val = value;
48                             }
49                         }
50                     }
51                 }
52                 if (binCount != 0) {
53                     if (binCount >= TREEIFY_THRESHOLD)
54                         treeifyBin(tab, i);
55                     if (oldVal != null)
56                         return oldVal;
57                     break;
58                 }
59             }
60         }
61         addCount(1L, binCount);
62         return null;
63     }

 1     private final Node<K,V>[] initTable() {
 2         Node<K,V>[] tab; int sc;
 3         while ((tab = table) == null || tab.length == 0) {
 4             if ((sc = sizeCtl) < 0)
 5                 Thread.yield(); // lost initialization race; just spin
 6             else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
 7                 try {
 8                     if ((tab = table) == null || tab.length == 0) {
 9                         int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
10                         @SuppressWarnings("unchecked")
11                         Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
12                         table = tab = nt;
13                         sc = n - (n >>> 2);
14                     }
15                 } finally {
16                     sizeCtl = sc;
17                 }
18                 break;
19             }
20         }
21         return tab;
22     }

 1   static class Node<K,V> implements Map.Entry<K,V> {
 2         final int hash;
 3         final K key;
 4         volatile V val;
 5         volatile Node<K,V> next;
 6 
 7         Node(int hash, K key, V val, Node<K,V> next) {
 8             this.hash = hash;
 9             this.key = key;
10             this.val = val;
11             this.next = next;
12         }
13 
14         public final K getKey()       { return key; }
15         public final V getValue()     { return val; }
16         public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
17         public final String toString(){ return key + "=" + val; }
18         public final V setValue(V value) {
19             throw new UnsupportedOperationException();
20         }
21 
22         public final boolean equals(Object o) {
23             Object k, v, u; Map.Entry<?,?> e;
24             return ((o instanceof Map.Entry) &&
25                     (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
26                     (v = e.getValue()) != null &&
27                     (k == key || k.equals(key)) &&
28                     (v == (u = val) || v.equals(u)));
29         }

 1     public V get(Object key) {
 2         Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
 3         int h = spread(key.hashCode());
 4         if ((tab = table) != null && (n = tab.length) > 0 &&
 5             (e = tabAt(tab, (n - 1) & h)) != null) {
 6             if ((eh = e.hash) == h) {
 7                 if ((ek = e.key) == key || (ek != null && key.equals(ek)))
 8                     return e.val;
 9             }
10             else if (eh < 0)
11                 return (p = e.find(h, key)) != null ? p.val : null;
12             while ((e = e.next) != null) {
13                 if (e.hash == h &&
14                     ((ek = e.key) == key || (ek != null && key.equals(ek))))
15                     return e.val;
16             }
17         }
18         return null;
19     }

 1 /**
 2  * A <i>thread</i> is a thread of execution in a program. The Java
 3  * Virtual Machine allows an application to have multiple threads of
 4  * execution running concurrently.
 5  * <p>
 6  * Every thread has a priority. Threads with higher priority are
 7  * executed in preference to threads with lower priority. Each thread
 8  * may or may not also be marked as a daemon. When code running in
 9  * some thread creates a new <code>Thread</code> object, the new
10  * thread has its priority initially set equal to the priority of the
11  * creating thread, and is a daemon thread if and only if the
12  * creating thread is a daemon.
13  * <p>
14  * When a Java Virtual Machine starts up, there is usually a single
15  * non-daemon thread (which typically calls the method named
16  * <code>main</code> of some designated class). The Java Virtual
17  * Machine continues to execute threads until either of the following
18  * occurs:
19  * <ul>
20  * <li>The <code>exit</code> method of class <code>Runtime</code> has been
21  *     called and the security manager has permitted the exit operation
22  *     to take place.
23  * <li>All threads that are not daemon threads have died, either by
24  *     returning from the call to the <code>run</code> method or by
25  *     throwing an exception that propagates beyond the <code>run</code>
26  *     method.
27  * </ul>
28  * <p>
29  * There are two ways to create a new thread of execution. One is to
30  * declare a class to be a subclass of <code>Thread</code>. This
31  * subclass should override the <code>run</code> method of class
32  * <code>Thread</code>. An instance of the subclass can then be
33  * allocated and started. For example, a thread that computes primes
34  * larger than a stated value could be written as follows:
35  * <hr><blockquote><pre>
36  *     class PrimeThread extends Thread {
37  *         long minPrime;
38  *         PrimeThread(long minPrime) {
39  *             this.minPrime = minPrime;
40  *         }
41  *
42  *         public void run() {
43  *             // compute primes larger than minPrime
44  *             &nbsp;.&nbsp;.&nbsp;.
45  *         }
46  *     }
47  * </pre></blockquote><hr>
48  * <p>
49  * The following code would then create a thread and start it running:
50  * <blockquote><pre>
51  *     PrimeThread p = new PrimeThread(143);
52  *     p.start();
53  * </pre></blockquote>
54  * <p>
55  * The other way to create a thread is to declare a class that
56  * implements the <code>Runnable</code> interface. That class then
57  * implements the <code>run</code> method. An instance of the class can
58  * then be allocated, passed as an argument when creating
59  * <code>Thread</code>, and started. The same example in this other
60  * style looks like the following:
61  * <hr><blockquote><pre>
62  *     class PrimeRun implements Runnable {
63  *         long minPrime;
64  *         PrimeRun(long minPrime) {
65  *             this.minPrime = minPrime;
66  *         }
67  *
68  *         public void run() {
69  *             // compute primes larger than minPrime
70  *             &nbsp;.&nbsp;.&nbsp;.
71  *         }
72  *     }
73  * </pre></blockquote><hr>
74  * <p>
75  * The following code would then create a thread and start it running:
76  * <blockquote><pre>
77  *     PrimeRun p = new PrimeRun(143);
78  *     new Thread(p).start();
79  * </pre></blockquote>
80  * <p>
81  * Every thread has a name for identification purposes. More than
82  * one thread may have the same name. If a name is not specified when
83  * a thread is created, a new name is generated for it.
84  * <p>
85  * Unless otherwise noted, passing a {@code null} argument to a constructor
86  * or method in this class will cause a {@link NullPointerException} to be
87  * thrown.
88  *
89  * @author  unascribed
90  * @see     Runnable
91  * @see     Runtime#exit(int)
92  * @see     #run()
93  * @see     #stop()
94  * @since   JDK1.0
95  */