Synopsis
本文主要讲解 HashMap 中比较重要的部分，如 threshold, hashcode，resize 等。
Node
HashMap 中，每一个元素都是一个结点（Node）：
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;
}
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
}
当我们 put(Key, Value) 到 HashMap 时，它会创建一个 Node，将 key, value 等存放进去。
structure
HashMap 内部会有一个数组，当 put 数据进来的时候，会根据 key 的哈希值散列到数组上，当发生哈希碰撞（不同的数据的哈希值相同）的时候（如 put 操作计算出位置为 table[5] ，但它已经有数据了），则会将碰撞的值放到 table[5] 中的结点的 next 中，即形成一个链表。
threshold
阈值（threshold）可以看作是当前哈希表的容量 * 加载因子 ，当元素达到阈值的时候需要进行扩容。
加载因子（loadFactor）描述了扩容时的填充程度。如果 loadFactor 过大，则 HashMap 扩容前发生的 hash 冲突的概率就会越大，那么单链表的长度也会越长，那么在查找的时候会因为单链表的长度过长而导致查找的效率变低。如果 loadFactor 设置过小，那么 HashMap 的空间利用率会降低，导致 HashMap 在很多空间没有利用的情况下就开始扩容。默认的为 0.75。首先来看下构造函数：
/**
* @param initialCapacity 初始容量
* @param loadFactor 加载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
this.loadFactor = loadFactor;
// 调用构造函数的时候会根据用户传进来的大小计算一个初始的阈值
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 由于 HashMap 的容量是2的幂，所以这里需要将用户传的初始容量计算出最终的容量
* 如 cap = 10，则要申请的容量为16
*/
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;
}
我们来看下他是如何计算出这个阈值的(由于 n >= 0，当 n = 0 时显然结果为0，所以下面只考虑 n > 0 的情况）：
n = cap -1。目的是为了防止 cap 已经是2的幂。如果不这样做的话，最后计算出来的容量将为初始容量的2倍。n |= n >>> 1。由于 n > 0，所以 n 至少有1位为1。这里考虑最高位的1。将 n 右移一位，那么最高为的后一位也为1，再做或运算，则得到的 n 的最后位和最高位的下一位也为1。n |= n >>> 2。将 n 再右移两位，再做或运算。由于第2步已将将高两位都变成1了，右移两位后，高两位的后两位也变成1了，再做或运算，最终 n 的高4位都变成1了。n |= n >>> 4。以此类推，高8位变成1了。n |= n >>> 8。高16位变成1了。n |= n >>> 16。高31位变成1了。由于 int 只有32位。那么最多是32个1。这时超过了 MAXIMUM_CAPACITY，那么就会去这个最大值。- 最终得到的 n < 0 则返回 1；n > MAXIMUM_CAPACITY 则返回 MAXIMUM_CAPACITY；否则返回 n + 1。
下面我们来看一个实例，假设 cap = 38，那么要计算出刚好比它大的2的幂即64：
可以看出 2-6 步骤所做的就是一件事：将 cap 最高位的1后面全部置为1。 最后变成11…1。然后第7步 n + 1 将其变为 10…0，即变成2的幂。
简而言之，就是将 cap: 01xxx 变成 10000。那么再看下第一步为什么要 cap -1,如果 cap 本身为2的幂，不减1的话，会将0100转换成1000即为原来的2倍。
扩容 resize
当元素的数量达到阈值的的时候，需要进行扩容。那么什么时候调用这个方法呢，我们看下源码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//当我们首次调用 put 方法添加元素的时候，table 为 null。此时会调用下面的 resize() 方法
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ...
++modCount;
// 当前的 size = threshold 的时候，也会调用 resize 进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
现在来看下 resize 方法到底做了什么，根据上面将的 threshold，当传进初始容量38是，它会计算出 threshold = 64，我们借用它来看下面的代码：
final Node<K,V>[] resize() {
Node<K,V>[] 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; // 直接将阈值翻倍
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // 初始的阈值为0时，使用默认值
newCap = DEFAULT_INITIAL_CAPACITY;
// 可以看到阈值是通过初始的容量乘以加载因子的（但构造函数中计算出来的 threshold 没有乘）
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<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;
}
当我们调用 put 方法往哈希表添加结点的时候，它会调用 putVal 方法。首次调用时 table 为 null，会调用 n = (tab = resize()).length，从而调用了 resize() 方法。
我们简化下代码，看首次调用时做了什么（直接使用上面的例子举例，构造函数中的容量传的是38，然后会得到 threshold = 64)：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 首次进来时 table = null 所以 oldCap = 0
int oldThr = threshold; // oldThr = 64
int newCap, newThr = 0;
else if (oldThr > 0)
newCap = oldThr; // newCap = 64
if (newThr == 0) {
// 这里就将构造函数中得到的 threshold 乘以了 loadFactor 得到了真实的阈值
// 也就解释了为什么在构造函数中得到的阈值没有乘以加载因子了
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //此时得到的阈值为 64 * 0.75 = 48
// 此时 threshold = 48，newCap = 64
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 首次进来创建了一个长度为 newCap 的数组
return newTab;
}
当我们第一次调用 put 方法，会调用 resize 方法，它会根据在构造函数中得到的一个 threshold（其实并非是真正的阈值（threshold)，而是容量(capacity)），得到一个真正的阈值（即乘以了加载因子 loadFactor），并且创建了一个长度为 capacity 的数组。
再来看看当元素数量达到阈值（即48）时，怎样去扩容：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; // oldCap = 64
int oldThr = threshold; // oldThr = 48
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 直接将容量翻倍 newCap = 64 * 2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 直接将阈值翻倍即 48 * 2 = 96
}
threshold = newThr;
// 此时阈值和容量都翻倍了: newCap = 128, newThr = 96
// 创建一个新的数组，然后将旧的数组中的数据迁移进去
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 首次进来创建了一个长度为 threshold 的数组
// ...
return newTab;
}
可以看到扩容的过程就是直接将阈值和容量翻倍即可。
计算结点在bucket中的位置
我们再来看看它是如何计算出一个结点在桶（bucket）中的位置的：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
...
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); // 将结点放在 (n - 1) & hash 位置
...
}
可以看出它是通过 (n - 1) & hash 计算出结点在数组中的位置而不是 hash % n（n 即为数组的长度）。hash % n 很好理解，就是通过 hash 得到一个不大于 n 的数作为 index。
那么 (n - 1) & hash 又是什么意思？其实它和 hash % n 等价，不过有一个前提就是 n 为2的幂。这就是为什么数组的长度要根据用户传进来的 capacity 重新计算出一个刚好比它大的2的幂。
如果容量为2的幂，则 n 为100..0，那么 n - 1 为011..1，那么 hash & (n -1) 会将 hash 的高位修改为0，低位不变，即实现了 h % n 的效果。通过这种方式的效率会比 h % n 的效率高。
HashMap 的 bucket 的容量必须为2的幂的另一个原因是它为偶数，那么 n-1 为基数，那么它的最后一位一定为1。 那么 hash & (n-1) 的末位既可能为0，也可能为1，即既可以为奇数，也可能为偶数，但如果不保证 n 为 2 的幂的话，那么当 n - 1 为偶数时，那么 hash & (n -1) 一定为偶数，导致 HashMap 的空间浪费了一半。
put 方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
// key 为 null 时，返回0
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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) //如果当前链表长度到达8的时候，就会变成红黑二叉树
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); // LinkedList 中会实现这个方法
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
可以看出，当 key 为 null 时，hash(key) 为 0，即 (n-1) & hash 为0，那么当 key 为空时，会放到 table[0] 中，多次插入空 key 的值的时候，仅会将 tab[0] 的 value 替换。
