集合面试题

1.List、Set、Queue和Map的区别

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

comparable 和 Comparator 的区别

comparable接口实际上是出自java.lang包中的一个CompareTo（Object obj）方法用来排序；
comparator实际上是出自java.util包中有一个compare（Object obj1,Object obj2）方法来排序。
当我们需要对一个集合进行自定义排序后，我们就要重写CompareTo或者是compare方法

List

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

1.ArrayList与Vector的区别

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

2.ArrayList与LinkedList的区别

ArrayList和LinkedList都是线程不同步的、线程不安全的。
ArrayList底层使用Object[]数组实现，LinkedList底层使用双向链表实现。
ArrayList底层使用数组实现，支持快速访问。而LinkedList底层是链表实现，不支持快速访问。
ArrayList的空间浪费主要体现在list列表结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素存储都需要比ArrayList消耗更多的空间（因为节点要放置前驱和后继）。

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

Arrays.copyOf()方法内部调用了System.arraycopy()方法。
arraycopy()方法需要目标数组，将原数组拷贝到自定义的数组中或者是原数组，并且可以选择拷贝的起点以及放入新的数组中的位置。
copyOf()时系统自动在内部新建一个数组，并返回该数组。

4.ArrayList扩容

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

Set

HashSet 无序、唯一，底层采用HashMap来保存元素。
TreeSet 有序、唯一，底层采用红黑树实现。

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

无序不等于随机，无序是指存储数据在底层数组中并非按照数组索引的顺序添加，而是通过数据的哈希值决定。
不可重复性是指添加的元素按照equals判断时，返回false，需要同时重写equals方法和hashCode方法。

2.HashSet、LinkedListHashSet、TreeSet的异同

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

Queue

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

1.Queue与Deque的区别

Queue是单端队列，只能从一端插入元素，另一端删除元素，遵循FIFO的规则。
Queue根据容量问题而导致操作失败后的处理方式不同。一种抛出异常，一种返回null。
Deque是双端队列，在队列的两端均可以插入或者删除元素，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

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

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没有这样的机制。
HashSet底层就是基于HashMap实现的。