原文链接：https://javaguide.cn

Java集合框架继承图

综合面试题

1.说说List、Set、Queue和Map四者的区别、

• List 存储的元素是有序的、可重复的
• Set 存储的元素是无序的、不可重复的
• Queue 按照特定的排队规则来排序，存储的元素是有序的、可重复的
• Map 使用key-value来进行存储数据，key是无序的、不可重复的，value是无序的、可重复的

2.集合的底层数据结构

List

• ArrayList Object[]数组
• Vector Object[]数组
• LinkedList 双向链表（jdk1.6之前是循环链表，1.7取消了循环）

Set

• HashSet（无序、唯一） 底层采用HashMap来保存元素
• TreeSet（有序、唯一） 底层采用红黑树（自平衡的二叉排序树）实现

Queue

• ArrayQueue Object[]数组 + 双指针
• PriorityQueue Object[]数组来实现二叉堆

Map

• HashMap jdk1.8之前由数组+链表组成，数组是HashMap的主体，而链表主要是为了解决哈希冲突。jdk1.8之后引入了红黑树。当链表长度大于等于8且数组长度大于等于64，链表就会转化为红黑树。如果只满足一个条件，那么会优先选择数组扩容。
• TreeMap 红黑树（自平衡的二叉排序树），底层是基于TreeSet实现的。
• HashTable 数组+链表组成，数组是HashTable的主题，链表则是主要是为了解决哈希冲突而存在的。

3.如何选取集合结构?

• 如果我们需要根据键值来获取元素值，就可以选用Map接口下的集合。需要排序就选用TreeMap，不需要排序就选用HashMap，需要保证线程安全就选用ConcurrentHashMap;
• 如果我们只需要存放元素值，就选择实现Collection接口的集合。需要保证元素唯一时选择Set接口下的集合，比如TreeSet或者是HashSet，不需要就选用List接口下的集合，比如ArrayList或者LinkedList。

4.我们为什么要使用集合？

当我们需要保存一组类型相同的数据的时候，由于数据的类型是多种多样的，所以我们使用了集合。集合提高了数据存储的灵活性，还可以保存具有映射关系的数据。

List

1.ArrayList和Vector的区别？

• ArrayList是List的主要实现类，底层使用Object[]数组存储，线程不安全；
• Vector是List的古老实现类，底层使用Object[]存储，线程安全。

2.ArrayList与LinkedList的区别？

​ （1）是否保证线程安全： ArrayList和LinkedList都是不同步的、线程不安全的。

​ （2）底层实现： ArrayList底层使用Object[]数组实现，LinkedList底层使用双向链表实现。（jdk1.6之前是双向循环链表，1.6之后取消了循环）。

​ （3）是否支持快速随机访问： ArrayList底层使用数组实现，支持快速访问。而LinkedList底层是链表实现，不支持快速访问。

​ （4）空间内存占用：ArrayList的空间浪费主要体现在list列表结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素存储都需要比ArrayList消耗更多的空间（因为节点要放置前驱和后继）。

3.System.arraycopy()方法和Arrays.copyOf()方法的区别

通过查看源码我们可以知道，Arrays.copyOf()方法内部调用了System.arraycopy()方法。

arraycopy()方法需要目标数组，将原数组拷贝到自定义的数组中或者是原数组，并且可以选择拷贝的起点以及放入新的数组中的位置。

copyOf()时系统自动在内部新建一个数组，并返回该数组。

拓展：

​ ArrayList实现了RandomAccess接口，只是作为一个标识，说明ArrayList支持快速随机访问功能。

4.ensureCapacity()方法的作用

ensureCapacity()方法并不是在ArrayList内部调用的，而是提供给用户来使用的，在向ArrayList里面添加大量元素之前最好先使用ensureCapacity方法，以减少增量重新分配的次数，提高效率。

ArrayList扩容

当使用无参构造方法直接创建ArrayList集合时，初始化的数组是一个空的数组，只有在add第一个元素时，数组的大小才会初始化为10，直到添加第11个元素时，ArrayList才会进行扩容操作。

Set

1.comparable 和 Comparator 的区别

• comparable接口实际上是出自java.lang包中的一个CompareTo（Object obj）方法用来排序；
• comparator实际上是出自java.util包中有一个compare（Object obj1,Object obj2）方法来排序。

当我们需要对一个集合进行自定义排序后，我们就要重写CompareTo或者是compare方法。

2.无序性和不可重复性的含义

（1）无序性？无序性不等于随机性，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。

（2）不可重复性？不可重复性是指添加的元素按照equals判断时，返回false，需要同时重写equals方法和hashCode方法。

3.比较HashSet、LinkedListHashSet、TreeSet的异同

• HashSet、LinkedListHashSet、TreeSet三者都是Set集合的实现类，都能保证元素唯一，并且都不是线程安全的。
• HashSet、LinkedListHashSet、TreeSet的主要区别在于底层数据结构不同。HashSet底层数据结构式HashMap（哈希表）；LinkedListHashSet的底层数据结构是链表和哈希表。TreeSet的底层数据结构是红黑树，元素是有序的。
• HashSet用于不需要保证元素插入和去除顺序的场景；LinkedListHashSet用于保证元素的插入和取出满足FIFO的场景；TreeSet用于支持元素自定义排序规则的场景。

Queue

1.Queue与Deque的区别

Queue是单端队列，只能从一端插入元素，另一端删除元素，遵循FIFO的规则。

Queue根据容量问题而导致操作失败后的处理方式不同。一种抛出异常，一种返回null。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Zzn588QN-1642240006941)(F:\笔记\深入java基础\面试题截图\Queue接口.png)]

Deque是双端队列，在队列的两端均可以插入或者删除元素。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RQh5h1Ya-1642240006942)(F:\笔记\深入java基础\面试题截图\Deque方法.png)]

实际上，Deque还提供了其他的方法，可以当作栈来使用。

2.ArrayDeque和LinkedList的区别

ArrayDeque和LinkedList都实现了Deque接口，两者都可以当作队列来使用。

• ArrayDeque是基于可变容量的数组和双指针来实现的，而LinkedList是通过链表来实现的
• ArrayDeque不支持Null数据，而LinkedLisr可以使用Null数据
• ArrayDeque是在jdk1.6引入的，而LinkedList早在jdk1.2都已存在
• ArrayDeque插入时可能存在扩容过程，不过插入的操作时间复杂度仍为O(1)，虽然LinkedList不需要扩容，但是每次插入数据时都需要重新申请空间，性能相比更差一点

从性能上来说，ArrayDeque来实现队列要比LinkedList要好一点，另外，ArrayDeque也可以直接用作栈。

3.简单说一下PriorityQueue

PriorityQueue是在jdk1.5被引入的，与Queue得区别在于元素出队顺序是与优先级相关得，即总是优先级高的元素出队列。

• PriorityQueue利用了二叉堆的数据结构来实现，底层使用可变长的数组来存储数剧
• PriorityQueue通过堆元素的上浮和下沉，实现了在（logn）的时间复杂度内插入元素和删除堆顶元素
• PriorityQueue是非线程安全的，而且不支持存储NULL对象
• PriorityQueue默认是小顶堆，但是可以接收一个comparator作为构造参数，可以自定义元素优先级的先后

Map

1.HashMap和Hashtable的区别

• 线程是否安全：HashMap是非线程安全的，而Hashtable是线程安全的。Hashtable内部的方法基本都经过synchronized修饰。
• 效率：因为线程安全的问题，HashMap要比Hashtable效率高，而且Hashtable已经快要淘汰了。
• 初始容量和每次扩充容量的大小：①创建时如果不指定初始容量，Hashtable默认初始容量为11，每次扩充之后，边缘原来的 2n+1 ；而HashMap默认初始化大小为16，每次扩容会变为原来的2倍。②如果给定容量大小，Hashtable就会使用给定容量大小，而HashMap就会将其扩充为大于原来数值的最小的2的n次幂的大小。
• 底层数据结构：JDK1.8之后HashMap在解决哈希冲突时，当链表长度大于8且数组长度大于64，链表就会转化为红黑树，若有一个条件不满足，那么会优先选择数组扩容。而Hashtable没有这样的机制。

2.HashMap和HashSet的区别

HashSet底层就是基于HashMap实现的。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C4FWRos7-1642240006943)(F:\笔记\深入java基础\面试题截图\HashMap和HashSet的区别.png)]

3.HashMap和TreeMap的区别

HashMap和TreeMap都继承于AbstractMap，但是TreeMap还实现了NavigableMap接口和SortedMap接口。

• 实现Navigable接口让TreeMap对集合内元素有了搜索的功能；
• 实现SortedMap接口让TreeMap有了对集合中的元素根据键排序的能力。

相比来说，TreeMap多了对集合中元素根据键排序的功能和对集合元素进行搜索的能力。

4.HashSet如何检查重复？

当把对象加入到HashSet中时，HashSet会先计算对象的hashCode值来判断对象加入的下标位置，同时也会与其他的对象的hashCode进行比较，如果没有相同的，就直接插入数据；如果有相同的，就进一步使用equals来进行比较对象是否相同，如果相同，就不会加入成功。

5.HashCode与equals的相关规定

（1）如果两个对象相等，则hashCode也一定是相等的

（2）两个对象相等，对两个进行equals也会返回true

（3）两个对象有相同的hashCode，他们也不一定是相等的

（4）hashCode和equals方法都必须被同时覆盖

6.==和equals的区别

对于基本类型来说，==比较的是值是否相等；

对于引用类型来说，equals比较的是两个引用是否指向同一个对象地址

对于引用类型（包括包装类型）来说，如果equals没有被重写，对比他们的地址是否相同，如果被重写，则比较的是地址里的内容是否相同。

7.HashMap的长度为什么是2的n次方？

为了能让HashMap存取高效，尽量减少哈希碰撞，尽量把数据均匀分配。

8.HashMap多线程下操作导致死循环问题

主要原因是并发下的Rehash会造成元素之间形成一个循环链表。多线程下HashMap会存在数据丢失的问题，并发环境下推荐使用Concurrent Hash Map、

9.ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashmap和Hashtable的区别主要体现在实现线程安全的方式上不同

• 底层数据结构： jdk1.7的ConcurrentHashMap底层采用分段的数组+链表实现，jdk1.8采用的数据结构跟HashMap1.8的结构是一样的，数组+链表/红黑树。Hashtable和jdk1.8之前的HashMap的底层数据结构类似，都是采用数组+链表的形式， 数组是hashMap的主体，链表则是为了解决哈希冲突。
• 实现线程安全的方法：①在1.7的时候，ConcurrentHashMap（分段锁）对整个桶数组进行了分割分段（Segment），到1.8直接使用数组+链表+红黑树的实现。

HashMap

1.put数据时key与已有数据的HashCode相等时会怎么样？

会产生哈希碰撞。

如果Hash码相同，则会通过equals方法进行比较key是否相同：

​ 如果key值相同，则使用新的value代替旧的value；

​ 如果key值不相同，则会在该节点的链表结构上新增一个节点（如果链表长度>=8并且数组节点数>=64 ，链表结构就会转化成红黑树）。

2.什么时候会产生hash碰撞？如何解决哈希碰撞？

只要通过hash函数计算所得到的两个元素的hash值相同就会产生hash碰撞。

HashMap在jdk8之前采用链表解决哈希碰撞，jdk8之后采用链表+红黑树解决哈希碰撞。

3.如果hashCode相同，那么如何存储key-value对？

当hashCode值相同时，就会进一步使用equals方法进行比较key是否相同。

如果key相同，那么新值覆盖旧值；

如果key不相同，则将新的key-value添加到HashMap中。

4.HashMap如何进行扩容？

当通过put方法不断进行数据添加时，如果元素个数超过了当前阈值就会进行扩容，默认扩容大小是原来的2倍，扩容之后会将原来的数据复制到新的数组中。

5.如果确定了要存储的元素个数n，设置多少的初始容量可以减少扩容导致的性能损失？

应该设置初始容量为 n/0.75 + 1 取整即可减少resize导致的性能损失。

Collections工具类

常用方法：

• 排序
• 查找，替换
• 同步控制（不推荐）

排序操作

void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面

查找,替换

int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素

集合注意事项

集合判空

集合判断是否为空，使用isEmpty()的方法，而不是size==0的方式

因为isEmpty()方法的可读性好，而且时间复杂度为O(1)

集合转化Map

使用Java.util.stream.Collectors类的toMap()方法转化为map集合时，要注释当value为null时会抛出NPE异常。

集合遍历

不要在foreach里面进行元素的remove/add操作，remove请使用Iterator方式，如果并发操作，需要对Iterator对象加锁。

fail-fast 机制 ：多个线程对 fail-fast 集合进行修改的时候，可能会抛出ConcurrentModificationException。

集合去重

可以利用Set元素唯一的特性，进行集合去重，避免使用List的contains进行遍历去重或者判断包含操作

集合转数组

使用集合转数组的方法，必须使用集合的toArray（T[] array）,传入的类型完全一致，长度为0的空数组。

toArray(T[] array) 方法的参数是一个泛型数组，如果 toArray 方法中没有传递任何参数的话返回的是 Object类 型数组。

数组转集合

使用工具类Arrays.asList()把数组转化成集合时，不能使用其修改集合相关的方法，它的add/remove/clear方法会抛出UnsupportedOperationException异常。