HashMap 的底层原理和扩容机制一直都是面试的时候经常被问到的问题，同时也是集合源码中最难阅读的一部分😢，之前更新的 ArrayList 源码阅读收获了很多朋友的喜欢，也给了我很多自信；本次我准备完成一个关于 HashMap 源码阅读和解析的专栏，共分为四部分内容：

1. 概念辨析、属性和构造方法的源码阅读
2. putVal() 和 resize() 方法的源码分析
3. 详细讲解红黑树
4. HashMap 中与树有关的方法

通过阅读这些内容相信大家一定可以彻底的搞懂 HashMap，如果喜欢文章的话不要忘记订阅专栏和关注。😊

前言：
本篇是专栏的第一部分：概念辨析、属性和构造方法的源码阅读，大家重点需要关注属性和常量的含义，还有对几种构造方法都初始化了哪些部分有了解和记忆，为下一篇更难的源码阅读打好基础。

1.基础理解

1.1 数组、链表、散列表

1）数组

数组是一种线性数据结构，由一组连续的内存单元组成，每个元素都有固定的索引位置。

数组的优点是可以通过索引快速访问元素，时间复杂度为O(1)。

但是因为数组的长度是指定的，所以进行插入和扩容的操作非常麻烦，需要将原本数组中的内容转移到新数组中才能完成扩容的操作。

2）链表

链表也是一种线性数据结构，由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

链表的优点是插入和删除操作可以在O(1)时间内完成，无需移动其他元素。

缺点是访问元素时需要遍历整个链表，时间复杂度为O(n)，并且相比数组占用更多的内存空间。

3）散列表

与上面的两种数据结构不同的是，散列表是用来存储 键值对（key-value），在实现方式上，散列表像是数组 + 链表的一个结合，也就是基本的结构是一个数组，但数组中存储的元素是一个链表。

提到数组，最显著的特点就是 索引，散列表是通过 哈希算法 将键（key）映射成一个 长度固定 的二进制数，然后通过 路由算法 将其映射到数组的索引中；在查找和修改的时候可以通过相同的算法快速的找到对应的数组的索引。

散列表的缺点是可能会发生哈希冲突，即经过映射之后映射到了相同的位置，需要解决冲突的方法，比如链地址法，也就是上面提到的，在数组中存储一个链表，如果产生哈希冲突就将数据拼接到数组索引位置的链表中。

4）哈希算法

Hash 的中文释义为散列，一般音译为哈希。它的基本原理就是把 任意长度 的输入，通过哈希算法转变为固定长度的输出。

映射的规则成为哈希算法，原始数据通过映射之后得到的二进制串就是哈希值。

哈希有如下的几个特点：

1. 无法通过哈希值反推出原始的数据，且数据一点微小的变化都会得到完全不同的哈希值，相同的数据会得到完全相同的哈希值，这两个特点使得哈希算法在安全方面也有广泛的应用，比如 https 的数字证书的签名认证等。
2. 哈希算法的执行效率很高效，长文本也能很快的算出对应的哈希值
3. 由于是将任意长度是输出映射为固定长度的输出，也就是一种 无限 => 有限 的一种对应关系，就会导致所谓的哈希冲突，即两个不同的数据输入映射为了相同的哈希值，如何处理哈希冲突是使用哈希函数的时候必须要解决的问题。

1.2 HashMap 中使用的数据结构和算法

1）数据结构

Java 中的 HashMap 就是基于 散列表 实现的，其底层是通过数组+链表（Java8 引入了红黑树）来存储数据的。

1）数组：HashMap 内部维护了一个数组（table），这个数组的每个元素称为桶（bucket）。数组的长度是固定的（有扩容机制），如果不指定的话默认为 16。

2）链表或红黑树：在 Java 8 中，HashMap 使用了数组+链表+红黑树的结构，以应对哈希冲突。每个桶可以存储一个链表或红黑树。当哈希冲突发生时（即多个键映射到了同一个桶），新的键值对会被插入到对应位置的链表或红黑树中，具体来说，当链表中的元素个数超过一定阈值（默认为8）时，链表会转换为红黑树，以提高查找、插入、删除操作的效率，因为红黑树的平均时间复杂度为 O(log n) 而链表则是 O(n)

3）在 Java 8 之前的版本中，HashMap 只使用链表来解决冲突，而在 Java 8 中引入了红黑树的优化，使得 HashMap 在处理大量数据时性能更加稳定。

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在每个节点上都附加了一个额外的表示节点颜色的属性，可以是红色或黑色。红黑树满足以下性质：

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色的。
3. 每个叶子节点（NIL节点，即空节点）都是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点（黑高相同）。

因为红黑树理解和讲解都比较复杂，之后单独出一篇博客来讲，这里优先关注 HashMap 的底层结构。

2）路由算法

通过 hashCode() 得到的整数是肯定无法直接作为下标的（Java 中获得的是一个32位的二进制数），此时就需要再经过一次映射来将哈希值对应为数组下标范围内的一个数字。

HashMap 将键映射为索引是通过了如下的步骤，比如说通过 map.put("key", "value") 插入一个键值对

1. 首先通过指定的哈希算法，Java 中使用 hashCode() 调用本地方法（一般映射的是内存），或者调用重写的 hashCode() 来得到 “key” 对应的 Hash 值。

2. 通过一个扰动函数，使得 Hash 值的分布更加分散，进一步降低哈希冲突的可能

3. 通过路由算法计算出对应的索引，比如如下的方法：

   (table.length - 1) & node.hash
   

   是通过将 数组的长度 - 1 和得到的哈希值进行 按位与运算（&）得到的，在 HashMap 中，table.length 一定是 2 的幂次，其二进制的特点就是开头为 1 后面为全 0（比如 0001 0000），减一之后转换为二进制就会表现为全 1（0000 1111），此时进行位与运算，得到的其实就是哈希值的后几位，下方展示一个运算案例：
   

3）HashMap 中使用的节点 Node

先来看一下源码：

	/*** Basic hash bin node, used for most entries.  (See below for* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)*/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;}

上面展示的就是 HashMap 中的静态内部类 Node，上方注释中解释的比较明确，这就是其中的 bin node（节点），这个静态内部类中有四个属性，分别为：

• int hash：存储映射的哈希值，需要注意的是这个值并不是直接将通过 hashCode() 得到的值，而是经过扰动函数处理后的值
• K key：本节点存储的键
• V value：本节点存储的值
• Node<K, V> next：存储下一个节点的位置

最后提供了一个有参的构造方法。

2.源码阅读第一部分-属性与构造方法

2.1 常量解读

下面就开始正式阅读 HashMap 的源码，我们先从类中的常量开始，源码中的常量通常与类的机制息息相关，理解常量对源码的阅读很有帮助

	/*** The default initial capacity - MUST be a power of two.*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

第一个常量是 DEFAULT_INITIAL_CAPACITY，这个常量的含义是：如果在初始化的时候没有指定初始容量（initialCapacity）的话，系统默认给的初始容量；上方的注释中提到，容量（table.length），必须是 2 的 n 次方；然后下面注释中 aka 的意思是 “also known as” 就是这个值也可以被称作为 16。

---

	/*** The maximum capacity, used if a higher value is implicitly specified* by either of the constructors with arguments.* MUST be a power of two <= 1<<30.*/static final int MAXIMUM_CAPACITY = 1 << 30;

这个常量指定的是数组（table）的最大长度，为 2 的 30 次方，是为了对数组的长度做一个限制，在后面的代码中经常作为判断条件使用。

---

	/*** The load factor used when none specified in constructor.*/static final float DEFAULT_LOAD_FACTOR = 0.75f;

这里指定的是默认的负载因子的值，为 0.75，负载因子（Load Factor）是指哈希表中已存储元素数量与哈希表容量的比例。在哈希表中，负载因子用于衡量哈希表的填充程度，即已存储元素占哈希表容量的比例。通常情况下，负载因子是一个介于 0 到 1 之间的数值，在哈希表中，当负载因子达到一定阈值时，通常会触发哈希表的扩容操作，以保持哈希表的性能。常见的默认负载因子值为 0.75，这是一个经验值，可以在平衡内存占用和性能之间做出权衡。

---

之后的三个常量都是和树化（红黑树）相关的，这里放在一起讲：

/*** The bin count threshold for using a tree rather than list for a* bin.  Bins are converted to trees when adding an element to a* bin with at least this many nodes. The value must be greater* than 2 and should be at least 8 to mesh with assumptions in* tree removal about conversion back to plain bins upon* shrinkage.*/static final int TREEIFY_THRESHOLD = 8;/*** The bin count threshold for untreeifying a (split) bin during a* resize operation. Should be less than TREEIFY_THRESHOLD, and at* most 6 to mesh with shrinkage detection under removal.*/static final int UNTREEIFY_THRESHOLD = 6;/*** The smallest table capacity for which bins may be treeified.* (Otherwise the table is resized if too many nodes in a bin.)* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts* between resizing and treeification thresholds.*/static final int MIN_TREEIFY_CAPACITY = 64;

第一个和第三个常量配合来决定一个链表树化的时机；数组中的某一个链表中树化的条件是：

数组的长度达到 MIN_TREEIFY_CAPACITY（64）且数组中的一个链表的长度达到 TREEIFY_THRESHOLD（8）

此时就对这个链表进行树化操作，将其转化为红黑树来优化查询速度。

第二个常量（UNTREEIFY_THRESHOLD）是树降级为链表的阈值，当树中的元素因为删除而达到阈值 UNTREEIFY_THRESHOLD（6）的时候，会将树降级为链表。

---

总结一下，HashMap 底层是散列表的结构（数组+链表（红黑树）），常量的定义也围绕着这些展开，规定了数组的长度、链表树化的阈值等。

2.2 属性解读

然后将源码翻到 Fields 部分，来看一下具体的属性，HashMap 中维护了一个数组（table），所以对于它来说会有两个长度，一个是 table.length 就是散列表（哈希表）中数组的长度，还有一个长度为 size，指的是存储元素的个数。

	/*** The table, initialized on first use, and resized as* necessary. When allocated, length is always a power of two.* (We also tolerate length zero in some operations to allow* bootstrapping mechanics that are currently not needed.)*/transient Node<K,V>[] table;

首先就是 table，这就是存储数据的 Node 数组。

---

	/*** Holds cached entrySet(). Note that AbstractMap fields are used* for keySet() and values().*/transient Set<Map.Entry<K,V>> entrySet;

这个属性是用来缓存 HashMap 中的 entrySet() 方法返回的键值对集合。通过缓存 entrySet 属性，可以在多次需要访问 HashMap 中所有键值对的情况下提高性能，避免重复生成键值对集合，从而节省时间和资源。此属性与基本源码关系不大，这里先不做深入解释。

---

 	/*** The number of key-value mappings contained in this map.*/transient int size;

当前 Map 中存储的 元素 数量

---

	/*** The number of times this HashMap has been structurally modified* Structural modifications are those that change the number of mappings in* the HashMap or otherwise modify its internal structure (e.g.,* rehash).  This field is used to make iterators on Collection-views of* the HashMap fail-fast.  (See ConcurrentModificationException).*/transient int modCount;

modCount 字段很多集合类中都有，它存储的是该集合 结构 被修改的次数，比如插入和删除的操作；修改 value 这种不会修改结构的方式不会引发 modCount 的自增，这在后面的源码中有体现。

---

	/*** The next size value at which to resize (capacity * load factor).** @serial*/// (The javadoc description is true upon serialization.// Additionally, if the table array has not been allocated, this// field holds the initial array capacity, or zero signifying// DEFAULT_INITIAL_CAPACITY.)int threshold;

在 HashMap 中，threshold 属性存储了在何时需要对哈希表进行扩容操作的阈值。当 HashMap 中的 元素数量 达到 threshold 时，就会触发哈希表的扩容操作，以保持哈希表的性能；threshold 的值通常是容量（capacity）乘以负载因子（load factor）得到的结果。当 HashMap 中的元素数量达到 threshold 时，就会进行扩容操作。

---

	/*** The load factor for the hash table.** @serial*/final float loadFactor;

这里就是负载因子属性，一般我们使用默认的，也就是 0.75f

2.3 构造方法解读

HashMap 提供了四种构造方法，分别是：

• 指定了初始容量和负载因子的构造方法
• 指定了初始容量的构造方法
• 默认的无参构造方法
• 传入 Map 的构造方法

下面来按照这个顺序分别说明这些方法：

	/*** Constructs an empty <tt>HashMap</tt> with the specified initial* capacity and load factor.** @param  initialCapacity the initial capacity* @param  loadFactor      the load factor* @throws IllegalArgumentException if the initial capacity is negative*         or the load factor is nonpositive*/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);}

上面的代码中，首先通过三个 if 语句对传入的参数进行检验：

• 初始容量是否大于等于零
• 初始容量是否大于table的最大容量（2的30次方）
• 传入的负载因子的准确性，其中 Float.isNaN(loadFactor 用于判断一个浮点数是否为 NaN（Not a Number））。

最后指定负载因子为传入的负载因子，然后通过 tableSizeFor() 方法来计算 threshold（扩容阈值），这个方法的作用是获取一个 2 的幂次方的值，这个值是在大于等于传入的 cap 中最小的那个值；比如传入的是 3，最终得到的结果就是 4，传入的是 5 获得的则是 8；这个值会被赋值到 threshold 中。

通过这个构造方法，给如下的属性进行了赋值：

• loadFactor：负载因子（传入的负载因子）
• threshold：扩容阈值（经过处理后的 initialCapacity）

读到这里可以发现数组（table）还没有被初始化，table 的初始化被放在第一次插入元素的时候进行，这种延迟初始化的可以节省内存。

---

    /*** Constructs an empty <tt>HashMap</tt> with the specified initial* capacity and the default load factor (0.75).** @param  initialCapacity the initial capacity.* @throws IllegalArgumentException if the initial capacity is negative.*/public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}

然后就是指定了容量的方法，其实就是调用了上面的方法，传入的参数是指定的容量和默认的负载因子（0.75）

这个方法调用了上面的方法，所以经过这个构造方法，也是初始化了两个属性：

• loadFactor：负载因子
• threshold：扩容阈值

---

	/*** Constructs an empty <tt>HashMap</tt> with the default initial capacity* (16) and the default load factor (0.75).*/public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}

默认的构造方法中只指定了负载因子，初始容量为默认值，也就是 0。

---

	/*** Constructs a new <tt>HashMap</tt> with the same mappings as the* specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with* default load factor (0.75) and an initial capacity sufficient to* hold the mappings in the specified <tt>Map</tt>.** @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 集合的方式，首先制定了默认的负载因子，然后调用了 putMapEntries() 方法，这个方法接收两个参数，分别是 Map 集合和是否执行驱逐操作(evict)。

	/*** Implements Map.putAll and Map constructor.** @param m the map* @param evict false when initially constructing this map, else* true (relayed to method afterNodeInsertion).*/final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {int s = m.size();if (s > 0) {if (table == null) { // pre-sizefloat 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);}}}

本方法比较复杂，需要先知道这个方法在哪里被使用到了，通过注释可以看出其主要使用的位置有两个：Map.putAll and Map constructor 就是 putAll 方法和构造方法，在这两个方法中调用本方法来将传入的集合加入到 Map 中。

putMapEntries() 方法首先将 s 设定为传入集合的长度，如果集合中有元素就要进行插入的操作：

首先来看第一个第一组内容：

    if (table == null) { // pre-sizefloat ft = ((float)s / loadFactor) + 1.0F;int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);if (t > threshold)threshold = tableSizeFor(t);}

执行这一段方法的条件是 s > 0 && table == null，也就是传入的集合长度大于零，且 table 并未被初始化的情况，此时就可以判断出本方法是在构造方法中被调用的

因为是在构造方法中被调用的，通过上面的构造方法可以得知，构造方法中仅制定了负载因子的大小，其他比如说 table 和 threshold（拓展阈值）等都是默认值。

首先计算值 ft，它代表着将这些元素放入 HashMap 之后，如果要满足负载因子的规范（0.75f），需要的数组容量为多少

然后去判断这个容量的合理性：是否大于最大容量（MAXIMUM_CAPACITY），如果大于这个值的话，就取这个值，反之就保留 ft 的 int 部分，将其复制到 t 中，此时 t 中存储的就是插入完这些元素后数组应该的长度；运用这个长度来计算拓展阈值，tableSizeFor() 方法上面提到过了，最终将这个值赋值给 threshold（扩展阈值），扩展阈值会在后面指定 table 的容量时使用。

然后来看第二段内容，当发现 table 不是 null，那就是在 putAll() 方法中调用的本方法了，此时会先去判断 s 是否大于 threshold ，如果大于的话，此时就会去调用 resize() 方法，resize() 方法是当元素数量达到扩展阈值（threshold）的时候进行的拓展操作，会将数组拓展为原来的二倍长度，并指定新的扩展阈值，这个方法在后面会详细讲解。

else if (s > threshold)resize();

这一段的设计其实非常的严谨，首先来思考一个问题，什么时候会进行扩容操作？

是当前元素的数量大于threshold（扩容阈值）的时候进行扩容的操作。

那此时你可能会想，那不是 size + s > threshold 的时候就该进行扩容操作嘛？

其实这个时候是不严谨的，因为 s 中的 key 和原本 HashMap 中的 key 可能会出现重合现象，此时执行的是修改的逻辑，这样会导致插入完成后，最终的 size 其实是小于等于 size + threshold；而当 s 已经大于 threshold 则不同，此时插入完这个集合后 size 的大小一定会大于扩展阈值，此时就 一定 要进行扩容的操作，这就体现了源码的严谨性，只有当 s 大于 threshold 的时候才在这里进行扩容操作。

当完成上面两个部分之后，就执行增强 for 循环将内容插入到本 HashMap 中

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);
}

putVal() 和 resize 是两个非常关键且复杂的方法，这个放到后面详细讲解。