简答一波 HashMap 常见八股口试题 —— 算法系列（2）

源代码 · 2024-9-28 09:17:10

请点赞，你的点赞对我意义庞大，满足下我的虚荣心。
? Hi，我是小彭。本文已收录到 GitHub · Android-NoteBook 中。这里有 Android 进阶发展知识体系，有守望相助的朋侪，欢迎跟我一起发展。

前言

HashMap 是我们熟悉的散列表实现，也是 “口试八股文” 的标准题库之一。今天，我给出一份 HashMap 高频口试题口述简答答案，渴望对你刷题有资助。如果能帮上忙请务必点赞加关注，这对我非常紧张。
这篇文章是数据布局与算法系列文章第 2 篇，专栏文章列表：
一、数据布局底子：

1、线性表（ArrayList & LinkedList 实现）
2、散列表（HashMap 实现）（本文）
3、队列
4、栈
5、二叉树（高频口试题与解题框架）
6、图

二、算法头脑：

1、回溯算法解题框架
2、二分查找解题框架
3、排序算法
4、贪心算法解题框架
5、动态规划解题框架

三、高级数据布局：

1、前缀和数组（区间查询标题）
2、线段树（区间查询标题）
3、树状数组（区间查询标题）
4、字典树
5、单调队列（下一个更大元素标题）
6、单调栈（滑动窗口最大值标题）
7、并查集（动态连通标题）
8、二叉堆（优先队列）

四、刷题题解：

1、高楼丢鸡蛋（动态规划）
2、盘算器（逆波兰表达式）
3、链表（高频口试题）
4、相交链表 & 环形链表（高频口试题）

1. 熟悉散列表

1.1 散列表的作用

散列算法是散列表的焦点，也就做哈希算法或 Hash 算法，是一个意思。散列算法是一种将恣意长度输入转换为固定长度输出的算法，输出的结果就是散列值。基于散列算法实现的散列表，可以实现快速查找元素的特性。
总结一下散列算法的重要性质：
性质形貌1、单向性（基天性质）支持从输入天生散列值，不支持从散列值反推输入2、高效性（基天性质）单次散列运算盘算量低3、划一性相同输入重复盘算，总是得到相同散列值4、随机性散列值在输出值域的分布只管随机5、输入敏感性相似的数据，盘算后的散列值差异很大1.2 什么是散列辩论？

散列算法肯定是一种压缩映射，由于输入值域非常大乃至无穷大，而散列值域为一个固定长度的值域。例如，MD5 的输出散列值为 128 位，SHA256 的输出散列值为 256 位，这就存在 2 个差异的输入产生相同输出的大概性，即散列辩论，或哈希辩论、Hash Collision。
这着实只要用鸽巢原理（又称：抽屉原理）就很好明白了，假设有 10 个鸽巢，现有 11 只鸽子，无论分配多么均匀，也肯定有一个鸽巢里有两只乃至多只鸽子。举一个直接的例子，Java中的字符串 "Aa" 与 "BB" 的散列值就辩论了：
示例程序
String str1 = "Aa";String str2 = "BB";System.out.println(str1.hashCode()); 2112System.out.println(str2.hashCode()); 2112 散列辩论

1.3 怎样低落散列辩论概率

虽然散列辩论是无法完全克制的，但可以尽大概低落发生散列辩论的概率。例如：

1、优化散列算法，提高散列值随机性： 将散列值尽大概匀称分布到输出值域的范围内，克制出现 “堆积” 线程。否则，当大部分散列值都堆积在一小块地域上时，势必会增大辩论概率。例如，HashMap 包管容量为 2^n 次幂就是提高随机性的方法。
2、扩大输出值域（即扩容）： 在散列值尽大概匀称分布的条件下，扩大输出值域可以直接低落辩论概率。例如，HashMap 在到达阈值时实行扩容，本质上是扩大了输出值域。

2. HashMap 操持思绪

2.1 说一下 HashMap 的底层布局？

HashMap 的底层布局是一个 “数组 + 拉链” 的二维布局，在 Java 7 中利用的是数组 + 链表，而在 Java 8 中当链表长度大于 8 时会转换为红黑树。
那么为什么 HashMap 要接纳如许的操持呢？我分为 3 点来回答：

第 1 点：HashMap 的界说是一个散列表，这是一种支持快速查找元素的数据布局，那么其背后就一定会利用到数组随机访问的特点。因此，HashMap 的一维布局就是一个数组，数组元素是一个包罗 Key、Value 和 hashcode 的 Entry 节点。当我们须要访问聚集元素时，着实就是先通过 key 盘算 hashcode，再将 hashCode 对数组长度取余得到数组下标，末了通过下标去数组中找到对应的 Value；
第 2 点：从 Key 到数组下标的转换过程一定是一个压缩映射的过程，由于差异的 key 盘算的 hashCode 大概相同，差异的 hashCode 取余得到的数组下标也大概相同，这就是哈希辩论。通例的哈希辩论办理方法有开放地点法和拉链法等，而 HashMap 接纳的是拉链法来办理哈希辩论。
第 3 点：为什么 Java 8 要引入红黑树的操持呢？由于当辩论加剧的时间，在链表中寻找对应元素的时间复杂度是 O(n)，n 是链表长度。而利用红黑树（近似均衡的二叉搜刮树）的话，树形布局的复杂度一样平常跟树的高度有关，查找复杂度是 O(lgn)，时间复杂度更低。

2.2 为什么 HashMap 接纳拉链法而不是开放地点法？

我认为 Java 给予 HashMap 的定位是一个相对通用的散列表容器，它应该在面临各种输入的时间都表现稳固。而开辟地点法相对来说轻易出现数据堆积，在数据量较大时大概出现连续辩论的环境，性能不敷稳固。
我们可以举个反例，在 Java 原生的数据布局中，也存在利用开放地点法的散列表 —— 就是 ThreadlLocal。由于项目中不会大量利用 ThreadLocal 线程局部存储，以是它是一个小规模数据场景，这里利用开辟地点法是没标题的。
2.3 为什么 HashMap 用红黑树而不是均衡二叉树？

红黑树沉寂衡二叉树的区别在于它们的均衡强弱差异：

均衡二叉树寻求的是一种完全均衡的状态，它的界说是任何结点的左右子树的高度差不会高出 1，如许的上风是树的结点是很均匀分配的；
红黑树不寻求这种完全均衡，而是寻求一种弱均衡的状态，就是让整个树最长路径不会高出最短路径的 2 倍。如许的话，红黑树虽然断送了一部分查找的性能服从，但是可以或许变更一部分维持树均衡状态的资本。

而我们知道 HashMap 的操持定位应该是一个相对通用的散列表，那么它的操持者会渴望如许一个数据布局应该具备更强盛的稳固性，因此它才选择了红黑树。
3. HashMap 源码细节

3.1 HashMap 的初始容量

HashMap 的初始容量是 0，这是一种懒加载机制，直到第一次 put 利用才会初始化数组巨细，默认巨细是 16。
3.2 HashMap 扩容

扩容本质上是扩大了散列算法的输出值域，在散列值尽大概匀称分布的条件下，扩大输出值域可以直接低落辩论概率。固然，由于 HashMap 利用的是拉链法来办理散列辩论，扩容并不是必须的，但是不扩容的话会造成拉链的长度越来越长，导致散列表的时间复杂度会倾向于 O(n) 而不是 O(1)。
HashMap 扩容的触发机会出现在元素个数高出阈值（容量 * loadFactor）的时间时，会将聚集的一维数组扩大一倍，然后重新盘算每个元素的位置。
3.3 为什么 HashMap 的长度是 2^n 次幂？

这是为了只管将聚集元素均摊到数组的差异位置上。

我们知道 HashMap 在确定元素对应的数组下标时，是接纳了 hashCode 对数组长度取余的运算，它着实等价于 hashCode 对数组长度 - 1 的与运算（h % length 等价于 h & (lenght -1)，与运算服从更高，偶数才建立）；
而 2^n 次幂对应的 length - 1 恰恰满是 1（1000-1 = 111），如许就把影响下标的因素归结于 hashCode 自己，因而可以或许实现尽大概均摊。

3.4 HashMap 中 Key 的匹配判断

简答一波 HashMap 常见八股口试题 —— 算法系列（2）

所属分类: 问答交流

新帖推荐: 30日

推荐作品