HashMap源码解析

size > threshold

如果只有一个节点，则直接使用e.hash获取需要放置的位置不需要判定newTab中对应位置是否为空，是因为该元素可能被放置的位置只有i或者i + N，这两个位置一定不会和其他不等于i的元素占用

Y也即自定义了Hash表大小和负载因子情况下默认的扩容阈值初始化方式

链表的Hash拆分。操作证明如下：1. 当我们原始数组长度为N的时候，如果这个数组内的元素的访问方式是head = oldTab[Node.hash % N]；2. 此时第i位的Hash表的内部的hash值均为(2k) * N + i或者(2k+1) * N + i，其中k为整数3. 则扩容到2N之后，我们就肯定可以知道，对于原始第i位的链表内的所有元素，其映射后的下标为(2k) * N + i) % 2N = i （依然留在第i位）或者 ((2k + 1) * N + i) % 2N = N + i （需要放置到N + i位）4. 这也就意味着，其实我们对于原始第i位上的元素，扩容的时候，实际上只要计算一次 hash / N，结果如果是偶数，那么久保留在原位置oldTab[i]，如果是奇数，那么就偏移到新的位置oldTab[N + i]即可基于这个背景情况下：1. 实际上我们的取模动作就是e.hash & (newCap - 1)（因为我们知道hash表的长度始终是2^n，并且(2^n)-1一定是一个全1的数(n!=0)，此时求与就是取模，参考IP的掩码运算）；2. 除法看奇偶的动作就是 e.hash & oldCap == 0，其实因为我们只关注这个数字是不是N的偶数倍，已知N是2^n的情况下，我们只要知道这个 数字&(1<<n) 是否为0即可。由此我们就可以回头看，为什么HashMap的实际的表的大小要定在2的N次幂，该方式下访问、扩容、链表拆分都会很快。

e instanceof TreeNode

afterNodeInsertion(evict)用于LinkedHashMap

迭代整个Hash表进行扩容

oldThr > 0

1. 如果当前Hash表的节点是一个链表的头结点，则插入链表尾（注，过程中可能会将链表转换成树）2. Java7放在链表头，Java8放在链表尾，Java8是由于是重要访问所有链表检查是否同一个key，因此遍历完成之后直接放末尾即可

newThr == 0

如果当前Hash表的节点是一个数的根节点，则往这棵树插入节点

N对应没有自定义阈值场景

N

newThr = oldThr << 1更新扩容的阈值

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

newCap = (1 << 4);newThr = (int)(0.75 * (1<<4));

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

int h;result = (h = key.hashCode()) ^ (h >>> 16)

initialCapacity < 0

newThr = Integer.MAX_VALUE)

Y

put操作结束

e = oldTab[j]

++modCount++size

return newTab

tableSizeFor(int cap)

操作目的：1. Hash表使用2的幂作为掩码（所以用1进行直接位移）2. 高位容易冲突且经常因为容量不够而不参与运算（所以通过高低异或让高位也参与运算）3. 已经用树状结构来解决冲突（所以不许忘因为需要高低位一起Hash消耗而很高的性能，注，以前java7 的 hash算法需要进行较多次异或操作，用于尽量散列key）

高低位合并if (loTail != null) {    loTail.next = null;    newTab[j] = loHead;}if (hiTail != null) {    hiTail.next = null;    newTab[j + oldCap] = hiHead;}

return null结束

n = (tab = resize()).length调用resize，初始化Hash表

return newTab

oldCap >= MAXIMUM_CAPACITY（旧容量 >= (1<<30) (也即2^30)）

1. 更新e的value2. 返回更新前的e的value

initialCapacity > (1<< 30)

已有的Hash表为空

return result

newCap < (1<<30) && ft < (float)(1<<30)

(newCap = oldCap << 1)

如果是红黑树结构，则调用红黑树的裂变方法

计算下一次扩容的目标容量标准二进制取整动作，和Integer.highestOneBit实现方案很类似

j = 0; j < oldCap; ++j

initialCapacity = (1<< 30)

e.next == null

Hash表如果为空，直接填充

这一步意味着1. Hash表扩容的条件，是总元素是否超过阈值，而不是已经放置KeyNode的Hash表的个数2. 此时总是先添加元素，再实施扩容resize()

return oldTab

多节点的链表使用高低位拆分

newCap = oldThr

throw IllegalArgumentException

低位赋值if (loTail == null)    loHead = e;else    loTail.next = e;loTail = e;

懒加载模式，构造的时候不会初始化Hash表，只初始化Hash表的长度

p = tab[i = (n - 1) & hash]因为扩容始终是2的N次倍，所以n-1是一个掩码，本初就是取出这段掩码所覆盖的Hash结果对应的下标

key == null

e用来缓存原始值，如果原始值没有，则为null

p == null

1. 如果插入链表过程中，找到了同一个key，则e为冲突的key对应的Node2. 否则为null

Y如果Hash表过大，则放开阈值

loop:1. 如果没有到尾部并且不是同一个key，则链式访问下一个节点2. 如果访问到Node对应的链表的尾部2.1 则在尾部插入新的Node2.2 如果这个插入行的Node之后，Hash表当前位置的Node节点对应的链表长度超过9，整个链表需要调用treeifyBin转变成红黑树（为什么是9，因为先执行了e = p.next，并且没有++binCount的情况下就开始判断链表是否超长，同时也意味着，在HashMap里面，解决Hash冲突的链表最长只会有8个元素）

释放原始的Hash表的oldTab[j]

int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;result = (n < 0) ? 1 : (n >= (1<<30)) ? (1<<30) : n + 1;

N按照负载因子和Hash表的的长度计算扩容阈值

e = p

HashMap.resize

threshold = Integer.MAX_VALUE调整扩容阈值为最大，同时不再扩容

构造完成

resize()

N对应默认的初始化操作

newCap < MAXIMUM_CAPACITY&&oldCap >= DEFAULT_INITIAL_CAPACITY

N对应的链式List

oldCap > 0

右侧对应了完全默认的场景下的Hash表的初始化

this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);

如果有自定义Hash表的大小和敷在因子，该场景下的阈值初始化

ft = (float)newCap * loadFactor

Y对应有自定义阈值场景

e != null

高位赋值if (hiTail == null) hiHead = e;else hiTail.next = e;hiTail = e;

N意味着Hash表当前位置的的节点及其后续的链表说或者树状结构，扩容之后需要二次映射

newThr = (int)ft

result = 0

e == null

Y如果是同一个key

e.hash & oldCap == 0

Y对应默认的扩容操作

int hash(Object key)

左侧流程对应了扩容过程中的阈值变化，在没有超过1<<30的情况下，始终会按照扩大一倍的方式进行扩展

p instanceof TreeNode

Y意味着Hash表当前位位置没有Key映射进来，也就不需要有扩展后的映射