HashMap源码剖析
HashMap是大家常用的基于哈希表的Map接口实现,这里解说的是JDK1.8的代码,在介绍它之前，我们先来看看编写HashMap代码的是哪几位大牛。
Doug Lea
就是这位鼻梁挂着眼镜，留着德王威廉二世的胡子的人。
他是JCP (Java社区项目)中的一员 由JDK 1.1到JDK 1.2的很重要的一项新创举就是Collections，其Collection的概念可以说承袭自Doug Lea于1995年发布的第一个被广泛应用的collections；2004年所推出的Tiger广纳了15项JSRs(Java Specification Requests)的语法及标准，其中一项JSR-166是来自于Doug编写的util.concurrent包。
Josh Bloch
别的不提，《Effective Java》作者这一身份就可以让你记得他。
Arthur van Hoff
公司首席技术官、创始人、临时CEO。
Neal Gafter
与Josh Bloch联合编著《Java解惑》一书。
注释中HashMap的简明介绍
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
在此，它与HashTable作了比较，主要有两个区别
1、HashMap是不同步的 如果多个线程并发访问一个哈希map，并且至少有一个线程对Map进行结构性修改，则必须在外部对其进行同步(结构性修改是指增加或删除一个或多个映射的操作;仅仅更改已经包含的键关联的值并不是结构性修改),即可以使用Collections.synchronizedMap包装。这最好在创建时完成，以防止意外的非同步访问:
Map m = Collections.synchronizedMap(new HashMap(...));
2、HashMap允许null值和null键
还介绍了其他需要注意的特性，即HashMap不保证Map的顺序(为基本操作get、put提供了稳定的时间性能，它假定散列函数将元素适当地分散到各个bucket中)、基本的数据结构等。
接着我们开始浏览下内部代码：
数据结构
为了方便后续理解，我们不得不先跳到HashMap数据结构相关的那段代码，了解下HashMap基本的数据结构：
transient Node<K,V>[] table;
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 K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
真的是数组链表结构，在首次使用时，数组即初始化，table中的每个元素即是一个链表(Node)。JDK8以后，为了更高效的检索，在链表节点数达到一定数量后，会转换为红黑树结构:
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
//代码量较多，此处省略
//......
}
TreeNode 继承了LinkedHashMap.Entry，这里代码较多，省略，有兴趣可以自己翻阅源码详细阅读。
图示:
(https://images.morethink.cn/b3e3671b2edf38a675b5a28587f37ae4.png)
类变量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
这是HashMap的默认初始容量，即创建时桶的个数，注释中说容量值必须是2的整数次幂
The default initial capacity - MUST be a power of two.
为什么是2的整数次幂?
1、这样可以通过hash&(length-1)的方法来代替取模，同样实现了均匀的散列，但效率要高很多。
2、 其次，length为2的整数次幂的话，为偶数，这样length-1为奇数，奇数的最后一位是1，这样便保证了hash&(length-1)的最后一位可能为0，也可能为1（这取决于hash的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样hash&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数标位置上，这便浪费了近一半的空间。另外,2的n次方能保证length-1的(n - 1)低位都是1，使hash低位的特征得以更好地保留,当hash低位相同时两个元素才能产生hash碰撞。因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。
在设置map的初始容量时，应该考虑map中条目期望数量及其负载因子，从而最小化rehash操作的数量。如果初始容量大于最大条目数除以负载因子的结果，则不会发生rehash操作。
static final int MAXIMUM_CAPACITY = 1 << 30;
最大容量，可以使用带有参数的构造函数自己重新指定。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认的负载因子。负载因子是度量哈希表数量达到多满时容量将自动扩容。当哈希表中的条目数超过负载因子和当前容量的乘积时，将对哈希表进行rehash(即重新构建内部数据结构)，使哈希表的桶数大约提高到原来的两倍。那为什么默认是0.75呢？一般来说，默认的负载因子(0.75)在时间和空间成本之间提供了很好的权衡。值取得高一点减少了空间开销，但增加了查找成本。想深入研究可以学习下泊松分布，0.75的碰撞最小。http://www.ruanyifeng.com/blog/2015/06/poisson-distribution.html#comment-356111
初始容量和负载因子是HashMap实例中两个影响其性能的重要参数。
集合视图迭代的时间与HashMap实例的“容量”(桶的数量)及其大小(键值对的数量)成比例.因此，如果迭代性能很重要，那么不要将初始容量设置得太高(或负载因子太低)。
static final int TREEIFY_THRESHOLD = 8;
树化阈值，若链表上节点超过TREEIFY_THRESHOLD - 1，即链表长度为8，将链表转变为红黑树
static final int UNTREEIFY_THRESHOLD = 6;
链表化阈值，当链表的节点个数小于等于解除树形化阀值UNTREEIFY_THRESHOLD时，将红黑树转为普通链表, 为什么上面两个阀值不一样呢？这里要解释下复杂度震荡的概念，假如TREEIFY_THRESHOLD为8，一个桶中链表长度为8时，此时继续向该桶中put会进行树化，然后remove又会链表化。如果反复put和remove,每次都会进行极其耗时的数据结构转换。
因此，推迟缩容的操作，将减少这种极端情况发生的概率
static final int MIN_TREEIFY_CAPACITY = 64;
对桶进行树化的最小容量。(如果小于这个容量，且桶中的节点超过树化阀值，就会进行扩容操作。)
实例变量
transient Node<K,V>[] table;
正是上面提到的数组链表数据结构中的数组。使用transient修饰，表示不能序列化，因为读写Map是根据Object.hashcode()来确定从哪个bucket读/写, 而Object.hashcode()是native方法, 不同的JVM里可能是不一样的。HashMap使用writeObject和readObject来实现自定义序列化，而不仅仅是让其字段正常序列化。它将桶的数量，总的容量和每个条目写入流，并在反序列化时从这些字段重建Map。table本身不需要序列化，节省空间。
transient Set<Map.Entry<K,V>> entrySet;
此map中包含的映射的Set视图，通过entrySet()获得。
transient int size;
此map中包含的键-值映射数量。
transient int modCount;
对该HashMap进行结构性修改的次数。此字段用于实现HashMap的集合视图迭代器的快速失败。
int threshold;
需要resize的下一个阀值(容量*负载因子)。
final float loadFactor;
哈希表的负载因子，默认是DEFAULT_LOAD_FACTOR，可通过构造函数指定。由于loadFactor不能改变，用final修饰。
构造函数
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);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
部分构造函数可以指定初始容量和负载因子。如果要将大量映射存储在HashMap实例中，那么用足够大的容量创建map比根据需要执行自动rehash扩展表能更有效地存储映射。这里请看第一个构造函数中的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;
}
如上所述,容量值必须是2的整数次幂,该方法将返回大于输入参数的最小的2的整数次幂(如不考虑最大容量限制的情况),如initialCapacity为7,则返回8,作为table数组的大小.
核心操作
接下来看下HashMap的两个核心操作:put和get。
put
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<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//case1:若table为null或者长度为0，则进行resize扩容操作,risize方法后续将介绍
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//case2:没有哈希冲突，则将值放入空桶中
tab[i] = newNode(hash, key, value, null);
else {
//case3:存在哈希冲突
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// case3.1：如果key已经存在，覆盖旧值
e = p;
else if (p instanceof TreeNode)
// case3.2：链表已转化为红黑树，加入红黑树
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// case3.3：节点加入链表尾部，如果超过阀值，则转化为红黑树
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;
}
}
//当key已经存在，执行覆盖旧值逻辑。
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;
}
关键方法进一步解析：
1、hash(key)：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这里为什么要将hashcode右位移16位。因为table使用2的整数次幂掩码，所以仅在当前掩码上方的位中变化的哈希集, 将发生冲突。因此，我们应用了一个转换，将高半区和低半区做异或,混合原始哈希码的高位和低位，以此来加大低位的随机性。
如果我们不做移位异或运算，那么在计算槽位时将丢失高区特征,当两个哈希码很接近时，就可能导致一次哈希碰撞。
2、
if ((p = tab[i = (n - 1) & hash]) == null)
//case2:没有哈希冲突，则将值放入空桶中
tab[i] = newNode(hash, key, value, null);
上面说了,使用了hash&(length-1)的方法来代替取模，同样实现了均匀的散列，但效率要高很多。
3、resize()
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; // double threshold
}
else if (oldThr > 0)
// 初始容量设置为阈值
newCap = oldThr;
else {
// 初始阈值为零表示使用默认值
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<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)
//只有一个元素，直接移到新的桶中,e.hash & (newCap - 1)计算桶新下标.
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//是树的情况
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//当前桶为链表,rehash
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//(e.hash & oldCap) == 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;
//元素依然在j位置,即oldIndex
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//元素移动到 oldIndex + oldCap 位置
newTab[ + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
如果table为null，则根据字段threshold中保持的初始容量值创建。如果不为null，因为我们根据2的整数次幂扩展，所以每个bin中的元素必须保持相同的索引，或者在新表中以2的整数次幂偏移,即原来桶中的元素将在新表的oldIndex或oldCap+oldIndex中。这样也尽量减少了rehash时元素位置的移动。
4、treeifyBin(tab, hash)
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;
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);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
如前述说明,假如桶数组长度小于MIN_TREEIFY_CAPACITY,则不会进行树化,而是扩容,树化本身就是耗时操作,这里是空间换时间的体现。
get：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//判断计算下标(n - 1) & hash
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash &&
((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;
}
迭代器遍历
HashMap所有“集合视图方法”返回的迭代器是快速失败的:在创建迭代器之后的任何时候，以任何方式(除了通过迭代器自己的remove方法)对map进行结构修改，迭代器将抛出ConcurrentModificationException异常。因此，在面对并发修改时，迭代器会快速失败，从而避免在将来某个不确定的时间发生任意的、不确定的行为风险。
注意迭代器的快速失败行为不能得到保证，因为一般来说，在存在非同步并发修改的情况下，不可能做出任何严格保证。快速迭代器在最大努力的基础上抛出ConcurrentModificationException。因此，期望依赖于这个异常编写正确的程序是不恰当的:迭代器的快速失败行为应该只用于检测bug。
后续内容计划
后面将继续剖析其他Java容器类。当然, HashMap也有很多特性值得思考,如JDK7中并发环境循环引用问题, 链表转红黑树的性能提升, hash算法过程的图解等等,后面也会继续拓展补充。