前言
从毕业到现在，也有有一年之久了。曾经经常看到各种HashMap源码解析，实现原理解析等文章，但都是看了又忘的状态。那这次我也从HashMap开始，将Java标准库的集合工具类（包括JUC并发包）源码捋一遍，并做博客输出。
集合工具类源码经过了精心设计，相信会让看过的人无不赞叹设计者Doug Lea（也是JUC的设计者）、Joshua J. Bloch的智慧，该设计者也出过一本书籍《Effective-Java》《Java并发编程实战》质量也相当不错，推荐看看。
类关系图
图（1）HashMap相关的类关系图
类解释（关键的类）：
- Map提供了将键映射到值的基本框架。
- Entry是Map的内部类接口，提供了将键与值绑定的容器框架。
- AbstractMap实现于Map，仅仅实现了最基础的查询/删除功能，它们都依赖于子类实现AbstractMap#entrySet()方法来获取Entry的Set集合与迭代器配合工作。
- HashMap实现于Map并继承自AbstractMap，基于“散列表+链表/红黑树”实现的完整功能。
- Node是HashMap的内部类，实现于Entry，基于“链表”的数据结构实现。建议不知道链表数据结构的同学去了解一下链表的原理，无非就是当前对象节点引用下一个对象节点，下一个对象节点再引用下一个对象节点，就像一根链条一样。
- TreeNode间接继承（实际继承自linkedHashMap#Entry,而前者继承自HashMap#Node）自Node，是JDK1.8版本新增的基于“红黑树”的实现。红黑树数据结构相比链表的优点是查询速度比后者者较快（前者 O(logN)内 对比 后者O(N) ,N为元素个数），不过如果树节点不多时效率并不比链表高多少，反而插入效率 O(logN)内 相对链表O(1)是慢了的些，因此HashMap在链表长度满足大于等于阀值（HashMap#TREEIFY_THRESHOLD成员属性表示）8时才将链表替换为红黑树结构。
- 其他类可以暂不关注，当前只会涉及到上面介绍的类。
初始值解释
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Node[] table;
transient int size;
int threshold;
final float loadFactor;
图（2） HashMap中的部分属性
分别表示：
- DEFAULT_INITIAL_CAPACITY：默认的容器容量大小，默认为1<<4（位左移运算，十进制为16）
- MAXIMUM_CAPACITY：最大容器容量大小。
- DEFAULT_LOAD_FACTOR：默认负载因子。
- table：一个由Node对象数组（亦称散列表）组成的数据容器。
- size：当前数据容器table中保存的元素个数。
- threshold：阀值，当size大于等于该值时将触发扩容，由table.lenght * loadFactor计算得来。
- loadFactor：当前容器的负载因子。
从创建容器开始
一、构造方法
构造方法挑两个主要作解析：
- public HashMap()
- public HashMap(int initialCapacity, float loadFactor)
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
图（3） HashMap主要构造方法
无参构造仅仅将常量DEFAULT_LOAD_FACTOR（默认负载因子）赋值给当前容器的负载因子属性，第二个构造方法则手动设置容器初始容量与负载因子。目前并未看到table[]数组变量进行初始化，这也意味着在创建容器对象时，容器并未分配元素空间，不会有任何额外开销。那么容器何时才会进行初始化呢？
在深入之前，注意到构造方法调用了HashMap#tableSizeFor()，该方法代码如下：
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;
}
图（4） HashMap#tableSizeFor()方法代码
你可以将该方法单独拿出来执行，你会发现这个算法得到的值永远都是当前给定值-1向后取得最近的2的N次幂（如果你深入研究一下这个算法，你会发现实际就是将最高权位以后的所有位权设置为1，再将结果加1后那么所有位权进1就得到了2的N次幂），将方法返回值赋值给threshold变量，这将在后期的初始化容器时作为初始化容量大小值。
二、扩容方法可能有人注意到构造方法中初始化容量值是赋值给threshload变量的。疑问来了，threshold不是一个阀值么，怎么没有乘于loadFactor后再赋值给这个阀值变量呢？答案就在HashMap#resize()方法中，代码如下：
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
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
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
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;
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;
}
图（4） HashMap#resize()方法代码
代码解析：
首先，咱们看到方法上的文档注释：“Initializes or doubles table size.”，翻译过来就是“初始化或加倍扩容表容量大小”，从而得知容器的初始化工作与扩容将在该方法中进行。另外这个注释中还提到：“ 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.”，翻译过来就是“因我们使用2的幂进行扩张，在新表中所有的元素要么在以前的位置，要么以2倍偏移”。发没发现和上面的HashMap#tableSizeFor()方法永远饭回2的幂有诸多联系呢。
深入到内部逻辑中大概以下步骤：
- 判断当前是否已经初始化容器（判断table变量是否为空或数组lenght是否为0）。
1.1.如果未初始化，判断threshold是否大于0（是否手动设置了初始化容量）
1.1.1.如果大于0，则将该值作为初始化容量。（这表明构造中对其赋值只是为了设置初始容量）
1.1.2.反之，使用默认DEFAULT_INITIAL_CAPACITY常量作为初始化容量。
1.2.反之，将旧的容量（oldCap）向左位移1位（2的N+1次幂） - 使用新的容量值（newCap）* loadFactor计算得出的值赋值给阀值threshold。
- 将旧的table备份（oldTab），使用新的容量值（newCap）重新创建Node数组并赋值给table。
- 将旧的table备份（oldTab）拷贝到新的容器table中，拷贝时根据当前元素是链表还是红黑树分别进行处理。
你有没有想过，为什么HashMap只支持扩容，而不去支持缩容呢？
三、添加元素目前为止，咱们虽然知道容器是如何扩容的，但还不知道容器什么时候进行扩容。仔细一想创建容器后都是直接HashMap#put()，那前者方法中应该可能有调用HashMap#resize()吧。事实如此，代码如下：
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[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
else {
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;
}
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;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
图（5） HashMap#put()以及相关方法代码
从中可以总结下列逻辑：
- 计算Key的hash值（稍后解析HashMap#hash()方法）
- 判断散列表table（Node数组）是否为分配空间，如果未分配则调用HashMap#resize()进行初始化。
- 根据hash值与表容量 - 1 进行位与计算（效果等于hash对表容量取余运算）得到当前Key在表中的位置。
3.1.索引处没有元素时，直接新建一个Node 。
3.2.否则索引有元素，判断该元素是否有子节点。
3.2.1.无子节点时，替换当前Node旧的Value。
3.2.2.有子节点时，判断节点是否为红黑树TreeNode。
3.2.2.1.是红黑树，进行红黑树的节点插入操作。
3.2.2.2.非红黑树，在链表尾部新建一个Node，如果当前链表长度大于等于TREEIFY_THRESHOLD阀值（默认值为8），则调用HashMap#treeifyBin()进行链表转红黑树操作 - 元素个数size记录值+1，判断是否超过阀值threshold，如果超过将调用HashMap#resize()进行扩容操作。
另外，可以看到逻辑中还调用了一些回调方法，包括HashMap#remove()代码逻辑中也调用了：
// Callbacks to allow linkedHashMap post-actions
void afterNodeAccess(Node p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node p) { }
图（6） HashMap中的模版方法
这在设计模式的术语叫“模板方法模式（Template Pattern）”，这几个方法实际上如注释所明是提供给linkedHashMap使用的，可用来实现LRU（一种缓存淘汰策略）功能特性。
那么是否也可以利用这几个模版方法对HashMap增加缩容机制呢？
四、HashMap#hash()方法与2次幂容量的关系先贴出hash()代码:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
图（7） HashMap#hash()方法
这段代码非常精炼。疑问来了，为什么不直接使用key.hashCode()获取的值 ？而是再次对它的高16位（无符号右移16位）进行亦或运算呢？为什么是亦或不是或(|)、与(&)呢?
1、为什么要与高16位进行亦或运算？
先给出答案：让索引分布更均匀，让所有位参与到运算当中。
解答：
在前面的代码里，我们会看到计算一个Key的索引使用的公式为：tab[].lenght - 1 & hash，与（&）运算实际上只会让hash与lenght表示相对应的位进行有效运算，那么hash相对应lenght最高位以前的位都将被抛弃，那么被抛弃的位将无法影响到索引值，没有有效参与到运算当中。因hash是一个int值，int值在java中固定占用4个字节（32位），故为让更多位参与到运算当中，使用前16位与后16位进行位运算，使得可能的结果分布更均匀。当然这仅仅是我的个人理解，也有其他许多解释。
2、为什么使用亦或而非其他呢？
先给出答案：保证1和0比例均匀。
解答：
看到过一个非常好的例子，位只会有两种值：1或0，那么它们进行运算的可能有4种：1和1，1和0，0和1，0和0。
- 使用 & 运算符得到的结果分别是：1，0，0，0 ;1与0比例为 1/3
- 使用 | 运算符得到的结果分别是：1，1，1，0 ;1与0比例为3/1
- 使用 ^ 运算符得到的结果分别是：1，0，0，1 ;1与0比例为2/2
很直观，亦或运算得到的值更均匀。
3、为什么扩容一定要是2的幂倍增长？
先给出答案：更好的复用以前的索引计算结果
解答：
前面的HashMap#resize()方法解析提到过：“在新表中所有的元素要么在以前的位置，要么以2倍偏移”，从代码逻辑中也可以看到：
if (oldTab != null) {
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;
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;
}
}
}
}
图（8）HashMap#resize()中扩容后的数据复制代码摘要
只需要重组对应索引下的链表或红黑树再将它们分别放置原位(loTail)或2倍原位(hiTail)中。
尾声
目前我觉得HashMap中重要的知识和逻辑就以上这些，设计相当精巧，代码利落不啰嗦。值得去研究研究。
