/*

* Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved.

* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*/

package java.util;

import java.io.IOException;

import java.io.InvalidObjectException;

import java.io.ObjectInputStream;

import java.io.Serializable;

import java.lang.reflect.ParameterizedType;

import java.lang.reflect.Type;

import java.util.function.BiConsumer;

import java.util.function.BiFunction;

import java.util.function.Consumer;

import java.util.function.Function;

/**

* hashMap术语介绍：

*    哈希表： 就是hashmap的table数组

*    bin（bucket）: 就是挂在数组上的链表

*   TreeNode: 红黑树

*   capacity： table总容量

*   MIN_TREEIFY_CAPACITY ：64   转化为红黑树table最小大小

*   TREEIFY_THRESHOLD ：8  转化为红黑树的阈值

*   loadFactor:  0.75  table扩容因子，当实际length大于等于 capacity*loadFactor时会进行扩容，并且扩容是按照2的整数次幂

* <p>

* 1)、HashMap中初始化大小为什么是16?

* 减少hash碰撞

* 提高map查询效率

* 分配过小防止频繁扩展

* 分配过大浪费资源

* 2）、为什么hahmap每次扩容都是以 2的整数次幂进行扩容?

* index = (n - 1) & hash

* 因为Hashmap计算存储位置时，使用了(n - 1) & hash。

* 只有当容量n为2的幂次方，n-1的二进制会全为1，

* 位运算时可以充分散列，避免不必要的哈希冲突，所以扩容必须2倍就是为了维持容量始终为2的幂次方。

* 3）、为什么链表的长度为8是变成红黑树？为什么为6时又变成链表？

* 综合链表和红黑树查询时间对比

* 每个链表元素个数出现概率，符合泊松分布，出现8以上概率很小。

*/

/**

* 基于哈希表的Map接口实现。这个实现提供了所有可选的映射操作，并允许空值和空键。

* （HashMap类大致相当于Hashtable，只是它不同步并且允许空值。）这个类不保证映射的顺序；

* 特别是，它不保证随着时间的推移顺序保持不变。

* <p>

* Hash table based implementation of the <tt>Map</tt> interface. This

* implementation provides all of the optional map operations, and permits

* <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>

* class is roughly equivalent to <tt>Hashtable</tt>, except that it is

* unsynchronized and permits nulls.) This class makes no guarantees as to

* the order of the map; in particular, it does not guarantee that the order

* will remain constant over time.

*

* <p>This implementation provides constant-time performance for the basic

* operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function

* disperses the elements properly among the buckets. Iteration over

* collection views requires time proportional to the "capacity" of the

* <tt>HashMap</tt> instance (the number of buckets) plus its size (the number

* of key-value mappings). Thus, it's very important not to set the initial

* capacity too high (or the load factor too low) if iteration performance is

* important.

*

* <p>An instance of <tt>HashMap</tt> has two parameters that affect its

* performance: <i>initial capacity</i> and <i>load factor</i>. The

* <i>capacity</i> is the number of buckets in the hash table, and the initial

* capacity is simply the capacity at the time the hash table is created. The

* <i>load factor</i> is a measure of how full the hash table is allowed to

* get before its capacity is automatically increased. When the number of

* entries in the hash table exceeds the product of the load factor and the

* current capacity, the hash table is <i>rehashed</i> (that is, internal data

* structures are rebuilt) so that the hash table has approximately twice the

* number of buckets.

*

* <p>As a general rule, the default load factor (.75) offers a good

* tradeoff between time and space costs. Higher values decrease the

* space overhead but increase the lookup cost (reflected in most of

* the operations of the <tt>HashMap</tt> class, including

* <tt>get</tt> and <tt>put</tt>). The expected number of entries in

* the map and its load factor should be taken into account when

* setting its initial capacity, so as to minimize the number of

* rehash operations. If the initial capacity is greater than the

* maximum number of entries divided by the load factor, no rehash

* operations will ever occur.

*

* <p>If many mappings are to be stored in a <tt>HashMap</tt>

* instance, creating it with a sufficiently large capacity will allow

* the mappings to be stored more efficiently than letting it perform

* automatic rehashing as needed to grow the table. Note that using

* many keys with the same {@code hashCode()} is a sure way to slow

* down performance of any hash table. To ameliorate impact, when keys

* are {@link Comparable}, this class may use comparison order among

* keys to help break ties.

*

* <p><strong>Note that this implementation is not synchronized.</strong>

* If multiple threads access a hash map concurrently, and at least one of

* the threads modifies the map structurally, it <i>must</i> be

* synchronized externally. (A structural modification is any operation

* that adds or deletes one or more mappings; merely changing the value

* associated with a key that an instance already contains is not a

* structural modification.) This is typically accomplished by

* synchronizing on some object that naturally encapsulates the map.

* <p>

* If no such object exists, the map should be "wrapped" using the

* {@link Collections#synchronizedMap Collections.synchronizedMap}

* method. This is best done at creation time, to prevent accidental

* unsynchronized access to the map:<pre>

* Map m = Collections.synchronizedMap(new HashMap(...));</pre>

*

* <p>The iterators returned by all of this class's "collection view methods"

* are <i>fail-fast</i>: if the map is structurally modified at any time after

* the iterator is created, in any way except through the iterator's own

* <tt>remove</tt> 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 <tt>ConcurrentModificationException</tt> on a best-effort basis.

* Therefore, it would be wrong to write a program that depended on this

* exception for its correctness: <i>the fail-fast behavior of iterators

* should be used only to detect bugs.</i>

*

* <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 Doug Lea

* @author Josh Bloch

* @author Arthur van Hoff

* @author Neal Gafter

* @see Object#hashCode()

* @see Collection

* @see Map

* @see TreeMap

* @see Hashtable

* @since 1.2

*/

public class HashMap<K, V> extends AbstractMap<K, V>

implements Map<K, V>, Cloneable, Serializable {

private static final long serialVersionUID = 362498820763181265L;

/*

* Implementation notes.

*

* This map usually acts as a binned (bucketed) hash table, but

* when bins get too large, they are transformed into bins of

* TreeNodes, each structured similarly to those in

* java.util.TreeMap. Most methods try to use normal bins, but

* relay to TreeNode methods when applicable (simply by checking

* instanceof a node). Bins of TreeNodes may be traversed and

* used like any others, but additionally support faster lookup

* when overpopulated. However, since the vast majority of bins in

* normal use are not overpopulated, checking for existence of

* tree bins may be delayed in the course of table methods.

*

* Tree bins (i.e., bins whose elements are all TreeNodes) are

* ordered primarily by hashCode, but in the case of ties, if two

* elements are of the same "class C implements Comparable<C>",

* type then their compareTo method is used for ordering. (We

* conservatively check generic types via reflection to validate

* this -- see method comparableClassFor). The added complexity

* of tree bins is worthwhile in providing worst-case O(log n)

* operations when keys either have distinct hashes or are

* orderable, Thus, performance degrades gracefully under

* accidental or malicious usages in which hashCode() methods

* return values that are poorly distributed, as well as those in

* which many keys share a hashCode, so long as they are also

* Comparable. (If neither of these apply, we may waste about a

* factor of two in time and space compared to taking no

* precautions. But the only known cases stem from poor user

* programming practices that are already so slow that this makes

* little difference.)

*

* Because TreeNodes are about twice the size of regular nodes, we

* use them only when bins contain enough nodes to warrant use

* (see TREEIFY_THRESHOLD). And when they become too small (due to

* removal or resizing) they are converted back to plain bins. In

* usages with well-distributed user hashCodes, tree bins are

* rarely used. Ideally, under random hashCodes, the frequency of

* nodes in bins follows a Poisson distribution

* (http://en.wikipedia.org/wiki/Poisson_distribution) with a

* parameter of about 0.5 on average for the default resizing

* threshold of 0.75, although with a large variance because of

* resizing granularity. Ignoring variance, the expected

* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /

* factorial(k)). The first values are:

*

* 0: 0.60653066

* 1: 0.30326533

* 2: 0.07581633

* 3: 0.01263606

* 4: 0.00157952

* 5: 0.00015795

* 6: 0.00001316

* 7: 0.00000094

* 8: 0.00000006

* more: less than 1 in ten million

*

* The root of a tree bin is normally its first node. However,

* sometimes (currently only upon Iterator.remove), the root might

* be elsewhere, but can be recovered following parent links

* (method TreeNode.root()).

*

* All applicable internal methods accept a hash code as an

* argument (as normally supplied from a public method), allowing

* them to call each other without recomputing user hashCodes.

* Most internal methods also accept a "tab" argument, that is

* normally the current table, but may be a new or old one when

* resizing or converting.

*

* When bin lists are treeified, split, or untreeified, we keep

* them in the same relative access/traversal order (i.e., field

* Node.next) to better preserve locality, and to slightly

* simplify handling of splits and traversals that invoke

* iterator.remove. When using comparators on insertion, to keep a

* total ordering (or as close as is required here) across

* rebalancings, we compare classes and identityHashCodes as

* tie-breakers.

*

* The use and transitions among plain vs tree modes is

* complicated by the existence of subclass LinkedHashMap. See

* below for hook methods defined to be invoked upon insertion,

* removal and access that allow LinkedHashMap internals to

* otherwise remain independent of these mechanics. (This also

* requires that a map instance be passed to some utility methods

* that may create new nodes.)

*

* The concurrent-programming-like SSA-based coding style helps

* avoid aliasing errors amid all of the twisty pointer operations.

*/

/**

* 默认初始容量-必须是2的幂。

* <p>

* The default initial capacity - MUST be a power of two.

*/

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**

* 最大容量，如果有参数的构造函数隐式指定了更高的值，则使用。必须是2的幂<=1<<30。

* <p>

* 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.

*/

static final int MAXIMUM_CAPACITY = 1 << 30;

/**

* 构造函数中未指定时使用的负载因子。

* <p>

* The load factor used when none specified in constructor.

*/

static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**

* 链表转换为红黑树

* 桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树

* <p>

* The bin(bucket) count threshold for using a tree rather than list for a

* bin. Bins are converted to trees when adding an element to a

* bin with at least this many nodes. The value must be greater

* than 2 and should be at least 8 to mesh with assumptions in

* tree removal about conversion back to plain bins upon

* shrinkage.

*/

static final int TREEIFY_THRESHOLD = 8;

/**

* 红黑树转换为链表

* 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表

* <p>

* The bin(bucket) count threshold for untreeifying a (split) bin during a

* resize operation. Should be less than TREEIFY_THRESHOLD, and at

* most 6 to mesh with shrinkage detection under removal.

*/

static final int UNTREEIFY_THRESHOLD = 6;

/**

* 最小树形化Hash表容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）

* 否则，若桶内元素太多时，则直接扩容，而不是树形化

* 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD

* <p>

* 如果Hash表容量大于了 TREEIFY_THRESHOLD ，但是capacity小于MIN_TREEIFY_CAPACITY 则依然使用链表结构进行存储，此时会对HashMap进行扩容；如果capacity大于了MIN_TREEIFY_CAPACITY ，则会进行树化。

* <p>

* The smallest table capacity for which bins may be treeified.

* (Otherwise the table is resized if too many nodes in a bin.)

* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts

* between resizing and treeification thresholds.

*/

static final int MIN_TREEIFY_CAPACITY = 64;

/**

* 哈希表table节点。HashMap是一个存放链表的数组

* <p>

* Basic hash bin node, used for most entries. (See below for

* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)

*/

static class Node<K, V> implements Map.Entry<K, V> {

final int hash;

final K key;

V value;

Node<K, V> next;

Node(int hash, K key, V value, Node<K, V> next) {

this.hash = hash;

this.key = key;

this.value = value;

this.next = next;

}

public final K getKey() {

return key;

}

public final V getValue() {

return value;

}

public final String toString() {

return key + "=" + value;

}

public final int hashCode() {

return Objects.hashCode(key) ^ Objects.hashCode(value);

}

public final V setValue(V newValue) {

V oldValue = value;

value = newValue;

return oldValue;

}

public final boolean equals(Object o) {

if (o == this)

return true;

if (o instanceof Map.Entry) {

Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;

if (Objects.equals(key, e.getKey()) &&

Objects.equals(value, e.getValue()))

return true;

}

return false;

}

}

/* ---------------- Static utilities -------------- */

/**

* 计算key.hashCode（）并将散列的高位（异或）扩散到低位。

* <p>

* Computes key.hashCode() and spreads (XORs) higher bits of hash

* to lower. Because the table uses power-of-two masking, sets of

* hashes that vary only in bits above the current mask will

* always collide. (Among known examples are sets of Float keys

* holding consecutive whole numbers in small tables.) So we

* apply a transform that spreads the impact of higher bits

* downward. There is a tradeoff between speed, utility, and

* quality of bit-spreading. Because many common sets of hashes

* are already reasonably distributed (so don't benefit from

* spreading), and because we use trees to handle large sets of

* collisions in bins, we just XOR some shifted bits in the

* cheapest possible way to reduce systematic lossage, as well as

* to incorporate impact of the highest bits that would otherwise

* never be used in index calculations because of table bounds.

*/

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

/**

* 如果x的类的形式为“Class C implements Comparable<C>”，则返回x的类，否则返回null。

* <p>

* Returns x's Class if it is of the form "class C implements

* Comparable<C>", else null.

*/

static Class<?> comparableClassFor(Object x) {

if (x instanceof Comparable) {

Class<?> c;

Type[] ts, as;

Type t;

ParameterizedType p;

if ((c = x.getClass()) == String.class) // bypass checks

return c;

if ((ts = c.getGenericInterfaces()) != null) {

for (int i = 0; i < ts.length; ++i) {

if (((t = ts[i]) instanceof ParameterizedType) &&

((p = (ParameterizedType) t).getRawType() ==

Comparable.class) &&

(as = p.getActualTypeArguments()) != null &&

as.length == 1 && as[0] == c) // type arg is c

return c;

}

}

}

return null;

}

/**

* Returns k.compareTo(x) if x matches kc (k's screened comparable

* class), else 0.

*/

@SuppressWarnings({"rawtypes", "unchecked"}) // for cast to Comparable

static int compareComparables(Class<?> kc, Object k, Object x) {

return (x == null || x.getClass() != kc ? 0 :

((Comparable) k).compareTo(x));

}

/**

* 返回给定目标容量的二次幂。

* <p>

* Returns a power of two size for the given target capacity.

*/

static final int tableSizeFor(int cap) {

int n = cap - 1;

n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

n |= n >>> 8;

n |= n >>> 16;

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

}

/* ---------------- Fields -------------- */

/**

* table数组，在第一次使用时初始化，并根据需要调整大小。分配时，长度总是2的幂。

* <p>

* The table, initialized on first use, and resized as

* necessary. When allocated, length is always a power of two.

* (We also tolerate length zero in some operations to allow

* bootstrapping mechanics that are currently not needed.)

*/

transient Node<K, V>[] table;

/**

* 保留缓存的entrySet（）。请注意，AbstractMap字段用于keySet（）和values（）。

* <p>

* Holds cached entrySet(). Note that AbstractMap fields are used

* for keySet() and values().

*/

transient Set<Map.Entry<K, V>> entrySet;

/**

* 此映射中包含的键值映射数。

* <p>

* The number of key-value mappings contained in this map.

*/

transient int size;

/**

* 此哈希映射在结构上被修改的次数,结构修改是指更改HashMap中映射的数量或修改其内部结构的修改

* <p>

* The number of times this HashMap has been structurally modified

* Structural modifications are those that change the number of mappings in

* the HashMap or otherwise modify its internal structure (e.g.,

* rehash). This field is used to make iterators on Collection-views of

* the HashMap fail-fast. (See ConcurrentModificationException).

*/

transient int modCount;

/**

* 要调整大小的下一个大小值（容量*负载系数）。

* <p>

* The next size value at which to resize (capacity * load factor).

* @serial

*/

// (The javadoc description is true upon serialization.

// Additionally, if the table array has not been allocated, this

// field holds the initial array capacity, or zero signifying

// DEFAULT_INITIAL_CAPACITY.)

int threshold;

/**

* 哈希表的加载因子。

* <p>

* The load factor for the hash table.

* @serial

*/

final float loadFactor;

/* ---------------- Public operations -------------- */

/**

* 用指定的初始容量和负载因子构造一个空的HashMap。

* <p>

* Constructs an empty <tt>HashMap</tt> with the specified initial

* capacity and load factor.

* @param initialCapacity the initial capacity

* @param loadFactor the load factor

* @throws IllegalArgumentException if the initial capacity is negative

* or the load factor is nonpositive

*/

public HashMap(int initialCapacity, float loadFactor) {

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal initial capacity: " +

initialCapacity);

if (initialCapacity > MAXIMUM_CAPACITY)

initialCapacity = MAXIMUM_CAPACITY;

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException("Illegal load factor: " +

loadFactor);

this.loadFactor = loadFactor;

this.threshold = tableSizeFor(initialCapacity);

}

/**

* 用指定的初始容量和默认负载因子（0.75）构造一个空的HashMap。

* <p>

* Constructs an empty <tt>HashMap</tt> with the specified initial

* capacity and the default load factor (0.75).

* @param initialCapacity the initial capacity.

* @throws IllegalArgumentException if the initial capacity is negative.

*/

public HashMap(int initialCapacity) {

this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

/**

* 用默认初始容量（16）和默认负载因子（0.75）构造一个空的HashMap。

* <p>

* Constructs an empty <tt>HashMap</tt> with the default initial capacity

* (16) and the default load factor (0.75).

*/

public HashMap() {

this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

}

/**

* 使用与指定映射相同的映射构造新的HashMap

* <p>

* Constructs a new <tt>HashMap</tt> with the same mappings as the

* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with

* default load factor (0.75) and an initial capacity sufficient to

* hold the mappings in the specified <tt>Map</tt>.

* @param m the map whose mappings are to be placed in this map

* @throws NullPointerException if the specified map is null

*/

public HashMap(Map<? extends K, ? extends V> m) {

this.loadFactor = DEFAULT_LOAD_FACTOR;

putMapEntries(m, false);

}

/**

* 实现Map.putAll和Map构造器。

* <p>

* Implements Map.putAll and Map constructor.

* @param m the map

* @param evict false when initially constructing this map, else

* true (relayed to method afterNodeInsertion).

*/

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {

int s = m.size();

if (s > 0) {

if (table == null) { // pre-size

float ft = ((float) s / loadFactor) + 1.0F;

int t = ((ft < (float) MAXIMUM_CAPACITY) ?

(int) ft : MAXIMUM_CAPACITY);

if (t > threshold)

threshold = tableSizeFor(t);

} else if (s > threshold)

resize();

for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {

K key = e.getKey();

V value = e.getValue();

putVal(hash(key), key, value, false, evict);

}

}

}

/**

* 返回此映射中的键值映射数。

* <p>

* Returns the number of key-value mappings in this map.

* @return the number of key-value mappings in this map

*/

public int size() {

return size;

}

/**

* 如果此映射不包含键值映射，则返回<tt>true</tt>。

* <p>

* Returns <tt>true</tt> if this map contains no key-value mappings.

* @return <tt>true</tt> if this map contains no key-value mappings

*/

public boolean isEmpty() {

return size == 0;

}

/**

* 返回指定键映射到的值，如果此映射不包含该键的映射，则返回{@code null}。

* <p>

* 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==null ? k==null :

* key.equals(k))}, then this method returns {@code v}; otherwise

* it returns {@code null}. (There can be at most one such mapping.)

*

* <p>A return value of {@code null} does not <i>necessarily</i>

* indicate that the map contains no mapping for the key; it's also

* possible that the map explicitly maps the key to {@code null}.

* The {@link #containsKey containsKey} operation may be used to

* distinguish these two cases.

* @see #put(Object, Object)

*/

public V get(Object key) {

Node<K, V> e;

return (e = getNode(hash(key), key)) == null ? null : e.value;

}

/**

* 实现Map.get以及相关方法。

* <p>

* Implements Map.get and related methods.

* @param hash hash for key

* @param key the key

* @return the node, or null if none

*/

final Node<K, V> getNode(int hash, Object key) {

Node<K, V>[] tab;

Node<K, V> first, e;

int n;

K k;

if ((tab = table) != null && (n = tab.length) > 0 &&

(first = tab[(n - 1) & hash]) != null) {

if (first.hash == hash && // always check first node

((k = first.key) == key || (key != null && key.equals(k))))

return first;

if ((e = first.next) != null) {

if (first instanceof TreeNode)

return ((TreeNode<K, V>) first).getTreeNode(hash, key);

do {

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

return e;

} while ((e = e.next) != null);

}

}

return null;

}

/**

* 如果此映射包含指定键的映射，则返回<tt>true</tt>。

* <p>

* Returns <tt>true</tt> if this map contains a mapping for the

* specified key.

* @param key The key whose presence in this map is to be tested

* @return <tt>true</tt> if this map contains a mapping for the specified

* key.

*/

public boolean containsKey(Object key) {

return getNode(hash(key), key) != null;

}

/**

* 将指定值与此映射中的指定键相关联。如果映射以前包含键的映射，则替换旧值。

* <p>

* Associates the specified value with the specified key in this map.

* If the map previously contained a mapping for the key, the old

* value is replaced.

* @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>.

* (A <tt>null</tt> return can also indicate that the map

* previously associated <tt>null</tt> with <tt>key</tt>.)

*/

public V put(K key, V value) {

return putVal(hash(key), key, value, false, true);

}

/**

* 实现Map.put以及相关方法。

* <p>

* Implements Map.put and related methods.

* @param hash hash for key

* @param key the key

* @param value the value to put

* @param onlyIfAbsent if true, don't change existing value

* @param evict if false, the table is in creation mode.

* @return previous value, or null if none

*/

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

Node<K, V>[] tab;

Node<K, V> p;

int n, i;

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

else {

Node<K, V> e;

K k;

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

e = p;

else if (p instanceof TreeNode)

e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);

else {

for (int binCount = 0; ; ++binCount) {

if ((e = p.next) == null) {

p.next = newNode(hash, key, value, null);

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

treeifyBin(tab, hash);

break;

}

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

break;

p = e;

}

}

if (e != null) { // existing mapping for key

V oldValue = e.value;

if (!onlyIfAbsent || oldValue == null)

e.value = value;

afterNodeAccess(e);

return oldValue;

}

}

++modCount;

if (++size > threshold)

resize();

afterNodeInsertion(evict);

return null;

}

/**

* 初始化或加倍表大小。如果为空，则根据字段阈值中保留的初始容量目标进行分配。

* 否则，因为我们使用的是二次幂展开，所以每个桶中的元素要么留在同一索引中，

* 要么在新表中以二次幂偏移量移动。

* <p>

* Initializes or doubles table size. If null, allocates in

* accord with initial capacity target held in field threshold.

* Otherwise, 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 in the new table.

* @return the table

*/

final Node<K, V>[] resize() {

Node<K, V>[] oldTab = table;

int oldCap = (oldTab == null) ? 0 : oldTab.length;

int oldThr = threshold;

int newCap, newThr = 0;

if (oldCap > 0) {

if (oldCap >= MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return oldTab;

} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)

newThr = oldThr << 1; // double threshold

} else if (oldThr > 0) // initial capacity was placed in threshold

newCap = oldThr;

else { // zero initial threshold signifies using defaults

newCap = DEFAULT_INITIAL_CAPACITY;

newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

}

if (newThr == 0) {

float ft = (float) newCap * loadFactor;

newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?

(int) ft : Integer.MAX_VALUE);

}

threshold = newThr;

@SuppressWarnings({"rawtypes", "unchecked"})

Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];

table = newTab;

if (oldTab != null) {

for (int j = 0; j < oldCap; ++j) {

Node<K, V> e;

if ((e = oldTab[j]) != null) {

oldTab[j] = null;

if (e.next == null)

newTab[e.hash & (newCap - 1)] = e;

else if (e instanceof TreeNode)

((TreeNode<K, V>) e).split(this, newTab, j, oldCap);

else { // preserve order

Node<K, V> loHead = null, loTail = null;

Node<K, V> hiHead = null, hiTail = null;

Node<K, V> next;

do {

next = e.next;

if ((e.hash & oldCap) == 0) {

if (loTail == null)

loHead = e;

else

loTail.next = e;

loTail = e;

} else {

if (hiTail == null)

hiHead = e;

else

hiTail.next = e;

hiTail = e;

}

} while ((e = next) != null);

if (loTail != null) {

loTail.next = null;

newTab[j] = loHead;

}

if (hiTail != null) {

hiTail.next = null;

newTab[j + oldCap] = hiHead;

}

}

}

}

}

return newTab;

}

/**

* 在给定哈希表的索引处替换bucket中的所有链接节点，除非表太小（小于64），

* 在这种情况下，将改为调整大小，即进行扩容。

* <p>

* Replaces all linked nodes in bin at index for given hash unless

* table is too small, in which case resizes instead.

*/

final void treeifyBin(Node<K, V>[] tab, int hash) {

int n, index;

Node<K, V> e;

// 要想树化，则hashMap中元素个数要不低于64个（MIN_TREEIFY_CAPACITY）

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

resize();

else if ((e = tab[index = (n - 1) & hash]) != null) {

TreeNode<K, V> hd = null, tl = null;

do {

TreeNode<K, V> p = replacementTreeNode(e, null);

if (tl == null)

hd = p;

else {

p.prev = tl;

tl.next = p;

}

tl = p;

} while ((e = e.next) != null);

if ((tab[index] = hd) != null)

hd.treeify(tab);

}

}

/**

* 将指定映射的所有映射复制到此映射。

* <p>

* Copies all of the mappings from the specified map to this map.

* These mappings will 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

* @throws NullPointerException if the specified map is null

*/

public void putAll(Map<? extends K, ? extends V> m) {

putMapEntries(m, true);

}

/**

* 从此映射中删除指定键的映射（如果存在）。

* <p>

* Removes the mapping for the specified key from this map if present.

* @param key key whose mapping is to be removed from the map

* @return the previous value associated with <tt>key</tt>, or

* <tt>null</tt> if there was no mapping for <tt>key</tt>.

* (A <tt>null</tt> return can also indicate that the map

* previously associated <tt>null</tt> with <tt>key</tt>.)

*/

public V remove(Object key) {

Node<K, V> e;

return (e = removeNode(hash(key), key, null, false, true)) == null ?

null : e.value;

}

/**

* 实现Map.remove以及相关方法。

* <p>

* Implements Map.remove and related methods.

* @param hash hash for key

* @param key the key

* @param value the value to match if matchValue, else ignored

* @param matchValue if true only remove if value is equal

* @param movable if false do not move other nodes while removing

* @return the node, or null if none

*/

final Node<K, V> removeNode(int hash, Object key, Object value,

boolean matchValue, boolean movable) {

Node<K, V>[] tab;

Node<K, V> p;

int n, index;

if ((tab = table) != null && (n = tab.length) > 0 &&

(p = tab[index = (n - 1) & hash]) != null) {

Node<K, V> node = null, e;

K k;

V v;

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

node = p;

else if ((e = p.next) != null) {

if (p instanceof TreeNode)

node = ((TreeNode<K, V>) p).getTreeNode(hash, key);

else {

do {

if (e.hash == hash &&

((k = e.key) == key ||

(key != null && key.equals(k)))) {

node = e;

break;

}

p = e;

} while ((e = e.next) != null);

}

}

if (node != null && (!matchValue || (v = node.value) == value ||

(value != null && value.equals(v)))) {

if (node instanceof TreeNode)

((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);

else if (node == p)

tab[index] = node.next;

else

p.next = node.next;

++modCount;

--size;

afterNodeRemoval(node);

return node;

}

}

return null;

}

/**

* 从此映射中删除所有映射。

* <p>

* Removes all of the mappings from this map.

* The map will be empty after this call returns.

*/

public void clear() {

Node<K, V>[] tab;

modCount++;

if ((tab = table) != null && size > 0) {

size = 0;

for (int i = 0; i < tab.length; ++i)

tab[i] = null;

}

}

/**

* 如果此映射将一个或多个键映射到指定值，则返回<tt>true</tt>。

* <p>

* Returns <tt>true</tt> if this map maps one or more keys to the

* specified value.

* @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

* specified value

*/

public boolean containsValue(Object value) {

Node<K, V>[] tab;

V v;

if ((tab = table) != null && size > 0) {

for (int i = 0; i < tab.length; ++i) {

for (Node<K, V> e = tab[i]; e != null; e = e.next) {

if ((v = e.value) == value ||

(value != null && value.equals(v)))

return true;

}

}

}

return false;

}

/**

* 返回此映射中包含的键的{@link Set}集合。

* <p>

* Returns a {@link Set} view of the keys contained in this map.