仔细瞄一下HashMap是怎么干活的

以下分析基于jdk11.0.2

1. 创建HashMap时发生了什么？

HashMap()，HashMap(int initialCapacity)，HashMap(int initialCapacity, float loadFactor)。这三个方法都直接或间接地会初始化loadFactor（加载因子）和threshold（扩容阈值）。其中threshold=capacity*loadFactor。

1.1 threshold如何确定？

当调用HashMap()创建HashMap时，threshold的值会在第一次resize()时赋值。由DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY可知threshold=0.75*16=12

当调用HashMap(int initialCapacity)/HashMap(int initialCapacity, float loadFactor) 创建HashMap时，threshold由 loadFactor*tableSizeFor(int cap) 计算得出。

2. 调用put(K key, V value)时发生了什么？

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

　　该方法首先调用了hash()方法获取key对应的hash值，然后调用putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)…

2.1. hash(Object key)做了些什么？

　　该方法将key的hashCode的高16位与低16位进行了一次异或位运算（hashCode为32bit的int类型）。v1.8+中该方法的实现较之前版本更容易发生hash碰撞（之前版本为4次异或运算），这是权衡性能和红黑树的优化…

2.2. putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)做了什么？

　　该方法除了供put()调用，也提供给putIfAbsent()调用。在此暂时讨论put()调用的情况，即 boolean onlyIfAbsent=false; boolean evict=true;

　　下面列出用无参构造函数new HashMap()创建的对象进行put的几种情况：

2.2.1. 第一次put时，执行步骤如下：

1. 执行resize()，将map中的table初始化为大小为DEFAULT_INITIAL_CAPACITY的Node数组；threshold赋值为DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY。

2. 使用hash, key, value创建Node节点，作为链表的头节点存于table[i]中，下标为 i = (n - 1) & hash 。

2.2.2. 当put后table[]内节点数<=threshold(默认threshold=12，而此时table[].size也就是capacity应为16，这两个值会随着resize更新)时，执行步骤如下：

1. 找到hash对应table[]中的链表/树

2. 当table[]存的是链表时，把key-value存入链表尾节点或替换key对应节点的value值，并判断链表长度是否>TREEIFY_THRESHOLD(默认值8)，如果是则调用treeifyBin()。调用treeifyBin()时会判断是否需要将该链表转为树。当table[].size>=MIN_TREEIFY_CAPACITY会转为树，否则只是resize()扩容；而当table[]存的是树时，调用TreeNode.putTreeVal()在树中存入/替换。

2.2.3. 当put后table[]内节点数>threshold时：

执行完2.2.2的操作后，执行执行resize()：capacity翻倍(<<1)，threshold也重新计算。

画了张流程图用来精简表示putVal：

3. 调用resize()时发生了什么？

在putVal途中调用有两种情况下HashMap会调用resize()进行扩容和table[]数据迁移（迁移几率50%）：

3.1. 第一次调用putVal后调用resize()：

3.1.1. 未指定initialCapacity或loadFactor值:

创建table[]，大小为DEFAULT_INITIAL_CAPACITY（默认值16）；赋值threshold=DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY（默认值12）。

3.1.2. 已指定initialCapacity或loadFactor值：

创建容量为tableSizeFor(initialCapacity)的table[]；给扩容阈值赋值 threshold = loadFactor * tableSizeFor(initialCapacity)。

简单说明一下tableSizeFor(int cap)函数：返回值为大于等于cap且与cap差值最小的2^n的值。例如3->4，4->4，9->16，65->128。

3.3. table[]内节点数>threshold时，执行步骤如下：

3.3.1. 重新计算table[]容量capacity和扩容阈值threshold，值皆为原值的2倍(<<1)，创建新table[capacity]

3.3.2. 遍历原table[]中的链表/树,

　　当链表为单节点时：将该节点放至新table[]，下标为hash&(capacity-1) ；

　　当链表为多节点时：遍历该链表并分离出一条需要移动位置的链表，将2条链表放至新table[]。可根据hash&oldCapacity==0判断Node是否需要移动；

　　当链表为红黑树时：调用TreeNode.split()将树拆分/移动。当树的大小<=UNTREEIFY_THRESHOLD（默认6）时会退化成链表。

巴特西