请点赞重视，你的支撑对我含义严重。

Hi，我是小彭。本文已收录到 GitHub AndroidFamily 中。这儿有 Android 进阶成长常识系统，有情投意合的朋友，重视大众号 [彭旭锐] 带你树立中心竞争力。

提示：直接看这两篇:

  • 怎么完成一个优秀的 HashTable 散列表？
  • 万字 HashMap 详解，根底（高雅）永不过时

前言

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());  2112
System.out.println(str2.hashCode());  2112 散列抵触

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

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 的匹配判别

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

3.5 为什么常常运用 String 作为 HashMap 的 Key？

这个问题我以为有 2 个原因：

  • 1、不可变类 String 能够防止修改后无法定位键值对： 假定 String 是可变类，当咱们在 HashMap 中构建起一个以 String 为 Key 的键值对时，此时对 String 进行修改，那么经过修改后的 String 是无法匹配到方才构建过的键值对的，因为修改后的 hashCode 或许是改变的。而不可变类能够规避这个问题。
  • 2、String 能够满足 Java 关于 hashCode() 和 equals() 的通用约定： 既两个目标 equals() 相同，则 hashCode() 相同，假如 hashCode() 相同，则 equals() 不一定相同。这个约定是为了防止两个 equals() 相同的 Key 在 HashMap 中存储两个独立的键值对，引起矛盾。

4. HashMap 线程安全性

4.1 HashMap 线程不安全的原因

  • 数据掩盖问题：假如两个线程并发履行 put 操作，而且两个数据的 hash 值抵触，就或许呈现数据掩盖（线程 A 判别 hash 值方位为 null，还未写入数据时挂起，此时线程 B 正常插入数据。接着线程 A 取得时间片，因为线程 A 不会从头判别该方位是否为空，就会把方才线程 B 写入的数据掩盖掉）；
  • 环形链表问题： 在 HashMap 触发扩容时，而且正好两个线程一起在操作同一个链表时，就或许引起指针混乱，构成环型链条（因为 JDK 1.7 版本选用头插法，在扩容时会翻转链表的顺序，而 JDK 1.8 选用尾插法，再扩容时会保持链表原本的顺序）。

4.2 HashMap 和 hashTable 的差异？

  • 1、hashTable 对每个办法都增加了 synchronized；
  • 2、hashTable 不允许 null 作为 Key；

4.3 ConcurrentHashMap 分段锁的原理

HashMap 呈现并发问题的中心在于多个线程一起操作同一个链表，而 ConcurrentHashMap 在操作链表前会用 synchronized 对链表的首个元素加锁，然后防止并发问题。

参考资料

  • 散列算法—— 维基百科
  • 都说 HashMap 是线程不安全的，究竟体现在哪儿？ —— developer 著
  • Java源码分析：HashMap 1.8 相关于1.7 究竟更新了什么？ —— Carson 著
  • 《数据结构与算法之美》（第21、22章） —— 王争 讲，极客时间 出品

我是小彭，带你构建 Android 常识系统。技术和职场问题，请重视大众号 [彭旭锐] 私信我提问。

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

我正在参与技术社区创作者签约方案招募活动，点击链接报名投稿。