共计 8409 个字符，预计需要花费 22 分钟才能阅读完成。
00 HashMap 的底层数据结构
在 JDK 1.7 中 HashMap 是以 数组加链表 的模式组成的，JDK 1.8 之后新增了 红黑树 的组成构造，当链表长度大于 8 并且 hash 桶的容量大于 64 时，链表构造会转换成红黑树结构。所以，它的组成构造如下图所示：
HashMap 中数组的每一个元素又称为哈希桶，也就是 key-value 这样的实例。在 Java7 中叫 Entry，Java8 中叫 Node。
因为它自身所有的地位都为 null，在 put 插入的时候会依据 key 的 hash 去计算一个 index 值。比方，我 put（” 狗哥 “，666），在 HashMap 中插入 “ 狗哥 ” 这个元素，通过 hash 算法算出 index 地位是 3。这时的构造如下所示，还是个数组。
以上没 hash 抵触时，若产生 hash 抵触就得引入链表啦。假如我再次 put（” 阿狗 “，666），在 HashMap 中插入 “ 阿狗 ” 这个元素，通过 hash 算法算出 index 地位也是 3。这时的构造如下所示：造成了链表。
它的源码如下所示：能够看出每个哈希桶中蕴含了四个字段：hash、key、value、next，其中 next 示意链表的下一个节点。
static class Node < K, V > implements Map.Entry < K, V > {
final int hash;
final K key;
V value;
Node < K,
V > next;
...
}JDK 1.8 之所以增加红黑树是因为一旦链表过长，会重大影响 HashMap 的性能，而红黑树具备疾速增删改查的特点，这样就能够无效的解决链表过长时操作比较慢的问题。
01 HashMap 的重要办法
PS：以下源码剖析全副基于 JDK1.8 版本。
1.0 查问（get 办法）
源码如下：
public V get(Object key) {
Node < K, V > e;
// 对 key 进行哈希操作
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;
// 非空判断
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) {
// 如果第一节点是树结构，则应用 getTreeNode 间接获取相应的数据
if (first instanceof TreeNode)
return ((TreeNode < K, V >) first).getTreeNode(hash, key);
do { // 非树结构，循环节点判断
// hash 相等并且 key 雷同，则返回此节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}代码正文曾经很具体，强调一点：当哈希抵触时咱们不仅须要判断 hash 值，还须要通过判断 key 值是否相等，能力确认此元素是不是咱们想要的元素。
1.1 新增（put 办法）
源码如下：
public V put(K key, V value) {
// 对 key 进行哈希操作
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)
n = (tab = resize()).length;
// 依据 key 的哈希值计算出要插入的数组索引 i
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果 table[i] 等于 null，则直接插入
tab[i] = newNode(hash, key, value, null);
else {
Node < K, V > e;
K k;
// 如果 key 曾经存在了，间接笼罩 value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果 key 不存在，判断是否为红黑树
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) // -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;
}
}
// existing mapping for key
if (e != null) {
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.2 扩容（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;
}
// 扩充容量为以后容量的两倍，但不能超过 MAXIMUM_CAPACITY
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 以后数组没有数据，应用初始化的值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 如果初始化的值为 0，则应用默认的初始化容量
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的容量等于 0
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
table = newTab;
// 原数据不为空，将原数据复制到新 table 中
if (oldTab != null) {
// 依据容量循环数组，复制非空元素到新 table
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
// 链表复制，JDK 1.8 扩容优化局部
// 如果节点不为空，且为单链表，则将原数组中单链表元素进行拆分
Node < K, V > loHead = null, loTail = null;// 保留在原有索引的链表
Node < K, V > hiHead = null, hiTail = null;// 保留在新索引的链表
Node < K, V > next;
do {
next = e.next;
// 哈希值和原数组长度进行 & 操作，为 0 则在原数组的索引地位
if ((e.hash & oldCap) == 0) {if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
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;
}
// 将原索引 + oldCap 放到哈希桶中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}从以上源码能够看出，扩容次要分两步：
- 扩容：创立一个新的 Entry 空数组，长度是原数组的 2 倍。
- 位运算：原来的元素哈希值和原数组长度进行 & 运算。
JDK 1.8 在扩容时并没有像 JDK 1.7 那样，从新计算每个元素的哈希值，而是通过高位运算（e.hash & oldCap）来确定元素是否须要挪动，假如 key1 的信息如下：
- key1.hash = 10；二进制：0000 1010
- oldCap = 16；二进制：0001 0000
应用 e.hash & oldCap 失去的后果，高一位为 0，当后果为 0 时示意元素在扩容时地位不会产生任何变动，而假如 key 2 信息如下：
- key2.hash = 17；二进制：0001 0001
- oldCap = 16；二进制：0001 0000
这时候失去的后果，高一位为 1，当后果为 1 时，示意元素在扩容时地位产生了变动，新的下标地位等于原下标地位 + 原数组长度，如下图所示：key2、kry4 虚线为挪动的地位。
02 HashMap 有哪些属性？
如下，看代码正文，写的很分明了。
// HashMap 初始化长度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// HashMap 最大长度
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824
// 默认的加载因子 (扩容因子)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当链表长度大于此值且数组长度大于 64 时，会从链表转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 转换链表的临界值，当元素小于此值时，会将红黑树结构转换成链表构造
static final int UNTREEIFY_THRESHOLD = 6;
// 最小树容量
static final int MIN_TREEIFY_CAPACITY = 64;03 为什么 HashMap 的初始化长度是 16？
后面说过，从 Key 映射到 HashMap 数组的对应地位，会用到一个 Hash 函数，比方：index = Hash(“ 狗哥 ”)
留神到 HashMap 初始化长度用的是 1<<4，而不是间接写 16。这是为啥呢？其实这样是为了位运算的不便，位与运算比算数计算的效率高太多了，之所以抉择 16，是为了服务将 Key 映射到 index 的算法。
那如何实现一个尽量均匀分布的 Hash 函数呢？从而缩小 HashMap 碰撞呢？没错，就是通过 Key 的 HashCode 值来做位运算。
有公式（Length 是 HashMap 的长度）：HashCode（Key）&（Length- 1）
我举个例子，key 为 “book” 的十进制为 3029737 那二进制就是 101110001110101110 1001
HashMap 长度是默认的 16，length – 1 的后果。十进制 : 15；二进制 : 1111
把以上两个后果做与运算：101110001110101110 1001 & 1111 = 1001；1001 的十进制 = 9, 所以 index=9。
也就是说：hash 算法最终失去的 index 后果，取决于 hashcode 值的最初几位
你能够试试把长度指定为 10 以及其余非 2 次幂的数字，做位运算。发现 index 呈现雷同的概率大大升高。而长度 16 或者其余 2 的幂，length – 1 的值是所有二进制位全为 1, 这种状况下，index 的后果等同于 hashcode 后几位的值，只有输出的 hashcode 自身散布平均，hash 算法的后果就是平均的
所以，HashMap 的默认长度为 16，是为了升高 hash 碰撞的几率。
04 为什么树化是 8，退树化是 6？
红黑树均匀查找长度为 log(n)，长度为 8 时，查找长度为 3，而链表均匀查找长度为 n/2；也就是 8 除以 2；查找长度链表大于树，转化为树，效率更高。
当为 6 时，树：2.6；链表：3。链表 > 树。这时理当也还是树化，然而树化须要工夫，为了这点效率就义工夫是不划算的。
05 什么是加载因子？加载因子为什么是 0.75？
后面说了扩容机制。那什么时候扩容呢？这就取决于原数组长度和加载因子两个因素了。
加载因子也叫扩容因子或负载因子，用来判断什么时候进行扩容的，如果加载因子是 0.5，HashMap 的初始化容量是 16，那么当 HashMap 中有 16*0.5=8 个元素时，HashMap 就会进行扩容。
那加载因子为什么是 0.75 而不是 0.5 或者 1.0 呢？这其实是出于容量和性能之间均衡的后果：
- 下面说到，为了晋升扩容效率，HashMap 的容量（capacity）有一个固定的要求，那就是肯定是 2 的幂。所以，如果负载因子是 3/4 的话，那么和 capacity 的乘积后果就能够是一个整数
- 当加载因子设置较大时，扩容门槛进步，扩容产生频率低，占用的空间小，但此时产生 Hash 抵触的几率就会晋升，因而须要更简单的数据结构来存储元素，这样对元素的操作工夫就会减少，运行效率也会升高；
- 当加载因子设置较小时，扩容门槛升高，会占用更多的空间，此时元素的存储就比拟稠密，产生哈希抵触的可能性就比拟小，因而操作性能会比拟高。
所以综合了以上状况就取了一个 0.5 到 1.0 的平均数 0.75 作为加载因子。
06 HashMap 是线程平安的么？
不是，因为 get 和 put 办法都没有上锁。多线程操作无奈保障：此刻 put 的值，片刻后 get 还是雷同的值，会造成线程平安问题。
还有个 HashTable 是线程平安的，然而加锁的粒度太大。并发度很低，最多同时容许一个线程拜访，性能不高。个别咱们应用 currentHashMap，当然啦，前面会聊到它的。
07 为什么重写 equals 办法的时，须要重写 hashCode 办法呢？
Java 中，所有的对象都是继承于 Object 类。Ojbect 类中有两个办法 equals、hashCode，这两个办法都是用来比拟两个对象是否相等的。
先来看看 equals 办法：
public boolean equals(Object obj) {return (this == obj);
}在未重写 equals 办法，他其实就是 ==。有以下两个特点：
- 对于值对象，== 比拟的是两个对象的值
- 对于援用对象，== 比拟的是两个对象的地址
看回 put 办法的源码：HashMap 是通过 key 的 hashcode 去寻找地址 index 的。如果 index 一样就会造成链表，也即是 ” 狗哥 ” 和 ” 阿狗 ” 是有可能在同一个地位上。
后面的 get 办法说过：当哈希抵触时咱们不仅须要判断 hash 值，还须要通过判断 key 值是否相等，能力确认此元素是不是咱们想要的元素 。咱们去 get 首先是找到 hash 值一样的，那怎么晓得你想要的是那个对象呢？ 没错，就是利用 equals 办法，如果重写 hashCode 办法，不写 equals 办法，当产生 hash 抵触，hashcode 一样时，就不晓得取哪个对象了。
08 HashMap 死循环剖析
以下代码基于 JDK1.7 剖析。这个问题，次要是 JDK1.7 的链表尾插法造成的。假如 HashMap 默认大小为 2，本来 HashMap 中没有一个元素。应用三个线程：t1、t2、t3 增加元素 key1，key2，key3。我在扩容之前打了个断点，让三个线程都停在这里。源码如下：
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;
}
}
}假如 3 个元素 hash 抵触，放到同一个链表上。其中 key1→key2→key3 这样的程序。没故障，所有很失常。
此时放开断点，HashMap 扩容。就有可能变成这样：原来是 key1→key2→key3。很可怜扩容之后，key1 和 key2 还是在同一个地位，这时造成链表，如果 key2 比 key1 前面插入，依据头插法。此时就变成 key2→key1
最终 3 个线程都调整结束，就会呈现下图所示的死循环：这个时候 get(key1) 就会呈现 Infinite Loop 异样。
当然产生死循环的起因是 JDK 1.7 链表插入方式为首部倒序插入，这种形式在扩容时会扭转链表节点之间的程序。这个问题在 JDK 1.8 失去了改善，变成了尾部正序插入，在扩容时会放弃链表元素本来的程序，就不会呈现链表成环的问题。
09 总结
HashMap 是 Java 根底中的重点。能够说无论是在工作中还是面试中都很罕用，小伙伴们必须做到纯熟使用、信手拈来才算是过关的。本篇文章根本说到了 HashMap 的所有重点，红黑树没有开展说，次要是因为篇幅起因，前面会独自聊。另外，如果发现本文有啥谬误，欢送友善斧正。
好啦，以上就是狗哥对于 HashMap 源码的解读。感激各技术社区大佬们的付出，尤其是极客工夫，真的牛逼。如果说我看得更远，那是因为我站在你们的肩膀上。心愿这篇文章对你有帮忙，咱们下篇文章见~
10 伟人的肩膀
- https://kaiwu.lagou.com/cours…
11 送点面试题 & 电子书
如果看到这里，喜爱这篇文章的话，请帮点个 难看。
初次见面，也不晓得送你们啥。罗唆就送 几百本电子书 和2021 最新面试材料 吧。微信搜寻 一个优良的废人 回复 电子书 送你 1000+ 本编程电子书；回复 面试 送点面试题；回复 1024 送你一套残缺的 java 视频教程。
面试题都是有答案的，如下所示：有须要的就来拿吧，相对收费，无套路获取。
