HashMap相关面试题（哈希表、HashMap的实现原理、HashMap的put方法的具体流程、HashMap的扩容机制、HashMap的寻址算法）

文章目录

1. 散列表（哈希表）
- 1.1 散列表的概念
- 1.2 散列函数
- 1.3 散列冲突
- 1.4 散列冲突-链表法（拉链法）
- - 1.4.1 插入操作
  - 1.4.2 查找和删除操作
2. HashMap的实现原理
3. HashMap 的 put 方法的具体流程
4. HashMap 的扩容机制
5. HashMap 的寻址算法
6. JDK 1.7 中 HashMap 的多线程死循环问题

1. 散列表（哈希表）

在了解 HashMap 前，我们先来了解一下散列表

1.1 散列表的概念

散列表（Hash Table）又名哈希表，允许我们通过一个键（Key）直接快速地找到对应的值（Value）在内存中的存储位置

散列表由数组演化而来，利用了数组支持按下标进行随机访问数据的特性

我们来看一个场景：假设有 100 个人参加马拉松，编号是 [1, 100] ，我们如果要查看某个选手的具体信息，只需要知道选手的编号

在这里插入图片描述

当然，实际场景可能没有这么简单，我们来看一个升级的场景：假设有 100 个人参加马拉松，不采用 [1, 100] 的自然数对选手进行编号，选手的编号有一定的规则，比如：2023ZHBJ001（其中 2023 代表年份，ZH 代表中国，B 代表北京，001 代表选手原来的编号）

此时选手的编号 2023ZHBJ001 不能直接作为数组的下标，该怎么办呢？

我们可以将选手的编号通过某种方式转换为数组的下标，然后将选手的信息存入数组中对应的位置

在这里插入图片描述

那具体该怎么转换呢？

一般来说，将将选手的编号转换为数组的下标，需要借助散列函数

在这里插入图片描述

1.2 散列函数

将键（key）映射为数组下标的函数叫做散列函数，可以表示为 hashValue = hash(key)

散列函数的基本要求：

散列函数计算得到的散列值必须是大于等于 0 的正整数，因为 hashValue 需要作为数组的下标
如果 key1 == key2，那么经过 hash 后得到的哈希值也必相同，即：hash(key1) == hash(key2)
如果 key1 != key2，那么经过 hash 后得到的哈希值也必不相同，即：hash(key1) != hash(key2)

1.3 散列冲突

在实际情况下，想找一个散列函数能够做到对于不同的 key 计算得到的散列值都不同几乎是不可能的，即便像著名的 MD5、SHA 等哈希算法也无法避免这一情况，这就是散列冲突（也叫哈希冲突，哈希碰撞，就是指多个 key 映射到了数组的同一个下标位置)

在这里插入图片描述

数组的空间越小，发生散列冲突的概率越大，既然有冲突，我们就要解决冲突

1.4 散列冲突-链表法（拉链法）

在散列表中，数组的每个下标位置我们可以称之为桶（bucket）或者槽（slot），每个桶（槽）会对应一条链表，所有散
列值相同的元素我们都放到相同槽位对应的链表中

在这里插入图片描述

下面我们来分析一下，如果使用链表法的话，操作数据的时间复杂度是多少

1.4.1 插入操作

通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，插入的时间复杂度是 O₍₁₎

1.4.2 查找和删除操作

当查找、删除一个元素时，我们同样需要通过散列函数计算出元素所在的桶，然后遍历链表查找元素或者删除元素

分析查找和删除操作的时间复杂度，我们只需要分析查找操作即可，因为删除元素之前也需要先找到元素所在的桶和元素在链表中所在的位置（删除操作耗时可以忽略不计，因为链表删除元素的速度是非常快的，只需要改变链表中某些节点的指针指向）

查找操作的时间复杂度分为两种情况：

平均情况（数组中元素的分布是比较均匀的，每个桶对应的链表的元素也不多）
数据量很大，产生了大量哈希冲突

平均情况下，基于链表法解决冲突时查询的时间复杂度是 O₍₁₎，因为查找元素的时候，只需要通过几次简单运算就能得到数据，效率比较高

数据量很大，产生了大量哈希冲突的情况下，会把多个数据挂到同一桶的链表下，链表将会变得很长，我们需要遍历链表才能获取到指定的元素，遍历链表的时间复杂度是 O_(n) ，所以查找操作的时间复杂度也变成了 O_(n)，查找操作的效率将会变得很低下

在这里插入图片描述

那该怎么解决这个问题呢？我们可以将链表法中的链表改造为其他高效的动态数据结构，比如红黑树，红黑树查询操作的时间复杂度是 O_(n)

在这里插入图片描述

将链表法中的链表改造红黑树还有一个非常重要的原因，可以防止 DDos 攻击（可以理解为有人恶意攻击，伪造了很多的 key ，造成严重的哈希冲突，导致哈希表中每个桶对应的链表变得十分冗长，进而导致访问散列表中的元素时效率大大降低）

DDos 攻击：Distributed Denial ofService，分布式拒绝服务攻击

处于不同位置的多个攻击者同时向一个或数个目标发动攻击，或者一个攻击者控制了位于不同位置的多台机器，并利用这些机器对受害者同时实施攻击
由于攻击的发出点是分布在不同地方的，这类攻击称为分布式拒绝服务攻击，其中的攻击者可以有多个

2. HashMap的实现原理

在这里插入图片描述

HashMap 底层采用的数据结构：哈希表（数组 + 链表 + 红黑树）

当我们往 HashMap 中 put 元素时，会利用 key 的 hashCode 重新 hash 计算出当前对象的元素在数组中的下标

我们可以简单地查看一下 HashMap 类 put 方法的源码

在这里插入图片描述

至于 (h = key.hashCode()) ^ (h >>> 16) 代码是什么意思，可以查看本文的 5. HashMap 的寻址算法部分

存储元素时，如果出现 hash 值相同的 key，会有两种情况：

如果 key 相同，则覆盖原始值
如果 key 不同(出现冲突)，则将当前的 key-value 放入链表或红黑树中

注意：当链表的长度大于 8 且 HashMap底层的数组长度大于 64 时，链表才转换为红黑树

在这里插入图片描述

获取元素时，先找到 hash 值对应的下标，再进一步判断 key 是否相同，从而找到对应的值

但是，面试官可能会追问：JDK 1.7 的HashMap 和 JDK 1.8 的 HashMap 有什么区别

JDK 1.8 之前采用的是拉链法（将链表和数组相结合），也就是说 HashMap 的底层是一个链表数组，数组中每一格就是一个链表，如果遇到哈希冲突，则将冲突的值加到链表中即可

JDK 1.8 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8），并且数组长度大于 64 时，将链表转化为红黑树，以减少搜索时间，扩容（resize）时，如果红黑树的节点数小于等于临界值 6 个，则退化成链表

3. HashMap 的 put 方法的具体流程

在这里插入图片描述

我们先来看一下 HashMap 中的常见属性（aka：also known as，又名）

在这里插入图片描述

以下是 HashMap 无参构造函数的源码

在这里插入图片描述

可以看到：

HashMap 是懒惰加载，在创建对象时并没有初始化数组
在无参的构造函数中，设置了默认的加载因子是 0.75

要了解 HashMap 的 put 方法的具体原理，需要阅读 put 方法的源码

在阅读源码之前，我们先看一下 HashMap 添加元素时的流程图

在这里插入图片描述

以下是 HashMap 的 put 方法的摘录

在这里插入图片描述

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 判断数组是否未初始化if ((tab = table) == null || (n = tab.length) == 0)// 如果未初始化，调用resize方法 进行初始化n = (tab = resize()).length;// 通过 & 运算求出该数据（key）的数组下标并判断该下标位置是否有数据if ((p = tab[i = (n - 1) & hash]) == null)// 如果没有，直接将数据放在该下标位置tab[i] = newNode(hash, key, value, null);// 该数组下标有数据的情况else {Node<K,V> e; K k;// 判断该位置数据的key和新来的数据是否一样if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 如果一样，证明为修改操作，该节点的数据赋值给e,后边会用到e = p;// 判断是不是红黑树else if (p instanceof TreeNode)// 如果是红黑树的话，进行红黑树的操作e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 新数据和当前数组既不相同，也不是红黑树节点，证明是链表else {// 遍历链表for (int binCount = 0; ; ++binCount) {// 判断next节点，如果为空的话，证明遍历到链表尾部了if ((e = p.next) == null) {// 把新值放入链表尾部p.next = newNode(hash, key, value, null);// 因为新插入了一条数据，所以判断链表长度是不是大于等于8if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st// 如果是，进行转换红黑树操作treeifyBin(tab, hash);break;}// 判断链表当中有数据相同的值，如果一样，证明为修改操作if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;// 把下一个节点赋值为当前节点p = e;}}// 判断e是否为空（e值为修改操作存放原数据的变量）if (e != null) { // existing mapping for key// 不为空的话证明是修改操作，取出老值V oldValue = e.value;// 一定会执行  onlyIfAbsent传进来的是falseif (!onlyIfAbsent || oldValue == null)// 将新值赋值当前节点e.value = value;afterNodeAccess(e);// 返回老值return oldValue;}}// 计数器，计算当前节点的修改次数++modCount;// 当前数组中的数据数量如果大于扩容阈值if (++size > threshold)// 进行扩容操作resize();// 空方法afterNodeInsertion(evict);// 添加操作时 返回空值return null;
}

4. HashMap 的扩容机制

在这里插入图片描述

要了解 HashMap 的扩容机制，我们需要阅读 resize 方法的源码

在阅读 resize 方法的源码前，我们先来看一下 HashMap 扩容的流程

在这里插入图片描述

以下是 HashMap 的 resize 方法的摘录

在这里插入图片描述

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;// 如果当前数组为null的时候，把oldCap老数组容量设置为0int oldCap = (oldTab == null) ? 0 : oldTab.length;// 老的扩容阈值int oldThr = threshold;int newCap, newThr = 0;// 判断数组容量是否大于0，大于0说明数组已经初始化if (oldCap > 0) {// 判断当前数组长度是否大于最大数组长度if (oldCap >= MAXIMUM_CAPACITY) {// 如果是，将扩容阈值直接设置为int类型的最大数值并直接返回threshold = Integer.MAX_VALUE;return oldTab;}// 如果在最大长度范围内，则需要扩容 OldCap << 1等价于oldCap*2// 运算过后判断是不是最大值并且oldCap需要大于16else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold 等价于oldThr*2}// 如果oldCap<0，但是已经初始化了，像把元素删除完之后的情况，那么它的临界值肯定还存在// 如果是首次初始化，它的临界值则为0else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;// 数组未初始化的情况，将阈值和扩容因子都设置为默认值else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 初始化容量小于16的时候，扩容阈值是没有赋值的if (newThr == 0) {// 创建阈值float ft = (float)newCap * loadFactor;// 判断新容量和新阈值是否大于最大容量newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 计算出来的阈值赋值threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})// 根据上边计算得出的容量 创建新的数组Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];// 赋值table = newTab;// 扩容操作，判断不为空证明不是初始化数组if (oldTab != null) {// 遍历数组for (int j = 0; j < oldCap; ++j) {Node<K,V> e;// 判断当前下标为j的数组如果不为空的话赋值个e，进行下一步操作if ((e = oldTab[j]) != null) {// 将数组位置置空oldTab[j] = null;// 判断是否有下个节点if (e.next == null)// 如果没有，就重新计算在新数组中的下标并放进去newTab[e.hash & (newCap - 1)] = e;// 有下个节点的情况，并且判断是否已经树化else if (e instanceof TreeNode)// 进行红黑树的操作((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 有下个节点的情况，并且没有树化（链表形式）else {// 比如老数组容量是16，那下标就为0-15// 扩容操作*2，容量就变为32，下标为0-31// 低位：0-15，高位16-31// 定义了四个变量// 低位头 低位尾Node<K,V> loHead = null, loTail = null;// 高位头 高位尾Node<K,V> hiHead = null, hiTail = null;// 下个节点Node<K,V> next;// 循环遍历do {// 取出next节点next = e.next;// 通过 与操作 计算得出结果为0if ((e.hash & oldCap) == 0) {// 如果低位尾为null，证明当前数组位置为空，没有任何数据if (loTail == null)// 将e值放入低位头loHead = e;// 低位尾不为null，证明已经有数据了else// 将数据放入next节点loTail.next = e;// 记录低位尾数据loTail = e;}// 通过 与操作 计算得出结果不为0else {// 如果高位尾为null，证明当前数组位置为空，没有任何数据if (hiTail == null)// 将e值放入高位头hiHead = e;// 高位尾不为null，证明已经有数据了else// 将数据放入next节点hiTail.next = e;// 记录高位尾数据hiTail = e;}} // 如果e不为空，证明没有到链表尾部，继续执行循环while ((e = next) != null);// 低位尾如果记录的有数据，是链表if (loTail != null) {// 将下一个元素置空loTail.next = null;// 将低位头放入新数组的原下标位置newTab[j] = loHead;}// 高位尾如果记录的有数据，是链表if (hiTail != null) {// 将下一个元素置空hiTail.next = null;// 将高位头放入新数组的(原下标+原数组容量)位置newTab[j + oldCap] = hiHead;}}}}}// 返回新的数组对象return newTab;
}

5. HashMap 的寻址算法

在这里插入图片描述

这个问题主要想问的是如何找到元素在 HashMap 底层数组的哪一个桶中

要回答这个问题，我们需要阅读 HashMap 的源码

在这里插入图片描述

其中的 (h = key.hashCode()) ^ (h >>> 16) 代码可以理解为一个扰动算法，主要是为了让生成的 hash 值在 HashMap 底层数组中分布更加均匀，减小哈希冲突的概率

为什么加上 ^ (h >>> 16) 就能减小哈希冲突的概率呢，有以下原因：

高位参与运算：
- key.hashCode() 返回一个整型哈希值，这个值是由对象的内存地址计算得出的
- h >>> 16 是一个无符号右移操作，它将哈希值的高 16 位移动到低 16 位
- 使用 ^（异或运算符）将哈希值的高 16 位与低 16 位进行混合，这样可以让高位的信息参与到低位运算中，从而减少哈希碰撞的几率
减少哈希碰撞：
- 如果不进行这样的操作，当哈希表的大小较小时，哈希值的高位部分将不会对桶索引的计算产生影响，因为桶索引通常是通过取模操作（h & (length-1)）来得到的，这会使得只有低位部分参与运算
- 通过将高位与低位混合，可以使得哈希值在哈希表中分布得更均匀，减少碰撞

那 (n - 1) & hash 代码又是什么意思呢？n 是 HashMap 底层数组的长度，(n - 1) & hash 的作用就是找到元素在 HashMap 底层数组中的下标位置，其实取模运算也能完成这个操作，那为什么要用 & 运算呢，主要是因为 & 运算的效率比取模运算高，但 HashMap 底层数组的长度必须要是 2 的 n 次幂

其实之所以这两个运算能等价，就是因为数组的长度是 2 的 n 次幂，例如，当数组的长度是 16 ，hash 值是 25190759513 时，25190759513 对 16 取余后得到的是 15

16 - 1 = 15，15 的二进制是 01111111，25190759513 & 01111111 相当于对 16 取余，因为进行 & 运算时，16、32、64 等高位全是 0，8、4、2、1 等低位全是 1，相当于 hash 值中大于等于 16 的部分全部截掉，只保留了小于 16 的部分

面试官可能会追问：为什么 HashMap 底层数组的长度一定是 2 的 n 次幂呢，主要有两个原因：