1.Java集合（List、Set、Queue）

1.集合概述

　　Java集合也被称为容器。主要由两个接口组成，一个是Collection接口，主要存放单一元素；一个是Map接口，主要存放键值对。Collection下面还有三个子接口，分别是List、Set、Queue。

Java框架如下图所示：

1.1 List、Set、Queue、Map简介

• List(对付顺序的好帮手): 存储的元素有序、可重复。
• Set(注重独一无二的性质): 存储的元素不可重复。
• Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素有序、可重复。
• Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，"x" 代表 key，"y" 代表 value，key 是无序、不可重复，value 是无序、可重复，每个键最多映射到一个值。key和value允许为null。

1.2 集合框架底层数据结构总结

List

• ArrayList：Object[] 数组；
• Vector：Object[] 数组；
• LinkedList：双向链表（JDK1.6之前为循环链表，JDK1.6之后取消了）；

Set

• HashSet（无序，唯一）：基于HashMap实现，底层采用HashMap保存元素；
• LinkedHashSet：LinkedHashSet是HashSet的子类，内部通过LinkedHashSet实现；
• TreeSet（有序，唯一）：红黑树（自平衡的二叉树）；

Queue

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

Map

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

1.3 如何选用集合?

我们要根据集合的特点来选择合适的集合。比如：

• 我们需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。
• 我们只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要保证元素唯一就选择实现 List 接口的集合比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。

1.4 为什么要使用集合？

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

2. List

2.1 ArrayList和Array的区别

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

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

2.2 ArrayList 可以添加 null 值吗？

　　ArrayList 中可以存储任何类型的对象，包括 null 值。但不建议向ArrayList 中添加 null 值， null 值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。

2.3 ArrayList 插入和删除元素的时间复杂度？

对于插入：

• 头部插入：需要将所有元素都依次向后移动一个位置，因此时间复杂度是 O(n)。
• 尾部插入：当 ArrayList 的容量未达到极限时，往列表末尾插入元素的时间复杂度是 O(1)，因为它只需要在数组末尾添加一个元素即可；当容量已达到极限并且需要扩容时，则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中，然后再执行 O(1) 的操作添加元素。
• 指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素，因此时间复杂度为 O(n)。

对于删除：

• 头部删除：需要将所有元素依次向前移动一个位置，因此时间复杂度是 O(n)。
• 尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O(1)。
• 指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

 2.4 LinkedList 插入和删除元素的时间复杂度？

• 头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
• 尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
• 指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

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

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

2.6 ArrayList和LinkedList接口的区别？

• 保证线程安全：ArrayList和LinkedList都是不同步的，无法保证线程安全；
• 底层数据结构：ArrayList底层结构是Object[] 数组，LinkedList底层结构是双向链表（JDK1.6之前是循环链表，JDK1.6之后取消）；
• 插入和删除是否受元素影响：ArrayList底层数据结构是Object[] 数组，对于头部插入/删除，需要移动元素，因此时间复杂度为O(n)。对于尾部插入，如果数组未达到容量极限，时间复杂度为O(1)；如果达到数组容量极限，则需要将当前数组复制到当前数组1.5大的新数组中，再执行插入操作，时间复杂度为O(n)；尾部删除，时间复杂度为O(1)。指定位置插入/删除需要移动n/2的元素，时间复杂度为O(n)。LinkedList底层数据结构为链表，对于头部和尾部的插入/删除，时间复杂度为O(1)。对于指定位置的插入/删除，需要先移动到指定位置，时间复杂度为O(n)，然后再执行插入/删除操作，时间复杂度为O(n)。
• 是否支持快速访问：ArrayList底层数据结构是Object[] 数组，其内存连续，可实现RandomAccess接口，可根据索引访问元素，因此支持快速访问。LinkedList底层结构是链表，内存不连续，无法实现实现RandomAccess接口，只能通过指针定位元素，因此无法实现快速访问。
• 内存空间占用：ArrayList空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间。LinkedList 空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

　　在我们的项目中，一般都是使用ArrayList存储单一元素，LiinkedLisy几乎所有的使用场景可通过ArrayList代替，且ArrayList性能更好。

 2.7 ArrayList的扩容机制

1. 初始大小：初始化时，ArrayList会创建一个默认大小的底层数组（一般为10）来存储元素。
2. 自动扩容：当往ArrayList中添加元素时，如果当前数组已满，ArrayList会按照一定的规则进行自动扩容。它会创建一个新的更大容量的数组，并将原数组中的元素复制到新数组中。
3. 扩容策略：一般情况下，ArrayList的扩容策略是将当前数组的容量（记为oldCapacity）扩大为原来的1.5倍，即新容量为oldCapacity + (oldCapacity >> 1)。这种策略在大多数场景下能够保持较好的性能。
4. 复制元素：在进行扩容时，ArrayList使用System.arraycopy()方法将原数组中的元素复制到新数组中，以保持元素的顺序不变。
5. 更新引用：扩容完成后，ArrayList会更新内部的引用指向新的数组，并释放旧数组的内存空间，从而完成扩容操作。

3.Set

3.1 Comparable和Comparator的区别

Comparable 接口和 Comparator 接口都是 Java 中用于排序的接口，它们在实现类对象之间比较大小、排序等方面发挥了重要作用：

• Comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序；
• Comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序；

　　当我们需要对一个集合使用自定义排序时，就重写compareTo()方法或compare()方法，当我们需要对某一个集合实现两种排序方式，比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo()方法和使用自定义的Comparator方法或者以两个 Comparator 来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的 Collections.sort().

3.1.1 Comparator自定义排序

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        Collections.addAll(list, -3, -5, -1, 5, 3, 1);
        System.out.println(list);
        System.out.println("---------------------");
        Collections.reverse(list);
        System.out.println(list);
        System.out.println("---------------------");
        Collections.sort(list);
        System.out.println(list);
        System.out.println("---------------------1");


        //自定义排序
        //Comparator函数式接口
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);//o2和o1可以直接调用compareTo方法是因为实现了Comparable接口
            }
        });
        System.out.println(list);
        System.out.println("---------------------2");
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);//o2和o1可以直接调用compareTo方法是因为实现了Comparable接口
            }
        });
        System.out.println(list);
        System.out.println("---------------------3");
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        System.out.println(list);
        System.out.println("---------------------4");
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        System.out.println(list);

    }

自定义Comparator排序列表

运行结果

[-3, -5, -1, 5, 3, 1]
---------------------
[1, 3, 5, -1, -5, -3]
---------------------
[-5, -3, -1, 1, 3, 5]
---------------------1
[5, 3, 1, -1, -3, -5]
---------------------2
[-5, -3, -1, 1, 3, 5]
---------------------3
[-5, -3, -1, 1, 3, 5]
---------------------4
[5, 3, 1, -1, -3, -5]

　　从运行结果可以发现，当我们使用Io1和o2进行比较的时候，如果o2.compareTo(o1)表示降序；o1.compareTo(o2)表示升序。同理，使用o2-o1降序，o1-o2升序。Comparator是一个函数式接口，而Integer类型的o1和o2之所以能直接调用compareTo()方法比较大小是因为Integer包装类实现了Comparator接口。

3.1.2 重写compareTo实现年龄排序

　　如果想调用Comparator接口的compareTo()方法来实现Person类中的年龄排序，那么必须使Person类实现Comparator接口。

//@Data
//@AllArgsConstructor
//可使用以上注解添加有参构造方法和get、set方法
public class Person implements Comparable<Person> {

    private String name;
    private Integer age;


    public Person(String name, Integer age) {
        super();
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    @Override
    public int compareTo(Person o) {
        if(this.age > o.getAge()){
            return 1;
        }
        if(this.age < o.getAge()){
            return -1;
        }
        return 0;
    }
}

compareTo升序

运行结果

李四-5
王五-10
张三-20

//@Data
//@AllArgsConstructor
//可使用以上注解添加有参构造方法和get、set方法
public class Person implements Comparable<Person> {

    private String name;
    private Integer age;


    public Person(String name, Integer age) {
        super();
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    @Override
    public int compareTo(Person o) {
        if(this.age > o.getAge()){
            return -1;
        }
        if(this.age < o.getAge()){
            return 1;
        }
        return 0;
    }
}

compareTo降序

运行结果

张三-20
王五-10
李四-5

　　从上述代码和运行结果，可以看出，当this.age>o.getAge返回1时类似于this.compareTo(o)，即当前对象与参数对象的年龄比较。this相当于o1，o相当于o2.反之则结果相反。

3.2 无序性和不可重复性

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

3.3 比较HashSet、LinkedHashSet、TreeSet的异同

• HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
• HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
• 底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景。上述重写compareTo()方法采用的就是TreeMap来自定义排序。

4.Queue

4.1 Queue与Deque的区别

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

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

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

4.2 ArrayDeque与LinkedList的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

• ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
• ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持存储NULL值。
• ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
• ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

4.3 PriorityQueue

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

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

PriorityQueue 在面试中可能更多的会出现在手撕算法的时候，典型例题包括堆排序、求第 K 大的数、带权图的遍历等。

4.4 BlockingQueue

　　BlockingQueue （阻塞队列）是一个接口，继承自 Queue。BlockingQueue阻塞的原因是其支持当队列没有元素时一直阻塞，直到有元素；还支持如果队列已满，一直等到队列可以放入新元素时再放入。

public interface<E> BlockingQueue extends Queue<E>{
}

　　BlockingQueue 常用于生产者-消费者模型中，生产者线程会向队列中添加数据，而消费者线程会从队列中取出数据进行处理。

 4.5 BlockingQueue的实现类

Java 中常用的阻塞队列实现类有以下几种（了解即可）：

1. ArrayBlockingQueue：使用数组实现的有界阻塞队列。在创建时需要指定容量大小，并支持公平和非公平两种方式的锁访问机制。
2. LinkedBlockingQueue：使用单向链表实现的可选有界阻塞队列。在创建时可以指定容量大小，如果不指定则默认为Integer.MAX_VALUE。和ArrayBlockingQueue类似， 它也支持公平和非公平的锁访问机制。
3. PriorityBlockingQueue：支持优先级排序的无界阻塞队列。元素必须实现Comparable接口或者在构造函数中传入Comparator对象，并且不能插入 null 元素。
4. SynchronousQueue：同步队列，是一种不存储元素的阻塞队列。每个插入操作都必须等待对应的删除操作，反之删除操作也必须等待插入操作。因此，SynchronousQueue通常用于线程之间的直接传递数据。
5. DelayQueue：延迟队列，其中的元素只有到了其指定的延迟时间，才能够从队列中出队。

4.6 ArrayListQueue和LinkedListQueue的区别

　　ArrayBlockingQueue 和 LinkedBlockingQueue 是 Java 并发包中常用的两种阻塞队列实现，它们都是线程安全的。不过，不过它们之间也存在下面这些区别：

• 底层实现：ArrayBlockingQueue 基于数组实现，而 LinkedBlockingQueue 基于链表实现。
• 是否有界：ArrayBlockingQueue 是有界队列，必须在创建时指定容量大小。LinkedBlockingQueue 创建时可以不指定容量大小，默认是Integer.MAX_VALUE，也就是无界的。但也可以指定队列大小，从而成为有界的。
• 锁是否分离： ArrayBlockingQueue中的锁是没有分离的，即生产和消费用的是同一个锁；LinkedBlockingQueue中的锁是分离的，即生产用的是putLock，消费是takeLock，可防止生产者和消费者线程之间的锁争夺。
• 内存占用：ArrayBlockingQueue 需要提前分配数组内存，而 LinkedBlockingQueue 则是动态分配链表节点内存。这意味着，ArrayBlockingQueue 在创建时就会占用一定的内存空间，且往往申请的内存比实际所用的内存更大，而LinkedBlockingQueue 则是根据元素的增加而逐渐占用内存空间。

参考链接

Java集合常见面试题总结(上) | JavaGuide(Java面试 + 学习指南)