面试爽文：开局一张图，花十分钟了解 HashMap 的树化逻辑

电玩女神 2023-10-16 09:39 36阅读 0赞

## 一. 前言 ##

闲来无事，对 HashMap 其中比较重要的节点做了一下深入，然后尝试用最通俗易懂的说法输出出来。

老规矩 ，给节省时间的小伙伴上菜 ：

![image.png][]

## 二. HashMap 的树化 ##

> 初级入门

之前面试别人的时候，就经常问这问题 ，问的比较多的一个点就是 HashMap 的树化 ，这个问题的标准答案也很简单 ：

*  在 **Java 1.8 之前** ， HashMap 通过**数组 + 链表的数据结构来处理哈希冲突**。当多个键具有同一个哈希码时，他们会存储在一个哈希桶中，形成一个链表结构
 *  在 **Java 1.8 之后**， 也是数组 + 链表，**但是当链表的长度超过一定阈值后，会转变成红黑树结构**，这个行为就叫树化

**会了这两点，一般就认为对HashMap有一定了解了，初级就算过了，但是如果是中级就会稍微问多点**

> 中级浅谈 ：

*  **如何实现的链表？**

每一个写入 HashMap 的对象会被封装到 **Node** 对象中，这个对象中有四个属性 ，其中一个属性同样是一个 Node 对象 ，用来指向链表中下一个 Node

java
    
    复制代码
    
    static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; // next 即为链表中下一个 Node Node<K,V> next; }

*  **如何实现的红黑树？**

基于 **TreeNode** 对象实现， 该对象包含了 **TreeNode-Left ，TreeNode-Right , TreeNode-Parent**对象，用于实现树形结构

java
    
    复制代码
    
    // 实际每个 TreeNode 包含了数据信息 TreeNode extends Node { // 父节点 TreeNode parent; // 左子节点 TreeNode left; // 右子节点 TreeNode right; // 上一节点用于生成双向链表,便于树形操作 TreeNode prev; boolean red; }

*  **为什么会有 Hash 冲突？**

因为 HashMap 的底层是数组，而**一个元素放在哪个数组格里面是通过 Hash & 数组长度来实现的**，这就意味着哪怕 Hash 算法很厉害 ，但是**取模下来得到同一个下标的可能性也非常大**。

*  **为什么选择红黑树？**

红黑树能保证两边元素的平衡 , 基于这个特性 ，红黑树能保证查询的效率，无论元素多少，都能让查询一直在对数级别。

## 三. 高级原理 ##

当然，像技术要求比较高的兄弟，可能还会继续问下去，这个时候就需要把前后的所有概念串起来了，不多说，直接上代码 ：

### 3.1 手写逻辑 ###

**HashMap 的逻辑线性表述不是很清晰，这里手写了一段逻辑，力求逻辑更加清晰 ：**

*  2个存储对象 ：**在树化和解除树化之间互相转换**
    
     *  Node 用来存储Map中的数据， 通过 **next** 引用**指向下一个节点形成链表**
     *  **TreeNode** 是 Node 的扩展 ， 用来形成树结构
 *  4个流程 ：
    
     *  如果Hash获得的数组下标对应的位点没有对象，则**直接放入Node对象**
     *  如果存在对象，但是小于树化阈值，则 **放入链表末尾**
     *  如果存在对象，且大于 **树化阈值（8）**，则 **先转换成树链表** ，在**对树链表进行树化**
     *  如果插入或者删除 **触发解除阈值(6)**，则解除树化

> 两个存储对象 ：

java
    
    复制代码
    
    /** * 基础节点 */ public static class Node { protected int hash; protected String key; protected String value; // 基于 next 指向下一个节点从而形成一个链表结构 protected Node next; } /** * 树节点 ，实际上继承了 Node ，意味着每个 TreeNode 实际也包含数据对象 */ public static class TreeNode extends Node { // 父节点 TreeNode parent; // 左子节点 TreeNode left; // 右子节点 TreeNode right; // 上一节点用于生成双向链表,便于树形操作 TreeNode prev; boolean red; public TreeNode(Node node) { this.key = node.key; this.value = node.value; this.next = node.next; this.hash = node.hash; } }

> 核心流程操作 ：

java
    
    复制代码
    
    public static void main(String[] args) { // 插入一个数据 HashMapDemo mapDemo = new HashMapDemo(); mapDemo.putVal("test", "1"); } /** * HashMap 底层数组结构 , 每一个 Node 对应一个实际的对象 */ Node[] table = null; /** * 树化条件,超过该条件则进行红黑树转化 */ static final int TREEIFY_THRESHOLD = 8; /** * 解除树化条件,小于该条件则解除树化 */ static final int UNTREEIFY_THRESHOLD = 6; /** * 红黑树的操作一般都是基于插入操作来实现的 */ public void putVal(String key, String value) { int hash = getHash(key); // S0 : 先获取 Hash Node newNode = new Node(getHash(key), key, value, null); // S1 : 判断桶中是否存在元素, 如果不存在元素 ，直接添加 if (table[hash] == null) { table[hash] = newNode; return; } // S2 : 先添加到链表中,判断添加后的长度是否超过最大长度 Node currentNode = table[hash]; boolean isAdd = addNode(currentNode, newNode); // S3 : 超过最大长度,进行树化操作 if (isAdd) { treeifyBin(currentNode); } } // 模拟Hash冲突 , 只有 Hash 冲突时才会触发 private static int hash(String key) { return 10; } private static boolean addNode(Node head, Node newNode) { int length = 0; Node lastNode = head; // S2-1 :循环整个链表, 把数据加入链表最后一位 for (; lastNode != null; lastNode = lastNode.next) { length++; } lastNode.next = newNode; // S2-2 :假代码，模拟当前链表长度超过树化阈值 return length > TREEIFY_THRESHOLD; } private static void treeifyBin(Node head) { TreeNode treeNode = null; // S3-1 : 执行树华，先将节点转换为树节点 ， 本质上形成的还是一个树形链表 for (Node currentNode = head; currentNode != null; currentNode = currentNode.next) { if (treeNode == null) { treeNode = new TreeNode(currentNode); } else { treeNode.next = new TreeNode(currentNode); } } // S3-2 : 执行树华逻辑 treeify(treeNode); } private static void treeify(TreeNode treeNode) { // S3-3 : 树形转换，此处略过 }

### 3.2 高级问题集锦 ###

> 什么时候红黑树会解除树化 ？

*  桶中的元素数量下降到一定阈值以下（UNTREEIFY\_THRESHOLD=6）时，如果再**触发删除节点**时，则会解除树化。
 *  **当整体容量缩容的时候**，Hash 取模会发生变化，（**resize**）此时也有可能触发解除树华

### 3.3 红黑树转换精华 ###

红黑树的代码很有意思，但是全记住不容易，掌握其中最重要的几点就足够了 ：

> 树链表转红黑树 : treeify(Node<K,V>\[\] tab)

*  S1 : 先预设 **Root 节点为 null** ，然后开始遍历所有的节点
 *  S2 : 将每个树节点从树链表中抽离出来，为**其初始化左右子节点（null）**
 *  S3 : 如果是第一个节点，则直接设置为root ，如果不是第一个节点，则**基于大小比较放在对应的节点侧**
 *  S4 : 调用 **balanceInsertion** 方法对树进行结构调整
 *  S5 : 返回调整后的root节点，移动到数组中，**作为入口的首位**

![image.png][image.png 1]

> 平衡的原理 ：

平衡的这一段代码是整个红黑树的精华，单独拉出来写一篇文章都足够了，篇幅有限，只说几个关键点 ：

*  S1 : 先把插入节点定义为红色 ，然后按照大小插入指定位置
 *  S2 : 从当前节点开始回到根节点 , 在这个过程中进行节点的位移和染色 ，通常包括2种位置 ，3种情况
    
     *  2 种位置 ： 当前节点的父节点是左子节点还是右子节点 （用于确定是左旋还是右旋）
     *  3 种情况 ： 树节点 （当前父节点的兄弟节点）的颜色和位置
        
         *  叔节点是红色 （修改颜色，上移当前节点）
         *  叔节点是黑色，且 x 是右子节点 （进行旋转）
         *  叔节点是黑色，且 x 是左子节点 （修改颜色，进行旋转）

![b872c054eabc482da0b557b9f5f47f31.gif][]

如果知道了这个流程，和具体旋转的方式，那么代码就很容易看清楚了 ，无非就像下面的这种方式

**再细节就不深入了，等后面出针对性的文章吧，这一块不自己写个始终差点意思。**

java
    
    复制代码
    
    x.parent.red = false; // 将父节点设为黑色 y.red = false; // 将叔节点设为黑色 x.parent.parent.red = true; // 将祖父节点设为红色 x = x.parent.parent; // 将 x 上移到祖父节点 rotateRight(root, x.parent.parent); // 右旋转 rotateLeft(root, x.parent.parent); // 左旋转

> 解除树化 ：

原因 ：**节省空间**，上面也能看的出来 ，TreeNode 包含了 pre ,next ,parent 等信息，会占用大量内存

解除树化主要在 **resize 和 removeNode** 逻辑中进行 ，resize 主要为了控制容量，通常在以下场景中可能会触发 Resize 操作 ：

*  插入元素时 ：在插入数据的时候，如果触发了阈值, 则会触发resize ，包括不限定于插入，合并，等等
 *  直接手动调用或者 Map 初始化时

在 untreeify 中进行解除树化操作，处理逻辑很简单 ：

*  S1 : for 循环节点的 next 属性，**把属性转换为 Node 对象**
 *  S2 : 把 Node 按照 **Next 属性连接的方式生成链表**

**PS ：哪怕转换成了 TreeNode ，但是由于TreeNode 继承了 Node ，所以 next 属性是保留的，也可以通过 next 循环所有的变量**

## 总结 ##

看完这篇还能被问住，那不怪你，那是面试官的问题。

[image.png]: https://img-blog.csdnimg.cn/img_convert/7fe531046bc16c034e70d1753467e6b8.webp?x-oss-process=image/format,png
[image.png 1]: https://img-blog.csdnimg.cn/img_convert/39c78ba382dad35e6de99e4d0f2a5cd8.webp?x-oss-process=image/format,png
[b872c054eabc482da0b557b9f5f47f31.gif]: https://img-blog.csdnimg.cn/b872c054eabc482da0b557b9f5f47f31.gif