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

/**
 * 哈希桶数组，默认长度16
 */
transient Node<K,V>[] table;

/**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * HashMap中实际存在的键值对数量
 */
transient int size;

/**
 * 记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。
 * 内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值
 * 被覆盖不属于结构变化。
 */
transient int modCount;

/**
 * 下次扩容的阈值(capacity * load factor).超过这个数目就重新扩容
 */
int threshold;

/**
 * 负载因子，默认为0.75f，在哈希桶数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
 */
final float loadFactor;

static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

tab[(n - 1) & hash]

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

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是空的或者未存储任何元素则需要先初始化进行tab的初始化
	// HashMap使用了Lazy策略，table数组只会在第一次调用put()函数时进行初始化，这是一种防止内存浪费的做法，像ArrayList也是Lazy的，它在第一次调用add()时才会初始化内部的数组。
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
	// 通过取模计算确定元素在table数组中的索引，当对应位置为null时，将新元素放入数组中
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
	// 若对应位置不为空时说明哈希冲突
	else {
		Node<K,V> e; K k;
		// 节点key存在，直接替换节点
		if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))
			e = p;
		// 当p为红黑树的节点时，向树内插入节点
		else if (p instanceof TreeNode)
			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
		// 当p是链表时，向链表插入节点
		else {
			for (int binCount = 0; ; ++binCount) {
				// 找到尾节点插入
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
					// 判断链表长度是否达到树化阈值8，达到就对链表进行树化
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						treeifyBin(tab, hash);
					break;
				}
				// key已经存在直接覆盖value
				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;
			 // 回调已允许LinkedHashMap后置操作
			afterNodeAccess(e);
			return oldValue;
		}
	}
	// 更新修改次数
	++modCount;
	// 检查数组是否需要进行扩容
	if (++size > threshold)
		resize();
	// 回调已允许LinkedHashMap后置操作
	afterNodeInsertion(evict);
	return null;
}

final Node<K,V>[] resize() {
	Node<K,V>[] oldTab = table;
	int oldCap = (oldTab == null) ? 0 : oldTab.length;
	// 获取扩容的阈值（容量*负载系数）
	int oldThr = threshold;
	// 定义并初始化新数组的长度和新阈值
	int newCap, newThr = 0;
	// 断是初始化数组还是扩容，等于或小于0表示需要初始化数组，大于0表示需要扩容数组。若  if(oldCap > 0)=true 表示需扩容而非初始化
	if (oldCap > 0) {
		// 判断数组长度是否已经是最大，MAXIMUM_CAPACITY =（2^30），如果已经最大， 将阈值设置为最大，不在扩容
		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
		// 说明调用的是HashMap的有参构造函数，因为无参构造函数并没有对threshold进行初始化
		newCap = oldThr;
	else {               // zero initial threshold signifies using defaults
		// 说明调用的是HashMap的无参构造函数
		newCap = DEFAULT_INITIAL_CAPACITY;
		newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
	}
	// 当阈值为0时需重新计算，公式：容量（newCap）*负载系数（loadFactor）
	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;
}

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

	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);