集合概述
说说Java集合
Java 集合， 也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。
- Set代表无序的，元素不可重复的集合；
- List代表有序的，元素可以重复的集合；
- Queue代表先进先出（FIFO）的队列；
- Map代表具有映射关系的集合。使用键值对（key-value）存储
这些接口拥有众多的实现类，其中最常用的实现类有HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap等。
集合框架底层数据结构
List
ArrayList：Object[]数组Vector：Object[]数组LinkedList：双向链表
Set
HashSet(无序，唯一): 基于HashMap实现LinkedHashSet:LinkedHashSet是HashSet的子类，内部是通过LinkedHashMap来实现的。TreeSet(有序，唯一): 红黑树
Queue
PriorityQueue:Object[]数组来实现二叉堆ArrayQueue:Object[]数组 + 双指针
Map
HashMap：JDK1.8 之前HashMap由数组+链表组成。JDK1.8 后由数组+链表+红黑树组成LinkedHashMap：LinkedHashMap继承自HashMap，在上面HashMap结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。Hashtable：数组+链表组成的TreeMap：红黑树
集合相比数组的优势有哪些
Java 集合提供了更灵活、更有效的方法来存储多个数据对象。
各种集合类和接口可以存储不同类型和数量的对象，同时还具有多样化的操作方式。
Java 集合大小可变、支持泛型、具有内建算法等。
List
ArrayList 和 Array（数组）的区别是什么
ArrayList 内部基于动态数组实现，比 Array（静态数组） 使用起来更加灵活：
- 扩容：
ArrayList会根据实际存储的元素动态地扩容或缩容，而Array被创建之后就不能改变它的长度了。 - 泛型支持：
ArrayList允许你使用泛型来确保类型安全，Array则不可以。 - 存储内容：
ArrayList中只能存储对象。对于基本类型数据，需要使用其对应的包装类。Array可以直接存储基本类型数据，也可以存储对象。 - 方法：
ArrayList支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如add()、remove()等。Array只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。
ArrayList 可以添加 null 值吗
ArrayList 中可以存储任何类型的对象，包括 null 值。
不建议向ArrayList 中添加 null 值， null 值无意义，会让代码难以维护(空指针异常)。
ArrayList 插入和删除元素的时间复杂度
对于插入：
- 头部插入：由于需要将所有元素都依次向后移动一个位置，时间复杂度是 O(n)。
- 尾部插入：容量未达到极限时，往列表末尾插入元素的时间复杂度是 O(1)
- 指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。需要移动平均 n/2 个元素，因此时间复杂度为 O(n)。
对于删除同理：
- 头部删除：O(n)。
- 尾部删除：O(1)。
- 指定位置删除： O(n)。
LinkedList 插入和删除元素的时间复杂度
- 头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
- 尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
- 指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。
ArrayList 实现 RandomAccess 接口有何作用？为何 LinkedList 却没实现这个接口？
RandomAccess 接口只是一个标志接口，只要 List 集合实现这个接口，就能支持快速随机访问。（通过下标快速访问元素）
LinkedList 底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现 RandomAccess 接口。
另外：
实现 RandomAccess 接口的 List 集合采用一般的 for 循环遍历，而未实现这接口则采用迭代器，即 ArrayList 一般采用 for 循环遍历，而 LinkedList 一般采用迭代器遍历；
ArrayList 与 LinkedList 区别是什么
- 是否保证线程安全：
ArrayList和LinkedList都是不同步的，也就是不保证线程安全； - 底层数据结构：
ArrayList底层使用的是Object数组；LinkedList底层使用的是 双向链表 数据结构 - 插入和删除是否受元素位置的影响：
ArrayList采用数组存储，插入和删除元素的时间复杂度受元素位置的影响。LinkedList采用链表存储，在头尾插入或者删除元素不受元素位置的影响，在指定位置i插入和删除元素的时间复杂度为 O(n)
- 是否支持快速随机访问：
LinkedList不支持高效的随机元素访问，而ArrayList支持。 - 内存空间占用：
ArrayList在列表的结尾会预留一定的容量空间，而 LinkedList 的的每一个元素都需要消耗比 ArrayList 更多的空间。
说说ArrayList 的扩容机制
- 初始容量：ArrayList在创建时会分配一个初始容量，默认为10。可以通过构造函数或
ensureCapacity()方法设置初始容量。（初始其实是空数组，当添加第一个元素的时候数组容量才变成10） - 扩容策略：当向ArrayList中添加元素时，如果当前元素数量已达到容量上限，就会触发扩容操作。
- 增量扩容：默认情况下，ArrayList的扩容增量是当前容量的50%。扩容操作会将元素数据从旧数组复制到一个新的、更大容量的数组中。
- 使用System.arraycopy()方法：ArrayList使用
System.arraycopy()方法来实现数组的复制。这个方法效率较高，能够快速地将旧数组中的元素复制到新数组中。
说说CopyOnWriteArrayList的原理
CopyOnWriteArrayList是Java并发包里提供的并发类，是一个线程安全且读操作无锁的ArrayList。
在写操作时会复制一份新的List，在新的List上完成写操作，然后再将原引用指向新的List。
在上锁执行写操作的过程中，如果有需要读操作，会作用在原容器上，因此上锁的写操作不会影响到并发访问的读操作。
- 优点：读操作性能很高，因为无需任何同步措施，比较适用于读多写少的并发场景。
- 缺点：内存占用问题，可能会引起频繁GC。无法保证实时性，读到的可能是老数据
ArrayList和Vector的区别是什么
-
ArrayList是List的主要实现类，底层使用Object[]存储，线程不安全 ； -
Vector是List的古老实现类，底层使用Object[]存储，对读写操作上锁，线程安全。
Set
比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同
同：
Set接口的实现类- 能保证元素唯一
- 不是线程安全的
不同：
底层数据结构不同
HashSet的底层数据结构是哈希表（基于HashMap实现）。LinkedHashSet的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
应用场景不同。
HashSet用于不需要保证元素插入和取出顺序的场景LinkedHashSet用于保证元素的插入和取出顺序满足 FIFO 的场景TreeSet用于支持对元素自定义排序规则的场景。
随机性、无序性和不可重复性是什么
- 随机性：存储的数据按照数组索引的顺序添加
- 无序性：存储的数据根据数据的哈希值决定的
- 不可重复性：添加的元素按照
equals()判断时 ，返回 false，元素值不重复
Comparable 和 Comparator 的区别是什么
Comparable 接口和 Comparator 接口都是 Java 中用于排序的接口
Comparable接口实际上是出自java.lang包 它有一个compareTo(Object obj)方法用来排序Comparator接口实际上是出自java.util包它有一个compare(Object obj1, Object obj2)方法用来排序
需要对一个集合使用自定义排序时，就要重写compareTo()方法或compare()方法
Queue
Queue 与 Deque 的区别是什么
Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。
Deque 是双端队列，在队列的两端均可以插入或删除元素。
ArrayDeque 与 LinkedList 的区别是什么
ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能
- 数据结构：
ArrayDeque是基于可变长的数组和双指针来实现，而LinkedList则通过链表来实现。 - 对NULL的支持：
ArrayDeque不支持存储NULL数据，但LinkedList支持。 - 性能：
LinkedList每次插入数据时均需要申请新的堆空间，ArrayDeque性能更好 - 功能：ArrayDeque` 也可以用于实现栈。
说一说 PriorityQueue
PriorityQueue与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。
PriorityQueue利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据PriorityQueue通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。PriorityQueue是非线程安全的，不支持存储NULL。PriorityQueue默认是小顶堆，但可以接收一个Comparator作为构造参数，从而来自定义元素优先级的先后。
什么是 BlockingQueue
BlockingQueue阻塞队列 是一个接口，继承自 Queue。
当队列没有元素时一直阻塞，直到有元素；
当队列已满，一直等到队列可以放入新元素时再放入。
BlockingQueue 常用于生产者-消费者模型中，生产者线程会向队列中添加数据，而消费者线程会从队列中取出数据进行处理。
BlockingQueue 的实现类有哪些？
ArrayBlockingQueue：使用数组实现的有界阻塞队列。在创建时需要指定容量大小LinkedBlockingQueue：使用单向链表实现的可选有界阻塞队列。在创建时可以指定容量大小，如果不指定则默认为Integer.MAX_VALUE。PriorityBlockingQueue：支持优先级排序的无界阻塞队列。元素必须实现Comparable接口或者在构造函数中传入Comparator对象，并且不能插入 null 元素。SynchronousQueue：同步队列，是一种不存储元素的阻塞队列。常用于线程之间的直接传递数据。DelayQueue：延迟队列，其中的元素只有到了其指定的延迟时间，才能够从队列中出队。
ArrayBlockingQueue 和 LinkedBlockingQueue 有什么区别
ArrayBlockingQueue 和 LinkedBlockingQueue 是 Java 并发包中常用的两种阻塞队列实现，它们都是线程安全的。
- 底层实现：
ArrayBlockingQueue基于数组实现，而LinkedBlockingQueue基于链表实现。 - 是否有界：
ArrayBlockingQueue是有界队列，必须在创建时指定容量大小。LinkedBlockingQueue创建时可以不指定容量大小，默认是Integer.MAX_VALUE，也就是无界的。但也可以指定队列大小，从而成为有界的。 - 锁是否分离：
ArrayBlockingQueue中的锁是没有分离的，即生产和消费用的是同一个锁；LinkedBlockingQueue中的锁是分离的，可以防止生产者和消费者线程之间的锁争夺。 - 内存占用：
ArrayBlockingQueue需要提前分配数组内存，而LinkedBlockingQueue则是动态分配链表节点内存。
