在看本文之前，强烈建议去读下我的上一篇文章HashMap的hash机制详解 ，有了这个基础后本文才更容易理解。
在分析源码之前，这里对整个HashMap机制大致做下介绍，HashMap还是基于hash表的数据结构，解决hash碰撞用的也是拉链法，不同的是，java8不只是一个简单的链表了，链表长度如果过长会变成红黑树。而且和普通固定大小的hash表不同，HashMap需要动态扩容。所以我们阅读源码时要重点关注：如何初始化，何时扩容，扩容时要考虑哪些，解决hash碰撞时何时变成红黑树，何时又会重新变成链表等等。
特殊属性
首先看下HashMap有哪些关键属性：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
/**
* 数组初始化大小为16
*/
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;
/**
*链表的长度超过这个值就会转换成红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
*红黑树的节点数量小于或等于这个值就要退化到链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
//真正存储的数据结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
//Hash表真正存储数据的数组
transient Node<K,V>[] table;
//如果总节点数量达到这个值就要扩容
int threshold;
}
初始化
public HashMap(int initialCapacity, float loadFactor) {
//此处省略一堆检查校验
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
//初始大小默认16，扩容因子为0.75
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
//默认0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
可以看到整个初始化其实就是确定两个值，初始容量以及扩容因子,另外计算了真正需要扩容的那个阈值：threshhold
这里大家注意，没有对数组table进行任何实例化操作，没有真正申请任何空间。
增加（碰撞解决）
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
这里首先是通过hash方法重新计算了key的hash值：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
至于这个方法为什么这么写，可以参考我的上一篇文章：HashMap的hash机制详解
然后就是真正的putVal()方法，由于方法本身比较长，这里不一次性贴出整个方法源码，我们一段一段来分析：
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;
//省略其他代码
}
这里首先判断了当前table数组是否为空，空了要去开始扩容，之所以要做这个判断是因为 上一步初始化时，HashMap并没有真正申请任何空间，所以这里是利用了扩容方法resize()顺带初始化table数组了。
*/
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);
//省略代码
}
这里大家注意i=(n-1)&hash的计算，这个就是根据hash值来确定当前value放置在table数组的哪个位置上，为什么这么算还是参考我的上篇文章：HashMap的hash机制详解。先判断目标位置有没有被之前的元素占用，如果没有直接放到该位置上，否者就是下面要开始处理hash碰撞了。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//此处省略代码
else {
Node<K,V> e; K k;
//此处的p就是产生hash碰撞位置的原有的数据，e用来存放被覆盖的数据
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 1
e = p;
else if (p instanceof TreeNode) // 2
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 3
//此处开始遍历链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null); //4
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//5
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) //6
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;
}
}
//此处省略代码
hash碰撞页分成好几种情况，
- key完全相同 ，这就是1号if对应的情况，key完全相同时，这里直接记录了原来的值，这里并没有直接覆盖
- key不同，但hash值相同，而且由于此处hash碰撞次数太多，处理碰撞的链表已经变成了红黑树，这是2号if对应的情况，这里直接将新的值插入到红黑树即可
- key不同，但hash值相同，而且目前处理hash碰撞还是链表形态，这里对应3好else情况，如果顺利的话直接遍历链表到尾节点，然后插入新的值（情况4），插入新值后如果链表长度达到了TREEIFY_THRESHOLD（8）就会开始转变成红黑树（情况5），以上是理想情况，但还有一种情况，如果和之前链表中某个节点的key相同呢（情况6）？ 这个时候就不用继续遍历链表了，此时的e就指向了那个相同key的节点。
上面我们处理了hash碰撞中key不相同的情况，现在看看key相同怎么处理的：
//此处的e就是key相同时的旧值，会被新的value替代
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
可以看到没有什么操作，只是在允许（HashMap可以设置不覆盖同key的旧值）的情况下直接覆盖旧值，并返回新值。
现在插入完成了，我们还需要判断是否需要扩容：
if (++size > threshold)
resize();
这里注意下，如果是同key的话，hashmap并没有使用新的空间，只是覆盖而已，上面已经直接return oldValue了，只有在插入了新的值的时候才会判断扩容。
扩容
在分析源码之前，大家先思考下：扩容到底扩的是哪部分？扩容时如果是table+链表的结构，扩容后链表怎么办？如果是红黑树呢？红黑树怎么办？
确定要扩多大
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 1
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) // 2 initial capacity was placed in threshold
newCap = oldThr;
else { // 3 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;
情况2是初始化时指定了threshold，这个情况比较少，我们重点关注情况3和情况1。
- 第一次扩容（情况3）
之前初始化时我们还记得那时只是简单的确定了初始容量和扩容因子，具体空间没有申请，我们第一次put的时候就会触发这个扩容机制，进入到情况3中来。 - 后续扩容（情况1）
后续正常扩容一般都会进入情况1，超过最大MAXIMUM_CAPAXITY的情况也比较少，所以一般都会走
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
这样容量翻倍，扩容threshold也翻倍。
申请新空间
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
这一步没什么，直接new了一个新的数组
原有数据迁移
接下来我们要将原来数组中的数据迁移到新的数组中来
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = 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);
这里对于红黑树的部分比较负责，本文就不做讲解，有兴趣的可以自己研究
- 碰撞后产生链表的元素
在看源码之前，我们先考虑一个问题：扩容后所有元素的位置都需要重新计算吗？我们举个例子说明：
原有容量为16，有两个元素hash值分别为 e1: 2, e2:18,
2 &（16-1） = 2；
18 &（16-1） = 2；
这两个元素都放置在位置2上，现在扩容一倍，两个元素如果重新计算位置的话
2 & (32 -1) = 2;
18 & (32 -1) = 18;
可以看到e1的位置还是不变的，e2的位置虽然变了，但只是在原有位置上增加了16而已，有了这个规律，我们就可以将链表上的元素分为两种，一种在新数组位置不变newTab[j]上，一种在新数组 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;
}
}
理解上面说的再看源码就很好理解了，就是将原本一条链表拆成了两条，一条放置在newTab[j]上，一条放置在newTab[j+oldCap]上。至于如何判断一个元素是否是在原位置还是在新位置上，这里用了一个位运算：
if ((e.hash & oldCap) == 0) {
如果等于0则在原位置，否则就要放置在新位置。
总结
到这里，hashmap基本就分析的差不多了，剩下的get，remove，update之类的操作也就没有必要再多说了，有了上面的基础一看就明白了，希望这篇文章对大家有帮助，如果有理解不到位的，也请各位指正。
网友评论