Java 中 HashMap 数据结构分析（语言无关）

港控/mmm° 2023-07-22 09:21 3阅读 0赞

### 文章目录 ###

*   *   *  Part1 数组、链表、红黑树简介
         *   *  1、二叉搜索树
             *  2、AVL树与红黑树
             *   *  2.1、AVL树
                 *  2.2、红黑树与AVL树的比较
                 *  2.3、红黑树的性质
                 *  2.4、红黑树的插入
         *  Part2 HashMap工作原理分析
         *   *  1、HashMap 用到的散列的原理
             *  2、用数组和链表实现 HashMap
         *  Part3 HashMap的实现
         *   *  1、插入
             *  2、查找
             *  3、扩容

### Part1 数组、链表、红黑树简介 ###

java 中的 HashMap 用到的数据结构：

1.  **数组**：查询快，插入和删除慢，底层实现依赖操作系统，在一块连续内存空间内，存储数据。
2.  **链表**：查询慢，插入和删除快，由一个个（节点、指针）组成。查询需要遍历整个链条。
3.  **红黑树**：红黑树借鉴了平衡二叉树的平衡思想，不妨先来看看平衡二叉树是怎么回事，而平衡二叉树又是从二叉搜索树来的。

我们先说二叉搜索树，再说平衡二叉树，最后红黑树。

#### 1、二叉搜索树 ####

又称之为二叉排序树（二叉查找树），它或许是一棵空树，或许是具有以下性质的二叉树：

*  若他的左子树不为空，则左子树上所有节点的值都小于根节点的值；
 *  若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
 *  它的左右子树也分别是二叉搜索树。

![format_png][]

> 二叉搜索树的这种特性，使得我们在此二叉树上查找某个值就很方便了，从根节点开始，若要寻找的值小于根节点的值，则在左子树上去找，反之则去右子树查找，知道找到与值相同的节点。插入节点也是一样的道理，从根节点出发，所要插入的值，若小于根节点则去左子树寻找该节点所对应的位置，反之去右子树寻找，直到找到该节点合适的位置。

二叉搜索树的特性便于我们进行查找插入删除等一系列操作，其时间复杂度为`O（logn）`，但是，如果遇见最差的情况，比如以下这棵树：

![format_png 1][]

> 这棵树，说是树，其实它已经退化成链表了，但从概念上来看，它仍是一棵二叉搜索树，只要我们按照逐次增大，如1、2、3、4、5、6的顺序构造一棵二叉搜索树，则形如上图。那么插入的时间复杂度就变成了`O(n)`，导致这种糟糕的情况原因是因为这棵树极其不平衡，右树的重量远大于左树，因此我们提出了叫平衡二叉搜索树的结构，又称之为 AVL 树，是因为平衡二叉搜索树的发明者为 Adel’son-Vel’skii 和Landis 二人。

#### 2、AVL树与红黑树 ####

它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均查找长度。

##### 2.1、AVL树 #####

AVL树的性质：

*  左子树与右子树高度之差的绝对值不超过1；
 *  树的每个左子树和右子树都是AVL树；
 *  每一个节点都有一个平衡因子（balance factor），任一节点的平衡因子是-1、0、1（每一个节点的平衡因子 = 右子树高度 - 左子树高度）。

**解决了树不平衡的问题，为什么还要红黑树呢？**

> 创建一颗平衡二叉树的成本其实不小，为了让它重新维持在一个平衡状态，就需要对其进行旋转处理。这个时候就有人开始思考，并且提出了红黑树的理论，那么红黑树到底比AVL树好在哪里？

##### 2.2、红黑树与AVL树的比较 #####

红黑树与AVL树的比较：

*  AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu 太快，可以忽略性能差异 ；
 *  红黑树的插入删除比 AVL 树更便于控制操作 ；
 *  红黑树整体性能略优于 AVL 树（红黑树旋转情况少于 AVL 树）。

##### 2.3、红黑树的性质 #####

红黑树的性质：

红黑树是一棵二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是 RED ,也可以是 BLACK ；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。

具体性质如下：

*  每个节点颜色不是黑色，就是红色；
 *  根节点是黑色的；
 *  如果一个节点是红色，那么它的两个子节点就是黑色的（没有连续的红节点）；
 *  对于每个节点，从该节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点。

那么为什么当满足以上性质时，就能保证最长路径不超过最短路径的二倍了呢？我们分析一下：

![format_png 2][]

最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，最后黑色节点相同时，最长路径刚好是最短路径的两倍

##### 2.4、红黑树的插入 #####

红黑树插入节点过程大致分析：

RBTree 为二叉搜索树，我们按照二叉搜索树的方法对其进行节点插入

RBTree 有颜色约束性质，因此我们在插入新节点之后要进行颜色调整

具体步骤如下：

*  根节点为NULL，直接插入新节点并将其颜色置为黑色；
 *  根节点不为NULL，找到要插入新节点的位置；
 *  插入新节点；
 *  判断新插入节点对全树颜色的影响，更新调整颜色。

### Part2 HashMap工作原理分析 ###

#### 1、HashMap 用到的散列的原理 ####

**什么是散列？**

Hash（哈希），又称“散列”，通过计算哈希值，打破元素之间原有的关系，使集合中的元素按照散列函数的分类进行排列。

计算 hashCode 的过程就称作 哈希，在某种程度上，散列是与排序相反的一种操作，排序是将集合中的元素按照某种方式比如字典顺序排列在一起。

在介绍一些集合时，我们总强调需要重写某个类的 equlas() 方法和 hashCode() 方法，确保唯一性。这里的 hashCode() 表示的是对当前对象的唯一标示。

**为什么要用到散列？**

通过 哈希 计算，可以大大减少比较次数，使用数组或者链表来存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在查找某个元素是否存在的过程中，数组和链表都需要挨个循环比较。

数组中如果找到某个值在什么位置，需要循环遍历整个数组，时间复杂度为O(n),而Hash表的时间复杂度基本为O(1)。因为哈希通过一次计算大幅度缩小查找范围，比从全部数据里查找速度要快。

**Hash（）函数的特点**

*  相同的输入得到相同的HashCode；
 *  不同的HashCode一定对应不同的输入；
 *  不同的输入可能产生相同的HashCode ，这种情况称为\*\*哈希冲突，\*\*在HashMap中使用拉链法解决冲突；
 *  如果两个对象的HashCode相同，不代表两个对象就相同，只能说明这两个对象在散列存储结构中，存放于同一个位置。

#### 2、用数组和链表实现 HashMap ####

基本数据结构就介绍到这里了，下面来看一下HashMap如何借助这些简单的数据结构实现高效的

![format_png 3][]

1.  **基于数组和链表的结构分析**

通过上图可以看出，使用Hash函数和数组结构，就可以快速定位Key在数组的上的位置，为了解决哈希冲突，引入了链表来存放冲突的K-V对。

1.  **链表查找时间复杂度为O(n)如何优化（树化过程）**

JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。

当 HashMap 中有大量的元素都存放到同一个桶（即数组的一个元素）中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。

HashMap 通过引入红黑树来解决这个问题，使复杂度降到了O(logn).

### Part3 HashMap的实现 ###

**增加和删除操作**

下面简介一下 HashMap 的插入、查找、扩容的基本逻辑

#### 1、插入 ####

**插入逻辑如下:**

*  先调用 hash() 方法计算哈希值，然后调用 putVal() 方法中根据哈希值进行相关操作，如果当前 哈希表内容为空，新建一个哈希表；
 *  如果要插入的桶中没有元素，新建个节点并放进去；
 *  否则从桶中第一个元素开始查找哈希值对应位置；
 *  如果桶中第一个元素的哈希值和要添加的一样，替换，结束查找；
 *  如果第一个元素不一样，而且当前采用的还是 JDK 8 以后的树形节点，调用 putTreeVal() 进行插入；
 *  否则还是从传统的链表数组中查找、替换，结束查找；
 *  当这个桶内链表个数大于等于 8，就要调用 treeifyBin() 方法进行树形化；
 *  最后检查是否需要扩容。

#### 2、查找 ####

**查找逻辑如下**：

*  先计算哈希值;
 *  然后再用 哈希函数 计算出桶的位置;
 *  在桶里的链表进行遍历查找。

#### 3、扩容 ####

**扩容操作**

**扩容过程中几个关键的点：**

*  新初始化哈希表时，容量为默认容量，阈值为 `容量*加载因子`；
 *  已有哈希表扩容时，容量、阈值均翻倍；
 *  如果之前这个桶的节点类型是树，需要把新哈希表里当前桶也变成树形结构；
 *  复制给新哈希表中需要重新索引（rehash）

[format_png]: /images/20230528/687078e5c957402ab262bd9fdb7d474d.png
[format_png 1]: /images/20230528/9e179cbef9384c9fbe90a9cc6be28192.png
[format_png 2]: /images/20230528/d29170b3a80040de9777edf6d27d8706.png
[format_png 3]: /images/20230528/7f6df5be566b4b389ff6b00dee34ae75.png