共计 5620 个字符，预计需要花费 15 分钟才能阅读完成。
HashMap 是一线资深 java 工程师必须要精通的汇合容器，它的重要性简直等同于 Volatile 在并发编程的重要性（可见性与有序性）。
本篇通过图文源码详解，深度分析 HashMap 的重要内核常识，易看易学易懂。倡议珍藏，多学一点总是好的，万一面试被问到了呢。
我是 Mike，10 余年 BAT 一线大厂架构技术倾囊相授 。 本篇重点：
- HashMap 的数据结构
- HashMap 核心成员
- HashMapd 的 Node 数组
- HashMap 的数据存储
- HashMap 的哈希函数
- 哈希抵触：链式哈希表
- HashMap 的 get 办法：哈希函数
- HashMap 的 put 办法
- 为什么槽位数必须应用 2^n？
HashMap 的数据结构
首先，咱们从数据结构的角度来看：HashMap 是: 数组 + 链表 + 红黑树（JDK1.8 减少了红黑树局部）的数据结构，如下所示:
这里须要搞明确两个问题：
* 数据底层具体存储的是什么？
这样的存储形式有什么长处呢？*
默认初始容量(数组默认大小):16，2 的整数次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
装载因子用来掂量 HashMap 满的水平，示意当 map 汇合中存储的数据达到以后数组大小的 75% 则须要进行扩容
链表转红黑树边界
static final int TREEIFY_THRESHOLD = 8;
红黑树转离链表边界
static final int UNTREEIFY_THRESHOLD = 6;
哈希桶数组
transient Node<K,V>[] table;
理论存储的元素个数
transient int size;
当 map 外面的数据大于这个 threshold 就会进行扩容
int threshold 阈值 = table.length * loadFactor2.Node 数组
从源码可知，HashMap 类中有一个十分重要的字段，就是 Node[] table，即哈希桶数组，显著它是一个 Node 的数组。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;// 用来定位数组索引地位
final K key;
V value;
Node<K,V> next;// 链表的下一个 Node 节点
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;
}
}Node 是 HashMap 的一个外部类，实现了 Map.Entry 接口，实质是就是一个映射(键值对)。
HashMap 的数据存储
1. 哈希表来存储
HashMap 采纳哈希表来存储数据。
哈希表（Hash table，也叫散列表），是依据关键码值 (Key value) 而间接进行拜访的数据结构，只有输出待查找的值即 key，即可查找到其对应的值。
哈希表其实就是数组的一种扩大，由数组演变而来。能够说，如果没有数组，就没有散列表。
2. 哈希函数
哈希表中元素是由哈希函数确定的, 将数据元素的关键字 Key 作为自变量，通过肯定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。
示意为：Addr = H（key）, 如下图所示：
哈希表中哈希函数的设计是相当重要的，这也是建哈希表过程中的关键问题之一。
3. 外围问题
建设一个哈希表之前，须要解决两个次要问题：
1) 结构一个适合的哈希函数, 平均性 H（key）的值均匀分布在哈希表中
2) 抵触的解决
抵触：在哈希表中，不同的关键字值对应到同一个存储地位的景象。
4. 哈希抵触：链式哈希表
哈希表为解决抵触，能够采纳地址法和链地址法等来解决问题，Java 中 HashMap 采纳了链地址法。
链地址法，简略来说，就是数组加链表的联合, 如下图所示：
HashMap 的哈希函数
/**
* 从新计算哈希值
*/
static final int hash(Object key) {
int h;
// h = key.hashCode() 为第一步 取 hashCode 值
// h ^ (h >>> 16) 为第二步 高位参加运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}// 计算数组槽位
(n - 1) & hash对 key 进行了 hashCode 运算，失去一个 32 位的 int 值 h, 而后用 h 异或 h>>>16 位。在 JDK1.8 的实现中，优化了高位运算的算法，通过 hashCode()的高 16 位异或低 16 位实现的：
(h = k.hashCode()) ^ (h >>> 16)。
这样做的益处是：
能够将 hashcode 高位和低位的值进行混合做异或运算，而且混合后，低位的信息中退出了高位的信息，这样高位的信息被变相的保留了下来。
等于说计算下标时把 hash 的高 16 位也参加进来了，掺杂的元素多了，那么生成的 hash 值的随机性会增大，缩小了 hash 碰撞。
备注：
- ^ 异或：不同为 1，雷同为 0
- >>>：无符号右移：左边补 0
- & 运算：两位同时为“1”，后果才为“1，否则为 0 h & (table.length -1)来失去该对象的保留位，而 HashMap 底层数组的长度总是 2 的 n 次方。
为什么槽位数必须应用 2^n
1. 为了让哈希后的后果更加平均
如果槽位数不是 16，而是 17，则槽位计算公式变成：(17 – 1) & hash
从上文能够看出，计算结果将会大大趋同，hashcode 加入 & 运算后被更多位的 0 屏蔽，计算结果只剩下两种 0 和 16，这对于 hashmap 来说是一种劫难。2. 等价于 length 取模
当 length 总是 2 的 n 次方时，h& (length-1)运算等价于对 length 取模，也就是 h%length，然而 & 比 % 具备更高的效率。
位运算的运算效率高于算术运算，起因是算术运算还是会被转化为位运算。
最终目标，还是为了让哈希后的后果更平均的分部，缩小哈希碰撞，晋升 hashmap 的运行效率。
剖析 HashMap 的 put 办法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
// 以后对象的数组是 null 或者数组长度时 0 时，则须要初始化数组
if ((tab = table) == null || (n = tab.length) == 0) {n = (tab = resize()).length;
}
// 应用 hash 与数组长度减一的值进行异或失去扩散的数组下标，预示着依照计算当初的
// key 会寄存到这个地位上，如果这个地位上没有值，那么间接新建 k - v 节点寄存
// 其中长度 n 是一个 2 的幂次数
if ((p = tab[i = (n - 1) & hash]) == null) {tab[i] = newNode(hash, key, value, null);
}
// 如果走到 else 这一步，阐明 key 索引到的数组地位上曾经存在内容，即呈现了碰撞
// 这个时候须要更为简单解决碰撞的形式来解决，如链表和树
else {
Node<K,V> e; K k;
// 节点 key 存在，间接笼罩 value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) {e = p;}
// 判断该链为红黑树
else if (p instanceof TreeNode) {
// 其中 this 示意以后 HashMap, tab 为 map 中的数组
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);
// TREEIFY_THRESHOLD = 8
// 从 0 开始的，如果到了 7 则阐明满 8 了，这个时候就须要转
// 从新确定是否是扩容还是转用红黑树了
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;
}
}
// 此时的 e 是保留的被碰撞的那个节点，即老节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 是办法的调用参数，示意是否替换已存在的值，// 在默认的 put 办法中这个值是 false，所以这里会用新值替换旧值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// Callbacks to allow LinkedHashMap post-actions
afterNodeAccess(e);
return oldValue;
}
}
// map 变更性操作计数器
// 比方 map 结构化的变更像内容增减或者 rehash，这将间接导致内部 map 的并发
// 迭代引起 fail-fast 问题，该值就是比拟的根底
++modCount;
// size 即 map 中包含 k - v 数量的多少
// 超过最大容量 就扩容
if (++size > threshold)
resize();
// Callbacks to allow LinkedHashMap post-actions
afterNodeInsertion(evict);
return null;
}HashMap 的 put 办法执行过程整体如下：
① 判断键值对数组 table[i] 是否为空或为 null，否则执行 resize() 进行扩容；
② 依据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i]==null，间接新建节点增加；
③ 判断 table[i]的首个元素是否和 key 一样，如果雷同间接笼罩 value；
④ 判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则间接在树中插入键值对；
⑤ 遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 曾经存在间接笼罩 value 即可；
⑥ 插入胜利后，判断理论存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容。
HashMap 总结
HashMap 底层构造？基于 Map 接口的实现，数组 + 链表的构造，JDK 1.8 后退出了红黑树，链表长度 >8 变红黑树,<6 变链表
两个对象的 hashcode 雷同会产生什么? Hash 抵触，HashMap 通过链表来解决 hash 抵触
HashMap 中 equals() 和 hashCode() 有什么作用？HashMap 的增加、获取时须要通过 key 的 hashCode() 进行 hash()，而后计算下标 (n-1 & hash)，从而取得要找的同的地位。当发生冲突（碰撞）时，利用 key.equals() 办法去链表或树中去查找对应的节点
HashMap 何时扩容？put 的元素达到容量乘负载因子的时候，默认 16*0.75
hash 的实现吗？h = key.hashCode()) ^ (h >>> 16)，hashCode 进行无符号右移 16 位，而后进行按位异或，失去这个键的哈希值，因为哈希表的容量都是 2 的 N 次方，在以后，元素的 hashCode() 在很多时候下低位是雷同的，这将导致抵触（碰撞），因而 1.8 当前做了个移位操作：将元素的 hashCode() 和本人右移 16 位后的后果求异或
HashMap 线程平安吗？HashMap 读写效率较高，然而因为其是非同步的，即读写等操作都是没有锁爱护的，所以在多线程场景下是不平安的，容易呈现数据不统一的问题，在单线程场景下十分举荐应用。
以上就是 HashMap 的介绍，本篇的视频版详解，留言可获取。
—END–
对于作者：mikechen，十余年 BAT 架构教训，资深技术专家，曾任职阿里、淘宝、百度。
欢送关注集体公众号：mikechen 的互联网架构，十余年 BAT 架构教训倾囊相授！
在公众号菜单栏对话框回复【架构 】关键词，即可查看我 原创的 300 期 +BAT 架构技术系列文章与 1000+ 大厂面试题答案合集。