剖析 JDK源码：HashMap 1.8版本详解
摘要
上一篇博文，分享了HashMap1.7版本的底层实现；本篇文章将继续带着小伙伴们探索HashMap1.8的底层原理；JDK1.8中对HashMap的底层数据结构进行了优化，它不再是之前的"数组+链表"的方式，而是"数组+链表+红黑树"的方式来实现；由于，此序列博文主要主要内容是关于源码分析，所以文章中关于数据结构方面的知识会比较简略提到。更详细的数据结构方面的知识，博主将会在后期的专题栏目中进行分享。
数据结构-树简介
树：定义树的一种自然方式是递归方式。一棵树是一些节点的集合。这个集合可以空集；若不是空集，则树由称作根的节点r以及0个或多个非空的子树T1、T2、T3...,Tn组成，这些子树中每一棵的根都被来自根r的一条有向边所连接。
树按照分叉来分，有两种：
二叉树：是一棵树，其中每个节点都不能有多于两个的儿子。二叉树的一个性质是一棵平均二叉树的深度要比节点个数N小得多，这个性质很重要。分析表明 ，其平均深度为O（根号N），而对于特殊类型的二叉树，即二叉查找树，其深度的平均值时O（logN）。不幸的是，这个深度是可以大道N-1的（此时，树已经退化为链表结构）。
多叉树：是一棵树，其中每个节点可以有多个儿子。
二叉查找树：使二叉树成为二叉查找树的性质是，对于树中的每个节点X，它的左子树中的所有项的值小于X中的项，它的右子树中的所有项的值大于X中的项。另外，二叉查找树要求所有的项都能够排序。需要说明的是，二叉查找树在经过长时间的添加、删除等操作后，可能变得不平衡，或者说它的某些分支相对于其它一些分支会变得非常的深（此处，与它的删除算法有关，一般删除一个节点的时候，如果它有右子树，则使用右子树中最小的节点来替代该节点）。当然，除了上面这种由实现引起的情况；还有就是当我们项二叉树添加一连串的排好序的数据，也会造成树的深度问题。
平衡二叉树（AVL): AVL 树是带有平衡条件的二叉树。一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树（空树的高度定义为-1）。
伸展树：它保证从空树开始连续M次对树的操作最多花费O（MlogN）时间。虽然这种保证并不排除任意单次操作花费O（N）时间的可能，而且这样的界也不如每次操作最坏情形的界为O（logN）那么强，但是时间效果却是医院的：不存在坏的输入序列。
红黑树：一种比较流行的AVL树的变种树。对红黑树的操作在最坏的情形下花费O（logN）时间，而且我们将看到，（对于插入操作的）一种审慎的非递归实现可以相对容易的完成（与AVL树相比）
红黑树是具有下列着色性质的二叉查找树：
1、每一个节点或者着成红色，或者着成黑色。
2、根式黑色的。
3、如果一个节点是红色的，那么它的子节点必须是黑色的。
4、从一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点。
着色法则的一个结论是，红黑树的高度最多是2log(N+1)。红黑树的优点是执行插入所需要的开销相对较低，另外就是实践中发生的旋转相对较少。
B(B-)树：是一种多路搜索树。1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
一、根结点至少有两个子女；
二、每一个非根节点所包含的关键字个数 j 满足：m/2 - 1 <= j <= m - 1；（向上取整）
三、除根结点之外的全部结点（不包括叶子结点）的个数正好是关键字总数加1，故内部子树个数 k 满足：m/2<= k <= m ；
四、全部的叶子结点都位于同一层。
B+树： B+树是应文件系统所需而出的一种B-树的变型树，这种树主要用在数据库索引中。一棵m阶的B+树和m阶的B-树的差别在于：
- 有n棵子树的结点中含有n个关键字，每一个关键字不保存数据，只用来索引，全部数据都保存在叶子节点。
- 全部的叶子结点中包含了所有关键字的信息，及指向含这些关键字记录的指针，且叶子结点自己依关键字的大小自小而大顺序连接。
- 全部的非终端结点能够当作是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。一般在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。
B*树：是B+树的变体，在B+树的非根和非叶子结点再增长指向兄弟的指针；B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3.
跳跃表(Skip List)：增加了向前指针的链表叫做指针。跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质是一种可以进行二分查找的有序链表。跳表在原有的有序链表上增加了多级索引，通过索引来实现快速查询。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。
应用场景：节点增加和更新比较少，查询频次较多的情况。
使用跳跃表的产品：
1、Lucene, elasticSearch
2、Redis：
Redis sorted set的内部使用HashMap和跳跃表(SkipList)来保证数据的存储和有序，HashMap里放的是成员到score的映射，而跳跃表里存放的 是所有的成员，排序依据是HashMap里存的score,使用跳跃表的结构可以获得比较高的查找效率，并且在实现上比较简单。
源码解析
这个map通常充当一个binned (bucketed)哈希表，但是当容器变得太大时，它们将被转换为TreeNodes的容器，每个容器的结构与java.util.TreeMap中的容器类似。 大多数方法尝试使用普通bins，但在适用的情况下传递到TreeNode方法(简单地通过检查节点的实例)。 TreeNodes的Bins可以像其他Bins一样遍历和使用，但在填充过多时还支持更快的查找。 然而，由于在正常使用中绝大多数的容器都没有被过度填充，所以在表方法过程中检查树容器是否存在可能会被延迟。
树容器(即，其元素都是TreeNodes的容器)主要由hashCode排序，但在纽带的情况下，如果两个元素是相同的“class C implements Comparable<C>”，类型则使用它们的compareTo方法进行排序。 (我们通过反射保守地检查泛型类型来验证这一点——参见方法comparableClassFor)。 当键具有不同的哈希值或可排序时，树容器增加的复杂性对于提供最坏情况下的O(log n)操作是值得的。因此，在偶然或恶意的用法下，性能会优雅地下降，其中hashCode()方法返回的值分布很差，以及许多键共享一个hashCode，只要它们也是Comparable。 (如果两者都不适用，与不采取预防措施相比，我们可能会浪费大约两倍的时间和空间。 但是，唯一已知的案例来自于糟糕的用户编程实践，它们已经如此缓慢，以至于没有什么区别。)
因为TreeNodes的大小大约是常规节点的两倍，所以我们只在容器包含足够的节点时才使用它们(参见TREEIFY_THRESHOLD)。 当它们变得太小时(由于移除或调整大小)，它们会被转换回普通bins。 在使用良好分布的用户hashCodes时，很少使用树容器。
树的根通常是它的第一个节点。 然而，有时(目前仅在Iterator.remove上)，根可能在其他地方，但可以在父链接之后恢复(方法TreeNode.root())。
当bin列表被树形化、拆分或未拆分时，我们将它们保持在相同的相对访问/遍历顺序(即字段Node.next)，以更好地保留局部性，并略微简化调用iterator.remove的拆分和遍历的处理。 当在插入中使用比较器时，为了在重新平衡中保持总排序(或尽可能接近)，我们比较类和identityHashCodes作为tie-breakers。
由于子类LinkedHashMap的存在，普通模式和树模式之间的使用和转换变得复杂。 请参阅下面定义的在插入、删除和访问时调用的钩子方法，这些方法允许LinkedHashMap内部保持独立于这些机制。 (这还需要将一个map实例传递给可能创建新节点的一些实用程序方法。)
(1)、类定义
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{
...
}
与JDK1.7定义一样，HashMap 继承了 AbstractMap，实现 Map、Cloneable、Serializable 接口。
(2)、HashMap 变量
/**
* 默认初始容量—必须是2的幂。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量，如果一个较大的值由带参数的构造函数中的任何一个隐式指定，则使用该值。 必须是2的幂<= 1<<30。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 在构造函数中没有指定时使用的负载因子。
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 使用树而不是列表的桶计数阈值。 当将元素添加到至少有这么多节点的bin中时，bin将被转换为树。 该值必须大于2且至少为8，
* 以便与树移除中关于收缩时转换回普通bins的假设相匹配
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 在调整大小操作期间取消(拆分)bin树化的bin计数阈值。 应该小于TREEIFY_THRESHOLD，并且在去除收缩检测时最多6个网格。
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 可将容器树形化的最小表容量。 (否则，如果一个bin中有太多的节点，表将被调整大小。) 应至少为4 * TREEIFY_THRESHOLD，
* 以避免调整大小和树化阈值之间的冲突。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 表，在第一次使用时初始化，并根据需要调整大小。 在分配时，长度总是2的幂。 (我们也允许在某些操作中长度为零，以允许当前不需要的引导机制。)
*/
transient Node<K,V>[] table;
/**
* 保存缓存entrySet()。 注意，AbstractMap字段用于keySet()和values()。
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* 此映射中包含的键值映射的数量。
*/
transient int size;
/**
* 结构化修改指的是改变HashMap中映射的数量或修改其内部结构(如rehash)。 该字段用于使HashMap的集合视图上的迭代器快速失败。
* (见ConcurrentModificationException)。
*/
transient int modCount;
/**
* 要调整大小的下一个大小值(容量*负载因子)。
*/
int threshold;
/**
* 哈希表的负载因子。
*/
final float loadFactor;
(3)、HashMap 构造
/**
* 使用指定的初始容量和加载因子构造一个空的HashMap。
*/
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);
}
/**
* 构造一个空的HashMap，使用指定的初始容量和默认的负载因子(0.75)。
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 构造一个空的HashMap，使用默认的初始容量(16)和默认的负载因子(0.75)。
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* 构造一个新的HashMap，具有与指定的Map相同的映射。
* 创建HashMap时使用默认负载因子(0.75)和足够容纳指定Map中的映射的初始容量。
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 实现 Map.putAll and Map constructor
*
* @param m the map
* @param evict 在最初构造此映射时为false，否则为true(转发给afternodeinsert方法)。
*/
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);
}
}
}
(4)、静态内部类 Node
/**
* 基本哈希bin节点，用于大多数条目。 (参见下面的TreeNode子类，以及它的Entry子类的LinkedHashMap。)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//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;
}
}
(5)、静态内部类 TreeNode
红黑树
/**
* 树容器的条目。 LinkedHashMap延伸。 条目(它扩展了Node)，因此可以用作常规或链接节点的扩展。
*/
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);
}
.....
}
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
(6)、 put(K key, V value)
/**
* 将指定值与此映射中的指定键关联。 如果映射之前包含键的映射，则替换旧值。
* @return 前一个与键关联的值，或null(如果键没有映射的话)。 (一个null返回也可以表示先前关联null与键的映射。)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 实现 Map.put 和相关 方法
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//tab赋值，如果当前tab为null，则resize()初始化tab; n赋值为tab.length
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果根据hash定位到的hash表槽位为空，则直接新建一个节点并赋值给此槽位
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//当前槽位非空，并且key匹配的话，则表示当前已存在该key的映射
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//当前槽位的节点类型为TreeNode，则将键值对存入红黑树
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);
//如果达到链表转换红黑树的长度阈值8，则根据情况进行表扩容或者将当前链表转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果链表中已存在该key的映射，跳出循环进行下面的value替换逻辑
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = 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;
}
}
++modCount;
//如果size达到达到扩容阈值，则进行扩容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* 替换桶中所有的链接节点在给定的哈希索引，除非表太小，在这种情况下，调整大小代替。
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//hash表长度小于64的时候，直接使用扩容
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);
}
}
由上面的源码，可以得到如下put逻辑：
- 1、首先，根据hash定位哈希表的槽位(桶);
- 2、如果当前桶为空，则直接新建节点插入，最后判断是否哈希表是达阈值需要进行扩容
- 3、当前槽位非空，并且槽位第一个Node节点key匹配上的话，则表示当前已存在该key的映射，进行value替换即可
- 4、当前槽位的第一个节点类型为TreeNode，则将键值对存入红黑树
- 5、否则，遍历该槽位的链表，如果存在该key，则替换value
- 6、继续第五步，如果链表不存在该key，则插入链表末端，最后判断如果链表长度达到链表转换阈值； 如果hash表长度小于64，则扩容；否则，将链表转为红黑树；最后判断是否哈希表是达阈值需要进行扩容
JDK1.8，HashMap扩容条件：
- 当hash表长度小于64时，如果键值对size达到阈值，则扩容；如果链表达到转树阈值8，则扩容
- 当hash表长度大于64是，如果键值对size达到阈值，则扩容；
(7)、get(Object key)
/**
* 返回指定键映射到的值，如果这个映射不包含该键的映射，则返回{@code null}。
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 实现 Map.get and 相关方法
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
// always check first node
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//第一个节点为TreeNode，则使用树查找并返回结果
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;
}
(9)、remove(Object key)
/**
* 如果存在，则从该映射中移除指定键的映射。
*/
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* 实现 Map.remove 和相关方法
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//判断第一个节点是否为要删除的节点
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
//如果为TreeNode类型，则从树中查找节点
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//从链表中查找节点
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
//如果为TreeNode类型，则调用树删除节点
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//删除链表节点
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
上面代码中，通过removeTreeNode方法删除节点时，会判断如果树的size大小<=阈值6，则红黑树重新转为链表
最后总结：HashMap1.8的整个主要方法逻辑还是比较清晰的，JDK1.7相比，它的底层数据结构，增加了红黑树相关的逻辑；由于红黑树的查找性能O(logN)，比链表快很多；所以，当hash冲突较多的情况下，1.8的性能会有显著提高。另外，由于红黑树相关添加，以及删除等逻辑比较复杂，其中涉及到各种旋转以及着色的改变等操作，所以本篇博文未对这块进行深入分析；在后续的数据结构专题中，博主将继续将红黑树具体的实现内容为大家详细分析！