本文已收录到 AndroidFamily，技能和职场问题，请关注公众号 [彭旭锐] 发问。
前言
大家好，我是小彭。
在上一篇文章里，咱们聊到了散列表的全体规划思维，在后续几篇文章里，咱们将以 Java 语言为例，剖析规范库中完成的散列表完成，包含 HashMap、ThreadLocalMap、LinkedHashMap 和 ConcurrentHashMap。
今日，咱们来评论 Java 规范库中非常典型的散列表结构，也是 “面试八股文” 的规范题库之一 —— HashMap。
本文源码根据 Java 8 HashMap，并相关剖析部分 Java 7 HashMap。
- 万字 HashMap 详解，根底（高雅）永不过期 —— 原理篇
- 万字 HashMap 详解，根底（高雅）永不过期 —— 源码篇
思维导图：
1. 回忆散列表作业原理
在剖析 HashMap 的完成原理之前，咱们先来回忆散列表的作业原理。
散列表是根据散列思维完成的 Map 数据结构，将散列思维应用到散列表数据结构时，就是经过 hash 函数提取键（Key）的特征值（散列值），再将键值对映射到固定的数组下标中，利用数组支撑随机访问的特性，完成 O(1) 时刻的存储和查询操作。
散列表示意图
在从键值对映射到数组下标的过程中，散列表会存在 2 次散列抵触：
- 第 1 次 – hash 函数的散列抵触： 这是一般意义上的散列抵触；
- 第 2 次 – 散列值取余转数组下标： 本质上，将散列值转数组下标也是一次 Hash 算法，也会存在散列抵触。一起，这也阐明 HashMap 中同一个桶中节点的散列值纷歧定是相同的。
事实上，因为散列表是紧缩映射，所以咱们无法防止散列抵触，只能确保散列表不会因为散列抵触而失掉正确性。常用的散列抵触解决办法有 2 类：
- 敞开寻址法： 例如 ThreadLocalMap；
- 别离链表法： 例如今日要剖析的 HashMap 散列表。
别离链表法（Separate Chaining）的核心思维是： 在呈现散列抵触时，将抵触的元素增加到同一个桶（Bucket / Slot）中，桶中的元素会组成一个链表，或许跳表、红黑树等动态数据结构。比较于敞开寻址法，链表法是更常用且更安稳的抵触解决办法。
别离链表法示意图
影响散列表功能的关键在于 “散列抵触的产生概率”，抵触概率越低，时刻复杂度越接近于 O(1)。 那么，哪些要素会影响抵触概率呢？主要有 3 个：
- 要素 1 – 装载因子： 装载因子 (Load Factor) = 散列表中键值对数目 / 散列表的长度。跟着散列表中元素越来越多，空闲方位越来越少，就会导致散列抵触的产生概率越来越大，使得散列表操作的均匀时刻会越来越大；
- 要素 2 – 选用的抵触解决办法： 敞开寻址法的抵触概率天然比别离链表法高，合适于小数据量且装载因子较小的场景；别离链表法对装载因子的容忍度更高，合适于大数据量且大目标（相关于一个指针）的场景；
- 要素 3 – 散列函数规划： 散列算法随机性和高效性也会影响散列表的功能。假如散列值不行随机，即使散列表全体的装载因子不高，也会使得数据集合在某一个区域或桶内，仍然会影响散列表的功能。
2. 认识 HashMap 散列表
2.1 说一下 HashMap 的底层结构？
HashMap 是根据别离链表法解决散列抵触的动态散列表：
-
在 Java 7 中运用的是 “数组 + 链表”，产生散列抵触的键值对会用头插法增加到单链表中；
-
在 Java 8 中运用的是 “数组 + 链表 + 红黑树”，产生散列抵触的键值对会用尾插法增加到单链表中。假如链表的长度大于 8 时且散列表容量大于 64，会将链表树化为红黑树。在扩容再散列时，假如红黑树的长度低于 6 则会还原为链表；
-
HashMap 的数组长度确保是 2 的整数幂，默许的数组容量是 16，默许装载因子上限是 0.75，扩容阈值是 12（16*0.75）；
-
在创立 HashMap 目标时，并不会创立底层数组，这是一种懒初始化机制，直到第一次 put 操作才会经过 resize() 扩容操作初始化数组;
-
HashMap 的 Key 和 Value 都支撑 null，Key 为 null 的键值对会映射到数组下标为 0 的桶中。
2.2 为什么 HashMap 选用拉链法而不是敞开地址法？
我认为 Java 给予 HashMap 的定位是一个相对 “通用” 的散列表容器，它应该在面对各种输入场景中都表现安稳。
敞开地址法的散列抵触产生概率天然比别离链表法更高，所以根据敞开地址法的散列表不能把装载因子的上限设置得很高。在存储相同的数据量时，敞开地址法需求预先请求更大的数组空间，内存利用率也不会高。因而，敞开地址法只合适小数据量且装载因子较小的场景。
而别离链表法关于装载因子的容忍度更高，可以合适大数据量且更高的装载因子上限，内存利用率更高。尽管链表节点会多耗费一个指针内存，但在一般的业务场景中可以忽略不计。
咱们可以举个反例，在 Java 原生的数据结构中，也存在运用敞开地址法的散列表 —— 就是 ThreadlLocal。因为项目中不会很多运用 ThreadLocal 线程部分存储，所以它是一个小规模数据场景，这儿运用敞开地址法是没问题的。
2.3 为什么 HashMap 在 Java 8 要引进红黑树呢？
因为当散列抵触加重的时分，在链表中寻找对应元素的时刻复杂度是 O(K)，K 是链表长度。在极点情况下，当所有数据都映射到相同链表时，时刻复杂度会 “退化” 到 O(n)。
而运用红黑树（近似平衡的二叉查找树）的话，树形结构的时刻复杂度与树的高度有关， 查找复杂度是 O(lgK)，最坏情况下时刻复杂度是 O(lgn)，时刻复杂度更低。
2.4 为什么 HashMap 运用红黑树而不是平衡二叉树？
这是在查询功能和保护成本上的权衡，红黑树和平衡二叉树的区别在于它们的平衡程度的强弱不同：
平衡二叉树寻求的是一种 “彻底平衡” 状况：任何结点的左右子树的高度差不会超越 1。优势是树的结点是很均匀分配的；
红黑树不寻求这种彻底平衡状况，而是寻求一种 “弱平衡” 状况：整个树最长途径不会超越最短途径的 2 倍。优势是尽管献身了一部分查找的功能功率，可是可以交换一部分坚持树平衡状况的成本。
2.5 为什么常常运用 String 作为 HashMap 的 Key？
- 1、不可变类 String 可以防止修改后无法定位键值对： 假设 String 是可变类，当咱们在 HashMap 中构建起一个以 String 为 Key 的键值对时，此刻对 String 进行修改，那么经过修改后的 String 是无法匹配到方才构建过的键值对的，因为修改后的 hashCode 或许会变化，而不可变类可以规避这个问题。
- 2、String 可以满意 Java 关于 hashCode() 和 equals() 的通用约定： 既两个目标 equals() 相同，则 hashCode() 相同，假如 hashCode() 相同，则 equals() 纷歧定相同。这个约定是为了防止两个 equals() 相同的 Key 在 HashMap 中存储两个独立的键值对，引起矛盾。
2.6 HashMap 的多线程程序中会呈现什么问题？
- 数据掩盖问题：假如两个线程并发履行 put 操作，而且两个数据的 hash 值抵触，就或许呈现数据掩盖（线程 A 判断 hash 值方位为 null，还未写入数据时挂起，此刻线程 B 正常插入数据。接着线程 A 获得时刻片，因为线程 A 不会从头判断该方位是否为空，就会把方才线程 B 写入的数据掩盖掉）。事实上，这个未同步数据在恣意多线程环境中都会存在这个问题。
- 环形链表问题： 在 HashMap 触发扩容时，而且正好两个线程一起在操作同一个链表时，就或许引起指针紊乱，构成环型链条（因为 Java 7 版别选用头插法，在扩容时会翻转链表的次序，而 Java 8 选用尾插法，再扩容时会坚持链表原本的次序）。
2.7 HashMap 怎么完成线程安全？
有 3 种办法：
- 办法 1 – 运用 hashTable 容器类（过期）： hashTable 是线程安全版别的散列表，它会在所有办法上增加 synchronized 关键字，且不支撑 null 作为 Key。
- 办法 2 – 运用 Collections.synchronizedMap 包装类： 原理也是在所有办法上增加 synchronized 关键字；
- 办法 3 – 运用 ConcurrentHashMap 容器类： 根据 CAS 无锁 + 分段完成的线程安全散列表；
3. HashMap 的特点
在剖析 HashMap 的履行流程之前，咱们先用一个表格整理 HashMap 的特点：
| 版别 | 数据结构 | 节点完成类 | 特点 |
|---|---|---|---|
| Java 7 | 数组 + 链表 | Entry（单链表） | 1、table（数组） 2、size（尺度） 3、threshold（扩容阈值） 4、loadFactor（装载因子上限） 5、modCount（修改计数） 6、默许数组容量 16 7、最大数组容量 2^30 8、默许负载因子 0.75 |
| Java 8 | 数组 + 链表 + 红黑树 | 1、Node（单链表） 2、TreeNode（红黑树） |
9、桶的树化阈值 8 10、桶的还原阈值 6 11、最小树化容量阈值 64 |
HashMap.java
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
// 默许数组容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 疑问 3：为什么最大容量是 2^30 次幂？
// 疑问 4：为什么 HashMap 要求数组的容量是 2 的整数幂？
// 数组最大容量：2^30（高位 0100，低位都是 0）
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默许负载因子：0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 疑问 5：为什么要设置桶的树化阈值，而不是直接运用数组 + 红黑树？
// （Java 8 新增）桶的树化阈值：8
static final int TREEIFY_THRESHOLD = 8;
// （Java 8 新增）桶的还原阈值：6（在扩容时，当原有的红黑树内数量 <= 6时，则将红黑树还原成链表）
static final int UNTREEIFY_THRESHOLD = 6;
// 疑问 6：为什么要在设置桶的树化阈值后，还要设置树化的最小容量？
// （Java 8 新增）树化的最小容量：64（只要整个散列表的长度满意最小容量要求时才答应链表树化，否则会直接扩容，而不是树化）
static final int MIN_TREEIFY_CAPACITY = 64;
// 底层数组（每个元素是一个单链表或红黑树）
transient Node<K,V>[] table;
// entrySet() 回来值缓存
transient Set<Map.Entry<K,V>> entrySet;
// 有用键值对数量
transient int size;
// 扩容阈值（容量 * 装载因子）
int threshold;
// 装载因子上限
final float loadFactor;
// 修改计数
transient int modCount;
// 链表节点（一个 Node 等于一个键值对）
static class Node<K,V> implements Map.Entry<K,V> {
// 哈希值（相同链表上 Key 的哈希值或许相同）
final int hash;
// Key（一个散列表上 Key 的 equals() 一定不同）
final K key;
// Value（Value 不影响节点方位）
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;
}
// Node 的 hashCode 取 Key 和 Value 的 hashCode
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
// 两个 Node 的 Key 和 Value 都相等，才认为相等
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;
}
}
// （Java 8 新增）红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
// 父节点
TreeNode<K,V> parent;
// 左子节点
TreeNode<K,V> left;
// 右子节点
TreeNode<K,V> right;
// 删除辅助节点
TreeNode<K,V> prev;
// 颜色
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// 回来树的根节点
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}
}
LinkedHashMap.java
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);
}
}
比较于线性表，HashMap 的特点可算是上难度了，HashMap 真卷。不出意外的话又有小朋友出来举手发问了♀️：
- ♀️疑问 1： 为什么字段不声明
private关键字？（答复过多少次了，把手给我放下） - ♀️疑问 2： 为什么字段声明
transient关键字？（答复过多少次了，把手给我放下） - ♀️疑问 3：为什么最大容量是 2^30？
因为 HashMap 要求散列表的数组容量是 2 的整数幂 ，而 int 类型可以表示的最大 2 的整数幂就是 2^30，即高位第 31 位是 1，低位都是 0。
- ♀️疑问 4：为什么 HashMap 要求数组的容量是 2 的整数幂？
这个问题咱们下面再答复。
- ♀️疑问 5：为什么要设置桶的树化阈值，而不是直接运用数组 + 红黑树？
其实，红黑树是 “兜底” 战略，而纷歧定是最优战略。
首要，红黑树节点自身的内存耗费是链表节点的 2 倍。其次，红黑树在增加和删除数据时需求保护红黑树的性质，会增加旋转等操作。所以，当桶的节点数很低时，并不能表现出红黑树的优势（类似于 Arrays.sort 在子数组长度小于 47 时用插入排序而不是快速排序）。
再结合散列剖析的数据计算，在装载因子上限为 0.75 且均匀负载因子为 0.5 HashMap 中，桶长度的呈现频率符合泊松散布，大部分的桶散布在 0 ~ 3 的长度上，长度大于 8 的桶的呈现频率低于千万分之一。
综上所述，为了防止在小桶中运用红黑树，HashMap 在桶的长度大于等于 8 时才会树化为红黑树。而且在扩容再散列时，假如桶的长度小于等于 6，也会还原为链表。
散列抵触数据计算
# 装载因子上限为 0.75、均匀负载因子为 0.5，且散列函数随机性良好时，不同长度桶的呈现频率
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million # 低于千万分之一
- ♀️疑问 6：为什么要在设置桶的树化阈值后，还要设置树化的最小容量？
这是为了防止无效的树化。
在散列表的容量较低时，增加数据时很容易会触发扩容。此刻，一部分原本已经树化的桶会因为长度下降而退还回链表。因而，红黑树为树化操作设置了最小容量要求：假如链表长度到达树化阈值，但散列表全体的长度未到达最小容量要求，那么就直接扩容，而不是在桶上树化。
后续源码剖析，见下一篇文章：万字 HashMap 详解，根底（高雅）永不过期 —— 源码篇。
版权声明
本文为稀土技能社区首发签约文章，14天内禁止转载，14天后未获授权禁止转载，侵权必究！
参考资料
- 数据结构与算法剖析 Java 语言描绘（第 5 章 散列）—— [美] Mark Allen Weiss 著
- 算法导论（第 11 章 散列表）—— [美] Thomas H. Cormen 等 著
- 数据结构与算法之美（第 18~22 讲） —— 王争 著，极客时刻 出品
- Java：这是一份具体&全面的HashMap 1.7 源码剖析 —— Carson 著
- Java源码剖析：HashMap 1.8 相关于1.7 究竟更新了什么？ —— Carson 著
- 都说 HashMap 是线程不安全的，究竟表现在哪儿？ —— developer 著
- 漫画：高并发下的HashMap —— 程序员小灰 著
- 面试官：”准备用HashMap存1w条数据，构造时传10000还会触发扩容吗？” —— 承香墨影 著
- 散列算法 —— Wikipedia
- Poisson Distribution —— Wikipedia
