Java 基础面试题——集合

刺骨的言语ヽ痛彻心扉 2023-10-07 23:50 104阅读 0赞

#### 目录 ####

*  1.概述
 *   *  1.1.Java 有哪些常用集合（容器）？
     *  1.2.分别简单介绍一下 Collection 接口和 Map 接口下的主要集合。
     *  1.3.Collection 和 Collections 有什么区别？
     *  1.4.List、Set、Queue、Map之间的区别是什么？
     *  1.5.Java 中为什么要使用集合？如何选用集合？
     *  1.6.有哪些集合是线程不安全的？如何解决？
     *  1.7.Iterable 与 Iterator 有什么区别？
     *  1.8.Comparable 和 Comparator 有什么区别？
     *  1.9.无序性和不可重复性的含义是什么？
 *  2.Collection
 *   *  2.1.✨ArrayList 和 LinkedList 有什么区别？
     *   *  2.1.1.区别
         *  2.1.2.扩展：RandomAccess 接口有什么作用？
     *  2.2.ArrayList 和 Vector 有什联系和区别？
     *  2.3.✨谈一谈 ArrayList 的扩容机制。
     *  2.4.Queue 和 Deque 有什么区别？
     *  2.5.ArrayDeque 和 LinkedList 有什么区别？
     *  2.6.比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同。
     *  2.7.谈一谈 PriorityQueue。
     *  2.8.数组与 List 相互转换的方法有哪些？
 *  3.Map
 *   *  3.1.HashMap 和 Hashtable 有什么区别？
     *  3.2.✨HashMap 和 HashSet 有什么联系与区别？
     *  3.3.✨HashMap 与 TreeMap 有什么区别？
     *  3.4.HashMap 有哪些遍历方式？
     *  3.5.✨HashMap 的底层数据结构是什么样的？对其源码了解多少？
     *  3.6.Hashmap 为什么是线程不安全的？线程不安全有哪些表现？
     *  3.7.HashTable 与 ConcurrentHashMap 有什么区别？
     *  3.8.HashSet 如何检查重复的元素？
     *  3.9.Java 中 LinkedHashMap 的底层实现原理是什么？
     *  3.10.TreeSet 有什么特点？
     *  3.11.Java 8 对链地址法做了什么优化？
     *  3.12.集合中的 poll() 和 remove() 有什么异同？

> 参考文章：  
> [Java集合常见面试题总结][Java]

## 1.概述 ##

### 1.1.Java 有哪些常用集合（容器）？ ###

![请添加图片描述][cb744ad88f534a83a8f3acbfb8dfec58.png]

从上图可以知道，Java 集合框架主要包括**两种类型的容器**：

*  `Collection`：用于存放单一元素；
 *  `Map`：用于存储键/值对映射。

> 注意：**上图中只列举了主要的继承派生关系，并没有列举完全**，如果想要深入了解，可以自行去查看源码。

### 1.2.分别简单介绍一下 Collection 接口和 Map 接口下的主要集合。 ###

（1）Collection 接口下面的集合：

*  **List**
    
     *  ArrayList：底层实现为 Object\[\] 数组；
     *  Vector：底层实现为 Object\[\] 数组；
     *  LinkedList：底层实现为双向链表（JDK1.6 之前为循环链表，JDK1.7 取消了循环）；
 *  **Queue**
    
     *  PriorityQueue: 元素出队顺序与**优先级**相关，即总是优先级最高的元素先出队，其底层是通过 Object\[\] 数组实现的**二叉堆**来完成的；
     *  ArrayQueue: 底层通过 Object\[\] 数组 + 双指针来实现；
 *  **Set**
    
     *  HashSet：基于 HashMap 实现的，底层采用 HashMap 来保存元素，**元素无序且唯一**；
     *  LinkedHashSet：**HashSet 的子类**，其内部是通过 LinkedHashMap 来实现的；
     *  TreeSet：**有序集合**，可以以任意顺序将元素插入到集合中。在对集合进行遍历时，每个值将自动地按照排序后的顺序呈现，其中排序是通过**红黑树**来完成的；

（2）Map 接口下面的集合：

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

### 1.3.Collection 和 Collections 有什么区别？ ###

（1）**Collection** 是 JDK 中集合层次结构中的最根本的**接口**，定义了集合类的基本方法。Collection 接口在 Java 类库中有很多具体的实现，其意义是为各种具体的集合提供了最大化的统一操作方式。

（2）**Collections 是一个包装类，是 Collection 集合框架的工具类**。它包含有各种有关集合操作的静态多态方法，常用的有：

*  `Collections.sort(List<T> list)`：对列表进行升序排序。
 *  `Collections.reverse(List<T> list)`：反转列表中的元素顺序。
 *  `Collections.shuffle(List<T> list)`：随机打乱列表中的元素顺序。
 *  `Collections.binarySearch(List<? extends Comparable<? super T>> list, T key)`：使用二分搜索算法查找指定元素在列表中的位置。
 *  `Collections.frequency(Collection<?> c, Object o)`：返回指定集合中指定元素的出现次数。
 *  `Collections.max(Collection<? extends T> coll)`：返回集合中的最大元素。
 *  `Collections.min(Collection<? extends T> coll)`：返回集合中的最小元素。
 *  `Collections.addAll(Collection<? super T> c, T... elements)`：将多个元素添加到集合中。
 *  `Collections.disjoint(Collection<?> c1, Collection<?> c2)`：检查两个集合是否没有任何相同的元素。
 *  `Collections.replaceAll(List<T> list, T oldVal, T newVal)`：将列表中所有的旧元素替换为新元素。

### 1.4.List、Set、Queue、Map之间的区别是什么？ ###

（1）List：存储的元素是**有序的、可重复的**。  
（2）Set：存储的元素是**无序的、不可重复的**，LinkedHashSet 按照插入排序，SortedSet 可排序，HashSet 无序。  
（3）Queue：按**特定的排队规则**来确定先后顺序，存储的元素是有序的、可重复的。  
（4）Map：**存储键值对 (key-value)**，其中要求 key 无序且唯一，而 value 则不要求有序，允许重复。

### 1.5.Java 中为什么要使用集合？如何选用集合？ ###

（1）当我们需要保存一组类型相同的数据时，可以选用数组，但是数组存在着一定的弊端，例如当数组声明后，其长度以及存储的数据类型也就固定了，并且存储的数据的特点单一。因此为了**提高数据存储的灵活性、数据特点的多样性**，Java 中使用了集合。

（2）在选用集合时，我们应主要根据**需求和集合特点**来选用：

*  当我们**只需要存储元素**时，就可以选择 Collection 接口下的集合，例如：
    
     *  如果需要保证**元素唯一**，可以选择 HashSet、TreeSet；
     *  如果需要保证**元素有序且唯一**，可以选择 TreeSet；
     *  不需要保证元素唯一，可以选择 ArrayList、LinkedList 等；
 *  当我们**需要根据键值获取元素值**时，就可以选择 Map 接口下的集合，例如：
    
     *  需要排序时选择 TreeMap，不需要排序时就选择 HashMap；
     *  需要保**证线程安全**，选择 ConcurrentHashMap；

### 1.6.有哪些集合是线程不安全的？如何解决？ ###

我们常⽤的 Arraylist , LinkedList , Hashmap , HashSet , TreeSet , TreeMap ， PriorityQueue 都不是线程安全的。解决办法很简单，可以使用线程安全的集合来代替。如果你要使用线程安全的集合的话， `java.util.concurrent` 包中提供了很多并发容器供我们使用：

*  `ConcurrentHashMap`：可以看作是线程安全的 HashMap；
 *  `CopyOnWriteArrayList`：可以看作是线程安全的 ArrayList ，在读多写少的场合性能非常好，远远好于 Vector；
 *  `ConcurrentLinkedQueue`：高效的并发队列，使用链表实现。可以看做⼀个线程安全的 LinkedList ，这是⼀个非阻塞队列。
 *  `BlockingQueue`：这是⼀个接口，JDK 内部通过链表、数组等方式实现了这个接口。表示阻塞队列，非常适合用于作为数据共享的通道。
 *  `ConcurrentSkipListMap`：跳表的实现，这是⼀个 Map ，使用跳表的数据结构进行快速查找。

### 1.7.Iterable 与 Iterator 有什么区别？ ###

（1）首先来看看 Iterator 与 Iterable 的英文含义：

*  Iterable：由英文的命名规则知道，后缀 able 的意思就是**可怎么样的**，因此 Iterable 就是**可迭代**的意思。
 *  Iterator：由英文的命名规则知道，后缀 or 或者 er 的都是**指代名词**，所以 Iterator 的意思是**迭代器**。

这两个概念之间有一个包含与被包含的关系，**如果一个对象是迭代器，那么这个对象肯定是可迭代的；但是反过来，如果一个对象是可迭代的，那么这个对象不一定是迭代器**。

（2）Iterable 是一个接口，它定义了返回一个 Iterator 的方法，使得实现了 Iterable 接口的类可以被 foreach 循环迭代，即提供一种简单的迭代方式。其源码如下所示：

package java.lang;
    
    import java.util.Iterator;
    import java.util.Objects;
    import java.util.Spliterator;
    import java.util.Spliterators;
    import java.util.function.Consumer;
    
    public interface Iterable<T> {
        
    
        Iterator<T> iterator();
    
        default void forEach(Consumer<? super T> action) {
        
            Objects.requireNonNull(action);
            for (T t : this) {
        
                action.accept(t);
            }
        }
    
        default Spliterator<T> spliterator() {
        
            return Spliterators.spliteratorUnknownSize(iterator(), 0);
        }
    }

（3）Iterator 也是一个接口，它定义了遍历集合元素的方法，并且更加灵活，它**允许在迭代过程中删除元素**。Iterator 接口的源码如下：

package java.util;
    
    import java.util.function.Consumer;
    
    public interface Iterator<E> {
        
        //判断集合中是否还有元素
        boolean hasNext();
    
        //获得集合中的下⼀个元素
        E next();
    
        //移除 iterator.next() 方法最后访问的元素
        default void remove() {
        
            throw new UnsupportedOperationException("remove");
        }
    
        //对集合中剩余的元素进行操作，直到元素完毕或者抛出异常
        default void forEachRemaining(Consumer<? super E> action) {
        
            Objects.requireNonNull(action);
            while (hasNext())
                action.accept(next());
        }
    }

（4）测试 Iterator 与 Iterable：

public class IterableVsIteratorExample {
        
        public static void main(String[] args) {
        
            List<String> list = new ArrayList<>();
            list.add("apple");
            list.add("banana");
            list.add("orange");
    
            //使用 Iterable 方式迭代
            for (String fruit : list) {
        
                System.out.println(fruit);
            }
    
            //使用 Iterator 方式迭代
            Iterator<String> iterator = list.iterator();
            while (iterator.hasNext()) {
        
                String fruit = iterator.next();
                System.out.println(fruit);
                iterator.remove(); 		//删除元素
            }
    
            System.out.println(list); 	//输出 []
        }
    }

在上面的例子中，我们首先使用了 Iterable 的方式迭代 List 中的元素，即使用 foreach 循环遍历。接下来，我们使用 Iterator 迭代器遍历 List 中的元素，并删除了每个元素。需要注意的是，**当我们在迭代过程中使用 Iterator 的 remove 方法删除元素时，List 中的元素也会被删除**。最后，我们输出 List 中的元素，发现它已经变成了空列表。

> 有关迭代器模式的具体知识可以参考 [Java 设计模式——迭代器模式][Java 1]这篇文章。

### 1.8.Comparable 和 Comparator 有什么区别？ ###

（1）在 Java 中，Comparable 接口和 Comparator 接口都用于**比较对象**。它们之间的主要区别是 Comparable 是在对象自身内部实现的比较方法，而 Comparator 则是在外部单独实现比较方法。

（2）**实现 Comparable 接口的类可以直接进行排序，而不需要使用其他的比较器**。这是因为 Comparable 接口定义了一个 compareTo 方法，该方法指定了如何比较两个对象。该方法的返回值为负数、零或正数，表示当前对象小于、等于或大于另一个对象。例如，以下是一个实现 Comparable 接口的 Student 类的例子：

package java.lang;
    
    import java.util.*;
    
    public interface Comparable<T> {
          
        public int compareTo(T o);
    }

public class Student implements Comparable<Student> {
        
        private String name;
        private int age;
        
        public Student(String name, int age) {
        
            this.name = name;
            this.age = age;
        }
        
        public String getName() {
        
            return name;
        }
        
        public int getAge() {
        
            return age;
        }
        
        @Override
        public int compareTo(Student o) {
        
            return this.age - o.age;
        }
        
        public static void main(String[] args) {
        
            Student stu1 = new Student("A", 20);
            Student stu2 = new Student("B", 18);
            System.out.println(stu1.compareTo(stu2) > 0);   // true
        }
    }

在上面的例子中，Student 类实现了 Comparable< Student > 接口，它的 compareTo 方法比较了两个 Student 对象的年龄，以此来决定它们之间的大小关系。

（3）与此相反，**Comparator 接口定义了一个 compare 方法，该方法指定了如何比较两个对象**。实现 Comparator 接口的类可以用于在不改变对象自身的情况下对对象进行排序。例如，以下是一个实现 Comparator 接口的 StudentAgeComparator 类的例子：

public class StudentAgeComparator implements Comparator<Student> {
        
        @Override
        public int compare(Student s1, Student s2) {
        
            return s1.getAge() - s2.getAge();
        }
    }

在上面的例子中，StudentAgeComparator 类实现了 Comparator 接口，它的 compare 方法比较了两个 Student 对象的年龄，以此来决定它们之间的大小关系。此外，Comparator 也可以用于对集合进行自定义排序，举例如下：

public static void main(String[] args) {
        
        List<Student> list = new ArrayList<>();
        list.add(new Student("A", 20));
        list.add(new Student("D", 24));
        list.add(new Student("B", 18));
        list.add(new Student("D", 19));
        list.sort(new Comparator<Student>() {
        
            @Override
            public int compare(Student stu1, Student stu2) {
        
                //先按照名字升序排序，再按照年龄降序排序
                if (stu1.getName().compareTo(stu2.getName()) != 0) {
        
                    return stu1.getName().compareTo(stu2.getName());
                } else {
        
                    return stu1.getAge() - stu2.getAge();
                }
            }
        });
        for (Student stu : list) {
        
            System.out.println(stu.getName() + " " + stu.getAge());
        }
    }

最终的输出结果如下：

A 20
    B 18
    D 19
    D 24

注：在 Java 8 中，上述代码的自定义排序部分可用 Lambda 表达式代替：

list.sort((stu1, stu2) -> {
        
        //先按照名字升序排序，再按照年龄降序排序
        if (stu1.getName().compareTo(stu2.getName()) != 0) {
        
            return stu1.getName().compareTo(stu2.getName());
        } else {
        
            return stu1.getAge() - stu2.getAge();
        }
    });

### 1.9.无序性和不可重复性的含义是什么？ ###

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

## 2.Collection ##

### 2.1.✨ArrayList 和 LinkedList 有什么区别？ ###

#### 2.1.1.区别 ####

（1）底层数据结构

*  ArrayList 底层使用的是**Object 数组**，在一片连续的内存空间中存储数据。
 *  LinkedList 底层使用的是**双向链表**（JDK1.6 之前为双向循环链表，JDK1.7 取消了循环），数据可以存储在分散的内存空间中。

（2）扩容

*  ArrayList 底层使用的是 Object 数组，在无参构造函数中**默认初始化长度为 10**，当需要扩容时会将原数组中的元素重新拷贝到**长度为原数组的 1.5 倍的新数组中**，扩容代价比较高；
 *  LinkedList 通过链表实现，新增元素根据要求插入到链表中即可。

> 有关 ArrayList 扩容的具体细节，可查看本节的 2.3。

（3）是否支持快速随机访问

*  ArrayList 实现了 `RandomAccess` 接口且底层是通过 Object 数组实现的，故**支持快速随机访问**。
 *  LinkedList 的底层是通过链表实现的，故**不支持快速随机访问**，查找某一元素的时间复杂度为 O(n)。

> 快速随机访问就是**通过元素的下标快速获取元素**，即对应于 ArrayList 中的 `get(int index)` 方法，其时间复杂度为 O(1)。

（4）插入和删除操作

*  ArrayList 底层采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响，同时可能需要进行**元素移动**甚至**扩容操作**。 比如：执行 `add(E e)` 方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话 (`add(int index, E element)`)时间复杂度就为 O(n - i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的 n - i 个元素都要执行向后位/向前移一位的操作。
 *  LinkedList 采用链表存储，所以如果是在头尾插入或者删除元素不受元素位置的影响 (`add(E e)`、`addFirst(E e)`、`addLast(E e)`、`removeFirst()`、`removeLast()`)，时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话 (`add(int index, E element)`，`remove(Object o)`)， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入。

（5）遍历操作  
ArrayList 和 LinkedList 常见的遍历方式有 3 种：for（结合 `get(int index)` 方法）、foreach、iterator。

*  在数据量比较小时，不同遍历方式的性能差别不大。
 *  但是在数据量比较大时：
    
     *  对于 ArrayList 来说，3 种遍历方式差距不是很大，其中 **for 循环的效率最高**，因为使用的是快速随机访问方式。
     *  对于 LinkedList 来说，**迭代器效率最高**，因为其相当于维护一个当前状态指针，遍历只需要扫描一遍双向链表即可，而 for 效率最低，因为需要扫描 n 遍链表。

> ① 在 List 遍历方式中，foreach 的底层就是由**迭代器**实现的，只不过为了方便书写，做了简单的封装。  
> ② 在遍历 LinkedList 时，尽量不要使用 `get(int index)` 方法，因为每次都要从链表头或者表尾去遍历，时间复杂度较高。

具体细节可参考[ ArrayList 和 LinkedList 的三种遍历方式][ArrayList _ LinkedList] 这篇文章。

（6）内存空间占用

*  ArrayList 除了存储数据所占用的内存空间外，**列表结尾往往会预留一定的容量空间**，这可能会造成一定的内存空间的浪费。
 *  LinkedList 的内存空间占用则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放**直接前驱**和**直接后继**以及数据）。

> 注意：在项目中一般不会使用 LinkedList，因为大部分需用到 LinkedList 的场景都可以使用 ArrayList 来代替，并且性能通常会更好！

#### 2.1.2.扩展：RandomAccess 接口有什么作用？ ####

（1）`RandomAccess` 接口是 Java 标准库中的一个接口，用于标识实现了随机访问能力的集合 (Collection) 类。**它本身不包含任何方法或常量，只是一个标记接口**。`RandomAccess` 接口的作用在于**提供了一种方式来表示集合是否支持快速随机访问元素的能力**。如果一个集合类实现了 `RandomAccess` 接口，那么可以认为该集合支持高效的随机访问，即可以通过索引快速访问集合中的元素。

package java.util;
    
    public interface RandomAccess {
        
    
    }

（2）在实际编程中，当我们需要对集合进行随机访问操作时，可以使用 `instanceof` 关键字来判断集合是否实现了 `RandomAccess` 接口，从而选择合适的访问方式。如果实现了 `RandomAccess` 接口，可以直接通过索引访问元素；如果没有实现 `RandomAccess` 接口，使用迭代器逐个遍历访问可能更高效。

public class Collections {
        
    	
    	//...
    
    	public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
        
            if (c==null)
                return binarySearch((List<? extends Comparable<? super T>>) list, key);
    
            if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
                return Collections.indexedBinarySearch(list, key, c);
            else
                return Collections.iteratorBinarySearch(list, key, c);
        }
    }

（3）需要注意的是，并不是所有的集合类都实现了 `RandomAccess` 接口。通常，数组和一些特定的集合类（如 `ArrayList`）实现了该接口，而链表类（如 `LinkedList`）则没有实现该接口。

（4）总的来说，`RandomAccess` 接口的作用是提供一种标记方式来表示集合是否支持高效的随机访问，以便我们在编程时可以根据需要选择合适的访问方式，提高程序的执行效率。

### 2.2.ArrayList 和 Vector 有什联系和区别？ ###

**（1）联系**

*  Vector 是早期 JDK 版本提供，ArrayList 是新版本中用来替代 Vector 的；
 *  底层都是通过数组实现的；
 *  功能相同，实现增删改查等操作的方法相似；

**（2）区别**

*  Vector 是**线程安全**的，而 ArrayList 是非线程安全的；
 *  Vector 类中的方法很多有 synchronized 进行修饰，以保证线程安全，这样就导致了 Vector 在效率上无法与 ArrayList 相比；
 *  默认初始化容量都是10，但扩容时 Vector 默认会翻倍，也可指定扩容的大小，而 ArrayList 的大小则是扩容为原来的 1.5 倍；

### 2.3.✨谈一谈 ArrayList 的扩容机制。 ###

参考 [Java 基础——ArrayList 的扩容机制][Java _ArrayList]这篇文章。

### 2.4.Queue 和 Deque 有什么区别？ ###

（1）Queue 是**单端队列**，只能从一端插入元素，另一端删除元素，实现上一般遵循先进先出 (FIFO) 规则。Queue 扩展了 Collection 的接口，根据**失败后处理方式的不同**可以分为以下两类方法：

<table> 
 <thead> 
  <tr> 
   <th>Queue 接口</th> 
   <th>抛出异常</th> 
   <th>返回特殊值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>在队尾插入元素</td> 
   <td>add(E e)</td> 
   <td>offer(E e)</td> 
  </tr> 
  <tr> 
   <td>删除队首元素</td> 
   <td>remove()</td> 
   <td>poll()</td> 
  </tr> 
  <tr> 
   <td>查询队首元素</td> 
   <td>element()</td> 
   <td>peek()</td> 
  </tr> 
 </tbody> 
</table>

（2）Deque 是**双端队列**，在队列的两端均可以插入或删除元素。**Deque 同时还是 Queue 的子接口**，增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

<table> 
 <thead> 
  <tr> 
   <th>Deque 接口</th> 
   <th>抛出异常</th> 
   <th>返回布尔值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>在队首插入元素</td> 
   <td>addFirst(E e)</td> 
   <td>offerFirst(E e))</td> 
  </tr> 
  <tr> 
   <td>在队尾插入元素</td> 
   <td>addLast(E e)</td> 
   <td>offerLast(E e)</td> 
  </tr> 
  <tr> 
   <td>删除队首元素</td> 
   <td>removeFirst()</td> 
   <td>pollFirst()</td> 
  </tr> 
  <tr> 
   <td>删除队尾元素</td> 
   <td>removeLast()</td> 
   <td>pollLast()</td> 
  </tr> 
  <tr> 
   <td>查询队首元素</td> 
   <td>getFirst()</td> 
   <td>peekFirst()</td> 
  </tr> 
  <tr> 
   <td>查询队尾元素</td> 
   <td>getLast()</td> 
   <td>peekLast()</td> 
  </tr> 
 </tbody> 
</table>

（3）Deque 还提供有 `push()` 和 `pop()` 等其他方法，可用于**模拟栈**。

Deque<Integer> stack = new ArrayDeque<>();

### 2.5.ArrayDeque 和 LinkedList 有什么区别？ ###

ArrayDeque 和 LinkedList 均实现了 Deque 接口，即都具有队列的功能，但两者具有以下这些区别：

*  ArrayDeque 在 JDK 1.6 才被引入，而 LinkedList 早在 JDK1.2 时就已经存在；
 *  ArrayDeque 底层是基于**动态数组 + 双指针**实现的，而 LinkedList 底层则是通过链表实现的；
 *  ArrayDeque 不支持存储 null 数据，但 LinkedList 支持；
 *  ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作的时间复杂度依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

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

### 2.6.比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同。 ###

（1）HashSet、LinkedHashSet 和 TreeSet 都是 Java 中实现了 Set 接口的集合类，它们都有一些共同点，比如元素不允许重复，没有下标索引，可以进行遍历等。不同之处在于它们内部的实现机制不同，导致它们在某些方面具有特殊的性质。

（2）HashSet、LinkedHashSet 和 TreeSet 的主要区别在于以下方面：

*  **底层实现**：HashSet 是基于哈希表实现的，它是最快的，但是它不保证元素的顺序。LinkedHashSet 继承自 HashSet，但是它通过维护一个**双向链表**来保证元素的插入顺序和遍历顺序与添加顺序一致。TreeSet 则是基于**红黑树**实现的，它可以自动将元素按照一定的顺序排序，并且支持按照自然顺序或者指定的比较器进行排序。
 *  **性能**：HashSet 的插入、删除和查询操作的平均时间复杂度是 O(1)，但是最坏情况下可能会达到 O(n)，因为哈希冲突的存在。LinkedHashSet 的性能与 HashSet 相似，但是因为需要维护双向链表，所以会稍微慢一些。TreeSet 的插入、删除和查询操作的平均时间复杂度是 O(log n)，因为它需要进行平衡操作，但是保证了元素的有序性。
 *  **元素的顺序**：HashSet 不保证元素的顺序。LinkedHashSet 的元素顺序与添加顺序一致。TreeSet 的元素按照自然顺序或者指定的比较器进行排序。
 *  **内存占用**：HashSet 和 LinkedHashSet 占用的内存比 TreeSet 小，因为它们不需要维护排序的结构。
 *  **迭代顺序**：HashSet 的迭代顺序是不确定的，而 LinkedHashSet 的迭代顺序与添加顺序一致。TreeSet 的迭代顺序与元素的排序顺序一致。

### 2.7.谈一谈 PriorityQueue。 ###

PriorityQueue 中元素出队顺序与**优先级**相关，即总是优先级最高的元素先出队。这里列举其相关的一些要点：

*  PriorityQueue 利用了**二叉堆**的数据结构来实现的，底层使用可变长的数组来存储数据；
 *  PriorityQueue 通过堆元素的上浮和下沉，实现了**在 O(log2n) 的时间复杂度内**插入元素和删除堆顶元素；
 *  PriorityQueue 是**非线程安全**的，且不支持存储 NULL 和 non-comparable 的对象；
 *  PriorityQueue 默认是**小顶堆**，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后；
 *  PriorityQueue 经常与面试中的典型算法题有关，例如堆排序、求第 K 大的数、带权图的遍历等。

### 2.8.数组与 List 相互转换的方法有哪些？ ###

具体参考[Java 基础——List 与数组、Map 相互转换][Java _List _Map]这篇文章。

## 3.Map ##

### 3.1.HashMap 和 Hashtable 有什么区别？ ###

（1）线程是否安全  
HashMap 是非线程安全的，Hashtable 是线程安全的（Hashtable 中的方法基本都使用 synchronized 修饰，同时在**效率**上不如 HashMap）。如果要保证线程安全，可以使用 ConcurrentHashMap，因为目前 Hashtable 使用的频率较低。

（2）对 null 键和 null 值的支持

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>HashMap</th> 
   <th>Hashtable</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>null 键</td> 
   <td>支持，但只允许有一个</td> 
   <td>不支持</td> 
  </tr> 
  <tr> 
   <td>null 值</td> 
   <td>支持</td> 
   <td>不支持</td> 
  </tr> 
 </tbody> 
</table>

> 注意：如果 HashTable 中存在 null 键或 null 值，会抛出 NullPointerException。

（3）初始容量和扩容操作

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>HashMap</th> 
   <th>Hashtable</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>初始容量</td> 
   <td>16，也可自己指定</td> 
   <td>11，也可自己指定</td> 
  </tr> 
  <tr> 
   <td>扩容操作</td> 
   <td>每次扩充容量变为原来的 2 倍</td> 
   <td>每次扩充容量变为 2n+1，n 为上一次的容量</td> 
  </tr> 
 </tbody> 
</table>

（4）计算 hash 值的方式  
① HashMap 计算 hash 值的方式为先调用 hashCode() 计算出来一个 hash 值，再将 hash 与 hash 右移 16 位后的值进行异或操作，从而得到最终的 hash 值，具体的代码实现如下：

static final int hash(Object key) {
        
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

② Hashtable 则通过计算 key 的 hashCode() 来得到最终的 hash 值。

（5）解决 hash 冲突的机制

*  HashMap：在 JDK 1.8 之前，HashMap 底层由**数组 + 链表**组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（通过“拉链法”解决冲突）。而 JDK 1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8，并且将链表转换成**红黑树**前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为**红黑树**，以减少搜索时间；
 *  HashTable：底层也是由**数组 + 链表**组成的，但没有像 HashMap 那样的机制。

具体细节可参考[这篇文章][Link 1]。

### 3.2.✨HashMap 和 HashSet 有什么联系与区别？ ###

（1）**HashSet 底层就是基于 HashMap 实现的**，具体见下面 HashSet 的几个构造函数：

public HashSet() {
        
        map = new HashMap<>();
    }
    
    public HashSet(Collection<? extends E> c) {
        
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
    public HashSet(int initialCapacity, float loadFactor) {
        
        map = new HashMap<>(initialCapacity, loadFactor);
    }
    
    public HashSet(int initialCapacity) {
        
        map = new HashMap<>(initialCapacity);
    }

（2）但 HashMap 和 HashSet 之间也存在着一些区别：

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>HashMap</th> 
   <th>HashSet</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>实现接口</td> 
   <td>实现了 Map 接口</td> 
   <td>实现了 Set 接口</td> 
  </tr> 
  <tr> 
   <td>添加方式</td> 
   <td>调用 put() 向 map 中添加键值对</td> 
   <td>调用 add() 向 set 中添加元素</td> 
  </tr> 
  <tr> 
   <td>计算 hashcode</td> 
   <td>通过键 (key) 来计算</td> 
   <td>使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以 equals() 方法用来判断对象的相等性</td> 
  </tr> 
 </tbody> 
</table>

（3）此外，在 HashSet 的实现中，存在一个私有的静态常量 `PRESENT`，它的类型是 Object，并且被设置为 `new Object()`。**这个对象作为 HashMap 中键的占位值，并通过共享对象节省内存空间**，具体分析如下：

*  HashSet 内部实际上是通过 HashMap 来实现的，HashSet 的元素被存储在 HashMap 的键上，而不需要存储对应的值。由于 HashMap 的键是唯一的，所以 HashSet 能够保证其中没有重复的元素。
 *  使用静态常量 `PRESENT` 的目的是为了节省内存空间。在 HashSet 中，每个元素实际上是作为 HashMap 的键存储的，而 HashMap 中的值是占位值 `PRESENT`。由于所有的元素在 HashMap 中共享同一个占位值对象，通过共享对象，可以在内存上更高效地表示元素的存在。
 *  此外，由于 `PRESENT` 是一个私有的静态常量，它只在 HashSet 的实现内部使用，确保了其他类无法修改这个对象的引用值，从而保持了 HashSet 的一致性和正确性。

public class HashSet<E>
        extends AbstractSet<E>
        implements Set<E>, Cloneable, java.io.Serializable {
        
        static final long serialVersionUID = -5024744406713321676L;
    
        private transient HashMap<E,Object> map;
    
        // Dummy value to associate with an Object in the backing Map
        private static final Object PRESENT = new Object();
    
    	//...
    }

（4）**思考：为什么 HashSet 中 map 的 value 不将 null 作为值？**

*  在 HashSet 的实现中，使用 `PRESENT` 占位值而不是 `null` 主要是为了**减少内存占用**。如果使用 `null` 作为占位值，那么每个元素在 HashMap 的键值对中都需要额外存储一个占位值 `null`，而这会增加内存的使用量。
 *  此外，使用 `null` 作为占位值**可能会引起错误**，因为 `null` 可能是元素的有效值之一。而使用特殊的占位值 `PRESENT` 可以避免这种混淆，因为 `PRESENT` 通常是一个编程约定，用于表示“键的存在”。
 *  总结而言，使用 `PRESENT` 占位值而不是 `null` 是为了节省内存空间，并且避免与元素有效值混淆。

### 3.3.✨HashMap 与 TreeMap 有什么区别？ ###

（1）TreeMap 和HashMap 都继承自 AbstractMap ，**但是 TreeMap 还实现了 NavigableMap 接口和 SortedMap 接口**：

*  实现 `NavigableMap` 接口让 TreeMap 有了对集合中的元素进行搜索的能力：
    
     *  **导航操作**：NavigableMap 提供了许多导航操作的方法，如 lowerKey、floorKey、ceilingKey、higherKey 等，用于获取指定键的前一个键、小于等于指定键的键、大于等于指定键的键、后一个键等。这些方法对于实现范围查询、区间检索等操作非常有用。
     *  **子映射操作**：NavigableMap 提供了 subMap、headMap 和 tailMap 方法，用于获取指定范围内的子映射。这些方法可以用来获取大于等于或小于等于某一键的子映射，并支持开放或关闭区间的边界。
     *  **键的排序**：NavigableMap 中的键是按照自然顺序或自定义顺序进行排序的。可以使用 Comparator 或 Comparable 接口来指定键的顺序。这使得可以对键进行排序，并通过键来按顺序迭代、搜索和访问映射的元素。
 *  实现 `SortedMap` 接口让 TreeMap 有了对集合中的元素**根据键排序**的能力：
    
     *  **有序性**：SortedMap 中的键值对是按照键的顺序进行排序的。可以根据键的自然顺序（如果键实现了 Comparable 接口）或者自定义的比较器（如果指定了 Comparator）对键进行排序。
     *  **范围视图**：SortedMap 提供了一些方法，例如 subMap、headMap 和 tailMap，用于获取指定范围内的子映射。这些范围视图方法允许根据键的范围来获取子映射，从而支持范围查询和处理。
     *  **排序遍历**：SortedMap 提供了方法来支持按照键的顺序进行遍历。可以使用 keySet、values 和 entrySet 方法获取按照键排序的键集合、值集合和键值对集合。

TreeMap 中的键值对默认是按 key 的升序排序，不过我们也可以指定排序的比较器。示例代码如下：

public class Person {
        
        private Integer age;
        
        public Person(Integer age) {
        
            this.age = age;
        }
        
        public Integer getAge() {
        
            return age;
        }
        
        public static void main(String[] args) {
        
            //重写排序规则
            TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
        
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            });
            treeMap.put(new Person(3), "person1");
            treeMap.put(new Person(18), "person2");
            treeMap.put(new Person(35), "person3");
            treeMap.put(new Person(16), "person4");
            treeMap.forEach((key, value) -> System.out.println(value));
        }
    }

输出结果如下：

person1
    person4
    person2
    person3

（2）总之，相比于 HashMap 来说，TreeMap 主要多了对集合中的元素**根据键排序的能力**以及**对集合内元素进行搜索的能力**。

![在这里插入图片描述][611131d293b941b29d6ca0ea3075b0d3.png]

![在这里插入图片描述][45a08794c4994039a76058018e055092.png]

### 3.4.HashMap 有哪些遍历方式？ ###

参考[Java 基础——HashMap 遍历方式][Java _HashMap]这篇文章。

### 3.5.✨HashMap 的底层数据结构是什么样的？对其源码了解多少？ ###

参考[Java 基础——HashMap 底层数据结构与源码分析][Java _HashMap 1]这篇文章。

### 3.6.Hashmap 为什么是线程不安全的？线程不安全有哪些表现？ ###

> 参考文章：  
> [HashMap 为什么线程不安全？][HashMap]

（1）HashMap 是一种常用的 Java 集合类，用于存储键值对数据。HashMap 是一种基于哈希表实现的数据结构，其内部实现包括了数组和链表或红黑树。由于哈希表本身的特性，HashMap 存在线程不安全的问题。

（2）具体来说，当多个线程同时对 HashMap 进行读写操作时，可能会发生以下情况：

*  **丢失更新**：当多个线程同时对同一个键进行写操作时，可能会出现数据被覆盖的情况。这是因为在进行写操作时，HashMap 中的数据结构可能会发生变化，导致某些操作被丢失。
 *  **死循环**：当多个线程同时对 HashMap 进行读写操作时，可能会出现死循环的情况。这是因为在进行读写操作时，HashMap 中的数据结构可能会发生变化，导致某些操作无法完成，从而导致线程陷入死循环。
 *  **错误计算**：当多个线程同时对 HashMap 进行读写操作时，可能会出现计算错误的情况。这是因为在进行读写操作时，HashMap 中的数据结构可能会发生变化，导致某些操作计算错误，从而导致程序出现逻辑错误。

### 3.7.HashTable 与 ConcurrentHashMap 有什么区别？ ###

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

*  **底层数据结构**： JDK1.7 的 ConcurrentHashMap 底层采用分段的**数组+链表**来实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，**数组+链表/红黑树**。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用数组+链表的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
 *  **实现线程安全的方式**：
    
     *  在 JDK1.7 的时候，ConcurrentHashMap 对整个桶数组进行了分割分段（Segment，分段锁），每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
     *  到了 JDK1.8 的时候，ConcurrentHashMap 已经摒弃了 Segment 的概念，而是直接用 **Node 数组+链表+红黑树**的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了**兼容旧版本**；
     *  Hashtable（同一把锁）：使用 synchronized 来保证线程安全，**效率非常低下**。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 方法添加元素，也不能使用 get 方法来获取元素，竞争会越来越激烈效率越低。

> 相关文章：  
> [关于 HashMap 和 ConcurrentHashMap 理解][HashMap _ ConcurrentHashMap]  
> [ConcurrentHashMap 源码分析][ConcurrentHashMap]

### 3.8.HashSet 如何检查重复的元素？ ###

（1）当把对象加入 HashSet 时，HashSet 会先计算对象的 hashcode 值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用 `equals()` 方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

（2）在 JDK1.8 中，HashSet 的 `add()` 方法只是简单的调用了 HashMap 的 `put()` 方法，并且判断了一下返回值以确保是否有重复元素。直接看一下 HashSet 中的源码：

//@return true if this set did not already contain the specified element
    public boolean add(E e) {
        
        return map.put(e, PRESENT)==null;
    }

而在 HashMap 的 `putVal()` 方法中也能看到如下说明：

// Returns : previous value, or null if none
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
    	...
    }

也就是说，在 JDK1.8 中，实际上无论 HashSet 中是否已经存在了某元素，HashSet都会直接插入，只是会在 `add()` 方法的返回值处告诉我们插入前是否存在相同元素。

### 3.9.Java 中 LinkedHashMap 的底层实现原理是什么？ ###

（1）LinkedHashMap 是 Java 中提供的一种特殊的哈希表 (HashMap) 实现，它可以维护键值对的插入顺序或者访问顺序，并且可以通过迭代器按照插入顺序或访问顺序访问元素。

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
        
    	//...
    }

（2）LinkedHashMap 的底层实现原理和 HashMap 非常相似，都是基于哈希表实现的。**不同的是，LinkedHashMap 在内部维护了一个双向链表，用于维护键值对的插入顺序或访问顺序。每个节点都包含了前驱节点和后继节点的引用**。

（3）在 LinkedHashMap 中，每个桶 (bucket) 都是一个指向双向链表头节点的引用。当**插入一个新的键值对**时，它会被插入到链表的尾部，并且在哈希表中的相应位置指向链表的新的尾节点。这样就保证了键值对的插入顺序。

（4）当使用迭代器按照访问顺序**访问 LinkedHashMap 中的元素**时，每次访问一个元素，该元素就会被移到链表的尾部，这样就可以保证最近访问的元素总是在链表的尾部，最早访问的元素总是在链表的头部。这样，就可以方便地实现 LRU（Least Recently Used，最近最少使用）缓存淘汰策略。

（5）总的来说，LinkedHashMap 是一种可以同时保证插入顺序和访问顺序的哈希表实现，它通过维护一个双向链表来实现这一功能。

> 设计 LRU 的相关算法题：[LeetCode\_数据结构设计\_中等\_146.LRU 缓存][LeetCode_146.LRU]

### 3.10.TreeSet 有什么特点？ ###

（1）TreeSet 是 Java 中的一种集合类型，它实现了 Set 接口，并使用**红黑树**作为底层数据结构。TreeSet 具有以下特点：

*  **有序性**：TreeSet 中的元素是按照自然顺序或指定的比较器顺序排序的，因此可以在集合中快速进行有序访问。
 *  **唯一性**：TreeSet 中不允许存储重复元素，保证了集合中的所有元素都是唯一的。
 *  **可排序性**：TreeSet 中的元素必须实现 `Comparable` 接口或通过构造函数提供 `Comparator` 对象，以便进行元素的比较和排序。
 *  **高效性**：TreeSet 的内部实现采用了红黑树，使得元素的查找、插入和删除操作具有较高的效率。

（2）需要注意的是，由于 TreeSet 是有序的，因此其性能通常比 HashSet 稍慢，特别是在添加和删除元素时。但是，对于需要有序性的场景，TreeSet 是一个非常有用的集合类型。

### 3.11.Java 8 对链地址法做了什么优化？ ###

（1）**链地址法**是哈希表中解决哈希冲突的一种方式，Java 8 对链地址法进行了优化，使得其在处理哈希冲突时更加高效。

（2）Java 8 在实现链地址法时，**使用了红黑树来替代链表**。当一个哈希桶中的链表长度超过了一定的阈值（默认为 8）时，Java 8 将会使用红黑树来存储这些元素，而不是继续使用链表。这种方式可以使得哈希表在处理哈希冲突时更加高效，因为**红黑树的查找、插入和删除操作的时间复杂度都是 O(log n)，而链表的时间复杂度则是 O(n)**。并且这个阈值是可以通过 JVM 参数来进行调整的，开发人员可以根据实际应用场景来设置合适的阈值。

（3）总之，Java 8 对链地址法进行了优化，**使得哈希表在处理哈希冲突时更加高效，提高了程序的性能。**

### 3.12.集合中的 poll() 和 remove() 有什么异同？ ###

（1）相同点：poll() 和 remove() 都是从队列中**取出一个元素**；  
（2）不同点：poll() 在获取元素失败的时候会**返回空**，但 remove() 失败的时候会**抛出异常**。

[Java]: https://javaguide.cn/java/collection/java-collection-questions-01.html
[cb744ad88f534a83a8f3acbfb8dfec58.png]: https://img-blog.csdnimg.cn/cb744ad88f534a83a8f3acbfb8dfec58.png
[Java 1]: https://xgqngu.blog.csdn.net/article/details/131743200
[ArrayList _ LinkedList]: https://blog.csdn.net/programmerylj/article/details/107550476
[Java _ArrayList]: https://blog.csdn.net/weixin_43004044/article/details/129898335
[Java _List _Map]: https://blog.csdn.net/weixin_43004044/article/details/129850486
[Link 1]: https://blog.csdn.net/xuhuaabc/article/details/91475761
[611131d293b941b29d6ca0ea3075b0d3.png]: https://img-blog.csdnimg.cn/611131d293b941b29d6ca0ea3075b0d3.png
[45a08794c4994039a76058018e055092.png]: https://img-blog.csdnimg.cn/45a08794c4994039a76058018e055092.png
[Java _HashMap]: https://blog.csdn.net/weixin_43004044/article/details/129851260
[Java _HashMap 1]: https://blog.csdn.net/weixin_43004044/article/details/130137431
[HashMap]: https://blog.csdn.net/weixin_44950062/article/details/108724123
[HashMap _ ConcurrentHashMap]: https://blog.csdn.net/qq_37672177/article/details/123401067
[ConcurrentHashMap]: https://javaguide.cn/java/collection/concurrent-hash-map-source-code.html
[LeetCode_146.LRU]: https://blog.csdn.net/weixin_43004044/article/details/124601850