猿兄

2021-08-05 14:37 已编辑北森云计算股份有限公司_CPU_后端开发

关注

面试必会！Java集合高频面试题分享！

上次分享： 面试必会的高频Java基础面试题

今天分享一些面试必会的高频Java基础面试题。

正文5000字，持续更新，建议先点赞收藏再看~

1. 什么是Java的集合？使用集合有什么好处？

Java 的集合也称为容器，是用来存放数据的容器；不过注意，集合存放的只能是引用数据类型的数据，也就是一个个的对象（如果存入基本数据类型的数据，会自动装箱成包装类）。

集合的好处：

集合的长度是可变的。
集合可以存放不同类型的对象。
使用集合之后，可以像操作基本数据类型那样来操作对象。
集合为我们提供了多种数据结构和操作的API，选用合适的集合，能够提程序性能和开发效率。

2. 常用的集合类以及它们的特点？

Java的集合类有两个父接口：Collection 接口和 Map 接口。

Collection接口主要的子接口：List接口、Set接口。

Map接口的主要实现类：HashMap、Hashtable、TreeMap 等。

List接口的主要实现类：ArrayList、Vector、LinkedList 等。

Set接口的主要实现类：HashSet、TreeSet、LinkedHashSet 等。

这些实现类的特点可以看下面的脑图：

3. List

3.1 ArrayList、LinkedList、Vector 各自的特点以及优缺点？

上面脑图中有，这里截图过来，清楚一些：

3.2 ArrayList 和 Vector 的区别/异同？

Vector类是List接口的古老实现类(JDK1.0就有了)，ArrayList类是List接口的主要的常用的实现类(JDK1.2新增的)。
Vector类的方法全都是同步的，两个线程可以安全的访问一个Vector对象；
但是如果一个线程访问Vector对象的话，要在同步操作上花费大量时间；
而 ArrayList 不是同步的，如果不需要保证线程的安全，建议使用ArrayList，效率较高；
（或者直接简单点说：Vector 线程安全但效率低，ArrayList 线程不安全但效率高。）
Vector扩容方式默认是当前容量的1倍；ArrayList扩容是当前容量×1.5+1 。

3.3 ArrayList 和 LinkedList 的区别/异同？

（其实大部分的区别就是数据结构的区别，一个是数组，一个是双向链表）。

ArrayList 底层使用的是数组实现，LinkedList 底层使用的是双向链表实现。
ArrayList 随机查找和遍历速度快，插入删除速度慢；LinkedList 随机查找和遍历速度快，插入和删除速度快。
ArrayList 插入和删除元素的速度会受插入位置的影响；LinkedList 插入和删除元素的速度不会受插入位置的影响。
ArrayList 内存空间会耗费在列表后面的预留空间；LinkedList 内存空间会耗费在每个数据要多存储一个前驱和后继。
ArrayList 需要扩容，扩容是当前容量×1.5+1 ； LinkedList 无需扩容。
ArrayList 和 LinkedList 都不是同步的，都是不保证线程安全。

3.4 ArryList 是线程不安全的？为什么？

ArrayList 是线程不安全的，因为ArrayList里的方法没有加锁，也没有使用其他保证线程安全的措施；当多个线程来对 ArrayList 进行操作时，就会出现并发修改异常。

可以来演示一下集合类线程不安全的情况：

多个线程向一个 ArrayList 中插入元素，代码如下：

然后运行这段代码，会报 java.util.ConcurrentModificationException（并发修改异常） ：

我们可以去看一下 ArrayList add() 方法的源码：

可以看到，ArrayList 的 add() 只是先检查了容量大小，然后就直接插入数据了，并没有做任何保证线程安全的操作，如此一来，多个线程同时来调用这个方法，就会出现线程安全的问题。

3.5 如何解决 ArrayList 线程不安全的问题？

解决 ArrayList 线程安全的办法有3种：

Vector 类替代。
Collections 工具类转换。
JUC 中的 CopyOnWriteArrayList。

下面来具体看一下这三种方法：

解决集合类不安全的方法 1 —— Vector

看过之前关于 Java 集合的，应该还记得脑图中的这个：

Vector 是 List 接口的古老实现类，ArrayList 是 List 接口后面新增的实现类。除了线程安全问题与扩容方式不同，Vector 几乎与 ArrayList 一样。

所以，可以把 Vector 作为解决 ArrayList 线程安全的一种方式（不过 Vector 效率太低）。
实现：

运行之后，发现不会报错了。
其实 Vector 之所以在多线程下插入元素不会发生问题，是因为 Vector 的 add 方法加了synchronized锁。
我们可以看下源码：

（顺便说一下，其实 Vector 很多其他方法也加了锁，比如读方法，相当于读的时候，同一时刻也只能有一个线程能读，效率很低。）
解决集合类不安全的方法 2 —— Collections
Collections 是 Collection 的工具类，其中就提供了一个 synchronizedList() 方法，可以将线程不安全的 ArrayList 转换成线程安全的。
看下实现：

运行之后，发现不会报错了。
至于怎么将 ArrayList 的 add 方法转换成安全的，同样，我们也来看下源码：

原来是在 arrayList 的 add() 的外面套了一层 synchronized 锁！
并且 Collections 工具类也支持将 HashMap, HashSet 之类的转换成线程安全的。

原来是在 arrayList 的 add() 的外面套了一层 synchronized 锁！

解决集合类不安全的方法 3 —— CopyOnWriteArrayList（写时复制）
CopyOnWriteArrayList 是 java.util.concurrent 包里的类，是个线程安全的类。

先看一下实现：
这个相比

这个相比于前面那些，效率又好，读的又快，又能保证一致性。

CopyOnWriteArrayList 的思想是写时复制。
写时复制：我们要向一个文件中添加新数据时，先将原来文件拷贝一份，然后在这个拷贝文件上进行添加；而此时如果有别人读取数据，还是从原文件读取；添加数据完成后，再用这个拷贝文件替换掉原来的文件。这样做的好处是，读写分离，写的是拷贝文件，读的是原文件，可以支持多线程并发读取，而不需要加锁。

来看一眼源码：

其中的 setArray 方法中的 array 是用 volatile 修饰的，可以保证可见性：

同样，JUC 也有 HashMap, HashSet 对应线程安全的实现：
HashSet => CopyOnWriteArraySet
HashMap => ConcurrentHashMap

这也是今天的主角: JUC 中的 CopyOnWriteArrayList 。

先看一下实现：

这个相比于前面那些，效率又好，读的又快，又能保证一致性。

CopyOnWriteArrayList 的思想是 写时复制。

写时复制：我们要向一个文件中添加新数据时，先将原来文件拷贝一份，然后在这个拷贝文件上进行添加；而此时如果有别人读取数据，还是从原文件读取；添加数据完成后，再用这个拷贝文件替换掉原来的文件。这样做的好处是，读写分离，写的是拷贝文件，读的是原文件，可以支持多线程并发读取，而不需要加锁。

其中的 setArray 方法中的 array 是用 volatile 修饰的，可以保证可见性：

4. Map

4.1 HashMap的底层实现原理？

jdk7及jdk7之前，底层是用数组+链表来实现的；

实现过程：
1. new HashMap() 之后，层并不会直接创建数组。而是等 put 数据时才会创建数组。
2. put 数据时（ .put(key,value) ），如果是第一次向这个集合中put数据，会先创建一个长度为 16 的一维数组（ Node[] table ），然后存储数据。存储数据时会先调用 key 所在类的 hashCode 方法，计算出此key的哈希值，再将此哈希值经过处理计算后，得到该数据在数组table上的位置。
3. 然后根据此位置来分情况判断是否存储：
  3.1 情况一：
  此位置为空，直接在此位置上存储put的数据。
  
  3.2 情况二：
  此位置不为空，则说明此位置上已有一个或多个数据了（多个数据以链表形式存储）；
  那么将 put数据的key的哈希值与此位置上已有数据的key的哈希值进行依次比较；
  如果和它们都不同，则存储put的数据；
  将put的数据放在此位置上，原有数据以链表形式存储：
  
  3.3 情况三：
  此位置不为空，且 put数据的key (假设为 key1) 的哈希值与此位置上已有的某个数据的key (假设为 key2 ) 的哈希值相同；
  则调用 key1 所在类的 equals() 方法与 key2 比较；（此 equals() 方法是重写过的，比较的是值；）
  若不同 (既返回false)，则存储put的数据；
  同样，将put的数据放在此位置上，原有数据以链表形式存储。
  
  3.4 情况四：
  若情况三中，key1，key2 equals()方法比较后的结果是相同 (既返回true)，
  则用 key1 的value1 替换 key2 的value2。
4. 扩容，当存储的数据超出临界值，且要存放数据的位置非空时，则扩容，扩容为原来容量的2倍。
  临界值 = 当前容量 x 填充因子
  (填充因子是 0.75)

jdk8及jdk8之后：底层是用数组+链表+红黑树来实现的；
实现过程：
1. new HashMap() 之后，底层并不会直接创建数组。而是等 put 数据时才会创建数组。
2. put 数据时（ .put(key,value) ），如果是第一次向这个集合中put数据，会先创建一个长度为 16 的一维数组（ Node[] table ），然后存储数据。
3. 存储数据的过程和 jdk7及之前基本一样，既先计算哈希值，然后分4种情况判断。
4. 不同点在于用链表存储数据时：
  jdk7 是将新数据放在数组位置上，原有数据以链表形式存储在后面；
  jdk8 是原有数据位置不变，而新数据以链表形式存储在最后。
  可看图：
  
  对比图：

容量扩充
如果使用的是默认初始容量，每次扩充，容量变为原来的 2 倍；
如果使用的是自己指定的初始容量，会先将这个容量扩充为 2 的幂次方大小。
jdk8还有一点不同的是，当数组的某一索引位置上的以链表形式存储的数据大于 8 个，
且当前数组长度大于64时，此索引位置上所有数据改为红黑树存储，这样可以减少搜索查找的时间。

４.２HashMap 容量的长度为什么总是2的幂次方？

为了让HashMap存取高效，要尽量减少碰撞，就是要尽量把数据分配均匀。
Hash值大概有40亿的映射空间，只要哈希函数映射得比较均匀松散，一般来说是很难有碰撞得。
但是解决碰撞之后，新的问题也出现了，内存放不下这40亿长度得数组。
所以用之前需要先对数组的长度取模运算，得到的余数才能作为要存放的位置(既对应的数组下标)。

运算方法：
我们可以用 hash值和数组长度取模，也就是 hash%n；
但这样的运算速度不够快，而如果我们保证数组长度为 2的幂次方时，我们就可以将式子改成 (n-1)&hash ，运算速度会大幅提升；

所以HashMap 容量的长度总是2的幂次方大小。

4.3 知道HashMap 扩容时候的死循环问题吗？

HashMap 1.7 插入数据时，使用的是头插法，并发下扩容时的Rehash，会出现死循环问题；

而 HashMap 1.8 插入数据时，改成了尾插法，解决了扩容时的死循环问题。

（如果还要具体一点的话，可以说一说rehash的流程，建议找篇文章看看，或者后面有时间我再写一篇。）

4.4 如何解决 HashMap 线程不安全的问题？

解决 HashMap 线程安全的办法同样也有3种：

Hashtable类替代。
Collections 工具类转换。
JUC 中的 ConcurrentHashMap 替代。

Hashtable类替代 和 Collections 工具类转换 这两种方法和在 ArrayList 里的用法一样，照着说就可以。

这里主要说一下 ConcurrentHashMap：

用ConcurrentHashMap 替代HashMap，可以解决线程安全的问题，但是其实 ConcurrentHashMap 也是有 jdk1.7 和 jdk1.8 的区别。

jdk1.7
采用Segment分段锁方式保证线程安全，将数据分成一段一段的存储，然后每一段数据单独一个锁；
所以当一个线程占用一个锁访问其中的一段数据时，其他段的数据可以被其他线程访问；
（jdk1.7 ConcurrentHashMap底层结构由 Segment数组和 HashEntry数组组成。一个ConcurrentHashMap里包含一个 Segment数组，数组中的每个Segment都包含一个HashEntry数组，每个HashEntry是一个链表结构的元素。）

jdk1.8
取消了Segment分段锁方式，改成了用 CAS 和 synchronized 来保证线程安全。
jdk1.8 的ConcurrentHashMap中锁的锁更细粒度了， synchronized 只锁定当前链表或红黑树的首节点，这样只要hash不冲突，就不会有线程安全问题，效率大幅提升。
（jdk1.8 ConcurrentHashMap 底层结构由数组+链表+红黑树实现。）

网上看到的一个对比图，感觉很好的展示了 ConcurrentHashMap jdk1.7 和 jdk1.8 的特点和不同，能让我们更好的理解，
给大家分享一下：

4.5 ConcurrentHashMap能完全替代Hashtable吗？

不能。

首先说一下 ConcurrentHashMap 和 Hashtable的异同：

线程安全：
ConcurrentHashMap 和 Hashtable 都是线程安全的；
底层数据结构：
ConcurrentHashMap 的底层数据结构： jdk1.7 是用分段数组+链表实现，jdk1.8 是用数组+链表+红黑树实现，红黑树可以保证查找效率；
Hashtable 底层数据结构是用数组+链表实现。
保证线程安全的方式：
ConcurrentHashMap jdk1.7 是用分段锁的方式保证线程安全，jdk1.8 是用 synchronized 和 CAS 保证线程安全；
Hashtable 是用全表锁来保证线程安全（既一个Hashtable 只用一把锁），这种的方式的效率非常低。

这样一看，好像ConcurrentHashMap什么都比Hashtable好啊！为什么还是不能完全替代Hashtable ？

原因在于一致性：

虽然ConcurrentHashMap 的效率远高于 Hashtable，但因为 ConcurrentHashMap的迭起器是弱一致性的，而Hashtable的迭代器是强一致性的。所以ConcurrentHashMap是不能能完全替代Hashtable的。

弱一致性简单来说就比如我put了一个数据进去，本来应该立刻就可以get到，但是却可能在一段时间内 get不到，一致性比较弱。
而如果是强一致性的话，加入数据后，马上就能get到。

其实要变成强一致性，就要处处用锁，甚至是用全局锁，Hashtable就是全局锁，但是这样的效率会很低。
而ConcurrentHashMap 为了提升效率，一致性自然会变弱。

4.6 HashMap 是 TreeMap 如何选用？

在需要大量插入、删除和查找元素这种操作的，选择HashMap，因为HashMap 底层使用数据+链表+红黑树实现，对于插入、删除、查找的性能都不错，但是HashMap的结果是没有排序的。

在需要对集合排序的时候，选择 TreeMap ，TreeMap 基于红黑树实现，TreeMap 的映射根据键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

5. Set

5.1 HashSet 和 HashMap 的区别？

HashMap是实现了Map接口，存储的是键值对；HashSet 是实现了Set接口，只存储对象。
HashMap 使用键来计算哈希值；HashSet 是使用成员对象来计算哈希值；
HashMap 比 HashSet 快。
HashSet 的底层其实是基于 HashMap 实现的，大部分方法都是直接调用 HashMap中的方法。
看下源码：
HashSet是基于HashMap实现的：

HashSet大部分方法是直接调用HashMap中的方法：

HashSet的少数方法是自己实现的：

6. 迭代器（Iterator ）

6.1 什么是迭代器（Iterator ）？

首先要知道：迭代器是一种模式，它可以使得对于序列类型的数据结构的遍历行为与被遍历的对象分离，也就是可以使我们无需关心该序列的底层结构是什么样子的。只要拿到这个对象,使用迭代器就可以遍历这个对象的内部。

Java 为我们提供了一个迭代器的接口就是 Iterator 。

next()：返回序列中的下一个元素。
hasNext()：检查序列中是否还有元素。
使用remove()：将迭代器新返回的元素删除。

Java 采用了迭代器来为各种容器提供了公共的操作接口。这样使得对容器的遍历操作与其具体的底层实现相隔离，达到解耦的效果。

6.2 Iterator 和foreach 遍历集合的区别？

Iterator 和 foreach 都可以遍历集合；
foreach 不可以在遍历的过程中删除元素，不然会出现 并发修改异常（ConcurrentModificationException） （基于快速失败机制，等下会说）；
使用 Iterator 遍历集合时，可以删除集合中的元素：

7. 什么是快速失败（fast-fail）机制？

快速失败是Java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast。

例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候，线程2 修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就可能会抛出 ConcurrentModificationException异常，从而产生fast-fail快速失败。

而迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedModCount值，是的话就返回遍历；否则抛出异常，终止遍历。

可以看下ArrayList中的源码：