HashMap 整体设计（1.8）
HashMap 实现了 Map 接口，存储 key-value 的散列表。与 HashTable 类似相似，区别是：1.线程不安全；2.允许键或值为null。
HashMap 采用数组+链表/红黑树的结构存储，数组可以扩容，链表可以转化为红黑树。能提供常量时间性能的基本操作 get 和 put。迭代器遍历的效率与容量和存储kv数量有关。HashMap 不保证存入的kv的次序。
HashMap 属性
DEFAULT_INITIAL_CAPACITY 默认初始化容量（2^4=16）
MAXIMUM_CAPACITY 最大的容量（2^30）
DEFAULT_LOAD_FACTOR 默认的载入因子（0.75f）
TREEIFY_THRESHOLD 当桶上的结点数大于这个值时转红黑树（8）
UNTREEIFY_THRESHOLD 当桶上的结点数小于这个值时转为链表（6）
MIN_TREEIFY_CAPACITY 最小的容量（64），并且为了避免扩容和转换树的冲突，至少是4*TREEIFY_THRESHOLD
初始容量大小和载入因子会影响 HashMap 的性能。初始容量指的是桶的大小。载入因子是来衡量 HashMap 在其容量增加之前允许达到的完整度。当 HashMap 中的kev数量超过了载入因子和当前容量，HashMap 就会扩容（resize），新的 HashMap 桶的数量变为原来的两倍。
通常载入因子设置成0.75，超过这个值会减少空间开销，但是会增加查询开销。设置初始容量的时候需要考虑 HashMap 将容纳的数量和载入因子，这样可以减少 resize 次数。
HashMap 在JDK8与JDK7实现上最大的不同在于，当桶上结点的数量过大的时候，会将结构改变成树结构。树结构在数量过多的时候查找效率会得到提升。
HashMap 构造函数
public HashMap(int initialCapacity, float loadFactor) {
// ... 检查 initialCapacity 和 loadFactor
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
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;
}
tableSizeFor(initialCapacity) 返回大于等于初始容量的的最小的二次幂数值，作为判断 resize 的阈值。
从构造函数可以看出，这时候并没有初始化哈希表（Node<K,V>[] table）。和JDK7的操作就不一样，其在构造方法中就初始化了哈希表。
另外一个重要的构造函数
transient Node<K,V>[] table;
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
// 将m的所有元素存入当前 HashMap 实例中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
其中 Node<K,V>[] table 是存储kv的结构，是一个 Node<K,V> 数组。
哈希桶
HashMap 采用哈希表存储数据，使用拉链法（链地址法）解决哈希值冲突，即每个哈希值对应存储一个链表。Node<K,V> 对象就是链表的实现。
static class Node<K,V> implements Map.Entry<K,V> {
// 键的哈希值，定位在Node[]中的位置
final int hash;
final K key;
V value;
// 桶是一个链表，表示当前结点所在链表的下一个结点
Node<K,V> next;
// ...
}
HashMap Get 方法
首先计算出 key 的 hashCode，找到 table 中的数组索引，即 Node<K, V> 对象，如果存在并且判断该结点是否等于要查询的节点，如果不是，按照链表或者红黑树的查询方式查找。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 判断 table 是否存在，hashCode 所在的索引是有为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 查询 key，先查询第一个，然后在查询 Node
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
(n - 1) & hash 得到哈希值对应 table 的索引。如果桶是由树组成，Node 是子类 TreeNode 实现的。
HashMap Put 方法
put 相比 get 更复杂，会涉及到 table 的 resize 和 treeify。首先判断 table 是否存在，不存在就创建。
判断 hashCode 对应位置是否有值，没有值就直接存入。存在就判断这第一个键是否相等，最后才根据 onlyIfAbsent（是否覆盖）来决定是否更新 value。如果第一个不相同，根据链表或者树的对应插入方法插入或更新（如果 key 存在，根据 onlyIfAbsent 判断）。
如果插入数据成功并且 Node 是链表，判断当前数量是否达到转换成树结构的阈值（TREEIFY_THRESHOLD），进行对应操作。最后再判断哈希表是否需要扩容。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 初始化 table
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;
// 先判断 Node 一个元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// 使用 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) // -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;
}
其中 modCount 介绍过，记录 HashMap 内部结构发生变化的次数，主要用于 fast-fail 机制。但是 key 值对应的 value 被更新不会计数 modCount。
Treeify
链表转换为树结构，当该链表的长度超过8时执行。（扩展：为什么Map桶中个数超过8才转为红黑树?）
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
// Node 转换 TreeNode
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 把转换后的 TreeNode，替换原来位置上的 Node
// 此时 TreeNode 还是双向链表的结构
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
如果 table 大小小于 MIN_TREEIFY_CAPACITY（树结构化的最小限制），不需要转换，table 需要 resize。当 table 某个位置上集中了多个键值对，是因为这些 key 的 hashCode 和数组长度取模之后结果相同（并不是因为这些 key 的 hashCode 相同，hashCode 相同的概率比较低），所以可能是 table 数组的数量比较小造成的，可以通过扩容的方式，使得这些 key 分散到多个数组位置上。
treeify 方法
遍历双向链表，转换为红黑树结构。
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
Resize
每次 resize，新的数组是原数组大小的两倍。resize 过程：
- 初始化过程，包括 oldTab（原表），oldCap（原表长度），newCap（新表长度）和 newThr（新表扩容阈值）。
- 根据计算出来的新表大小生成新表 newTab
- 如果 oldTab 不为空，遍历 oldTab 的每个桶，放入 newTab。
- 返回 newTab。
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)
newCap = oldThr;
else {
// 使用默认容量（16）
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;
// 创建新的表，并且覆盖 table
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 遍历 oldTable 的每个桶
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 如果桶中只有一个元素，直接放入 newTab
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 如果桶中是 TreeNode
// 将树的数据重新散列到 newTab 中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 如果桶中是链表 Node
// 这里就解释了为什么要扩容为两倍
// 扩容两倍之后，数据在新桶中的位置只有两个 lo 和 hi
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;
}
// 新桶中位置为 old + oldCap
else {
// 逻辑与上面相同
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 转换为两个新的链表（或一个），放入 newTab
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
在扩容开始的时候，table 就被覆盖为 newTab（空的扩容后大小），如果自此有 put 方法调用，会写入新的空的 table，不会写入 oldTab。
为什么扩容两倍？
更加容易计算他们所在的新桶位置。如原桶长度是4，现在桶长度是8，那么：桶0中的元素会被分到桶0和桶4中，桶1中的元素会被分到桶1和桶5中，以此类推。
oldCap 假如是16（二进制为10000），扩容变成32（二进制为100000）。当 hashCode & 10000 ==0，那么 hashCode 的右起第五位肯定也是0，所以 hashCode & 100000 还是0，反之亦然。
与 JDK7 的区别
JDK7 的实现
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 创建一个新的 Entry 数组
Entry[] newTable = new Entry[newCapacity];
// 将数据转移到新的 Entry 数组里
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 覆盖 table 和 threshold
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 重点全在这个函数中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 元素在新数组中的位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
函数 transfer() 是优化前的链表重新散列，也是导致 HashMap 死锁问题的关键：
- 对原数组中的元素遍历，并计算出元素 e 在新数组中的位置 i
- e 放入新数组 i 对应链表 Entry 的头部，因为 Entry 可能有元素存在，所以先将 e.next 指向 Entry 第一个元素（如果 Entry 是空，则 e.next = null)，这时候 Entry 第一个元素是 e，newTable[i] 指向的是原 Entry 的第一个元素，所以设置 newTable[i] = e
- 循环2，直到链表节点全部转移
- 循环1，直到所有索引数组全部转移
在多线程场景下会出现同时 put 操作，并进入了 transfer。假设现在有三个线程：T1、T2， oldTable[i]=A，newTable[i]=B（B.next=C），A在 newTable 的位置还是i，当前e引用A。
当T1运行到 e.next=newTable[i] 时，T2运行到 Entry<K,V> next = e.next。
T1运行 newTable[i]=e, e=next，会产生的结果：newTable[i]=A，A.next=B，B.next=C，e=B。
T2运行 e.next=newTable[i]，会产生的结果：B.next=A，同时 A.next=B，
JDK8 改进算法后不会再出现环状链表的情况，但并发时仍然不建议使用 HashMap。
网友评论