分析 java.util.HashMap 源码
概述
HashMap是一个用的比较多的容器，HashMap解决了Hashtable的一些问题，带来了性能的提高，HashMap是线程不安全的。
下文环境基于J11
HashMap 的结构
HashMap 是由 数组+链表+红黑树构成的，当冲突的元素超过8则使用红黑树存储，否则使用链表存储。相比于Hashtable ，HashMap使用了红黑树，当散列冲突较多时性能比Hashtable要高得多。
HashMap中有两种类型的节点 ; Node 和 TreeNode
Node 用于链表和数组， TreeNode 用于红黑树
HashMap整个是用一个 Node 数组，称谓哈希桶存储：
transient Node[] table;
Node 的结构如下所示，它实现了Map.Entry 这个接口，是Map 的集合形式，方便来遍历。定义的一些字段也都表明是方便来访问的
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
....
}
hash 字段用来存储该元素的哈希值
next字段用作链表
class TreeNode extends LinkedHashMap.Entry {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
}
通过一些继承关系可以很清楚的了解 HashMap 的一些特性
要了解HashMap必须要知道几个关键字段的作用：
int threshold; // 临界点，桶的大小，所能容纳 Node 的个数极限
final float loadFactor; // 负载因子
transient int modCount; // 记录修改次数，用于快速失败 fail-fast
int size; // 大小
一些用来表示结构的字段：
transient Node[] table;
一些默认值字段：
int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 桶的默认大小
int MAXIMUM_CAPACITY = 1 << 30 // 桶的最大大小
float DEFAULT_LOAD_FACTOR = 0.75f; // 默认的负载因子
int TREEIFY_THRESHOLD = 8; // 转换为红黑树的临界点
\(临界点=桶的大小 * 负载因子\)，其中桶的大小是固定的，定义了就不能够更改。
所以负载因子决定着桶能容纳的键值对的最大数量，负载因子越大所能容纳的就越多。
modCount 修改计数，统计着修改HashMap的次数，用于快速失败。用于多线程访问HashMap导致线程安全问题，一个线程修改一个线程迭代，这肯定是会出现问题的，快速失败（fail-fast，也可以称为及时失败）机制是一种设计上的权衡，降低检测（并发导致的线程安全问题）对程序性能带来的影响。
size 就是桶中实际存在的键值对的数量
桶的默认大小为 \(16\) 。桶的大小必须为2的倍数（合数）。这么做主要是为了在取模合扩容时做优化，同时为了减少冲突。
负载因子固定为 \(0.75\) ，这是在时间和空间上最好的折中。
转换为红黑树的临界点为8，这个数值在文档注释中提到了。根据泊松分布，假设HashMap容量为16，假设临界点为12（\(16*0.75\)) ，能够放入12个键值对到HashMap中。其中链表存放8个的概率为0.00000006。由泊松分布得出
\[P(X = k) = \frac{\lambda^k e^{-\lambda}}{k!}, \]- \(\lambda\) 是随机事件发生次数的数学期望
- k 是事件在这一段时间发生的次数
- \(\lambda = 0.5\) ，
可能是负载因子为0.75发生扩容的平均值 - k 表示链表大小
存放1-7个的概率\(P\)分别为：
- 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个节点的概率非常小
所以 TREEIFY_THRESHOLD 树化（链表转换为树）的临界点为 8，值已经非常趋近于0
较为重要的功能
HashMap作为一个容器，最重要的还是存入和取出。先分析HashMap是如何存入一个又一个元素的。
确定存入的位置
以下是HashMap存入元素的方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
它是通过计算的哈希值和桶的大小来计算索引的，n为桶的大小：
i = (n - 1) & hash
哈希值的计算
int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
哈希计算方法中，将哈希值异或高16bit。这样将高16bit和低16bit进行了参杂，这种方法称为“搅动”，这样可以保证低位包含着高位的特征。增大了之后索引的随机性
put 存入
HashMap的put分为几个步骤：
- 桶为空则创建
- 当前位置为空则直接插入
- 节点key相同则直接覆盖
- 是否为树
- 为树则直接插入节点
- 处理链表
- 长度过大则转换为红黑树
- key存在则直接覆盖
- 超过可容纳的临界点扩容
V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// 步骤1： 桶为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤2：当前位置为空则直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
// 步骤3： 节点key相同则直接覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤4： 判断是否为树
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
// 步骤5：为链表
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;
}
// 相同的key则覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步骤6
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
扩容
当HashMap无法装更多的元素时，就需要扩容。好比桶太小，需要换一个桶一样，并且还需要把旧桶中的水倒入新桶。
HashMap 通过 resize() 这个方法来扩容，通过一些代码来逐步分析：
首先，HashMap 每次扩容都增大两倍
newCap = oldCap << 1
到最大容量则不再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
之后重新计算临界值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
threshold = newThr;
然后逐步地将元素移动到新数组中
for (int j = 0; j < oldCap; ++j) {
Node 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)e).split(this, newTab, j, oldCap);
// 对链表进行处理
else { // preserve order
// 位置不变化的链表
Node loHead = null, loTail = null;
// 位置变化的链表
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
// 这里不需要重新计算位置，只需要比较前一位是1还是0
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;
}
}
}
}
按照普通思维来看，从旧桶移动到新桶中是需要重新计算每一个元素的位置的。1.8之前是这么做的，1.8之后采用了性能更加高的方法，用最少的时间来计算出元素的新位置。
根据索引算法
i = (n - 1) & hash
所以只需要判断高一位是1还是0，如果是0则还是原来的位置，如果是1则需要变动位置。变动的位置也只需要在原来的位置上加上原来容量的大小。例如 原来位置是1，大小是16，那么新位置就是17
下面是用来计算高位是1还是0的算法，用的是旧桶的容量，刚好是高位的位置
e.hash & oldCap