HashMap 重点源码解析

package com.util;

import java.io.IOException;

import java.io.InvalidObjectException;

import java.io.Serializable;

import java.util.AbstractCollection;

import java.util.AbstractSet;

import java.util.Collection;

import java.util.ConcurrentModificationException;

import java.util.Iterator;

import java.util.Map;

import java.util.NoSuchElementException;

import java.util.Set;

import java.util.Spliterator;

import java.util.function.BiConsumer;

import java.util.function.BiFunction;

import java.util.function.Consumer;

import java.util.function.Function;

import sun.misc.SharedSecrets;

public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {

	private static final long serialVersionUID = 362498820763181265L;

	/*

	 * 这个映射通常作为一个桶状哈希表，但是 当箱子太大时，它们会被转换成 TreeNodes，每个结构类似于

	 * java.util.TreeMap。大多数方法尝试使用正常的箱子，但是 在适用时中继到TreeNode方法(只需通过检查)

	 * instanceof一个节点)。

	 * 

	 * 可以遍历和遍历TreeNodes的Bins 与其他类似，但额外支持更快的查找 当人口过剩时。

	 * 

	 * 然而，由于绝大多数垃圾箱在 正常使用时不超载，检查是否存在 树箱可能在表方法的过程中被延迟。

	 * 

	 * 树箱(即，其元素都是treenode的箱)是主要由hashCode排序，但在领带的情况下，如果两个

	 * 元素具有相同的"class C implements Comparable<C>"，类型，

	 * 

	 * 则使用它们的compareTo方法进行排序。(我们 通过反射保守检查泛型类型来验证 this——参见methodcomparableClassFor)。

	 * 

	 * 增加的复杂性 的树箱在提供最坏情况O(log n)时是值得的 当键有不同的哈希值或者是 有序的，因此，性能下降优雅

	 * hashCode()方法的意外或恶意使用 返回分布不佳的值，以及 许多键共享一个hashCode，

	 * 

	 * 只要它们也是具有可比性。(如果这两项都不适用，我们可能会浪费大约100万美元 在时间和空间上是不采取行动的两倍 预防措施。但唯一已知的案例源于糟糕的使用者

	 * 编程实践已经非常缓慢，这使得 差别不大。) ＊ 因为treenode的大小大约是普通节点的两倍，我们 仅当bin包含足够的节点以保证使用时使用它们

	 * (见MapUtilConst.MapUtilConst.TREEIFY_THRESHOLD)。当它们变得太小时(由于)

	 * 移除或调整大小)它们被转换回普通的垃圾箱。在 使用分布良好的用户hashCodes，树箱是 很少使用。 理想情况下，在随机哈希码下，的频率

	 * 箱中的*节点遵循泊松分布(http://en.wikipedia.org/wiki/Poisson_distribution)与a

	 * 参数，默认大小调整平均约为0.5 阈值为0.75，虽然由于 调整粒度。忽略方差，即期望值 列表大小k的出现次数为(exp(-0.5) * pow(0.5,

	 * k) / factorial (k))。第一个值是:

	 * 

	 * 

	 * 笔记 拼音

	 *

	 * 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

	 *

	 * bin树的根通常是它的第一个节点。然而,有时 (目前仅在Iterator.remove上)，根节点可能在其他地方，但可以

	 * 在父链接之后恢复(方法TreeNode.root())。

	 *

	 * 所有适用的内部方法都接受一个哈希码作为参数 通常由公共方法提供)，允许它们相互调用 无需重新计算用户的哈希值。大多数内部方法也接受一个“tab”。

	 * 参数，通常是当前表，但也可能是新表或旧表 当调整大小或转换时。

	 *

	 * 当bin列表被树形化、分割或未树形化时，我们将它们保持不变 更好地保存相对访问/遍历顺序(即Node.next字段) 局部性，并稍微简化拆分和遍历的处理

	 * 调用iterator.remove方法。在插入时使用比较器时，保留一个总数 在重新平衡时进行排序(或尽可能接近)，我们进行比较

	 * classes和identityHashCodes是决定因素。

	 *

	 * 普通模式和树模式之间的使用和转换是复杂的 存在子类LinkedHashMap。下面是钩子方法的定义

	 * 在允许LinkedHashMap内部操作的插入、删除和访问时调用 保持独立于这些机制。(这也要求 将map实例传递给一些可能会创建新节点的工具方法。)

	 *

	 * 类似于并发编程的基于ssa的编码风格有助于避免别名 所有扭曲的指针操作都会出错。

	 * 

	 */

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

	/**

	 * 计算key.hashCode()，并将哈希值的高位按XORs对齐到低位。 因为该表使用2的幂次掩码，所以散列值的集合只在

	 * 当前掩码上方的比特位始终会发生碰撞。 (已知的例子有 在小表格中保存连续整数的浮点键集合。) 所以我们

	 * 应用一个转换，将高比特位的影响向下扩展。有一个比特扩展的速度、效用和质量之间的权衡。 因为很多 公共哈希集合已经合理分布(所以不要从中受益

	 * 避免传播)，因为我们使用树来处理大量的碰撞 在bin中，我们只需要以可能的最便宜的方式异或移位一些位即可 系统损耗，以及对合并影响的最高位表示

	 * 由于表的边界，否则将永远不会用于索引计算。

	 * https://blog.csdn.net/liuxingrong666/article/details/103640412

	 */

	static final int hash(Object key) {

		int h;

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

	}

	/**

	 * 把不是2的幂的值改成是2的幂 https://blog.csdn.net/ywb201314/article/details/120022308

	 */

	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 >= MapUtilConst.MAXIMUM_CAPACITY) ? MapUtilConst.MAXIMUM_CAPACITY : n + 1;

	}

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

	/**

	 * 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.) hash表

	 */

	transient Node<K, V>[] table;

	/**

	 * 保存缓存的entrySet()。注意，AbstractMap字段用于keySet() 和values()。

	 */

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

	/**

	 * 包含的键值映射的数量。

	 */

	transient int size;

	/**

	 * <pre>

	 * modCount便是hashmap结构修改的次数。

	 * 在之前对iterator（迭代器）进行讲解的时候我已经进行了说明，

	 * 需要注意的是在hashmap中modcount指的是结构更改的次数，例如添加新的node，

	 * 但是如果是替换原有node的value，modcount是不变的，因为它不属于结构变化。

	 * </pre>

	 */

	transient int modCount;

	/**

	 * threshold是hashmap所能容纳的最大数据量的Node个数，

	 * 默认为0.75，threshold=DEFAULT_INITIAL_CAPACITY*loadFactor;当添加元素数量超过这个数量过后，就要进行扩容，扩容后hashmap的容量是之前的两倍

	 */

	int threshold;

	/**

	 * The load factor for the hash table.

	 *

	 * @serial

	 */

	final float loadFactor;

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

	/**

	 * 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 > MapUtilConst.MAXIMUM_CAPACITY)

			initialCapacity = MapUtilConst.MAXIMUM_CAPACITY;

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

			throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

		this.loadFactor = loadFactor;

		this.threshold = tableSizeFor(initialCapacity);

	}

	/**

	 * 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, MapUtilConst.DEFAULT_LOAD_FACTOR);

	}

	/**

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

	 * and the default load factor (0.75).

	 */

	public HashMap() {

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

	}

	/**

	 * 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 = MapUtilConst.DEFAULT_LOAD_FACTOR;

		putMapEntries(m, false);

	}

	/**

	 * 该函数用于将一个map赋值给新的HashMap

	 * 

	 * <pre>

	

	if (table == null)分支，说明是HashMap的拷贝构造函数来调用的putMapEntries，或者是构造以后还没有放过任何元素，然后再调用putAll。

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

	这里的加1是因为，size / loadFactor = capacity，但如果算出来的capacity是小数，却又向下取整，会造成容量不够大，

	所以，如果是小数的capacity，那么必须向上取整。

	

	算出来的容量必须小于最大容量MAXIMUM_CAPACITY，否则直接让capacity等于MAXIMUM_CAPACITY。

	

	if (t > threshold)这里的threshold成员实际存放的值是capacity的值。

	因为在table还没有初始化时（table还是null），用户给定的capacity会暂存到threshold成员上去（毕竟HashMap没有一个成员叫做capacity，capacity是作为table数组的大小而隐式存在的）。

	

	else if (s > threshold)说明传入map的size都已经大于当前map的threshold了，即当前map肯定是装不下两个map的并集的，所以这里必须要执行resize操作。

	最后循环里的putVal可能也会触发resize操作

	 * </pre>

	 * 

	 * 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) {

			return;

		}

		// 判断table是否已经初始化 如果table=null一般就是构造函数来调用的putMapEntries，或者构造后还没放过任何元素

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

			// 如果未初始化，则计算HashMap的最小需要的容量（即容量刚好不大于扩容阈值）。这里Map的大小s就被当作HashMap的扩容阈值，然后用传入Map的大小除以负载因子就能得到对应的HashMap的容量大小（当前m的大小

			// / 负载因子 = HashMap容量）

			// 先不考虑容量必须为2的幂，那么下面括号里会算出来一个容量，使得size刚好不大于阈值。但这样会算出小数来，但作为容量就必须向上取整，所以这里要加1。此时ft可以临时看作HashMap容量大小

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

			// 比较最大容量与ft，取小值； 到这里t暂时表示HashMap的容量大小。如果是将ft浮点型赋值给t整形，因为前面加了1.0f,这里也就实现了向上取整

			int t = ((ft < (float) MapUtilConst.MAXIMUM_CAPACITY) ? (int) ft : MapUtilConst.MAXIMUM_CAPACITY);

			// 只有在算出来的容量t >

			// 当前暂存的容量(容量可能会暂放到阈值上的,刚使用构造函数构造出来的HashMap并且没有存入元素时，容量大小就会被暂时存在threshold中)时

			// 才会用t计算出新容量，暂时存放到阈值上,在后面触发resize()扩容的时候会对threshold重新计算正确的阈值

			if (t > threshold)

				threshold = tableSizeFor(t);

		}

		// 如果当前Map已经初始化,且这个map中的元素个数大于扩容的阀值就得扩容

		// 这种情况属于预先扩大容量，再put元素

		else if (s > threshold)

			resize();

		// 遍历map,将map中的key和value都添加到HashMap中

		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);

		}

	}

	/**

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

	}

	/**

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

	}

	/**

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

	}

	/**

	 * 大致流程：

	 * 

	 * <pre>

	1.根据hash值去找到桶。

	

	2.判断桶上的key是否等于传入的的key，如果相等，则直接返回。

	

	3.桶上的key如果不是我们需要的key，则查看next指向的结点。

	 

	 3.1 如果指向的结点是树结点，调用红黑树的查找方法找到key。

	

	 3.2 如果指向的结点是链表，则遍历链表找到key。

	

	1，map不能为空，且hash对应的下标要存在。否则返回null

	

	2，取下标对应的对象，如果该对象的key与入参key一致，则返回该对象

	

	3，否则，获取下一个对象，如果该对象为空，返回null

	

	4，如果当前对象是树结构，则调用getTreeNode，获取是否存在

	

	5，如果不是树结构，循环对象，如果存在对象的key与入参key一致，则返回该对象

	

	6，最终返回要么有值，要么null

	 * 

	 * 

	 * </pre>

	 */

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

		// 主要用于将哈希表赋值给tab

		Node<K, V>[] tab;

		// 主要是通过(哈希表的长度-1) & hash值，计算出数组下标first = tab[n](第 一个节点)

		Node<K, V> first,

				// 主要是将当前节点的下个结点赋值给e

				e;

		// 主要用去哈希表的长度赋值给n

		int n;

		// 主要用于当前结点的key赋值给k

		K k;

		// 将哈希表赋值给tab然后判断是否为空

		// &&将哈希表的长度赋值给n判断是否大于0

		// && 将hash的低十六位(绝大多数情况下length一般都小于2^16)与长度进行运算得到数组下标， tab[下标]赋值给first

		if ((tab = table) == null || (n = tab.length) < 0 || (first = tab[(n - 1) & hash]) == null) {

			return null;

		}

		// 拿到第一个结点(first)的hash值和key，跟传入的has值和key作比较，如果相同返回first结点；

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

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

			return first;

		// 该索引下面存储多个节点的情况下：将first的下一个结点赋值给e，判断e是否为空

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

			return null;

		}

		// 判断first是否是TreeNode的对象

		if (first instanceof TreeNode)

			// 如果是，调用在红黑树中的查找方法

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

		// 以链表的方式存储，遍历该节点下面的所有结点

		do {

			// 判断当前结点(e)的hash值和key，跟传入的has值和key作比较，如果相同返回first结点；(与判断first的结点相同)

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

				return e;

		} while (null != (e = e.next)); // 获取e节点的下一个是否为空

		

		return null;

	}

	/**

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

	}

	/**

	 * 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);

	}

	/**

	 * Implements Map.put and related methods.

	 *

	 * @param hash hash for key

	 * @param key the key

	 * @param value the value to put

	 * @param onlyIfAbsent 如果为true，则不更改现有值

	 * @param evict 如果为false，则表处于创建模式.

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

		/*

		 * 如果table为空，或者数组当前长度为0，说明没有创建HashMap，要先创建

		 * 也说明了HashMap在插入第一个元素的时候才初始化，而不是定义出来才开始初始化 延迟初始化逻辑

		 */

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

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

		// 路由算法 （n-1） & hash == hash%n （n必须为2的次方数）

		// 如果这个位置为null，则说明其中没有数据，直接放进去

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

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

		// 这个位置已经有数据了

		else {

			// e：临时节点

			// k：表示临时的一个key

			Node<K, V> e;

			K k;

			// p在上面的if语句中赋值，代表对应数组下标的元素

			// hash值相同并不一定代表值相同，但如果hash值不相同，值一定不相同

			// 表示桶位中的元素该元素，和你当前插入的key完全一致，表示后续需要进行替换操作

			if (p.hash == hash &&

			// 判断基本类型的key值是否相同，直接使用等于判断 || 判断非基本类型的key值是否相同，要使用equals

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

				e = p;

			// e值为key值相等的这个元素

			// key值不相等，且已经发生树化=>红黑树

			else if (p instanceof TreeNode)

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

			// 不是树，且key不相等，剩下一种情况=>链表

			// 链表的头元素和key不一致，则要遍历整个链表，找到key值就替换，不然就在链表末尾插

			else {

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

					// 遍历整个链表

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

						// 一直遍历到空都没有找到key值相等，在表尾插入一个新节点

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

						// MapUtilConst.TREEIFY_THRESHOLD为树化阈值，默认为8

						// 因为binCount从0开始，所以当binCount为7的时候，已经有八个节点了，binCount在for循环结束的时候才自增，因此要和树化阈值-1作比较

						// 当大于等于阈值的时候，链表树化

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

							treeifyBin(tab, hash);

						// 此时e中存储的为null

						break;

					}

					// 判断key值是否相同，逻辑与上面一样

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

						break;

					// 此时跳出e中存储的是key相同的那个地址

					p = e;

				}

			}

			// 只有替换操作会进入整个if，插入操作中e的值为null

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

				// 将原来对应的value值存起来

				V oldValue = e.value;

				// onlyIfAbsent为false时 或者 原来key对应的value为空值的时候，e.value被赋值为新的value

				// 即如果onlyIfAbsent传入的值为true且oldvalue不为空，不执行此if操作，value没有被插入，没有发生替换操作

				if (!onlyIfAbsent || oldValue == null)

					e.value = value;

				afterNodeAccess(e);

				// 返回值为oldvalue，即被覆盖的value值

				return oldValue;

			}

		}

		// modCount表示散列表结构被修改次数，替换操作不会走到这里。

		++modCount;

		// size是散列表中元素的个数，如果大于扩容阈值，会触发扩容

		if (++size > threshold)

			resize();

		afterNodeInsertion(evict);

		return null;

	}

	/**

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

		// 新数组的容量，新数组的扩容阀值都初始化为0

		int newCap, newThr = 0;

		// 如果老数组长度大于0，说明已经存在元素

		if (oldCap > 0) {

			// 如果数组元素个数大于等于限定的最大容量（2的30次方）

			if (oldCap >= MapUtilConst.MAXIMUM_CAPACITY) {

				// 扩容阀值设置为int最大值（2的31次方 -1 ），因为oldCap再乘2就溢出了。

				threshold = Integer.MAX_VALUE;

				// 返回老的元素数组

				return oldTab;

			}

			/*

			 * 如果数组元素个数在正常范围内，那么新的数组容量为老的数组容量的2倍（左移1位相当于乘以2） 如果扩容之后的新容量小于最大容量 并且

			 * 老的数组容量大于等于默认初始化容量（16），那么新数组的扩容阀值设置为老阀值的2倍。（老的数组容量大于16意味着：

			 * 要么构造函数指定了一个大于16的初始化容量值，要么已经经历过了至少一次扩容）

			 */

			else if ((newCap = oldCap << 1) < MapUtilConst.MAXIMUM_CAPACITY

					&& oldCap >= MapUtilConst.DEFAULT_INITIAL_CAPACITY)

				newThr = oldThr << 1; // double threshold

		}

		// PS2

		// 运行到这个else if 说明老数组没有任何元素

		// 如果老数组的扩容阀值大于0，那么设置新数组的容量为该阀值

		// 这一步也就意味着构造该map的时候，指定了初始化容量。

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

			newCap = oldThr;

		else { // zero initial threshold signifies using defaults

			// 能运行到这里的话，说明是调用无参构造函数创建的该map，并且第一次添加元素

			// 设置新数组容量 为 16

			newCap = MapUtilConst.DEFAULT_INITIAL_CAPACITY;

			// 设置新数组扩容阀值为 16*0.75 = 12。0.75为负载因子（当元素个数达到容量了4分之3，那么扩容）

			newThr = (int) (MapUtilConst.DEFAULT_LOAD_FACTOR * MapUtilConst.DEFAULT_INITIAL_CAPACITY);

		}

		// 如果扩容阀值为0 （PS2的情况）

		if (newThr == 0) {

			float ft = (float) newCap * loadFactor;

			newThr = (newCap < MapUtilConst.MAXIMUM_CAPACITY && ft < (float) MapUtilConst.MAXIMUM_CAPACITY ? (int) ft

					: Integer.MAX_VALUE);

		}

		// 设置map的扩容阀值为 新的阀值

		threshold = newThr;

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

		// 创建新的数组（对于第一次添加元素，那么这个数组就是第一个数组；对于存在oldTab的时候，那么这个数组就是要需要扩容到的新数组）

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

		// 将该map的table属性指向到该新数组

		table = newTab;

		// 如果老数组不为空，说明是扩容操作，那么涉及到元素的转移操作

		if (oldTab != null) {

			// 遍历老数组

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

				Node<K, V> e;

				// 如果当前位置元素不为空，那么需要转移该元素到新数组

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

					// 释放掉老数组对于要转移走的元素的引用（主要为了使得数组可被回收）

					oldTab[j] = null;

					// 如果元素没有有下一个节点，说明该元素不存在hash冲突

					if (e.next == null)

						// PS3

						// 把元素存储到新的数组中，存储到数组的哪个位置需要根据hash值和数组长度来进行取模

						// 【hash值 % 数组长度】 = 【 hash值 & （数组长度-1）】

						// 这种与运算求模的方式要求 数组长度必须是2的N次方，但是可以通过构造函数随意指定初始化容量呀，

						// 如果指定了17,15这种，岂不是出问题了就？没关系，最终会通过tableSizeFor方法将用户指定的转化为大于其并且最相近的2的N次方。

						// 15 -> 16、17-> 32

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

					// 如果该元素有下一个节点，那么说明该位置上存在一个链表了（hash相同的多个元素以链表的方式存储到了老数组的这个位置上了）

					// 例如：数组长度为16，那么hash值为1（1%16=1）的和hash值为17（17%16=1）的两个元素都是会存储在数组的第2个位置上（对应数组下标为1），当数组扩容为32（1%32=1）时，hash值为1的还应该存储在新数组的第二个位置上，但是hash值为17（17%32=17）的就应该存储在新数组的第18个位置上了。

					// 所以，数组扩容后，所有元素都需要重新计算在新数组中的位置。

					// 如果该节点为TreeNode类型

					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;

						// 以上的低位指的是新数组的 0 到 oldCap-1 、高位指定的是oldCap 到 newCap - 1

						Node<K, V> next;

						// 遍历链表

						do {

							next = e.next;

							// 这一步判断好狠，拿元素的hash值 和 老数组的长度 做与运算

							// PS3里曾说到，数组的长度一定是2的N次方（例如16），如果hash值和该长度做与运算，结果为0，就说明该hash值小于数组长度（例如hash值为7），

							// 那么该hash值再和新数组的长度取摸的话mod值也不会放生变化，所以该元素的在新数组的位置和在老数组的位置是相同的，所以该元素可以放置在低位链表中。

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

								// PS4

								// 如果没有尾，说明链表为空

								if (loTail == null)

									// 链表为空时，头节点指向该元素

									loHead = e;

								else

									// 如果有尾，那么链表不为空，把该元素挂到链表的最后。

									loTail.next = e;

								// 把尾节点设置为当前元素

								loTail = e;

							}

							// 如果与运算结果不为0，说明hash值大于老数组长度（例如hash值为17）

							// 此时该元素应该放置到新数组的高位位置上

							// 例：老数组长度16，那么新数组长度为32，hash为17的应该放置在数组的第17个位置上，也就是下标为16，那么下标为16已经属于高位了，低位是[0-15]，高位是[16-31]

							else {

								// 以下逻辑同PS4

								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;

							// 例：hash为 17 在老数组放置在0下标，在新数组放置在16下标； hash为 18 在老数组放置在1下标，在新数组放置在17下标；

							newTab[j + oldCap] = hiHead;

						}

					}

				}

			}

		}

		return newTab;

	}

	/**

	 * <pre>

	 1，如果table数组为空，或者大小未超过64，则重置table大小

	 2，如果table大小超过64，把当前链表转换成红黑树

		2.1，循环链表，把每一个对象转换成红黑树，并绑定上下级关系

		2.2，重置红黑树相关信息

	 * </pre>

	 */

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

		int n, index;

		Node<K, V> e;

		// 1，如果table数组为空，或者大小未超过64，则重置table大小

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

			resize();

		// 2，如果table大小超过64，把当前链表转换成红黑树

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

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

			do {

				// 2.1，循环链表，把每一个对象转换成红黑树，并绑定上下级关系

				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);

		}

	}

	/**

	 * 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);

	}

	/**

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

	}

	/**

	 * 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) {

		// tab：当前map

		// 的数组，p：hash对应的数组索引index位置上的节点/遍历链表时表示当前遍历到的节点的前一个节点，n：数组长度，index：hash对应的数组索引

		// 这几个值在hashMap的源码中很常见

		Node<K, V>[] tab;

		Node<K, V> p;

		int n, index;

		// 定位到哈希桶中位置

		// 前提判断 数组不为空，并且长度大于0 并且

		// hash对应的数组索引位置上的节点p也不为null

		if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {

			// node：被移除的节点，e：当前头节点的下一个节点/遍历链表时表示当前遍历到的节点，

			// k：e节点的key，v：被移除节点node 的value

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

			K k;

			V v;

			// 直接检索到-挺幸运

			// 如果第一个节点p就是目标节点，则将node指向第一个节点p

			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)

					// 调用红黑树的查询节点的方法，getTreeNode()

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

				// 第一个节点不是红黑树，并且还有第二个节点，那就说明，这里是链表了

				else {

					// 那么开始循环链表，从第二个节点开始循环，因为第一个节点已经处理过了

					do {

						// 判断e节点是不是目标节点，是的话就将node指向e，并且终止循环

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

							node = e;

							break;

						}

						// e节点不是目标节点，那就将p节点指向e节点，

						// 然后while里面e节点后移，在进入循环后发现e是目标节点了，退出循环，退出后此时p节点还是e节点的前一个节点，

						// 也就保证了在整个循环的过程中，p节点始终是e节点的前一个节点。

						p = e;

					} while ((e = e.next) != null); // e指针后移，并且下一个节点不为null则继续遍历，不为null表示没到链表最后。

				}

			}

			// 找到目标节点了 matchValue为true，则仅在值相等时删除。如果是false，则值不管相不相等，只要key和hash值一致就移除该节点。

			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);

				// 目标节点是p节点，

				// 还记得之前 如果第一个节点p（数组桶中的节点）就是目标节点，则将node指向第一个节点p

				else if (node == p)

					// 将目标节点的下一个节点作为该索引位置的第一个元素

					// 也就是跳过目标节点，指向目标节点的下一位

					tab[index] = node.next;

				// 这里就是遍历链表找到了目标节点

				else

					// p节点始终作为node的上一个节点，p.next始终指向目标节点node

					// 现在将p.next 指向目标节点node的next，这样跳过了目标节点node，就把node移除掉了

					p.next = node.next;

				// 记录map结构被修改的次数，主要用于并发编程

				++modCount;

				// 记录table存储了多少键值对，因为移除了一个，所以此处就减一

				--size;

				// 该方法在hashMap中是空方法，主要是供LinkedHashMap使用，因为LinkedHashMap重写了该方法

				afterNodeRemoval(node);

				// 返回被移除的节点

				return node;

			}

		}

		// 没找到 返回null

		return null;

	}

	/**

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

		}

	}

	/**

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

	}

	/**

	 * 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. If the map is modified while an iteration over the set is in

	 * progress (except through the iterator's own <tt>remove</tt> operation), the

	 * results of the iteration are undefined. 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.

	 *

	 * @return a set view of the keys contained in this map

	 */

	public Set<K> keySet() {

		Set<K> ks = keySet;

		if (ks == null) {

			ks = new KeySet();

			keySet = ks;

		}

		return ks;

	}

	final class KeySet extends AbstractSet<K> {

		public final int size() {

			return size;

		}

		public final void clear() {

			HashMap.this.clear();

		}

		public final Iterator<K> iterator() {

			return new KeyIterator();

		}

		public final boolean contains(Object o) {

			return containsKey(o);

		}

		public final boolean remove(Object key) {

			return removeNode(hash(key), key, null, false, true) != null;

		}

		public final Spliterator<K> spliterator() {

			return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);

		}

		public final void forEach(Consumer<? super K> action) {

			Node<K, V>[] tab;

			if (action == null)

				throw new NullPointerException();

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

				int mc = modCount;

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

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

						action.accept(e.key);

				}

				if (modCount != mc)

					throw new ConcurrentModificationException();

			}

		}

	}

	/**

	 * 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. If the map is modified while an iteration over

	 * the collection is in progress (except through the iterator's own

	 * <tt>remove</tt> operation), the results of the iteration are undefined. The

	 * collection supports element removal, which removes the corresponding mapping

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

	 *

	 * @return a view of the values contained in this map

	 */

	public Collection<V> values() {

		Collection<V> vs = values;

		if (vs == null) {

			vs = new Values();

			values = vs;

		}

		return vs;

	}

	final class Values extends AbstractCollection<V> {

		public final int size() {

			return size;

		}

		public final void clear() {

			HashMap.this.clear();

		}

		public final Iterator<V> iterator() {

			return new ValueIterator();

		}

		public final boolean contains(Object o) {

			return containsValue(o);

		}

		public final Spliterator<V> spliterator() {

			return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);

		}

		public final void forEach(Consumer<? super V> action) {

			Node<K, V>[] tab;

			if (action == null)

				throw new NullPointerException();

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

				int mc = modCount;

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

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

						action.accept(e.value);

				}

				if (modCount != mc)

					throw new ConcurrentModificationException();

			}

		}

	}

	/**

	 * 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. If the map is modified while an iteration over the set is in

	 * progress (except through the iterator's own <tt>remove</tt> operation, or

	 * through the <tt>setValue</tt> operation on a map entry returned by the

	 * iterator) the results of the iteration are undefined. 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.

	 *

	 * @return a set view of the mappings contained in this map

	 */

	public Set<Map.Entry<K, V>> entrySet() {

		Set<Map.Entry<K, V>> es;

		return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;

	}

	final class EntrySet extends AbstractSet<Map.Entry<K, V>> {

		public final int size() {

			return size;

		}

		public final void clear() {

			HashMap.this.clear();

		}

		public final Iterator<Map.Entry<K, V>> iterator() {

			return new EntryIterator();

		}

		public final boolean contains(Object o) {

			if (!(o instanceof Map.Entry))

				return false;

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

			Object key = e.getKey();

			Node<K, V> candidate = getNode(hash(key), key);

			return candidate != null && candidate.equals(e);

		}

		public final boolean remove(Object o) {

			if (o instanceof Map.Entry) {

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

				Object key = e.getKey();

				Object value = e.getValue();

				return removeNode(hash(key), key, value, true, true) != null;

			}

			return false;

		}

		public final Spliterator<Map.Entry<K, V>> spliterator() {

			return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);

		}

		public final void forEach(Consumer<? super Map.Entry<K, V>> action) {

			Node<K, V>[] tab;

			if (action == null)

				throw new NullPointerException();

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

				int mc = modCount;

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

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

						action.accept(e);

				}

				if (modCount != mc)

					throw new ConcurrentModificationException();

			}

		}

	}

	// Overrides of JDK8 Map extension methods

	@Override

	public V getOrDefault(Object key, V defaultValue) {

		Node<K, V> e;

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

	}

	@Override

	public V putIfAbsent(K key, V value) {

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

	}

	@Override

	public boolean remove(Object key, Object value) {

		return removeNode(hash(key), key, value, true, true) != null;

	}

	@Override

	public boolean replace(K key, V oldValue, V newValue) {

		Node<K, V> e;

		V v;

		if ((e = getNode(hash(key), key)) != null && ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {

			e.value = newValue;

			afterNodeAccess(e);

			return true;

		}

		return false;

	}

	@Override

	public V replace(K key, V value) {

		Node<K, V> e;

		if ((e = getNode(hash(key), key)) != null) {

			V oldValue = e.value;

			e.value = value;

			afterNodeAccess(e);

			return oldValue;

		}

		return null;

	}

	/*

	 * 功能：判断给定的key在hashMap中是否存在，如果key已经存在，则返回key对应的value

	 * 如果key不存在，则新生成一个节点(hash,key,value,null),value的值是通过 V v =

	 * mappingFunction.apply(key);获取的，重点是要搞明白mappingFunction.apply(key)这个方法。

	 */

	@Override

	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {

		// 如果自定义的函数为空，抛出空指针异常

		if (mappingFunction == null)

			throw new NullPointerException();

		// 算出给定key的hash值

		int hash = hash(key);

		// 定义node类型的数组tab,node类型的节点first,定义n,i;

		Node<K, V>[] tab;

		Node<K, V> first;

		int n, i;

		// 定义二叉树的计数变量

		int binCount = 0;

		// 定义TreeNode类型的对象t;

		TreeNode<K, V> t = null;

		// 定义存放node类型的节点old；

		Node<K, V> old = null;

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

			// 如果hashMap的长度大于扩容临界值或table及tab的长度为空，

			// 则走 resize()，该方法可初始化hashMap,也可以对hashMap进行扩容

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

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

			// 算出key在tab中的存储位置，如果该位置不为空，把该位置存储的节点赋值给first

			// 这种情况key已经存在，返回key对应的value值oldValue，key不存在时直接走

			// int mc = modCount;及后面的内容，直接新建node，存入key ,value，这种情况下first为null,

			if (first instanceof TreeNode)

				// 走红黑树分支，找出指定key的赋值给old,t;

				old = (t = (TreeNode<K, V>) first).getTreeNode(hash, key);

			else {

				// 如果不是红黑树，走到这里就是链表

				// 把first节点赋值给e,定义k;

				Node<K, V> e = first;

				K k;

				do {

					// 通过do-while循环，在链表中找出和给定hash值和key相同的节点，找到之后把链表上的节点e赋值给old,然后推出循环;

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

						old = e;

						break;

					}

					// 二叉树计算变量+1；

					++binCount;

				} while ((e = e.next) != null); // 循环遍历链表上的节点

			}

			V oldValue;

			if (old != null && (oldValue = old.value) != null) {

				// 红黑树和链表中如果old节点不为空且old节点的value不为空，返回old的value

				// //回调函数；

				afterNodeAccess(old);

				return oldValue;

			}

		}

		/**

		 * mappingFunction.apply(key)是理解整个computeIfAbsent方法的关键，apply传入的参数是key

		 * apply(key)执行后返回什么？这个需看apply函数定义： R apply(T t); 该返回值R是接口Function<T, R>的第二个参数，

		 * 到这里我们在看调用函数里面传入的参数： Integer integer1 = map.computeIfAbsent("4", (s)->new

		 * Integer(6)); 对比computeIfAbsent的方法定义:computeIfAbsent(K key,Function<? super K,

		 * ? extends V> mappingFunction) 可知：key是4，s=key，也是4，Function<? super 4, ?

		 * extends V>，V对应new Integer(6)的执行结果，所以V对应的是6， 所以Function<T, R> --->Function<4,

		 * 6>---> R apply(T 4),R=6;执行完mappingFunction.apply(key)的值是6，所以v=6;

		 */

		V v = mappingFunction.apply(key);

		if (v == null) {

			// 通过自定义函数mappingFunction获取的value为空，直接返回null;

			return null;

		} else if (old != null) {

			// 如果old不为空，把v赋值给old的value

			old.value = v;

			// 回调函数

			afterNodeAccess(old);

			return v;

		}

		// 如果在红黑树节点中找到的t节点不为空

		else if (t != null)

			// 把当前的map，数组tab,hash，key，v存储到红黑树中

			t.putTreeVal(this, tab, hash, key, v);

		else {

			// 在数组tab中新建节点，存入(hash, key, v, first),此时first为null,因为first = tab[i = (n - 1) &

			// hash]) = null

			tab[i] = newNode(hash, key, v, first);

			// 如果大于二叉树转换的条件，走二叉树分支

			if (binCount >= MapUtilConst.TREEIFY_THRESHOLD - 1)

				// 把tab转换成二叉树

				treeifyBin(tab, hash);

		}

		// 记录hashMap的修改次数

		++modCount;

		// hashMap的长度加1

		++size;

		// 回调函数

		afterNodeInsertion(true);

		return v;

	}

	/**

	 * 作用是根据指定键获取该键对应的值，并使用指定的函数生成一个新值，然后将新值存储回 Map 中。

	 */

	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {

		if (remappingFunction == null)

			throw new NullPointerException();

		Node<K, V> e;

		V oldValue;

		int hash = hash(key);

		if ((e = getNode(hash, key)) != null && (oldValue = e.value) != null) {

			V v = remappingFunction.apply(key, oldValue);

			if (v != null) {

				e.value = v;

				afterNodeAccess(e);

				return v;

			} else

				removeNode(hash, key, null, false, true);

		}

		return null;

	}

	/**

	 * 如果哈希表中不存在 key 这个键，则用 key 和 remappingFunction 计算得到一个新值，并将这个键值对插入到哈希表中；

	 * 如果哈希表中已经存在 key 这个键，则通过 remappingFunction 计算出一个新值，并用这个新值更新 key 对应的值。

	 */

	@Override

	public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {

		if (remappingFunction == null)

			throw new NullPointerException();

		int hash = hash(key);

		Node<K, V>[] tab;

		Node<K, V> first;

		int n, i;

		int binCount = 0;

		TreeNode<K, V> t = null;

		Node<K, V> old = null;

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

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

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

			if (first instanceof TreeNode)

				old = (t = (TreeNode<K, V>) first).getTreeNode(hash, key);

			else {

				Node<K, V> e = first;

				K k;

				do {

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

						old = e;

						break;

					}

					++binCount;

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

			}

		}

		V oldValue = (old == null) ? null : old.value;

		V v = remappingFunction.apply(key, oldValue);

		if (old != null) {

			if (v != null) {

				old.value = v;

				afterNodeAccess(old);

			} else

				removeNode(hash, key, null, false, true);

		} else if (v != null) {

			if (t != null)

				t.putTreeVal(this, tab, hash, key, v);

			else {

				tab[i] = newNode(hash, key, v, first);

				if (binCount >= MapUtilConst.TREEIFY_THRESHOLD - 1)

					treeifyBin(tab, hash);

			}

			++modCount;

			++size;

			afterNodeInsertion(true);

		}

		return v;

	}

	@Override

	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {

		if (value == null)

			throw new NullPointerException();

		if (remappingFunction == null)

			throw new NullPointerException();

		int hash = hash(key);

		Node<K, V>[] tab;

		Node<K, V> first;

		int n, i;

		int binCount = 0;

		TreeNode<K, V> t = null;

		Node<K, V> old = null;

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

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

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

			if (first instanceof TreeNode)

				old = (t = (TreeNode<K, V>) first).getTreeNode(hash, key);

			else {

				Node<K, V> e = first;

				K k;

				do {

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

						old = e;

						break;

					}

					++binCount;

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

			}

		}

		if (old != null) {

			V v;

			if (old.value != null)

				v = remappingFunction.apply(old.value, value);

			else

				v = value;

			if (v != null) {

				old.value = v;

				afterNodeAccess(old);

			} else

				removeNode(hash, key, null, false, true);

			return v;

		}

		if (value != null) {

			if (t != null)

				t.putTreeVal(this, tab, hash, key, value);

			else {

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

				if (binCount >= MapUtilConst.TREEIFY_THRESHOLD - 1)

					treeifyBin(tab, hash);

			}

			++modCount;

			++size;

			afterNodeInsertion(true);

		}

		return value;

	}

	@Override

	public void forEach(BiConsumer<? super K, ? super V> action) {

		Node<K, V>[] tab;

		if (action == null)

			throw new NullPointerException();

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

			int mc = modCount;

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

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

					action.accept(e.key, e.value);

			}

			if (modCount != mc)

				throw new ConcurrentModificationException();

		}

	}

	@Override

	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {

		Node<K, V>[] tab;

		if (function == null)

			throw new NullPointerException();

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

			int mc = modCount;

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

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

					e.value = function.apply(e.key, e.value);

				}

			}

			if (modCount != mc)

				throw new ConcurrentModificationException();

		}

	}

	/* ------------------------------------------------------------ */

	// Cloning and serialization

	/**

	 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and values

	 * themselves are not cloned.

	 *

	 * @return a shallow copy of this map

	 */

	@SuppressWarnings("unchecked")

	@Override

	public Object clone() {

		HashMap<K, V> result;

		try {

			result = (HashMap<K, V>) super.clone();

		} catch (CloneNotSupportedException e) {

			// this shouldn't happen, since we are Cloneable

			throw new InternalError(e);

		}

		result.reinitialize();

		result.putMapEntries(this, false);

		return result;

	}

	// These methods are also used when serializing HashSets

	final float loadFactor() {

		return loadFactor;

	}

	final int capacity() {

		return (table != null) ? table.length : (threshold > 0) ? threshold : MapUtilConst.DEFAULT_INITIAL_CAPACITY;

	}

	/**

	 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e., serialize

	 * it).

	 *

	 * @serialData The <i>capacity</i> of the HashMap (the length of the bucket

	 * array) is emitted (int), followed by the <i>size</i> (an int, the

	 * number of key-value mappings), followed by the key (Object) and

	 * value (Object) for each key-value mapping. The key-value mappings

	 * are emitted in no particular order.

	 */

	private void writeObject(java.io.ObjectOutputStream s) throws IOException {

		int buckets = capacity();

		// Write out the threshold, loadfactor, and any hidden stuff

		s.defaultWriteObject();

		s.writeInt(buckets);

		s.writeInt(size);

		internalWriteEntries(s);

	}

	/**

	 * Reconstitutes this map from a stream (that is, deserializes it).

	 * 

	 * @param s the stream

	 * @throws ClassNotFoundException if the class of a serialized object could not

	 * be found

	 * @throws IOException if an I/O error occurs

	 */

	private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException {

		// Read in the threshold (ignored), loadfactor, and any hidden stuff

		s.defaultReadObject();

		reinitialize();

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

			throw new InvalidObjectException("Illegal load factor: " + loadFactor);

		s.readInt(); // Read and ignore number of buckets

		int mappings = s.readInt(); // Read number of mappings (size)

		if (mappings < 0)

			throw new InvalidObjectException("Illegal mappings count: " + mappings);

		else if (mappings > 0) { // (if zero, use defaults)

			// Size the table using given load factor only if within

			// range of 0.25...4.0

			float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);

			float fc = (float) mappings / lf + 1.0f;

			int cap = ((fc < MapUtilConst.DEFAULT_INITIAL_CAPACITY) ? MapUtilConst.DEFAULT_INITIAL_CAPACITY

					: (fc >= MapUtilConst.MAXIMUM_CAPACITY) ? MapUtilConst.MAXIMUM_CAPACITY : tableSizeFor((int) fc));

			float ft = (float) cap * lf;

			threshold = ((cap < MapUtilConst.MAXIMUM_CAPACITY && ft < MapUtilConst.MAXIMUM_CAPACITY) ? (int) ft

					: Integer.MAX_VALUE);

			// Check Map.Entry[].class since it's the nearest public type to

			// what we're actually creating.

			SharedSecrets.getJavaOISAccess().checkArray(s, Map.Entry[].class, cap);

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

			Node<K, V>[] tab = (Node<K, V>[]) new Node[cap];

			table = tab;

			// Read the keys and values, and put the mappings in the HashMap

			for (int i = 0; i < mappings; i++) {

				@SuppressWarnings("unchecked")

				K key = (K) s.readObject();

				@SuppressWarnings("unchecked")

				V value = (V) s.readObject();

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

			}

		}

	}

	/* ------------------------------------------------------------ */

	// iterators

	abstract class HashIterator {

		Node<K, V> next; // next entry to return

		Node<K, V> current; // current entry

		int expectedModCount; // for fast-fail

		int index; // current slot

		HashIterator() {

			expectedModCount = modCount;

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

			current = next = null;

			index = 0;

			if (t != null && size > 0) { // advance to first entry

				do {

				} while (index < t.length && (next = t[index++]) == null);

			}

		}

		public final boolean hasNext() {

			return next != null;

		}

		final Node<K, V> nextNode() {

			Node<K, V>[] t;

			Node<K, V> e = next;

			if (modCount != expectedModCount)

				throw new ConcurrentModificationException();

			if (e == null)

				throw new NoSuchElementException();

			if ((next = (current = e).next) == null && (t = table) != null) {

				do {

				} while (index < t.length && (next = t[index++]) == null);

			}

			return e;

		}

		public final void remove() {

			Node<K, V> p = current;

			if (p == null)

				throw new IllegalStateException();

			if (modCount != expectedModCount)

				throw new ConcurrentModificationException();

			current = null;

			K key = p.key;

			removeNode(hash(key), key, null, false, false);

			expectedModCount = modCount;

		}

	}

	final class KeyIterator extends HashIterator implements Iterator<K> {

		public final K next() {

			return nextNode().key;

		}

	}

	final class ValueIterator extends HashIterator implements Iterator<V> {

		public final V next() {

			return nextNode().value;

		}

	}

	final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K, V>> {

		public final Map.Entry<K, V> next() {

			return nextNode();

		}

	}

	/* ------------------------------------------------------------ */

	// spliterators

	/* ------------------------------------------------------------ */

	// LinkedHashMap support

	/*

	 * The following package-protected methods are designed to be overridden by

	 * LinkedHashMap, but not by any other subclass. Nearly all other internal

	 * methods are also package-protected but are declared final, so can be used by

	 * LinkedHashMap, view classes, and HashSet.

	 */

	// Create a regular (non-tree) node

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

		return new Node<>(hash, key, value, next);

	}

	// For conversion from TreeNodes to plain nodes

	Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {

		return new Node<>(p.hash, p.key, p.value, next);

	}

	// Create a tree bin node

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

		return new TreeNode<>(hash, key, value, next);

	}

	// For treeifyBin

	TreeNode<K, V> replacementTreeNode(Node<K, V> p, Node<K, V> next) {

		return new TreeNode<>(p.hash, p.key, p.value, next);

	}

	/**

	 * Reset to initial default state. Called by clone and readObject.

	 */

	void reinitialize() {

		table = null;

		entrySet = null;

		keySet = null;

		values = null;

		modCount = 0;

		threshold = 0;

		size = 0;

	}

	// Callbacks to allow LinkedHashMap post-actions

	void afterNodeAccess(Node<K, V> p) {

	}

	void afterNodeInsertion(boolean evict) {

	}

	void afterNodeRemoval(Node<K, V> p) {

	}

	// Called only from writeObject, to ensure compatible ordering.

	void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {

		Node<K, V>[] tab;

		if (size <= 0 || (tab = table) == null) {

			return;

		}

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

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

 s.writeObject(e.key);

 s.writeObject(e.value);

 }

		}

	}

}