Java：从 Map到HashMap 的一步步实现！

作者：山猫先生

www.cnblogs.com/king0/p/14176609.html

一、 Map

1.1 Map 接口

在 Java 中, Map 提供了键——值的映射关系。映射不能包含重复的键,并且每个键只能映射到一个值。

以 Map 键——值映射为基础，java.util 提供了 HashMap（最常用）、 TreeMap、Hashtble、LinkedHashMap 等数据结构。

衍生的几种 Map 的主要特点：

HashMap：最常用的数据结构。键和值之间通过 Hash函数 来实现映射关系。当进行遍历的 key 是无序的

TreeMap：使用红黑树构建的数据结构，因为红黑树的原理，可以很自然的对 key 进行排序，所以 TreeMap 的 key 遍历时是默认按照自然顺序（升序）排列的。

LinkedHashMap: 保存了插入的顺序。遍历得到的记录是按照插入顺序的。

1.2 Hash 散列函数

Hash （散列函数）是把任意长度的输入通过散列算法变换成固定长度的输出。Hash 函数的返回值也称为 哈希值 哈希码 摘要或哈希。Hash作用如下图所示:

Hash 函数可以通过选取适当的函数，可以在时间和空间上取得较好平衡。

解决 Hash 的两种方式：拉链法和线性探测法

1.3 键值关系的实现

在 HashMap 中基于链表的实现

用树的方式实现：

1.4 Map 约定的 API

1.4.1 Map 中约定的基础 API

基础的增删改查：

1.4.2 Map 约定的较为高级的 API

1.4.3 Map 高级 API 的使用

getOrDefault() 当这个通过 key获取值，对应的 key 或者值不存在时返回默认值，避免在使用过程中 null 出现，避免程序异常。

ForEach() 传入 BiConsumer 函数式接口，表达的含义其实和 Consumer 一样，都 accept 拥有方法，只是 BiConsumer 多了一个 andThen() 方法，接收一个BiConsumer接口，先执行本接口的，再执行传入的参数的 accept 方法。

更多的函数用法：

https://www.cnblogs.com/king0/p/runoob.com/java/java-hashmap.html

1.5 从 Map 走向 HashMap

HashMap 是 Map的一个实现类，也是 Map 最常用的实现类。

1.5.1 HashMap 的继承关系

在 HashMap 的实现过程中，解决 Hash冲突的方法是拉链法。因此从原理来说 HashMap 的实现就是 数组 + 链表（数组保存链表的入口）。当链表过长，为了优化查询速率，HashMap 将链表转化为红黑树（数组保存树的根节点），使得查询速率为 log(n)，而不是链表的 O(n)。

二、HashMap

首先 HashMap 由 Doug Lea 和 Josh Bloch 两位大师的参与。同时 Java 的 Collections 集合体系，并发框架 Doug Lea 也做出了不少贡献。

2.1 基本原理

对于一个插入操作，首先将键通过 Hash 函数转化为数组的下标。若该数组为空，直接创建节点放入数组中。若该数组下标存在节点,即 Hash 冲突，使用拉链法，生成一个链表插入。

引用图片来自https://blog.csdn.net/woshimaxiao1/article/details/83661464

如果存在 Hash 冲突，使用拉链法插入，我们可以在这个链表的头部插入，也可以在链表的尾部插入，所以在 JDK 1.7 中使用了头部插入的方法，JDK 1.8 后续的版本中使用尾插法。

在 HashMap 中，前面说到的 数组+链表 的数组的定义

链表的定义：

2.1.2 提供的构造函数

三个构造函数，都没有完全的初始化 HashMap，当我们第一次插入数据时，才进行堆内存的分配，这样提高了代码的响应速度。

2.2 HashMap 中的 Hash函数定义

这里可以看到，Map 的键可以为 null，且 hash 是一个特定的值 0。

Hash 的目的是获取数组 table 的下标。Hash 函数的目标就是将数据均匀的分布在 table 中。

让我们先看看如何通过 hash 值得到对应的数组下标。第一种方法：hash%table.length()。但是除法操作在 CPU 中执行比加法、减法、乘法慢的多，效率低下。第二种方法 table[(table.length - 1) & hash] 一个与操作一个减法，仍然比除法快。这里的约束条件为  table.length = 2^N。

上面的例子可以让我们获取到对应的下标,而  让高 16 也参与运算，让数据充分利用，一般情况下 table 的索引不会超过 216，所以高位的信息我们就直接抛弃了， 让我们在数据量较少的情况下，也可以使用高位的信息。如果 table 的索引超过 216， hashCode() 的高 16 为 和 16 个 0 做异或得到的 Hash 也是公平的。

2.3 HashMap 的插入操作

上面我们已经知道如果通过 Hash 获取到 对应的 table 下标，因此我们将对应的节点加入到链表就完成了一个 Map 的映射，的确 JDK1.7 中的 HashMap 实现就是这样。让我们看一看 JDK 为实现现实的 put 操作。

定位到 put() 操作。

可以看到 put 操作交给了 putVal 来进行通用的实现。

2.3.1 putVal 的流程分析

其实 putVal() 流程的函数非常的明了。这里挑了几个关键步骤来引导。

是否第一次插入，true 调用 resizer() 进行调整，其实此时 resizer() 是进行完整的初始化，之后直接赋值给对应索引的位置。

如果链表已经转化为树，则使用树的插入。

用遍历的方式遍历每个 Node，如果遇到键相同，或者到达尾节点的next 指针将数据插入，记录节点位置退出循环。若插入后链表长度为 8 则调用 treeifyBin() 是否进行树的转化 。

对键重复的操作：更新后返回旧值，同时还取决于onlyIfAbsent，普通操作中一般为 true，可以忽略。

~

后续的数据维护。

2.3.2 modCount 的含义

fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。一种多线程错误检查的方式，减少异常的发生。

一般情况下，多线程环境 我们使用  来代替 HashMap。

2.4 resize() 函数

HashMap 扩容的特点：默认的table 表的大小事 16，threshold 为 12。负载因子 loadFactor .75，这些都是可以构造是更改。以后扩容都是 2 倍的方式增加。

至于为何是0.75 代码的注释中也写了原因，对 Hash函数构建了泊松分布模型，进行了分析。

2.4.1 HashMap 预定义的一些参数

这些变量都是和 HashMap 的扩容机制有关，将会在下文中用到。

2.4.2 resize() 方法解析

当一些参数设置正确后便开始扩容。

当扩容完毕之后，自然就是将原表中的数据搬到新的表中。下面代码完成了该任务。

如何正确的，快速的扩容调整每个键值节点对应的下标？第一种方法：遍历节点再使用 put() 加入一遍，这种方法实现，但是效率低下。第二种，我们手动组装好链表，加入到相应的位置。显然第二种比第一种高效，因为第一种 put() 还存在其他不属于这种情况的判断，例如重复键的判断等。

所以 JDK 1.8 也使用了第二种方法。我们可以继续使用找到对应的下标位置,对于旧的链表，执行 操作，只能产生两个不同的索引。一个保持原来的索引不变，另一个变为 原来索引 + oldCap(因为 newCap 的加入产生导致索引的位数多了 1 位，即就是最左边的一个，且该位此时结果为 1，所以相当于 原来索引 + oldCap)。所以可以使用  来确定出索引是否来变化。

因此这样我们就可以将原来的链表拆分为两个新的链表，然后加入到对应的位置。为了高效，我们手动的组装好链表再存储到相应的下标位置上。

特殊条件处理

普通情况处理：

到此 resize() 方法的逻辑完成了。总的来说 resizer() 完成了 HashMap 完整的初始化，分配内存和后续的扩容维护工作。

2.5 remove 解析

将 remove 删除工作交给内部函数 removeNode() 来实现。

三、 HashMap 从链表到红黑树的转变

如果链表的长度（冲突的节点数）已经达到8个，此时会调用 treeifyBin() ，treeifyBin() 首先判断当前hashMap 的 table的长度，如果不足64，只进行resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树。在源码还有这样的一个字段。

3.1 红黑树的数据结构

因为 继承了 LinkedHashMap.Entry ，所以存储的数据还是在Entry 中：

3.2 承上启下的 treeifyBin()

treeifyBin() 决定了一个链表何时转化为一个红黑树。treeifyBin() 有两种格式：

下面函数真正实现了链表的红黑树的转变。首先构建一个标准查询二叉树，然后在标准查询二叉树然后调整为一个红黑树。而 balanceInsertion() 实现了调整。

3.3 将一个二叉树转化为红黑树的操作-balanceInsertion()

当红黑树中新增节点的时候需要调用balanceInsertion方法来保证红黑树的特性。

如果想要了解红黑树的插入过程那么必须对红黑树的性质有一个较为清晰的了解。

红黑树的性质：

每个结点或是红色的，或是黑色的

根节点是黑色的

每个叶结点（NIL）是黑色的

如果一个节点是红色的，则它的两个儿子都是黑色的。

对于每个结点，从该结点到其叶子结点构成的所有路径上的黑结点个数相同。

TreeNode 红黑树总结

TreeNode 完整的实现了一套红黑树的增删改查的规则。实现参考了《算法导论》

这里推荐一个红黑树动画演示网站 https://rbtree.phpisfuture.com/

红黑树是一个不严格的平衡二叉查找树，高度近似 log(N)。

四、HashMap 的扩展

Map中 key 有一个性质，就是 key 不能重复，而 Java Set 的含义：集合中不能有重复的元素。HashMap 的实现已经足够的优秀。那么我们是否可以用 key 的性质来实现 Set ？的确 JDK 中的 HashSet 就是这样做的。

就是存进 Map 中的 value，而 key 正是 Set 语义的实现。而且可以判断出 HashSet 中是允许存入 Null 值的。