问遍了身边的面试官朋友，我整理出这份Java集合高频面试题（2022年最新版）

微信搜索【程序员囧辉】&＃xff0c;关注这个坚持分享技术干货的程序员。

我的最新文章&＃xff1a;百万级QPS&＃xff0c;支撑淘宝双11商品浏览需要哪些技术

大家好&＃xff0c;我是囧辉&＃xff0c;面试系列开篇&＃xff1a;Java 基础高频面试题&＃xff08;2021年最新版&＃xff09;&＃xff0c;发表后受到不少同学的喜欢。

今天我们继续下一个重要的面试内容&＃xff1a;集合框架。HashMap 作为 Java 中最靓的仔&＃xff0c;毋庸置疑将是本文的主角。

可能有些同学看过我之前的 HashMap 文章&＃xff1a;面试阿里&＃xff0c;HashMap 这一篇就够了&＃xff0c;会想&＃xff1a;辉哥果然又颓废了、堕落了&＃xff0c;估计是将之前的内容就照搬过来水一篇&＃xff0c;鄙视&＃xff0c;取关&＃xff0c;不看也罢&＃xff0c;*&＃xff08;&＃xff09;&*……&*。

你们不对劲&＃xff0c;你辉哥是这种人&＃xff1f;当然不是的&＃xff0c;本文的 HashMap 部分在之前的基础上进行了补充和完善&＃xff0c;希望大家能看到完善的点。

最后&＃xff0c;本文按 BAT 面试标准给出解析&＃xff0c;希望在这金三银四的日子里&＃xff0c;祝你一臂之力&＃xff0c;拿下大厂 Offer。

我自己前前后后加起来总共应该参加了不下四五十次的面试&＃xff0c;拿到过几乎所有一线大厂的 offer&＃xff1a;阿里、字节、美团、快手、拼多多等等。

每次面试后我都会将面试的题目进行记录&＃xff0c;并整理成自己的题库&＃xff0c;最近我将这些题目整理出来&＃xff0c;并按大厂的标准给出自己的解析&＃xff0c;希望在这金三银四的季节里&＃xff0c;能助你一臂之力。

面试文章持续更新中... 

1、介绍下 HashMap 的底层数据结构吧。

在 JDK 1.8&＃xff0c;HashMap 底层是由 “数组&＃43;链表&＃43;红黑树” 组成&＃xff0c;如下图所示&＃xff0c;而在 JDK 1.8 之前是由 “数组&＃43;链表” 组成&＃xff0c;就是下图去掉红黑树。

3、为什么要改成“数组&＃43;链表&＃43;红黑树”&＃xff1f;

通过上题可以看出&＃xff0c;“数组&＃43;链表” 已经充分发挥了这两种数据结构的优点&＃xff0c;是个很不错的组合了。

但是这种组合仍然存在问题&＃xff0c;就是在定位到索引位置后&＃xff0c;需要先遍历链表找到节点&＃xff0c;这个地方如果链表很长的话&＃xff0c;也就是 hash 冲突很严重的时候&＃xff0c;会有查找性能问题&＃xff0c;因此在 JDK1.8中&＃xff0c;通过引入红黑树&＃xff0c;来优化这个问题。

使用链表的查找性能是 O(n)&＃xff0c;而使用红黑树是 O(logn)。

4、那在什么时候用链表&＃xff1f;什么时候用红黑树&＃xff1f;

对于插入&＃xff0c;默认情况下是使用链表节点。当同一个索引位置的节点在新增后超过8个&＃xff08;阈值8&＃xff09;&＃xff1a;如果此时数组长度大于等于 64&＃xff0c;则会触发链表节点转红黑树节点&＃xff08;treeifyBin&＃xff09;&＃xff1b;而如果数组长度小于64&＃xff0c;则不会触发链表转红黑树&＃xff0c;而是会进行扩容&＃xff0c;因为此时的数据量还比较小。

对于移除&＃xff0c;当同一个索引位置的节点在移除后达到 6 个&＃xff08;阈值6&＃xff09;&＃xff0c;并且该索引位置的节点为红黑树节点&＃xff0c;会触发红黑树节点转链表节点&＃xff08;untreeify&＃xff09;。

5、为什么链表转红黑树的阈值是8&＃xff1f;

我们平时在进行方案设计时&＃xff0c;必须考虑的两个很重要的因素是&＃xff1a;时间和空间。对于 HashMap 也是同样的道理&＃xff0c;简单来说&＃xff0c;阈值为8是在时间和空间上权衡的结果&＃xff08;这 B 我装定了&＃xff09;。

JDK1.8&＃xff1a;底层结构为&＃xff1a;数组&＃43;链表&＃43;红黑树&＃xff1b;实现线程安全的方式&＃xff1a;CAS &＃43; Synchronized

区别&＃xff1a;

1、JDK1.8 中降低锁的粒度。JDK1.7 版本锁的粒度是基于 Segment 的&＃xff0c;包含多个节点&＃xff08;HashEntry&＃xff09;&＃xff0c;而 JDK1.8 锁的粒度就是单节点&＃xff08;Node&＃xff09;。

2、JDK1.8 版本的数据结构变得更加简单&＃xff0c;使得操作也更加清晰流畅&＃xff0c;因为已经使用 synchronized 来进行同步&＃xff0c;所以不需要分段锁的概念&＃xff0c;也就不需要 Segment 这种数据结构了&＃xff0c;当前还保留仅为了兼容。

3、JDK1.8 使用红黑树来优化链表&＃xff0c;跟 HashMap 一样&＃xff0c;优化了极端情况下&＃xff0c;链表过长带来的性能问题。

4、JDK1.8 使用内置锁 synchronized 来代替重入锁 ReentrantLock&＃xff0c;synchronized 是官方一直在不断优化的&＃xff0c;现在性能已经比较可观&＃xff0c;也是官方推荐使用的加锁方式。

23、ConcurrentHashMap 的并发扩容

ConcurrentHashMap 在扩容时会计算出一个步长&＃xff08;stride&＃xff09;&＃xff0c;最小值是16&＃xff0c;然后给当前扩容线程分配“一个步长”的节点数&＃xff0c;例如16个&＃xff0c;让该线程去对这16个节点进行扩容操作&＃xff08;将节点从老表移动到新表&＃xff09;。

如果在扩容结束前又来一个线程&＃xff0c;则也会给该线程分配一个步长的节点数让该线程去扩容。依次类推&＃xff0c;以达到多线程并发扩容的效果。

例如&＃xff1a;64要扩容到128&＃xff0c;步长为16&＃xff0c;则第一个线程会负责第113&＃xff08;索引112&＃xff09;~128&＃xff08;索引127&＃xff09;的节点&＃xff0c;第二个线程会负责第97&＃xff08;索引96&＃xff09;~112&＃xff08;索引111&＃xff09;的节点&＃xff0c;依次类推。

具体处理&＃xff08;该流程后续可能会替换成流程图&＃xff09;&＃xff1a;

1&＃xff09;如果索引位置上为null&＃xff0c;则直接使用 CAS 将索引位置赋值为 ForwardingNode&＃xff08;hash值为-1&＃xff09;&＃xff0c;表示已经处理过&＃xff0c;这个也是触发并发扩容的关键点。

2&＃xff09;如果索引位置的节点 f 的 hash 值为 MOVED&＃xff08;-1&＃xff09;&＃xff0c;则代表节点 f 是 ForwardingNode 节点&＃xff0c;只有 ForwardingNode 的 hash 值为 -1&＃xff0c;意味着该节点已经处理过了&＃xff0c;则跳过该节点继续往下处理。

3&＃xff09;.否则&＃xff0c;对索引位置的节点 f 对象使用 synchronized 进行加锁&＃xff0c;遍历链表或红黑树&＃xff0c;处理每个一节点&＃xff0c;这边和 HashMap 的扩容类似&＃xff0c;会构造出2个链表&＃xff1a;ln&＃xff08;索引位置为原索引位置&＃xff09;、hn&＃xff08;索引位置为&＃xff1a;原索引位置&＃43;老表容量&＃xff09;&＃xff0c;处理完该位置的节点后&＃xff0c;最后将 ln 和 hn 放到对应位置&＃xff0c;然后继续处理下一个索引位置。

ForwardingNode&＃xff1a;一个特殊的 Node 节点&＃xff0c;hash 值为-1&＃xff08;源码中定义成 MOVED&＃xff09;&＃xff0c;其中存储 nextTable 的引用。 只有发生扩容的时候&＃xff0c;ForwardingNode才会发挥作用&＃xff0c;作为一个占位符放在 table 中表示当前节点已经被处理&＃xff08;或则为 null &＃xff09;。

24、ConcurrenHashMap 和 Hashtable 的区别&＃xff1f;

1&＃xff09;底层数据结构&＃xff1a; 

ConcurrentHashMap&＃xff1a;1&＃xff09;JDK1.7 采用 分段的数组&＃43;链表 实现&＃xff1b;2&＃xff09;JDK1.8 采用 数组&＃43;链表&＃43;红黑树&＃xff0c;跟 JDK1.8 的 HashMap 的底层数据结构一样。

Hashtable&＃xff1a; 采用 数组&＃43;链表 的形式&＃xff0c;跟 JDK1.8 之前的 HashMap 的底层数据结构类似。

2&＃xff09;实现线程安全的方式&＃xff08;重要&＃xff09;&＃xff1a;

ConcurrentHashMap&＃xff1a;

1&＃xff09;JDK1.7&＃xff1a;使用分段锁&＃xff08;Segment&＃xff09;保证线程安全&＃xff0c;每个分段&＃xff08;Segment&＃xff09;包含若干个 HashEntry&＃xff0c;当并发访问不同分段的数据时&＃xff0c;不会产生锁竞争&＃xff0c;从而提升并发性能。

2&＃xff09;JDK1.8&＃xff1a;使用 synchronized &＃43; CAS 的方式保证线程安全&＃xff0c;每次只锁一个节点&＃xff08;Node&＃xff09;&＃xff0c;进一步降低锁粒度&＃xff0c;降低锁冲突的概率&＃xff0c;从而提升并发性能。

Hashtable&＃xff1a;使用 synchronized 修饰方法来保证线程安全&＃xff0c;每个实例对象只有一把锁&＃xff0c;并发性能较低&＃xff0c;相当于串行访问。

25、ConcurrentHashMap 的 size() 方法怎么实现的&＃xff1f;

JDK 1.7&＃xff1a;先尝试在不加锁的情况下尝进行统计 size&＃xff0c;最多统计3次&＃xff0c;如果连续两次统计之间没有任何对 segment 的修改操作&＃xff0c;则返回统计结果。否则&＃xff0c;对每个segment 进行加锁&＃xff0c;然后统计出结果&＃xff0c;返回结果。

JDK 1.8&＃xff1a;直接统计 baseCount 和 counterCells 的 value 值&＃xff0c;返回的是一个近似值&＃xff0c;如果有并发的插入或删除&＃xff0c;实际的数量可能会有所不同。

该统计方式改编自 LongAdder 和 Striped64&＃xff0c;这两个类在 JDK 1.8 中被引入&＃xff0c;出自并发大神 Doug Lea 之手&＃xff0c;是原子类&＃xff08;AtomicLong 等&＃xff09;的优化版本&＃xff0c;主要优化了在并发竞争下&＃xff0c;AtomicLong 由于 CAS 失败的带来的性能损耗。

值得注意的是&＃xff0c;JDK1.8中&＃xff0c;提供了另一个统计的方法 mappingCount&＃xff0c;实现和 size 一样&＃xff0c;只是返回的类型改成了 long&＃xff0c;这也是官方推荐的方式。

public int size() {long n &＃61; sumCount();return ((n <0L) ? 0 :(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :(int)n);
}
// 一个ConcurrentHashMap包含的映射数量可能超过int上限&＃xff0c;
// 所以应该使用这个方法来代替size()
public long mappingCount() {long n &＃61; sumCount();return (n <0L) ? 0L : n; // ignore transient negative values
}
final long sumCount() {CounterCell[] as &＃61; counterCells; CounterCell a;long sum &＃61; baseCount;if (as !&＃61; null) {for (int i &＃61; 0; i }

26、比较下常见的几种 Map&＃xff0c;在使用时怎么选择&＃xff1f;

30、ArrayList 和 Vector 的区别。

Vector 和 ArrayList 的实现几乎是一样的&＃xff0c;区别在于&＃xff1a;

1&＃xff09;最重要的的区别&＃xff1a; Vector 在方法上使用了 synchronized 来保证线程安全&＃xff0c;同时由于这个原因&＃xff0c;在性能上 ArrayList 会有更好的表现。

2&＃xff09; Vector 扩容后容量默认变为原来 2 倍&＃xff0c;而 ArrayList 为原来的 1.5 倍。

有类似关系的还有&＃xff1a;StringBuilder 和 StringBuffer、HashMap 和 Hashtable。

31、ArrayList 和 LinkedList 的区别&＃xff1f;

1、ArrayList 底层基于动态数组实现&＃xff0c;LinkedList 底层基于双向链表实现。

2、对于随机访问&＃xff08;按 index 访问&＃xff0c;get/set方法&＃xff09;&＃xff1a;ArrayList 通过 index 直接定位到数组对应位置的节点&＃xff0c;而 LinkedList需要从头结点或尾节点开始遍历&＃xff0c;直到寻找到目标节点&＃xff0c;因此在效率上 ArrayList 优于 LinkedList。

3、对于随机插入和删除&＃xff1a;ArrayList 需要移动目标节点后面的节点&＃xff08;使用System.arraycopy 方法移动节点&＃xff09;&＃xff0c;而 LinkedList 只需修改目标节点前后节点的 next 或 prev 属性即可&＃xff0c;因此在效率上 LinkedList 优于 ArrayList。

4、对于顺序插入和删除&＃xff1a;由于 ArrayList 不需要移动节点&＃xff0c;因此在效率上比 LinkedList 更好。这也是为什么在实际使用中 ArrayList 更多&＃xff0c;因为大部分情况下我们的使用都是顺序插入。

5、两者都不是线程安全的。

6、内存空间占用&＃xff1a; ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间&＃xff0c;而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间&＃xff08;因为要存放直接后继和直接前驱以及数据&＃xff09;。

32、HashSet 是如何保证不重复的&＃xff1f;

HashSet 底层使用 HashMap 来实现&＃xff0c;见下面的源码&＃xff0c;元素放在 HashMap 的 key 里&＃xff0c;value 为固定的 Object 对象。当 add 时调用 HashMap 的 put 方法&＃xff0c;如果元素不存在&＃xff0c;则返回 null 表示 add 成功&＃xff0c;否则 add 失败。

由于 HashMap 的 Key 值本身就不允许重复&＃xff0c;HashSet 正好利用 HashMap 中 key 不重复的特性来校验重复元素&＃xff0c;简直太妙了。

private transient HashMap map;// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT &＃61; new Object();public boolean add(E e) {return map.put(e, PRESENT)&＃61;&＃61;null;
}

33、TreeSet 清楚吗&＃xff1f;能详细说下吗&＃xff1f;

“TreeSet 和 TreeMap 的关系” 和上面说的 “HashSet 和 HashMap 的关系” 几乎一致。

TreeSet 底层默认使用 TreeMap 来实现。而 TreeMap 通过实现 Comparator&＃xff08;或 Key 实现 Comparable&＃xff09;来实现自定义顺序。

private transient NavigableMap m;
private static final Object PRESENT &＃61; new Object();TreeSet(NavigableMap m) {this.m &＃61; m;
}
public TreeSet() {this(new TreeMap());
}public boolean add(E e) {return m.put(e, PRESENT)&＃61;&＃61;null;
}

34、介绍下 CopyOnWriteArrayList&＃xff1f;

CopyOnWriteArrayList 是 ArrayList 的线程安全版本&＃xff0c;也是大名鼎鼎的 copy-on-write&＃xff08;COW&＃xff0c;写时复制&＃xff09;的一种实现。

在读操作时不加锁&＃xff0c;跟ArrayList类似&＃xff1b;在写操作时&＃xff0c;复制出一个新的数组&＃xff0c;在新数组上进行操作&＃xff0c;操作完了&＃xff0c;将底层数组指针指向新数组。适合使用在读多写少的场景。

例如 add(E e) 方法的操作流程如下&＃xff1a;使用 ReentrantLock 加锁&＃xff0c;拿到原数组的length&＃xff0c;使用 Arrays.copyOf 方法从原数组复制一个新的数组&＃xff08;length&＃43;1&＃xff09;&＃xff0c;将要添加的元素放到新数组的下标length位置&＃xff0c;最后将底层数组指针指向新数组。

35、Comparable 和 Comparator 比较&＃xff1f;

1、Comparable 是排序接口&＃xff0c;一个类实现了 Comparable接口&＃xff0c;意味着“该类支持排序”。Comparator 是比较器&＃xff0c;我们可以实现该接口&＃xff0c;自定义比较算法&＃xff0c;创建一个 “该类的比较器” 来进行排序。

2、Comparable 相当于“内部比较器”&＃xff0c;而 Comparator 相当于“外部比较器”。

3、Comparable 的耦合性更强&＃xff0c;Comparator 的灵活性和扩展性更优。

4、Comparable 可以用作类的默认排序方法&＃xff0c;而 Comparator 则用于默认排序不满足时&＃xff0c;提供自定义排序。

耦合性和扩展性的问题&＃xff0c;举个简单的例子&＃xff1a;

当实现类实现了 Comparable 接口&＃xff0c;但是已有的 compareTo 方法的比较算法不满足当前需求&＃xff0c;此时如果想对两个类进行比较&＃xff0c;有两种办法&＃xff1a;

1&＃xff09;修改实现类的源代码&＃xff0c;修改 compareTo 方法&＃xff0c;但是这明显不是一个好方案&＃xff0c;因为这个实现类的默认比较算法可能已经在其他地方使用了&＃xff0c;此时如果修改可能会造成影响&＃xff0c;所以一般不会这么做。

2&＃xff09;实现 Comparator 接口&＃xff0c;自定义一个比较器&＃xff0c;该方案会更优&＃xff0c;自定义的比较器只用于当前逻辑&＃xff0c;其他已有的逻辑不受影响。

36、List、Set、Map三者的区别?

List&＃xff08;对付顺序的好帮手&＃xff09;&＃xff1a; 存储的对象是可重复的、有序的。

Set&＃xff08;注重独一无二的性质&＃xff09;&＃xff1a;存储的对象是不可重复的、无序的。

Map&＃xff08;用 Key 来搜索的专业户&＃xff09;: 存储键值对&＃xff08;key-value&＃xff09;&＃xff0c;不能包含重复的键&＃xff08;key&＃xff09;&＃xff0c;每个键只能映射到一个值。

37、Map、List、Set 分别说下你了解到它们有的线程安全类和线程不安全的类&＃xff1f;

Map

线程安全&＃xff1a;CocurrentHashMap、Hashtable

线程不安全&＃xff1a;HashMap、LinkedHashMap、TreeMap、WeakHashMap

List

线程安全&＃xff1a;Vector&＃xff08;线程安全版的ArrayList&＃xff09;、Stack&＃xff08;继承Vector&＃xff0c;增加pop、push方法&＃xff09;、CopyOnWriteArrayList

线程不安全&＃xff1a;ArrayList、LinkedList

Set

线程安全&＃xff1a;CopyOnWriteArraySet&＃xff08;底层使用CopyOnWriteArrayList&＃xff0c;通过在插入前判断是否存在实现 Set 不重复的效果&＃xff09;

线程不安全&＃xff1a;HashSet&＃xff08;基于 HashMap&＃xff09;、LinkedHashSet&＃xff08;基于 LinkedHashMap&＃xff09;、TreeSet&＃xff08;基于 TreeMap&＃xff09;、EnumSet

38、Collection 与 Collections的区别

Collection&＃xff1a;集合类的一个顶级接口&＃xff0c;提供了对集合对象进行基本操作的通用接口方法。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式&＃xff0c;常见的 List 与 Set 就是直接继承 Collection 接口。

Collections&＃xff1a;集合类的一个工具类/帮助类&＃xff0c;提供了一系列静态方法&＃xff0c;用于对集合中元素进行排序、搜索以及线程安全等各种操作。

面试系列持续创作中&＃xff0c;有疑问的地方欢迎留言&＃xff0c;我看到后都会回复。

原创不易&＃xff0c;如果你觉得本文写的还不错&＃xff0c;对你有帮助&＃xff0c;请通过【点赞】和【关注】让我知道&＃xff0c;支持我写出更好的文章。

我是囧辉&＃xff0c;我的目标是帮助大家拿到心仪的大厂 Offer&＃xff0c;我们下期见。