当前位置：首页 > news >正文

【备战面试】每日10道面试题打卡-Day4

news 文章来源：https://blog.csdn.net/apple_51673523/article/details/129349766 2025/4/4 7:57:57

本篇总结的是Java集合知识相关的面试题，后续也会更新其他相关内容

文章目录

1、HashMap在JDK1.7和JDK1.8中有哪些不同？
2、HashMap 的长度为什么是2的幂次方？
3、HashMap的扩容操作是怎么实现的？
4、HashMap是怎么解决哈希冲突的？
5、HashMap 多线程导致死循环问题
6、HashMap、ConcurrentHashMap及Hashtable 的区别
7、HashMap的put方法的具体流程？
8、说一下 ArrayList 的优缺点
9、如果使用Object作为HashMap的Key，应该怎么办呢？
10、HashTable的底层实现知道吗？

1、HashMap在JDK1.7和JDK1.8中有哪些不同？

答：先看看两个版本HashMap的Hash函数，如下：

JDK1.7的Hash函数

static final int hash(int h){h ^= (h >>> 20) ^ (h >>>12);return h^(h >>> 7) ^ (h >>> 4);
}

JDK1.8的Hash函数

static final int hash(Onject key){    int h;    return (key == null) ? 0 : (h = key.hashCode())^(h >>> 16);
}

可以看到JDK1.8的函数经过了一次异或一次位运算一共两次扰动，而JDK1.7经过了四次位运算五次异或一共九次扰动。

这里简单解释下JDK1.8的hash函数，两次扰动分别是key.hashCode() 与 key.hashCode() 右移16位进行异或。这样做的目的是，高16位不变，低16位与高16位进行异或操作，进而减少碰撞的发生，高低Bit都参与到Hash的计算。如何不进行扰动处理，因为hash值有32位，直接对数组的长度求余，起作用只是hash值的几个低位。

区别

在这里插入图片描述

2、HashMap 的长度为什么是2的幂次方？

答：因为 HashMap 是通过 key 的hash值来确定存储的位置，但Hash值的范围是-2147483648到2147483647，不可能建立一个这么大的数组来覆盖所有hash值。所以在计算完hash值后会对数组的长度进行取余操作，如果数组的长度是2的幂次方， (length - 1)&hash 等同于 hash%length ，可以用(length - 1)&hash 这种位运算来代替%取余的操作进而提高性能。

使用位运算比取余性能高

3、HashMap的扩容操作是怎么实现的？

答：

初始值为16，负载因子为0.75，阈值为负载因子*容量；
resize() 方法是在 hashmap 中的键值对大于阀值时或者初始化时，就调用 resize() 方法进行扩容；
每次扩容，容量都是之前的两倍；
扩容时有个判断 e.hash & oldCap 是否为零，也就是相当于hash值对数组长度的取余操作，若等于0，则位置不变，若等于1，位置变为原位置加旧容量；

1.HashMap默认加载因子为什么选择0.75？

这个主要是考虑空间利用率和查询成本的一个折中。如果加载因子过高，空间利用率提高，但是会使得哈希冲突的概率增加；如果加载因子过低，会频繁扩容，哈希冲突概率降低，但是会使得空间利用率变低。具体为什么是0.75，不是0.74或0.76，这是一个基于数学分析（泊松分布）和行业规定一起得到的一个结论。

2.为什么不刚开始就使用红黑树？

因为红黑树的节点所占的空间是普通链表节点的两倍，但查找的时间复杂度低，所以只有当节点特别多时，红黑树的优点才能体现出来。至于为什么是8，是通过数据分析统计出来的一个结果，链表长度到达8的概率是很低的，综合链表和红黑树的性能优缺点考虑将大于8的链表转化为红黑树。
链表转化为红黑树除了链表长度大于8，还要HashMap 中的数组长度大于64。也就是如果HashMap 长度小于64，链表长度大于8是不会转化为红黑树的，而是直接扩容。

4、HashMap是怎么解决哈希冲突的？

答：哈希冲突： hashMap 在存储元素时会先计算 key 的hash值来确定存储位置，因为 key 的hash值计算最后有个对数组长度取余的操作，所以即使不同的 key 也可能计算出相同的hash值，这样就引起了hash冲突。 hashMap 的底层结构中的链表/红黑树就是用来解决这个问题的。

HashMap 中的哈希冲突解决方式可以主要从三方面考虑（以JDK1.8为背景）

拉链法

HasMap 中的数据结构为数组+链表/红黑树，当不同的 key 计算出的hash值相同时，就用链表的形式将Node结点（冲突的 key 及 key 对应的 value ）挂在数组后面。

hash函数

key 的hash值经过两次扰动， key 的 hashCode 值与 key 的 hashCode 值的右移16位进行异或，然后对数组的长度取余（实际为了提高性能用的是位运算，但目的和取余一样），这样做可以让hashCode 取值出的高位也参与运算，进一步降低hash冲突的概率，使得数据分布更平均。

红黑树

在拉链法中，如果hash冲突特别严重，则会导致数组上挂的链表长度过长，性能变差，因此在链表长度大于8时，将链表转化为红黑树，可以提高遍历链表的速度。

5、HashMap 多线程导致死循环问题

答：由于JDK1.7的 hashMap 遇到hash冲突采用的是头插法，多线程会导致HashMap的Entry链表形成环形数据结构在多，线程情况下会存在死循环问题，但JDK1.8已经改成了尾插法，不存在这个问题了。但需要注意的是JDK1.8中的 HashMap 仍然是不安全的，在多线程情况下使用仍然会出现线程安全问题。

6、HashMap、ConcurrentHashMap及Hashtable 的区别

答：如下图：

在这里插入图片描述

7、HashMap的put方法的具体流程？

答：如下图：
在这里插入图片描述

8、说一下 ArrayList 的优缺点

答：
ArrayList的优点

ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了 RandomAccess 接口，因此查找的时候非常快。
ArrayList 在顺序添加一个元素的时候非常方便。

ArrayList 的缺点

删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。
插入元素的时候，也需要做一次元素复制操作，缺点同上。

ArrayList 比较适合顺序添加、随机访问的场景。

9、如果使用Object作为HashMap的Key，应该怎么办呢？

答：需要重写hashCode()和equals()方法：

重写 hashCode() 方法，因为需要计算hash值确定存储位置；
重写 equals() 方法，因为需要保证 key 的唯一性；

10、HashTable的底层实现知道吗？

答：HashTable 的底层数据结构是数组+链表，链表主要是为了解决哈希冲突，并且整个数组都是synchronized 修饰的，所以 HashTable 是线程安全的，但锁的粒度太大，锁的竞争非常激烈，效率很低。