2024-12-04 12:14 已编辑中南大学 Java 发布于湖南

关注

[八股大全]Java常见集合类篇

1.集合基础知识

1.Java集合有哪几种？

Java集合类主要由两个接口Collection和Map派生出来的，

一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue(念q)。

哪些是线程安全哪些线程不安全？

java.util包下的集合类大部分都是线程不安全的，例如我们常用的HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap，这些都是线程不安全的集合类，但是它们的优点是**性能好。**如果需要使用线程安全的集合类，则可以使用Collections工具类提供的synchronizedXxx()方法，将这些集合类包装成线程安全的集合类。java.util包下也有线程安全的集合类，例如Vector、Hashtable。这些集合类都是比较古老的API，虽然**实现了线程安全，但是性能很差。**所以即便是需要使用线程安全的集合类，也建议将线程不安全的集合类包装成线程安全集合类的方式，而不是直接使用这些古老的API。从Java5开始，Java在java.util.concurrent包下提供了大量支持高效并发访问的集合类，它们既能包装良好的访问性能，有能包装线程安全。这些集合类可以分为两部分，它们的特征如下：

以Concurrent开头的集合类：以Concurrent开头的集合类代表了支持并发访问的集合，它们可以支持多个线程并发写入访问，这些写入线程的所有操作都是线程安全的，但读取操作不必锁定。以Concurrent开头的集合类采用了更复杂的算法来保证永远不会锁住整个集合，因此在并发写入时有较好的性能。
以CopyOnWrite开头的集合类：以CopyOnWrite开头的集合类采用复制底层数组的方式来实现写操作。当线程对此类集合执行读取操作时，线程将会直接读取集合本身，无须加锁与阻塞。当线程对此类集合执行写入操作时，集合会在底层复制一份新的数组，接下来对新的数组执行写入操作。由于对集合的写入操作都是对数组的副本执行操作，因此它是线程安全的。

2.集合的具体实现类

List

ArrayList：Object[] 数组。
Vector：Object[] 数组。
LinkedList：双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)。

Map

HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
Hashtable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。
TreeMap：红黑树（自平衡的排序二叉树）。

Set

HashSet(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素。
LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。
TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)。

Queue

PriorityQueue: Object[] 数组来实现小顶堆。
DelayQueue:PriorityQueue。
ArrayDeque: 可扩容动态双向数组。

3.说说 List, Set, Queue, Map 四者的区别？

Java中的集合类主要由Collection和Map这两个接口派生而出，其中Collection接口又派生出三个子接口，分别是Set、List、Queue。所有的Java集合类，都是Set、List、Queue、Map这四个接口的实现类，这四个接口将集合分成了四大类，其中

Set代表无序的，元素不可重复的集合；
List代表有序的，元素可以重复的集合；
Queue代表先进先出（FIFO）的队列；
Map代表具有映射关系（key-value）的集合。

4.为什么要使用集合？

因为在实际开发中，存储的数据类型多种多样且数量不确定。这时，Java 集合就派上用场了。与数组相比，Java 集合提供了更灵活、更有效的方法来存储多个数据对象。Java 集合框架中的各种集合类和接口可以存储不同类型和数量的对象，同时还具有多样化的操作方式。相较于数组，Java 集合的优势在于它们的大小可变、支持泛型、具有内建算法等。总的来说，Java 集合提高了数据的存储和处理灵活性，可以更好地适应现代软件开发中多样化的数据需求，并支持高质量的代码编写。

5.什么是fail fast快速失败机制？

快速失败（fail-fast）是Java集合框架中的一种错误检测机制。

Fail-fast 机制主要用于确保集合在遍历过程中不被修改，从而保证数据的一致性和稳定性。

当多个线程对同一个ArrayList进行操作时，如果一个线程在遍历该集合的过程中，另一个线程同时尝试修改它（例如添加、删除元素），那么遍历线程会抛出ConcurrentModificationException异常。这种机制旨在防止并发修改导致的数据不一致问题。

6.什么是fail safe安全失败机制？

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。

缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

7.如何让一个集合不能被修改？

可以采用Collections包下的unmodifiableMap/unmodifiableList/unmodifiableSet方法，通过这个方法返回的集合，是不可以修改的。如果修改的话，会抛出 java.lang.UnsupportedOperationException异常。

List<String> list = new ArrayList<>();
list.add("x");
Collection<String> clist = Collections.unmodifiableCollection(list);
clist.add("y"); // 运行时此行报错
System.out.println(list. size());

对于List/Set/Map集合，Collections包都有相应的支持。

那使用final关键字进行修饰可以实现吗？

答案是不可以。

final关键字修饰的成员变量如果是是引用类型的话，则表示这个引用的地址值是不能改变的，但是这个引用所指向的对象里面的内容还是可以改变的。

而集合类都是引用类型，用final修饰的话，集合里面的内容还是可以修改的。

引用类型有哪些？

在Java中，引用类型主要包括类（Class）、接口（Interface）、数组（Array）以及基于这些结构的其他数据类型如字符串（String）和枚举类型（Enum）。

Java将数据类型主要分为两大类：基本数据类型和引用数据类型。基本数据类型包括byte、short、int、long、float、double、char和boolean，它们直接存储值而非对象的引用。引用类型的变量则存储的是对象在内存中的地址，即引用了对象的位置。

2.List

-1.List有哪些类？

0.什么是ArrayList?

ArrayList 的底层是动态数组，它的容量能动态增长。在添加大量元素前，应用可以使用ensureCapacity操作增加 ArrayList 实例的容量。ArrayList 继承了 AbstractList ，并实现了 List 接口

0.有哪些线程安全的List?

参考答案

Vector Vector是比较古老的API，虽然保证了线程安全，但是由于效率低一般不建议使用。
Collections.SynchronizedList SynchronizedList是Collections的内部类，Collections提供了synchronizedList方法，可以将一个线程不安全的List包装成线程安全的List，即SynchronizedList。它比Vector有更好的扩展性和兼容性，但是它所有的方法都带有同步锁，也不是性能最优的List。
CopyOnWriteArrayList CopyOnWriteArrayList是Java 1.5在java.util.concurrent包下增加的类，它采用复制底层数组的方式来实现写操作。当线程对此类集合执行读取操作时，线程将会直接读取集合本身，无须加锁与阻塞。当线程对此类集合执行写入操作时，集合会在底层复制一份新的数组，接下来对新的数组执行写入操作。由于对集合的写入操作都是对数组的副本执行操作，因此它是线程安全的。在所有线程安全的List中，它是性能最优的方案。

1.ArrayList 和 Array（数组）的区别？

ArrayList 内部基于动态数组实现，比 Array（静态数组）使用起来更加灵活：

ArrayList会根据实际存储的元素动态地扩容或缩容，而 Array 被创建之后就不能改变它的长度了。
ArrayList 允许你使用泛型来确保类型安全，Array 则不可以。
ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。Array 可以直接存储基本类型数据，也可以存储对象。
ArrayList 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如 add()、remove()等。Array 只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。
ArrayList创建时不需要指定大小，而Array创建时必须指定大小

2.ArrayList 和 Vector 的区别?

ArrayList 是 List 的主要实现类，底层使用 Object[]存储，适用于频繁的查找工作，线程不安全。
Vector 是 List 的古老实现类，底层使用Object[] 存储，线程安全。
ArrayList在内存不够时扩容为原来的1.5倍，Vector是扩容为原来的2倍。

3.ArrayList 可以添加 null 值吗？

ArrayList 中可以存储任何类型的对象，包括 null 值。

4.Arraylist 与 LinkedList的区别

ArrayList的实现是基于数组，LinkedList的实现是基于双向链表；
对于随机访问ArrayList要优于LinkedList，ArrayList可以根据下标以O(1)时间复杂度对元素进行随机访问，而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起，查找某个元素的时间复杂度是O(N)；
对于插入和删除操作，LinkedList要优于ArrayList，因为当元素被添加到LinkedList任意位置的时候，不需要像ArrayList那样重新计算大小或者是更新索引；
LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素

5.ArrayList扩容原理

ArrayList有三种构造方法，无参构造方法将创建一个空的ArrayList，其内部使用一个默认容量为10的空数组初始化。如果通过指定初始容量来构造ArrayList，那么会创建一个具有该初始容量的数组。第三种构造方法允许传入一个集合，并将其所有元素添加到ArrayList中。

无参构造方法扩容过程如下

ArrayList的底层是动态数组，默认第一次插入元素时创建大小为10的数组。当调用add方法添加一个元素时，首先会确保当前ArrayList维护的数组具有存储新元素的能力。如果数组的容量不足以存储新元素，那么就会通过grow方法进行扩容。扩容的方式是将数组的容量扩大到原来的1.5倍，然后将原数组的数据复制到新的数组中。最后，将新元素添加到数组的末尾

6. 面试题-ArrayList list=new ArrayList(10)中的list扩容几次

在ArrayList的源码中提供了一个带参数的构造方法，这个参数就是指定的集合初始长度，所以给了一个10的参数，就是指定了集合的初始长度是10，这里面并没有扩容。

7.谈谈CopyOnWriteArrayList的原理

CopyOnWriteArrayList是Java并发包里提供的并发类，简单来说它就是一个线程安全且读操作无锁的ArrayList。CopyOnWriteArrayList允许线程并发访问读操作，这个时候是没有加锁限制的，性能较高。正如其名字一样，在写操作时会复制一份新的List，在新的List上完成写操作，然后再将原引用指向新的List。这样就保证了写操作的线程安全。

优点：读操作性能很高，因为无需任何同步措施，比较适用于读多写少的并发场景。在遍历传统的 List时，若中途有别的线程对其进行修改，则会抛出ConcurrentModificationException异常。而 CopyOnWriteArrayList由于其"读写分离"的思想，遍历和修改操作分别作用在不同的List容器，所以在使用迭代器进行遍历时候，也就不会抛出ConcurrentModificationException异常了。
缺点：一是内存占用问题，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC。二是无法保证实时性，Vector对于读写操作均加锁同步，可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。

7.LinkedList 为什么不能实现 RandomAccess 接口？

RandomAccess 是一个标记接口，用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）。由于 LinkedList 底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现 RandomAccess 接口

8.怎么在遍历 ArrayList 时移除一个元素？

foreach删除会导致快速失败问题，可以使用迭代器的 remove() 方法。

Iterator itr = list.iterator();
while(itr.hasNext()) {
      if(itr.next().equals("jay") {
        itr.remove();
      }
}

9.什么是ArrayList的快速失败fail fast机制

ArrayList的快速失败（fail-fast）是Java集合框架中的一种错误检测机制。

当多个线程对同一个ArrayList进行操作时，如果一个线程在遍历该集合的过程中，另一个线程同时尝试修改它（例如添加、删除元素），那么遍历线程会抛出ConcurrentModificationException异常。Fail-fast 机制主要用于确保集合在遍历过程中不被修改，从而保证数据的一致性和稳定性。

10.如何实现数组和List之间的转换

数组转list，可以使用jdk自动的一个工具类Arrars，里面有一个asList方法可以转换为数组

List 转数组，可以直接调用list中的toArray方法、，需要给一个参数，指定数组的类型，需要指定数组的长度。

11.用Arrays.asList转List后，如果修改了数组内容，list受影响吗？List用toArray转数组后，如果修改了List内容，数组受影响吗

Arrays.asList转换list之后，如果修改了数组的内容，list会受影响，因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址

list用了toArray转数组后，如果修改了list内容，数组不会影响，当调用了toArray以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影响。

12.ArrayList 和 LinkedList 不是线程安全的，你们在项目中是如何解决这个的线程安全问题的？

第一：我们使用这个集合，优先在方法内使用，定义为局部变量，这样的话，就不会出现线程安全问题。

第二：如果非要在成员变量中使用的话，可以使用线程安全的集合来替代

ArrayList可以用CopyOnWriteArrayList

LinkedList 换成ConcurrentLinkedQueue来使用

3.Map相关面试题

0.Map有哪些类？

Map接口有很多实现类，其中比较常用的有HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap。

对于不需要排序的场景，优先考虑使用HashMap，因为它是性能最好的Map实现。如果需要保证线程安全，则可以使用ConcurrentHashMap。它的性能好于Hashtable，因为它在put时采用分段锁/CAS的加锁机制，而不是像Hashtable那样，无论是put还是get都做同步处理。对于需要排序的场景，如果需要按插入顺序排序则可以使用LinkedHashMap，如果需要将key按自然顺序排列甚至是自定义顺序排列，则可以选择TreeMap。如果需要保证线程安全，则可以使用Collections工具类将上述实现类包装成线程安全的Map。

TreeMap 基于红黑树实现。

HashMap 1.7基于哈希表实现，1.8基于数组+链表+红黑树。

HashTable 和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高(1.7 ConcurrentHashMap 引入了分段锁, 1.8 引入了红黑树)。

LinkedHashMap 使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用(LRU)顺序。

1.HashMap 和 Hashtable 的区别

线程是否安全：HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；
对 Null key 和 Null value 的支持：HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间（后文中我会结合源码对这一过程进行分析）。Hashtable 没有这样的机制。

2.HashSet与HashMap的区别

(1)HashSet实现了Set接口, 仅存储对象; HashMap实现了 Map接口, 存储的是键值对.

(2)HashSet底层其实是用HashMap实现存储的, HashSet封装了一系列HashMap的方法. 依靠HashMap来存储元素值,(利用hashMap的key键进行存储), 而value值默认为Object对象. 所以HashSet也不允许出现重复值, 判断标准和HashMap判断标准相同, 两个元素的hashCode相等并且通过equals()方法返回true.

4.HashMap的底层实现(jdk1.7和jdk1.8有区别)

jdk1.7

JDK7中的HashMap，是基于数组+链表来实现的，它的底层维护一个Entry数组。它会根据计算的hashCode将对应的KV键值对存储到该数组中，一旦发生hashCode冲突，那么就会将该KV键值对放到对应的已有元素的后面，此时便形成了一个链表式的存储结构。

JDK7中HashMap的实现方案有一个明显的缺点，即当Hash冲突严重时，在桶上形成的链表会变得越来越长，这样在查询时的效率就会越来越低，其时间复杂度为O(N)。

jak1.8

JDK8中的HashMap，是基于数组+链表+红黑树来实现的，它的底层维护一个Node数组。当链表长度大于阈值（默认为 8）外加数组长度大于64时时，将链表转化为红黑树，以减少搜索时间。这么做主要是在查询的时间复杂度上进行优化，链表为O(N)，而红黑树一直是O(logN)，可以大大的提高查找性能。

1.线性探测法和链地址法

线性探测法是开放地址法的一种，用于处理哈希表中的冲突问题。

线性探测法的核心在于解决哈希冲突时不采用链表，而是通过探测散列表中的下一个位置来寻找空位。具体来说，如果一个关键字通过散列函数计算的地址已经被占用，它会尝试下一个地址，即当前地址加一（也可以考虑为负数或固定步长，视情况而定），直到找到一个空位为止。这种方法在实际操作中简单且易于实现，但当哈希表较为拥挤时，可能会导致很多空闲位置之间出现很多“堆积”，增加了平均查找时间。

链地址法则是将具有相同哈希值的所有元素链接在同一个链表中。

链地址法也被称为拉链法，它采用了不同的策略来解决哈希冲突。在这个方法中，每个哈希到同一个值的元素都会被插入到对应哈希值下的链表中。这意味着如果多个元素的哈希值相同，它们会被放在同一个链表里，以此来区分这些具有相同哈希值的元素。链地址法的优点是可以减少在插入和查找过程中的平均比较次数，因为每次比较的都是同义词节点。然而，这种方法需要额外的空间来存储指针信息。

总之，这两种方法各有利弊，在不同的场景下可能会选择不同的方法来优化性能。线性探测法更适合于哈希冲突较少时使用，而链地址法适合于处理大量冲突的情况。在实际应用中，选择哪种方法取决于具体的需求和场景。

2.红黑树

1.红黑树的介绍

（1）概述

红黑树（Red Black Tree）：也是一种自平衡的二叉搜索树(BST)，之前叫做平衡二叉B树（Symmetric Binary B-Tree）

（2）红黑树的特质

性质1：节点要么是红色,要么是黑色

性质2：根节点是黑色

性质3：叶子节点都是黑色的空节点

性质4：红黑树中红色节点的子节点都是黑色

性质5：从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

在添加或删除节点的时候，如果不符合这些性质会发生旋转，以达到所有的性质，保证红黑树的平衡

（3）红黑树的复杂度

查找：红黑树也是一棵BST（二叉搜索树）树，查找操作的时间复杂度为：O(log n)
添加：添加先要从根节点开始找到元素添加的位置，时间复杂度O(log n)添加完成后涉及到复杂度为O(1)的旋转调整操作故整体复杂度为：O(log n)
删除：首先从根节点开始找到被删除元素的位置，时间复杂度O(log n)删除完成后涉及到复杂度为O(1)的旋转调整操作故整体复杂度为：O(log n)

2.为什么选红黑树，和二叉搜索树、AVL树（平衡二叉树）有什么区别？

二叉搜索树：在二叉搜索树中，左子节点的值小于根节点的值，右子节点的值大于根节点的值。这使得二叉搜索树在查找操作上具有优势。然而**，二叉搜索树可能退化为线性结构，即链**表，当数据插入顺序有序或接近有序时，其查找效率会大大降低，时间复杂度可能达到O(n)。
AVL树:是一种高度平衡的二叉搜索树，它要求每个节点的左右子树的高度差不超过1。这种严格的平衡条件使得AVL树在查找操作上具有很高的效率，时间复杂度为O(log n)。然而，为了维护这种严格的平衡，AVL树在插入和删除操作时需要进行频繁的旋转调整，这增加了维护成本。因此，AVL树适合用于查找操作频繁但插入和删除操作较少的场景。
红黑树：**红黑树是一种近似平衡的二叉搜索树，它通过一系列性质（如节点颜色、黑高）来维护树的平衡。与AVL树相比，红黑树的平衡条件相对宽松，因此在插入和删除操作时的维护成本较低。**虽然红黑树的查找效率略低于AVL树，但其综合性能较好，适用于各种操作（插入、删除和查找）都较频繁的场景。此外，红黑树的高度近似为2log n，在实际应用中表现出良好的性能。

3.在解决 hash 冲突的时候，为什么选择先用链表，再转红黑树?

**因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要,所以元素的插入操作非常高效。所以，当元素个数小于8个的时候，采用链表结构可以保证查询性能。**而当元素个数大于8个的时候并且数组容量大于等于64，会采用红黑树结构。因为红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，在n比较大的时候，使用红黑树可以加快查询速度。