2 万字 42 道Java经典面试题总结（2024修订版）- Java集合篇

柔情只为你懂 2024-04-17 10:28 26阅读 0赞

#### 目录 ####

*   *   *  1、Java中常用的集合有哪些？
         *  2、Collection 和 Collections 有什么区别？
         *  3、为什么集合类没有实现 Cloneable 和 Serializable 接口？
         *  4、数组和集合有什么本质区别？
         *  5、数组和集合如何选择？
         *  6、list与Set区别
         *  7、HashMap 和 Hashtable 有什么区别？
         *  8、concurrentHashMap和HashTable有什么区别
         *  9、HashMap 的工作原理是什么？
         *  10、Hashmap什么时候进行扩容？
         *  11、说一下 HashMap 的实现原理？
         *  12、为什么HashMap使用红黑树而不使用AVL树
         *  13、Java中的ConcurrentHashMap中为什么不能存储null?
         *  14、Java8开始ConcurrentHashMap，为什么舍弃分段锁？
         *  15、ConcurrentHashMap(JDK1.8)为什么要使用synchronized而不是如ReentranLock这样的可重入锁？
         *  16、set有哪些实现类？
         *  17、说一下HashSet的实现原理
         *  18、Set是如何保证元素不重复的？
         *  19、HashMap和HashSet的区别
         *  20、TreeSet常用方法有哪些？
         *  21、TreeMap 和 TreeSet 在排序时如何比较元素？
         *  22、ArrayList 和 LinkedList 的区别是什么？
         *  23、ArrayList 和 Vector 的区别？
         *  24、队列和栈是什么？有什么区别？
         *  25、Queue和Deque的区别是什么？
         *  26、在 Queue 中 poll()和 remove()有什么区别？
         *  27、说说你对优先队列的理解
         *  28、说说你对双端队列的理解
         *  29、CopyOnWriteArrayList是什么，有哪些应用场景？
         *  30、使用CopyOnWriteArrayList时需要注意哪些问题？
         *  31、说一下链表的实现原理
         *  32、说一下散列表的实现原理
         *  33、说说你对映射视图的理解
         *  34、说说你对弱散列映射WeakHashMap的理解
         *  35、说说你对链接散列映射LinkedHashMap的理解
         *  36、说说你对LinkedHashSet的理解
         *  37、说说你对枚举集EnumSet的理解
         *  38、说说你对EnumMap的理解
         *  39、Comparator与Comparable有什么区别
         *  40、Iterator 怎么使用？有什么特点？
         *  41、Iterator 和 ListIterator 有什么区别？
         *  42、快速失败 (fail-fast) 和安全失败 (fail-safe) 的区别是什么？

> 🍅 作者简介：哪吒，CSDN2021博客之星亚军🏆、新星计划导师✌、博客专家💪
> 
> 🍅 哪吒多年工作总结：[Java学习路线总结，搬砖工逆袭Java架构师][Java_Java]
> 
> 🍅 技术交流：[定期更新Java硬核干货，不定期送书活动][Java]
> 
> 🍅 关注公众号【哪吒编程】，回复 面试题 ，获取《10万字208道Java经典面试题总结(附答案)》2024修订版pdf，背题更方便，一文在手，面试我有

#### 1、Java中常用的集合有哪些？ ####

Java集合框架为不同类型的集合定义了大量接口。

![在这里插入图片描述][a41fedbb12064ec4bc44be23d192fa7c.png_pic_center]  
Java类库中的集合：

1.  ArrayList，可以动态增长和缩减的一个索引序列。
2.  LinkedList，可以在任意位置高效插入和删除的一个有序序列。
3.  ArrayDeque，实现为循环数组的一个双端队列。
4.  HashSet，没有重复元素的一个无序集合。
5.  TreeSet，有序集。
6.  EnumSet，包含枚举类型值的集合。
7.  LinkedHashSet，可以记住元素插入次序的集合。
8.  PriorityQueue，允许高效删除最小元素的集合。
9.  HashMap，存储键值对的数据结构。
10. TreeMap，键有序的键值对集合。
11. EnumMap，键是枚举类型的键值对集合。
12. LinkedHashMap，可以记住添加次序的键值对集合。
13. WeakHashMap，这个集合中的键如果不在使用，就会被垃圾回收。

#### 2、Collection 和 Collections 有什么区别？ ####

（1）Collection是最基本的集合接口，Collection派生了两个子接口list和set，分别定义了两种不同的存储方式。

（2）Collections是一个包装类，它包含各种有关集合操作的静态方法（对集合的搜索、排序、线程安全化等）。

此类不能实例化，就像一个工具类，服务于Collection框架。

#### 3、为什么集合类没有实现 Cloneable 和 Serializable 接口？ ####

集合类通常包含多个元素，这些元素的类型和数量可能会非常复杂。实现Cloneable和Serializable接口需要对这些元素的状态进行精确的控制和管理，这可能会导致代码变得复杂且容易出错。

序列化和克隆操作可能会消耗大量的计算资源，尤其是在处理大型集合时。不实现这些接口可以避免不必要的性能开销。

序列化和克隆操作可能会引发安全问题，因为它们允许对对象的深拷贝。如果不小心使用，可能会导致敏感信息的泄露或不当访问。

#### 4、数组和集合有什么本质区别？ ####

数组的大小是固定的，一旦创建后就不能改变，而集合的大小是动态的，可以根据需要扩展和缩减。

数组可以存储基本数据类型和引用数据类型，而集合只能存储引用数据类型（对象）。

数组通常用于存储同一类型的数据，而集合可以存储不同类型的数据。

数组的长度是不可变的，而集合的长度是可变的，这意味着可以在运行时向集合中添加或删除元素。

#### 5、数组和集合如何选择？ ####

如果数据的大小是固定的，那么数组可能是一个更好的选择，因为它提供了固定大小的存储空间。相反，如果数据的大小可能会发生变化，那么集合可能更合适。

如果需要存储基本数据类型，那么只能使用数组，如果需要存储不同类型的数据，集合可能更适合。

数组在访问速度上通常比集合更快，因为它们可以通过索引直接访问元素。

集合提供了许多有用的方法，如add、remove、contains等，这些方法使得数据的操作更加方便。如果需要使用这些方法，那么集合可能是更好的选择。

#### 6、list与Set区别 ####

（1）List简介

实际上有两种List：一种是基本的ArrayList,其优点在于随机访问元素，另一种是LinkedList,它并不是为快速随机访问设计的，而是快速的插入或删除。

① ArrayList：由数组实现的List。允许对元素进行快速随机访问，但是向List中间插入与移除元素的速度很慢。

② LinkedList ：对顺序访问进行了优化，向List中间插入与删除的开销并不大。随机访问则相对较慢。

还具有下列方 法：addFirst(), addLast(), getFirst(), getLast(), removeFirst() 和 removeLast(), 这些方法 (没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈、队列和双向队列使用。

（2）Set简介

Set具有与Collection完全一样的接口，因此没有任何额外的功能。实际上Set就是Collection,只是行为不同。这是继承与多态思想的典型应用：表现不同的行为。Set不保存重复的元素(至于如何判断元素相同则较为负责)

① Set : 存入Set的每个元素都必须是唯一的，因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。

② HashSet：为快速查找设计的Set。存入HashSet的对象必须定义hashCode()。

③ TreeSet： 保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。

（3）list与Set区别

① List,Set都是继承自Collection接口

② List特点：元素有放入顺序，元素可重复 ，Set特点：元素无放入顺序，元素不可重复，重复元素会覆盖掉，（元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的，加入Set 的Object必须定义equals()方法 ，另外list支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。）

③ Set和List对比：

1.  Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
2.  List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。

#### 7、HashMap 和 Hashtable 有什么区别？ ####

1.  Hashtable不允许键或值为null，否则会抛出NullPointerException异常。而HashMap可以存储key和value为null的元素；
2.  Hashtable继承自Dictionary类，HashMap继承自AbstractMap类并实现了Map接口；
3.  Hashtable在创建时必须指定容量大小，且默认大小为11。而HashMap可以在创建时不指定容量大小，系统会自动分配初始容量，并采用2倍扩容机制；
4.  迭代器 Iterator 对 Hashtable 是安全的，而 Iterator 对 HashMap 不是安全的，因为迭代器被设计为工作于一个快照上，如果在迭代过程中其他线程修改了 HashMap，则会抛出并发修改异常；
5.  Hashtable是线程安全的，而HashMap是非线程安全的。Hashtable通过在每个方法前加上synchronized关键字来保证线程安全性，而HashMap则没有实现这种机制。

#### 8、concurrentHashMap和HashTable有什么区别 ####

concurrentHashMap融合了hashmap和hashtable的优势，hashmap是不同步的，但是单线程情况下效率高，hashtable是同步的同步情况下保证程序执行的正确性。

concurrentHashMap锁的方式是细粒度的。concurrentHashMap将hash分为16个桶（默认值），诸如get、put、remove等常用操作只锁住当前需要用到的桶。

concurrentHashMap的读取并发，因为读取的大多数时候都没有锁定，所以读取操作几乎是完全的并发操作，只是在求size时才需要锁定整个hash。

而且在迭代时，concurrentHashMap使用了不同于传统集合的快速失败迭代器的另一种迭代方式，弱一致迭代器。在这种方式中，当iterator被创建后集合再发生改变就不会抛出ConcurrentModificationException，取而代之的是在改变时new新的数据而不是影响原来的数据，iterator完成后再讲头指针替代为新的数据，这样iterator时使用的是原来的数据。

#### 9、HashMap 的工作原理是什么？ ####

（1）存储

当向HashMap中添加一个键值对时，首先会计算键（Key）的哈希值，这个哈希值将决定该键值对在内部数组中的索引位置。然后，该键值对会被存储在对应索引的链表中。如果两个不同的键拥有相同的哈希值，它们会被存储在同一个索引位置，这种现象称为哈希冲突。为了解决冲突，HashMap会在链表中维护这些具有相同哈希值的键值对。

（2）查找

当需要获取某个特定键对应的值时，HashMap会再次计算该键的哈希值，并沿着对应索引的链表查找匹配的键。一旦找到，就返回对应的值。

（3）扩容

随着HashMap中元素的增加，为了防止性能下降，当链表的长度超过一定阈值时，HashMap会进行自动扩容。这个过程涉及到创建一个新的、更大的数组，并将旧数组中的所有元素重新映射到新数组的索引上。这个过程也被称为rehashing。

（4）数据结构

HashMap的内部结构是一个Entry数组，每个Entry包含一个key-value键值对。这样设计的目的是为了高效地存储和检索数据。

#### 10、Hashmap什么时候进行扩容？ ####

在初始化HashMap时，需要指定其初始容量和负载因子。负载因子是一个介于0到1之间的浮点数，默认值为0.75。

当HashMap中的元素数量达到当前容量乘以负载因子时，即满足capacity \* loadFactor条件时，就会触发扩容操作。

在扩容过程中，HashMap会创建一个新的数组，这个新数组的容量是原来容量的两倍。然后，它会重新计算每个键值对的哈希值，并将这些键值对重新映射到新数组的对应位置上。这个过程可能会涉及到一些性能开销，因为它需要重新计算哈希值和重新分配元素。

由于每次扩容都需要重新计算哈希值并重新分配元素，这会带来一定的性能开销。因此，我们应该尽量避免让HashMap频繁地进行扩容，以提高性能。

#### 11、说一下 HashMap 的实现原理？ ####

HashMap实现了Map接口，Map接口对键值对进行映射。Map中不允许重复的键。Map接口有两个基本的实现，HashMap和TreeMap。TreeMap保存了对象的排列次序，而HashMap则不能。HashMap允许键和值为null。HashMap是非synchronized的，但collection框架提供方法能保证HashMap synchronized，这样多个线程同时访问HashMap时，能保证只有一个线程更改Map。

HashMap在JDK1.7中采用数组+链表的存储结构。

HashMap采取Entry数组来存储key-value，每一个键值对组成了一个Entry实体，Entry类时机上是一个单向的链表结构，它具有next指针，指向下一个Entry实体，以此来解决Hash冲突的问题。

HashMap实现一个内部类Entry，重要的属性有hash、key、value、next。

![在这里插入图片描述][1fadd53356a545eab11331ebd3d84dbb.png_pic_center]

JDK1.8中采用数据+链表+红黑树的存储形式。当链表长度超过阈值（8）时，将链表转换为红黑树。在性能上进一步得到提升。

![在这里插入图片描述][aaf30a3880854b5eb926314bb221658e.png_pic_center]

#### 12、为什么HashMap使用红黑树而不使用AVL树 ####

1.  AVL树是更加严格的平衡，因此可以提供更快的查找速度，一般读取查找密集型任务，适用AVL树；
2.  红黑树更适合于插入修改密集型任务，即更适合HashMap；
3.  通常，AVL树的旋转比红黑树的旋转更加难以平衡和调试。

深入理解红黑树与AVL树：

1.  AVL以及红黑树是高度平衡的树数据结构。它们非常相似，真正的区别在于在任何添加/删除操作时完成的旋转操作次数。
2.  两种实现都缩放为a O(lg N)，其中N是叶子的数量，但实际上AVL树在查找密集型任务上更快：利用更好的平衡，树遍历平均更短。另一方面，插入和删除方面，AVL树速度较慢：需要更高的旋转次数才能在修改时正确地重新平衡数据结构。
3.  在AVL树中，从根到任何叶子的最短路径和最长路径之间的差异最多为1。在红黑树中，差异可以是2倍。
4.  两个都给O（log n）查找，但平衡AVL树可能需要O（log n）旋转，而红黑树将需要最多两次旋转使其达到平衡（尽管可能需要检查O（log n）节点以确定旋转的位置）。旋转本身是O（1）操作，因为你只是移动指针。

#### 13、Java中的ConcurrentHashMap中为什么不能存储null? ####

与HashMap一样，ConcurrentHashMap也是一个基于散列的Map，但它使用了一种完全不同的加锁策略来提供更高的并发性和伸缩性。ConcurrentHashMap并不是将每个方法都在同一个锁上同步并使得每次只能有一个线程访问容器，而是使用一种更细的加锁机制来实现更大程度的共享，这种机制成为分段锁。在这种机制中，任意数量的读取线程可以并发地访问Map，执行读取操作的线程和执行写入操作的线程可以并发地访问Map，并且一定数量的写入线程可以并发地修改Map。ConcurrentHashMap带来的结果是，在并发访问环境下将实现更高的吞吐量，而在单线程环境中只损失非常小的性能。

ConcurrentHashMap返回的迭代器具有弱一致性，而并非“及时失败”。弱一致性的迭代器可以容忍并发的修改，当创建迭代器时会遍历已有的元素，并可以在迭代器被构造后将修改操作反映给容器。ConcurrentHashMap返回的迭代器具有弱一致性，而并非“及时失败”。弱一致性的迭代器可以容忍并发的修改，当创建迭代器时会遍历已有的元素，并可以在迭代器被构造后将修改操作反映给容器。

#### 14、Java8开始ConcurrentHashMap，为什么舍弃分段锁？ ####

ConcurrentHashMap的原理是引用了内部的 Segment ( ReentrantLock ) 分段锁，保证在操作不同段 map 的时候， 可以并发执行， 操作同段 map 的时候，进行锁的竞争和等待。从而达到线程安全， 且效率大于 synchronized。

但是在 Java 8 之后， JDK 却弃用了这个策略，重新使用了 synchronized+CAS。

Java 8 中的 ConcurrentHashMap 放弃了分段锁，而是引入了 CAS 操作，即 Compare and Swap，利用原子性的操作和无锁编程的思想，来实现并发写入：采用一种乐观锁的方式，通过比较当前值与期望值是否相等，来决定是否更新。这种方式避免了对整个数据结构加锁，提高了并发写入时的性能和效率。

#### 15、ConcurrentHashMap(JDK1.8)为什么要使用synchronized而不是如ReentranLock这样的可重入锁？ ####

我想从下面几个角度讨论这个问题：

（1）锁的粒度

首先锁的粒度并没有变粗，甚至变得更细了。每当扩容一次，ConcurrentHashMap的并发度就扩大一倍。

（2）Hash冲突

JDK1.7中，ConcurrentHashMap从过二次hash的方式（Segment -> HashEntry）能够快速的找到查找的元素。在1.8中通过链表加红黑树的形式弥补了put、get时的性能差距。  
JDK1.8中，在ConcurrentHashmap进行扩容时，其他线程可以通过检测数组中的节点决定是否对这条链表（红黑树）进行扩容，减小了扩容的粒度，提高了扩容的效率。

#### 16、set有哪些实现类？ ####

其实面试官想听到的不只是有哪些实现类，而是触类旁通，比如它们的原理、对比、使用场景等。

（1）HashSet

1.  基于散列表实现的Set集合，内部的存储结构是哈希表，是线程不安全的
2.  它的底层数据结构是HashMap，因此它拥有快速的存取速度，是用的最多的实现类；
3.  HashSet不保证元素的迭代顺序，也不保证该顺序会随着时间的推移保持不变；
4.  允许使用null元素；

（2）TreeSet

1.  基于红黑树（Red-Black tree）或者AVL树等自平衡二叉查找树实现的Set集合；
2.  TreeSet可以确保集合元素处于排序状态；
3.  不允许插入null元素

TreeSet对元素进行排序的方式：

1.  元素自身具备比较功能，需要实现Comparable接口，并覆盖compareTo方法；
2.  元素自身不具备比较功能，需要实现Comparator接口，并覆盖compare方法。

（3）链接散列集LinkedHashSet

1.  LinkedHashSet结合了哈希表和链表两种数据结构，具有可预知的迭代顺序；
2.  它继承自HashSet，但是又添加了一个双向链表来维持插入的顺序；
3.  LinkedHashSet的元素迭代顺序是它们被插入的顺序，或者最近访问的顺序。

HashSet和LinkedHashSet内部使用哈希表来存储元素，当多个元素经过哈希函数计算后产生同一个索引位置时，就会产生哈希冲突。为了解决哈希冲突，HashSet和LinkedHashSet使用链式散列技术，即在哈希表每个索引位置上维护一个链表，将所有哈希值相同的元素存放在同一个链表中，从而实现快速查找和添加元素。

LinkedHashMap的常用方法包括：

1.  put(K key, V value)：将一个键值对添加到链接散列集中；
2.  get(K key)：返回一个键值对，如果键不存在则返回null；
3.  remove(K key)：从链接散列集中删除一个键值对；
4.  containsKey(K key)：检查一个键是否存在于链接散列集中；
5.  size()：返回链接散列集中键值对的数量；

这些方法都是基于链表实现的，因此它们的时间复杂度都是O(1)，其中n是Map中元素的数量。

（4）AbstractSet

这是一个抽象类，它为创建新的set实现提供了一个框架。它本身不能直接实例化，但可以通过继承并实现其抽象方法来创建自定义的set实现类。

面试中能说出AbstractSet的肯定不多，面试加分项。

#### 17、说一下HashSet的实现原理 ####

HashSet底层使用的是数组加链表或者红黑树的数据结构。在JDK1.8之前，主要是数组加链表的方式，而在JDK1.8及以后的版本中，为了优化性能，引入了红黑树。

当我们向HashSet中添加一个元素时，首先会计算该元素的哈希值，然后根据哈希值确定元素在内部HashMap中的存储位置。如果该位置为空，则直接存储；如果不为空，则需要通过链表或红黑树来处理冲突。

在查找元素时，也是通过计算哈希值来确定位置，然后在对应的链表或红黑树中进行搜索。

HashSet的性能可以通过合理设置初始容量和负载因子来提高。一个较大的初始容量可以减少扩容操作的频率，而合适的负载因子可以平衡空间利用率和查找效率。

#### 18、Set是如何保证元素不重复的？ ####

HashSet内部实际上是通过HashMap来实现的。当向HashSet中添加一个元素时，它会调用该元素的hashCode()方法来计算其哈希值，然后根据这个哈希值决定元素在HashMap中的存储位置。

如果有两个元素具有相同的哈希值，那么它们会被视为同一个位置的候选者。为了区分这些具有相同哈希值的元素，HashSet还会使用equals()方法来比较它们是否相等。只有当元素在HashMap中不存在时，它才会被添加到集合中。如果已经存在，则不会重复添加，从而保证了Set集合中元素的唯一性。

#### 19、HashMap和HashSet的区别 ####

（1）先了解一下HashCode

Java中的集合有两类，一类是List，一类是Set。

List：元素有序，可以重复；

Set：元素无序，不可重复；

要想保证元素的不重复，拿什么来判断呢？这就是Object.equals方法了。如果元素有很多，增加一个元素，就要判断n次吗？

显然不现实，于是，Java采用了哈希表的原理。哈希算法也称为散列算法，是将数据依特定算法直接指定到一根地址上，初学者可以简单的理解为，HashCode方法返回的就是对象存储的物理位置（实际上并不是）。

这样一来，当集合添加新的元素时，先调用这个元素的hashcode()方法，就一下子能定位到他应该放置的物理位置上。如果这个位置上没有元素，他就可以直接存储在这个位置上，不用再进行任何比较了。如果这个位置上有元素，就调用它的equals方法与新元素进行比较，想同的话就不存了，不相同就散列其它的地址。所以这里存在一个冲突解决的问题。这样一来实际上调用equals方法的次数就大大降低了，几乎只需要一两次。

简而言之，在集合查找时，hashcode能大大降低对象比较次数，提高查找效率。

Java对象的equals方法和hashCode方法时这样规定的：

相等的对象就必须具有相等的hashcode。

1.  如果两个对象的hashcode相同，他们并不一定相同。
2.  如果两个对象的hashcode相同，他们并不一定相同。

如果两个Java对象A和B，A和B不相等，但是A和B的哈希码相等，将A和B都存入HashMap时会发生哈希冲突，也就是A和B存放在HashMap内部数组的位置索引相同，这时HashMap会在该位置建立一个链接表，将A和B串起来放在该位置，显然，该情况不违反HashMap的使用规则，是允许的。当然，哈希冲突越少越好，尽量采用好的哈希算法避免哈希冲突。

equals()相等的两个对象，hashcode()一定相等；equals()不相等的两个对象，却并不能证明他们的hashcode()不相等。

（2）HashMap和HashSet的区别

![在这里插入图片描述][0760927951c14795963357cf835876fc.png_pic_center]

#### 20、TreeSet常用方法有哪些？ ####

1.  add(Object obj)：将一个对象添加到TreeSet中；
2.  remove(Object obj)：从TreeSet中移除一个对象；
3.  pollFirst()：返回TreeSet中的第一个对象，如果TreeSet为空则返回null；
4.  pollLast()：返回TreeSet中的最后一个对象，如果TreeSet为空则返回null;
5.  size()：返回TreeSet中元素的个数;
6.  isEmpty()：判断TreeSet是否为空;
7.  contains(Object obj)：判断一个对象是否在TreeSet中;
8.  addAll(Collection<? extends E> c)：将一个Collection对象中的元素添加到TreeSet中;
9.  removeAll(Collection<? extends E> c)：从TreeSet中移除一个Collection对象中的元素;
10. retainAll(Collection<? extends E> c)：保留一个Collection对象中的元素，并将它们添加到TreeSet中；

#### 21、TreeMap 和 TreeSet 在排序时如何比较元素？ ####

TreeMap 和 TreeSet 都是基于红黑树实现的，它们在排序时会使用元素的自然顺序（如果元素实现了 Comparable 接口）或者比较器（如果构造时提供了 Comparator）。

当插入一个元素到 TreeSet 中时，它会按照指定的比较方式（自然顺序或比较器）找到正确的位置来插入该元素，以保证集合中的元素是有序的。如果元素没有实现 Comparable 接口且没有提供比较器，则无法进行排序，编译时会报错。

TreeMap 会根据键来对元素进行排序。当插入一个键值对到 TreeMap 中时，它会根据键的自然顺序或者提供的比较器来确定键值对在映射中的正确位置。同样，如果键的类型没有实现 Comparable 接口且没有提供比较器，则无法进行排序。

#### 22、ArrayList 和 LinkedList 的区别是什么？ ####

ArrayList和LinkedList都是Java集合框架中的一部分，它们实现了List接口，用于存储元素的动态数组。然而，它们在内部实现、效率、以及操作特点上有一些显著的区别。

（1）内部实现

ArrayList是基于数组实现的，其内部维护了一个动态数组来存储元素。数组是一块连续的内存空间，因此ArrayList在随机访问元素时非常高效，时间复杂度为O(1)。然而，当添加或删除元素时，如果数组已满或需要移动元素，可能需要进行扩容或数据移动操作，这可能会降低效率。

LinkedList则是基于链表实现的，其内部元素是通过节点（Node）连接在一起的。每个节点包含实际的数据以及指向下一个和上一个节点的指针。因此，LinkedList在内存中的存储不是连续的。这种结构使得LinkedList在添加或删除元素时效率较高，因为只需要修改相关节点的指针，而不需要移动大量数据。然而，随机访问元素时，LinkedList需要从头或尾开始遍历，效率较低。

（2）效率

当需要频繁地进行随机访问元素（如通过索引获取元素）时，ArrayList通常比LinkedList更高效，因为ArrayList可以直接通过索引定位到元素。

而在添加或删除元素时，LinkedList通常比ArrayList更高效，因为LinkedList只需要修改相关节点的指针，而不需要移动其他元素。

（3）控件开销

ArrayList的主要控件开销在于需要在其内部数组中预留一定的空间以存储元素。当元素数量超出当前容量时，ArrayList会自动进行扩容，以适应更多的元素。这种扩容操作可能会导致一定的性能开销。

LinkedList的主要控件开销在于需要存储每个节点的信息以及节点之间的指针信息。这增加了额外的内存开销，但使得在链表中间添加或删除元素的操作变得高效。

（4）线程安全

ArrayList和LinkedList都不是线程安全的。如果在多线程环境下使用，需要手动进行同步处理或者使用线程安全的集合类，如Collections.synchronizedList()或CopyOnWriteArrayList。

综上所述，ArrayList和LinkedList各有其优势和适用场景。在选择使用哪种集合时，应根据具体的应用需求和性能要求来做出决策。如果需要频繁地进行随机访问元素，ArrayList可能更合适；而如果需要频繁地进行添加或删除元素的操作，LinkedList可能更合适。

#### 23、ArrayList 和 Vector 的区别？ ####

ArrayList和Vector都是基于数组实现的List集合类，它们提供了动态数组的功能，可以根据需要自动调整大小以存储对象。

Vector的公共方法大多带有synchronized关键字，确保了方法是同步的，因此Vector是线程安全的。而ArrayList没有这样的同步措施，所以它是线程不安全的。

由于Vector的方法是同步的，因此在多线程环境下会涉及锁的获取和释放，这可能导致性能上的开销。相比之下，ArrayList由于没有额外的同步开销，通常运行得更快。

当底层数组容量不足以容纳新元素时，ArrayList会在原有基础上扩展约0.5倍的容量，而Vector则扩展一倍的容量。这意味着在频繁进行大量添加操作的情况下，ArrayList可能会有更高的效率。

#### 24、队列和栈是什么？有什么区别？ ####

（1）队列先进先出，栈先进后出。

（2）遍历数据速度不同。

栈只能从头部取数据 也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性；

队列则不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多。

#### 25、Queue和Deque的区别是什么？ ####

Queue以及Deque都是继承于Collection，Deque是Queue的子接口。

Queue是FIFO的单向队列，Deque是双向队列。

Queue有一个直接子类PriorityQueue，而Deque中直接子类有两个：LinkedList以及ArrayDeque。

PriorityQueue的底层数据结构是数组，而无边界的形容，那么指明了PriorityQueue是自带扩容机制的。

ArrayDeque是无初始容量的双端队列，LinkedList则是双向链表。

PriorityQueue可以作为堆使用，而且可以根据传入的Comparator实现大小的调整，会是一个很好的选择。  
ArrayDeque通常作为栈或队列使用，但是栈的效率不如LinkedList高。  
LinkedList通常作为栈或队列使用，但是队列的效率不如ArrayQueue高。

#### 26、在 Queue 中 poll()和 remove()有什么区别？ ####

（1）offer()和add()区别：

增加新项时，如果队列满了，add会抛出异常，offer返回false。

（2）poll()和remove()区别：

poll()和remove()都是从队列中删除第一个元素，remove抛出异常，poll返回null。

（3）peek()和element（）区别：

peek()和element（）用于查询队列头部元素，为空时element抛出异常，peek返回null。

#### 27、说说你对优先队列的理解 ####

优先队列中的元素可以按照任意的顺序插入，但会按照有序的顺序获取。

优先队列常用结构是PriorityQueue和ArrayDeque。

也就是在调用remove时，总是删除队列中最小的元素。

优先队列使用堆作为存储数据结构，堆是一个自组织的二叉树，其添加和删除操作会让最小的元素移动到根，而不必花费时间对元素进行排序。

优先队列的主要用途是调度。每个任务有一个优先级，任务以随机顺序插入到队列中，每当启动一个新的任务时，将从队列中删除优先级最高的任务。

#### 28、说说你对双端队列的理解 ####

双端队列是一种特殊的队列，它的两端都可以进行插入和删除操作。这种队列的实现方式是使用两个指针，一个指针指向队列的头部，另一个指针指向队列的尾部。当需要插入或删除元素时，只需要移动指针即可。

双端队列的主要优点是可以在队列的两端进行操作，因此具有较高的效率。此外，双端队列还具有一些其他的优点，例如可以在队列的两端进行查询操作，因此具有较高的查询效率。

双端队列的缺点是插入和删除操作的时间复杂度都是O(1)，因此在处理大量数据时可能会导致性能问题。此外，双端队列的空间复杂度也是O(1)，因此在插入和删除元素时需要使用额外的空间。

#### 29、CopyOnWriteArrayList是什么，有哪些应用场景？ ####

CopyOnWriteArrayList是Java并发包java.util.concurrent下提供的一个线程安全的ArrayList实现，它是写时复制（Copy-On-Write）的容器。

CopyOnWriteArrayList的核心特性在于，当修改容器（例如添加、删除元素）时，不是直接修改当前容器，而是先复制当前容器的副本，然后在副本上进行修改。修改完成后，再将原容器的引用指向新的容器。这种策略使得读操作可以完全不用加锁，因此读取性能极高。同时，写入操作也不会阻塞读取操作，只有写入和写入之间需要进行同步等待。

由于CopyOnWriteArrayList的这些特性，它特别适用于以下场景：

1.  读多写少的场景：当对数据的读操作次数远远高于写操作时，使用CopyOnWriteArrayList可以有效提升系统性能。因为每次修改操作都会创建底层数组的副本，从而避免了读取操作受到写入操作的干扰。
2.  数据更新要求不频繁的场景：由于每次添加、修改或删除列表中的元素时，CopyOnWriteArrayList都需要重新创建一个新的底层数组，因此在实现上会消耗更多的内存空间。因此，它更适用于数据更新不频繁的场景。
3.  互斥访问数据不方便的场景：在多线程环境下，如果需要对一个ArrayList实例进行访问，通常需要加锁以保证数据一致性。但在某些场景下，加锁可能会给程序带来额外的复杂度和延迟。此时，可以考虑使用CopyOnWriteArrayList。
4.  需要保证数据一致性的场景：由于每个线程都在自己的副本上进行操作，因此不存在读取过程中数据被其他线程修改的问题，从而保证了数据的一致性。

#### 30、使用CopyOnWriteArrayList时需要注意哪些问题？ ####

（1）内存占用问题

由于CopyOnWriteArrayList的写时复制机制，当进行写操作时，内存中会同时驻扎两个对象的内存，旧的对象和新写入的对象。在复制时只复制容器里的引用，在写时才会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存。

（2）数据一致性问题

CopyOnWriteArrayList只能保证数据的最终一致性，不能保证数据的实时一致性。因为复制和操作元素需要一些时间，所以会有延迟。如果希望写入的数据马上能读到，要求数据强一致性的话，建议不要使用CopyOnWriteArrayList。

（3）线程安全

CopyOnWriteArrayList是写同步，读非同步的。多个线程对CopyOnWriteArrayList进行写操作是线程安全的，但是在读操作时是非线程安全的。如果在for循环中使用下标的方式去读取数据，可能会报错ArrayIndexOutOfBoundsException。

（4）不支持add()、set()、remove()方法

CopyOnWriteArrayList的迭代器实现了ListIterator接口，但是add()、set()、remove()方法都直接抛出了UnsupportedOperationException异常，所以应该避免使用迭代器的这几个方法。

#### 31、说一下链表的实现原理 ####

从数组中间删除一个元素开销很大，其原因是向数组中插入元素时，此元素之后的所有元素都要向后端移动，删除时也是，数组中位于被删除元素之后的所有元素都要向数组的前端移动。

![在这里插入图片描述][67b00985562a4b208e6616dfef7c0d21.png_pic_center]

此时，在Java中，可以通过链表解决这个问题。

数组是在连续的存储位置上存放对象引用，而链表则是将每个对象存放在单独的链接link中。每个链接还存放着序列中下一个链接的引用。在Java中，所有的链表都是双向链接，即每个链接还存储前驱的引用。

![在这里插入图片描述][2a6b537edde2454ea55b0ba82a5751e5.png_pic_center]

在链表中新增、删除一个元素是很轻松的操作，只需要更新锁删除元素前后对应的链接即可。

![在这里插入图片描述][5cab72004cd44d8baf500634b01f9ea0.png_pic_center]  
有的同学可能觉得上面两个图，没啥区别，其实就是前后链接指向的问题，so easy。

在Java中，可以使用双指针法来向链表中间添加元素。

ListNode newNode = new ListNode(val);  
    if (head == null) {
          
        head = newNode;  
    } else {
          
        ListNode curr = head;  
        while (curr.next != null && curr.next.next != null) {
          
            curr = curr.next;  
        }  
        curr.next = newNode;  
    }

在上面的代码中，我们首先创建一个新的节点newNode，并将其插入到链表的中间。如果链表为空，则将新节点设置为头部节点。否则，我们遍历链表，找到最后一个节点，并将新节点插入到该节点的后面。

#### 32、说一下散列表的实现原理 ####

如果想要查找某个元素，但又不知道它的存储位置，此时，就需要遍历所有元素，直到找到匹配的元素为止。如果集合中包含的元素很多，就需要耗费很长时间时间。

此时，散列表闪亮登场。

散列表可以快速的查找对象，散列表为每个元素计算一个整数，称为散列码，散列码是以某种方式由对象的实例字段得出的一个整数，可以保证不同的数据对象拥有不同的散列码。

在Java中，删列表实现为链表数组，每个列表被称为桶bucket，可以通过：先计算散列码，再与桶的总数取余，所得到的数就是保存这个元素的那个桶的索引。

可以通过初始化桶数的方式，快速的进行元素插入。

如果装载因子是0.75，当表中已经填到75%就会进行自动再散列，新的桶数就是原来的两倍。对大多数情况而言，装载因子为0.75是比较合理的。

#### 33、说说你对映射视图的理解 ####

Java中的映射视图是指一种将Map转换为Set或Collection的机制，以便于更方便地操作Map中的元素。

1.  keySet()：返回包含Map中所有键的Set；
2.  values()：返回包含Map中所有值的Collection；
3.  entrySet()：返回包含Map中所有键值对的Set；

通过这些映射视图，可以方便地遍历Map中的元素、检查某个键是否存在、删除指定键等操作。

在使用时需要注意，映射视图只是一个视图，即对原Map进行的修改会反映到相应的映射视图中，反之亦然，因此要谨慎使用。

另外，由于映射视图是基于Map实现的，因此对映射视图的修改也可能影响到原Map中的元素。

#### 34、说说你对弱散列映射WeakHashMap的理解 ####

Java中的弱散列映射指的是一种特殊的Map实现，即WeakHashMap类。和普通HashMap不同，WeakHashMap中的键是弱引用，即当某个键不再被外部对象引用时，该键及其对应的值会被自动清除掉，以避免内存泄漏问题。

通过使用WeakHashMap，可以将某些对象与其他应用逻辑分离开来，使得它们的生命周期仅由其它对象的引用决定，当没有任何对象引用时，这些对象会被自动清除，从而释放系统资源。在Java中，常用WeakHashMap来实现缓存、事件通知等场景。需要注意的是，由于弱引用的存在，WeakHashMap无法保证元素的顺序，因此在遍历时应该谨慎。

WeakHashMap是一种基于红黑树实现的有序映射，它的常用方法包括：

1.  put(K key, V value)：将一个键值对添加到弱散列映射中；
2.  get(K key)：返回一个键值对，如果键不存在则返回null；
3.  remove(K key)：从弱散列映射中删除一个键值对；
4.  containsKey(K key)：检查一个键是否存在于弱散列映射中；
5.  size()：返回弱散列映射中键值对的数量；

这些方法都是基于红黑树实现的，因此它们的时间复杂度都是O(log n)，其中n是Map中元素的数量。

#### 35、说说你对链接散列映射LinkedHashMap的理解 ####

Java中的链接散列映射指的是HashMap和LinkedHashMap这两个键值对映射集合实现类。它们都是基于哈希表实现的，链式散列是解决哈希冲突的一种方法。

具体来说，HashMap和LinkedHashMap内部使用哈希表来存储键值对，当多个键经过哈希函数计算后产生同一个索引位置时，就会产生哈希冲突。为了解决哈希冲突，HashMap和LinkedHashMap使用链式散列技术，即在哈希表每个索引位置上维护一个链表，将所有哈希值相同的键值对存放在同一个链表中，从而实现快速查找和添加元素。

HashMap和LinkedHashMap的区别在于，前者是无序键值对集合，而后者是有序键值对集合。具体来说，LinkedHashMap内部使用一个双向链表来维护键值对的插入顺序，因此遍历LinkedHashMap时可以按照键值对插入的顺序进行。需要注意的是，在使用HashMap和LinkedHashMap时，应根据具体的业务需求和性能要求选择合适的实现类。

#### 36、说说你对LinkedHashSet的理解 ####

Java中的链接散列集指的是HashSet和LinkedHashSet这两个集合实现类。它们都是基于哈希表（Hash Table）实现的，链式散列是解决哈希冲突的一种方法。

HashSet和LinkedHashSet的区别在于，前者是无序集合，而后者是有序集合。具体来说，LinkedHashSet内部使用一个双向链表来维护元素的插入顺序，因此遍历LinkedHashSet时可以按照元素插入的顺序进行。需要注意的是，在使用HashSet和LinkedHashSet时，应根据具体的业务需求和性能要求选择合适的实现类。

LinkedHashMap的常用方法包括：

这些方法都是基于链表实现的，因此它们的时间复杂度都是O(1)，其中n是Map中元素的数量。

#### 37、说说你对枚举集EnumSet的理解 ####

Java中的枚举集指的是基于枚举类型实现的集合类，即EnumSet。

它是一个专门用于存储枚举类型值的高效集合实现类，可以实现基本操作（如添加、删除、查找等）和集合运算（如交、并、补等），同时还提供了高性能的迭代器，可以按照枚举类型常量在内存中出现的顺序进行遍历。

EnumSet使用位向量（bit vector）实现，即将每个枚举类型常量映射到一个二进制位上，从而快速进行集合运算。由于EnumSet只能存储枚举类型值，因此它具有类型安全性、性能高效、空间利用率高等优点。

EnumSet是一个抽象类，不能直接实例化，但可以通过EnumSet的静态工厂方法创建实例，例如EnumSet.of()、EnumSet.range()等。此外，EnumSet也支持各种集合转换操作，可以与其他集合实现类进行互相转换。

#### 38、说说你对EnumMap的理解 ####

Java中的枚举映射指的是基于枚举类型实现的键值对集合类，即EnumMap。它是一个专门用于存储枚举类型作为键的键值对集合实现类，可以实现基本操作（如添加、删除、查找等）和集合运算（如交、并、补等），同时还提供了高性能的迭代器，可以按照枚举类型常量在内存中出现的顺序进行遍历。

EnumMap使用数组实现，数组的长度等于枚举类型常量数目，每个位置上存储的是该枚举类型常量所对应的值。由于EnumMap只能存储枚举类型作为键，因此它具有类型安全性、性能高效、空间利用率高等优点。

需要注意的是，EnumMap也是一个抽象类，不能直接实例化，但可以通过EnumMap的构造方法或静态工厂方法创建实例，例如new EnumMap<>(MyEnum.class)、EnumMap.copyOf()等。此外，EnumMap也支持各种集合转换操作，可以与其他集合实现类进行互相转换。

#### 39、Comparator与Comparable有什么区别 ####

Comparator与Comparable在Java中都是用于比较对象大小的接口。

首先，从功能角度来看，Comparable是一个排序接口，当一个类实现了Comparable接口时，它表示这个类的对象之间可以相互比较大小，即这个类支持排序。而Comparator则是一个比较器接口，它允许我们实现该接口，自定义比较算法，从而创建一个特定类的比较器来进行排序。可以说，Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。

其次，从使用灵活性来看，Comparable接口的耦合性相对较强，通常用作类的默认排序方法。这意味着如果我们需要对一个类的实例进行排序，而该类的定义又没有发生变化，我们通常会让该类实现Comparable接口，并提供比较的逻辑。而Comparator接口的灵活性和扩展性更优，它主要用于当默认排序不满足需求时，提供自定义排序。例如，我们可能需要对一个已经存在的类进行排序，而这个类并没有实现Comparable接口，或者我们想要对这个类进行不同的排序，这时就可以使用Comparator接口。

最后，从方法定义上来看，Comparable接口定义了一个抽象方法compareTo(T o)，用于比较当前对象与另一个对象的大小。而Comparator接口定义了一个抽象方法compare(T o1, T o2)，用于比较两个对象的大小。

#### 40、Iterator 怎么使用？有什么特点？ ####

为了方便的处理集合中的元素,Java中出现了一个对象,该对象提供了一些方法专门处理集合中的元素.例如删除和获取集合中的元素.该对象就叫做迭代器(Iterator)。

Iterator 接口源码中的方法：

1.  java.lang.Iterable 接口被 java.util.Collection 接口继承，java.util.Collection 接口的 iterator() 方法返回一个 Iterator 对象
2.  next() 方法获得集合中的下一个元素
3.  hasNext() 检查集合中是否还有元素
4.  remove() 方法将迭代器新返回的元素删除

#### 41、Iterator 和 ListIterator 有什么区别？ ####

（1）ListIterator 继承 Iterator

（2）ListIterator 比 Iterator多方法

*  add(E e) 将指定的元素插入列表，插入位置为迭代器当前位置之前
 *  set(E e) 迭代器返回的最后一个元素替换参数e
 *  hasPrevious() 迭代器当前位置，反向遍历集合是否含有元素
 *  previous() 迭代器当前位置，反向遍历集合，下一个元素
 *  previousIndex() 迭代器当前位置，反向遍历集合，返回下一个元素的下标
 *  nextIndex() 迭代器当前位置，返回下一个元素的下标

（3）使用范围不同，Iterator可以迭代所有集合；ListIterator 只能用于List及其子类

*  ListIterator 有 add 方法，可以向 List 中添加对象；Iterator 不能
 *  ListIterator 有 hasPrevious() 和 previous() 方法，可以实现逆向遍历；Iterator不可以
 *  ListIterator 有 nextIndex() 和previousIndex() 方法，可定位当前索引的位置；Iterator不可以
 *  ListIterator 有 set()方法，可以实现对 List 的修改；Iterator 仅能遍历，不能修改。

#### 42、快速失败 (fail-fast) 和安全失败 (fail-safe) 的区别是什么？ ####

快速失败（fail-fast）策略的核心在于一旦发现数据结构在迭代过程中被修改，系统会立即停止迭代并通过抛出ConcurrentModificationException异常来报告错误。这样做的目的是尽早地发现错误，防止错误的扩散，从而保证软件的稳定性和可靠性。例如，在使用ArrayList或HashMap等集合类进行迭代时，如果尝试在迭代过程中修改集合内容，就会触发这种快速失败的行为。

安全失败（fail-safe）策略则相对宽容，它允许在迭代过程中对数据结构进行修改，而不会立即抛出异常。这种策略通常通过使用额外的措施，如迭代器复制、锁或其他同步机制，来确保即使在多线程环境下也能安全地进行操作。这样可以减少因并发修改导致的问题，提高程序的容错性。

上一篇：[3万字80道Java经典面试题总结（2024修订版）- Java基础篇][3_80_Java_2024_- Java]

🏆文章收录于：[100天精通Java从入门到就业][100_Java]

全网最细Java零基础手把手入门教程，系列课程包括：Java基础、Java8新特性、Java集合、高并发、性能优化等，适合零基础和进阶提升的同学。

🏆哪吒多年工作总结：[**Java学习路线总结，搬砖工逆袭Java架构师**][Java_Java]。

> 华为OD机试 2023B卷题库疯狂收录中，刷题[**点这里**][Link 1]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

[Java_Java]: https://blog.csdn.net/guorui_java/article/details/120098618
[Java]: https://bbs.csdn.net/topics/614261188
[a41fedbb12064ec4bc44be23d192fa7c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/27489f9697ee4c9b857855c4f69192ad.png
[1fadd53356a545eab11331ebd3d84dbb.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/89e25ce0381148e0aa84593c0e120fa1.png
[aaf30a3880854b5eb926314bb221658e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/f5555e8b14fc4c28847cc0b5370a2343.png
[0760927951c14795963357cf835876fc.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/c3162f3c119c432b90a2b2318e5fa006.png
[67b00985562a4b208e6616dfef7c0d21.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/9f67d92179274ac4bb8def64dc7bb1e3.png
[2a6b537edde2454ea55b0ba82a5751e5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/fe966b346c5444d6a482216d28f473c9.png
[5cab72004cd44d8baf500634b01f9ea0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/b8c22040c07f4a4f83d2602194d81959.png
[3_80_Java_2024_- Java]: https://blog.csdn.net/guorui_java/article/details/137203696
[100_Java]: https://blog.csdn.net/guorui_java/category_12196381.html
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473