Java 基础面试题——集合_java集合面试

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

1.概述

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

从上图可以知道，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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

（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());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

（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); 	//输出 []
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

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

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);
}
1
2
3
4
5
6
7

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
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

在上面的例子中，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();
    }
}
1
2
3
4
5
6

在上面的例子中，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());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

最终的输出结果如下：

A 20
B 18
D 19
D 24
1
2
3
4

注：在 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
2
3
4
5
6
7
8

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

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

1.10.✨Java 集合的快速失败机制 “fail-fast” 和安全失败机制 “fail-safe” 分别是指什么？

Java 集合框架中有两种常见的容器修改检测机制：快速失败机制 “fail-fast” 和安全失败机制 “fail-safe”：

1.10.1.快速失败机制 “fail-fast”

（1）快速失败机制 “fail-fast” 这种机制通过在迭代器遍历集合时，如果检测到集合在遍历过程中被修改（如添加、删除元素），会立即抛出 ConcurrentModificationException 异常，从而防止可能的并发修改造成数据不一致。快速失败机制是一种保守策略，它假定集合操作多半是非并发的，如若发生并发修改，则认为程序有错误，因此立即报错。例如：

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
    list.remove(element); // 修改集合，会触发快速失败机制
}
1
2
3
4
5
6
7
8
9
10
11

上述代码在遍历集合时尝试删除元素，由于并发修改了集合，会导致 ConcurrentModificationException 异常被抛出：

a
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at com.exam.Main.main(Main.java:67)
1
2
3
4
5

正确的做法是用迭代器的 remove() 方法，便可正常运行，具体代码如下所示：

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
    //list.remove(element); 	//修改集合，会触发快速失败机制
    iterator.remove();
}
System.out.println(list.size());  // 0
1
2
3
4
5
6
7
8
9
10
11
12
13

（2）造成这种情况的原因是什么？通过上述代码可以发现两次调用的 remove() 方法不同，一个带参数据，一个不带参数。经过查看 ArrayList 源码，找到了抛出异常的代码：

public class ArrayList<E> extends AbstractList<E> 
			implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
	//...

	final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
    }
}
1
2
3
4
5
6
7
8
9

从上面代码中可以看到如果 modCount 和 expectedModCount 这两个变量不相等就会抛出 ConcurrentModificationException 异常。

protected transient int modCount = 0; 	//在 AbstractList 中定义的变量
int expectedModCount = modCount;		//在 ArrayList 中的内部类 Itr 中定义的变量
1
2

从上面代码可以看到， modCount 初始值为 0，而 expectedModCount 初始值等于 modCount 。也就是说在遍历的时候直接调用集合的 remove() 方法会导致 modCount 不等于 expectedModCount 进而抛出 ConcurrentModificationException 异常，而使用迭代器的 remove() 方法则不会出现这种问题。具体源码分析如下：

public class ArrayList<E> extends AbstractList<E> 
			implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
	
	//...

	private class Itr implements Iterator<E> {
		
		//...

		public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }
}        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

从上面代码可以看到 expectedModCount = modCount 这一行代码保证了 expectedModCount 和 modCount 是相等的，进而保证了在增强 for 循环中修改集合内容不会抛出 ConcurrentModificationException 异常。

1.10.2.安全失败机制 “fail-safe”

安全失败机制 “fail-safe”：与快速失败机制不同，安全失败机制允许在迭代期间对集合进行修改操作，并且不会抛出异常。这是通过在迭代时复制原始集合的数据来实现的，迭代器操作的是被复制后的数据副本。因此，安全失败机制可以实现并发修改而不会触发异常，但可能会导致迭代结果不一致。例如：

List<String> list = new CopyOnWriteArrayList<>();
list.add("a");
list.add("b");
list.add("c");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
    list.remove(element); // 安全失败机制允许修改集合
}
1
2
3
4
5
6
7
8
9
10
11

上述代码使用 CopyOnWriteArrayList 类来进行迭代和修改操作，由于该类在迭代时使用了一份原始集合的快照，因此可以安全地删除元素而不会引发异常。

总结来说，快速失败机制 “fail-fast” 更适用于单线程环境，能够及早地检测到并发修改错误；而安全失败机制 “fail-safe” 更适用于多线程环境，能够保证遍历过程的稳定性。开发者在使用集合时需要根据具体的场景选择适合的机制。

相关知识点：
Java 设计模式——迭代器模式

1.11.Array 和 ArrayList 有什么区别？

Array 和 ArrayList 是 Java 中两种常见的数据结构，它们之间有一些区别。

• 大小固定 vs 可变大小：Array 是一个固定大小的数据结构，一旦创建后，其大小就不能再改变。而 ArrayList 是一个可变大小的数据结构，可以根据需要动态地添加或删除元素。
• 数据类型：Array 可以存储任意类型的元素，包括基本数据类型和引用类型。而 ArrayList 只能存储引用类型的对象，无法直接存储基本数据类型，需要使用其对应的包装类。
• 语法：声明和初始化 Array 需要指定数组的大小，例如 int[] arr = new int[5];。而 ArrayList 的声明和初始化比较简单，例如 ArrayList<Integer> list = new ArrayList<>();。
• 功能和灵活性：Array 提供了一些基本的操作方法，如访问指定索引的元素、修改指定索引的元素等。而 ArrayList 实现了 List 接口，提供了更多的方法，如添加元素、删除元素、查找元素等，并且支持动态扩容。
• 性能：由于 Array 是一个连续存储的数据结构，访问和修改元素的速度较快。而 ArrayList 内部使用了一个数组来存储元素，但在需要扩容时需要进行数组复制操作，可能会引入一些性能开销。

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 的三种遍历方式 这篇文章。

（6）内存空间占用

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

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

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

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

package java.util;

public interface RandomAccess {

}
1
2
3
4
5

（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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

（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 的扩容机制这篇文章。

2.4.Queue 和 Deque 有什么区别？

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

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

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

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

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(log₂n) 的时间复杂度内插入元素和删除堆顶元素；
• PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象；
• PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后；
• PriorityQueue 经常与面试中的典型算法题有关，例如堆排序、求第 K 大的数、带权图的遍历等。

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

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

3.Map

3.1.HashMap 和 Hashtable 有什么区别？

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

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

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

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

（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);
}
1
2
3
4

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

（5）解决 hash 冲突的机制

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

具体细节可参考这篇文章。

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

（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();

	//...
}
1
2
3
4
5
6
7
8
9
10
11
12

（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));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

输出结果如下：

person1
person4
person2
person3
1
2
3
4

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

3.4.HashMap 有哪些遍历方式？

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

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

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

3.6.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 理解
ConcurrentHashMap 源码分析

3.8.为什么 ConCurrentHashMap 的 key 和 value 不能为 null，而 HashMap 则可以？

ConcurrentHashMap 的 key 和 value 不能为 null，主要是为了保证线程安全性。

在 ConcurrentHashMap 中，为了支持并发读写操作，需要对数据进行分段，每个段（Segment）都拥有自己的锁。如果允许插入 null 值，那么在获取值时可能无法判断对应的 key 或 value 是否存在，这将给并发读写操作带来很大的风险，可能导致死锁或者其他异常情况。

因此，对于 ConcurrentHashMap，为了保证线程安全性，禁止插入 null 值。而对于 HashMap，虽然允许插入 null 值，但需要注意空指针异常和冲突问题。

（1）ConCurrentHashMap 的 key 和 value 不能为 null 的具体分析如下：

• 如果允许 ConcurrentHashMap 中的 key 和 value 为 null，那么可能会出现二义性问题。如果 ConcurrentHashMap.get(key) 的返回值为 null，此时无法判断到底是 key 对应的 value 的值为 null，还是不存在对应的 key 值。
• 之所以 ConcurrentHashMap 会产生这个问题，主要是因为 ConcurrentHashMap 一般在并发环境下使用，如果在调用 get(key) 之前先用 containsKey(key) 方法进行判断，那么在这个过程中是无法保证 key 是不变的。例如，在 containsKey(key) 方法和 get(key) 方法的中间某一时刻，key 的值已经发生了改变。
• 综上所述，ConcurrentHashMap 的 key 和 value 不能为 null。而为了保证这一点，ConcurrentHashMap 的源代码中进行了空值校验，即在向 ConcurrentHashMap 中插入数据时，会判断 key 和 value 是否为空，如果发现为空，则会抛出 NullPointerException；

（2）而在 HashMap 中，由于没有并发读写操作的保护措施，允许插入 null 值也不会影响线程安全性。但是，在使用 null 值作为 key 时，需要注意它可能会与已有的 key 冲突，导致覆盖原有值。而对于 null 值作为 value，HashMap 并不会出现冲突，但在获取值时也需要进行非空判断，以避免空指针异常。并且在单线程场景下的 HashMap 中，可以使用 containsKey(key) 来判断到底是否存在这个 key。

3.9.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;
}
1
2
3
4

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

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

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

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

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

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

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

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

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

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

设计 LRU 的相关算法题：LeetCode_数据结构设计_中等_146.LRU 缓存

3.11.TreeSet 有什么特点？

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

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

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

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

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

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

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

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

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