Java 集合 常见面试问题

集合概述

Java 集合概览

Java 集合，也叫作容器，主要是由两大接口派生而来：一个是 Collection 接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于 Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。

Java 集合框架如下图所示：

注：图中只列举了主要的继承派生关系，并没有列举所有关系。比方省略了 AbstractList, NavigableSet 等抽象类以及其他的一些辅助类，如想深入了解，可自行查看源码。

说说 List、Set、Queue、Map 四者的区别？

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

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

先来看一下 Collection 接口下面的集合。

List

• ArrayList：Object[] 数组。详细可以查看：ArrayList 源码分析。
• Vector：Object[] 数组。
• LinkedList：双向链表 (JDK 1.6 之前为循环链表，JDK 1.7 取消了循环)。详细可以查看：LinkedList 源码分析。

Set

• HashSet (无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素。
• LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。
• TreeSet (有序，唯一): 红黑树 (自平衡的排序二叉树)。

Queue

• PriorityQueue: Object[] 数组来实现小顶堆。详细可以查看：PriorityQueue 源码分析。
• DelayQueue: PriorityQueue。详细可以查看：DelayQueue 源码分析。
• ArrayDeque: 可扩容动态双向数组。

再来看看 Map 接口下面的集合。

Map

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

如何选用集合?

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

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

为什么要使用集合？

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

List

ArrayList 和 Array（数组）的区别？

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

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

下面是二者使用的简单对比：

Array：

// 初始化一个 String 类型的数组
String[] stringArr = new String[]{"hello", "world", "!"};
// 修改数组元素的值
stringArr[0] = "goodbye";
System.out.println(Arrays.toString(stringArr));// [goodbye, world, !]
// 删除数组中的元素，需要手动移动后面的元素
for (int i = 0; i < stringArr.length - 1; i++) {
    stringArr[i] = stringArr[i + 1];
}
stringArr[stringArr.length - 1] = null;
System.out.println(Arrays.toString(stringArr));// [world, !, null]

ArrayList ：

// 初始化一个 String 类型的 ArrayList
 ArrayList<String> stringList = new ArrayList<>(Arrays.asList("hello", "world", "!"));
// 添加元素到 ArrayList 中
 stringList.add("goodbye");
 System.out.println(stringList);// [hello, world, !, goodbye]
 // 修改 ArrayList 中的元素
 stringList.set(0, "hi");
 System.out.println(stringList);// [hi, world, !, goodbye]
 // 删除 ArrayList 中的元素
 stringList.remove(0);
 System.out.println(stringList); // [world, !, goodbye]

ArrayList 和 Vector 的区别?（了解即可）

• ArrayList 是 List 的主要实现类，底层使用 Object[] 存储，适用于频繁的查找工作，线程不安全。
• Vector 是 List 的古老实现类，底层使用 Object[] 存储，线程安全。

Vector 和 Stack 的区别?（了解即可）

• Vector 和 Stack 两者都是线程安全的，都是使用 synchronized 关键字进行同步处理。
• Stack 继承自 Vector，是一个后进先出的栈，而 Vector 是一个列表。

随着 Java 并发编程的发展，Vector 和 Stack 已经被淘汰，推荐使用并发集合类（例如 ConcurrentHashMap、CopyOnWriteArrayList 等）或者手动实现线程安全的方法来提供安全的多线程操作支持。

ArrayList 可以添加 null 值吗？

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

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

对于插入：

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

对于删除：

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

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

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

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

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

ArrayList 与 LinkedList 区别?

• 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
• 底层数据结构： ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK 1.6 之前为循环链表，JDK 1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
• 插入和删除是否受元素位置的影响：
  • ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行 add(E e) 方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O (1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)），时间复杂度就为 O (n)。因为在进行上述操作的时候集合中第 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), remove(int index)），时间复杂度为 O (n) ，因为需要先移动到指定位置再插入和删除。
• 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList（实现了 RandomAccess 接口） 支持。快速随机访问就是通过元素的序号快速获取元素对象 (对应于 get(int index) 方法)。
• 内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）自己都说从来不会使用 LinkedList 。

另外，不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景。我在上面也说了，LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O (1)，其他情况增删元素的平均时间复杂度都是 O (n) 。

补充内容: 双向链表和双向循环链表

双向链表： 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。

双向循环链表： 最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。

补充内容: RandomAccess 接口

public interface RandomAccess {
}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以，在我看来 RandomAccess 接口不过是一个标识罢了。标识什么？ 标识实现这个接口的类具有随机访问功能。

在 binarySearch（) 方法中，它要判断传入的 list 是否 RandomAccess 的实例，如果是，调用 indexedBinarySearch() 方法，如果不是，那么调用 iteratorBinarySearch() 方法

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

ArrayList 实现了 RandomAccess 接口，而 LinkedList 没有实现。为什么呢？我觉得还是和底层数据结构有关！ArrayList 底层是数组，而 LinkedList 底层是链表。数组天然支持随机访问，时间复杂度为 O (1)，所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O (n)，所以不支持快速随机访问。ArrayList 实现了 RandomAccess 接口，就表明了他具有快速随机访问功能。 RandomAccess 接口只是标识，并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的！

说一说 ArrayList 的扩容机制吧

Set

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().

Comparator 定制排序

ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(-1);
arrayList.add(3);
arrayList.add(3);
arrayList.add(-5);
arrayList.add(7);
arrayList.add(4);
arrayList.add(-9);
arrayList.add(-7);
System.out.println("原始数组:");
System.out.println(arrayList);
// void reverse(List list)：反转
Collections.reverse(arrayList);
System.out.println("Collections.reverse(arrayList):");
System.out.println(arrayList);

// void sort(List list),按自然排序的升序排序
Collections.sort(arrayList);
System.out.println("Collections.sort(arrayList):");
System.out.println(arrayList);
// 定制排序的用法
Collections.sort(arrayList, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
});
System.out.println("定制排序后：");
System.out.println(arrayList);

Output:

原始数组:
[-1, 3, 3, -5, 7, 4, -9, -7]
Collections.reverse(arrayList):
[-7, -9, 4, 7, -5, 3, 3, -1]
Collections.sort(arrayList):
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后：
[7, 4, 3, 3, -1, -5, -7, -9]

重写 compareTo 方法实现按年龄来排序

// person对象没有实现Comparable接口，所以必须实现，这样才不会出错，才可以使treemap中的数据按顺序排列
// 前面一个例子的String类已经默认实现了Comparable接口，详细可以查看String类的API文档，另外其他
// 像Integer类等都已经实现了Comparable接口，所以不需要另外实现了
public  class Person implements Comparable<Person> {
    private String name;
    private int age;

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

    public String getName() {
        return name;
    }

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

    public int getAge() {
        return age;
    }

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

    /**
     * T重写compareTo方法实现按年龄来排序
     */
    @Override
    public int compareTo(Person o) {
        if (this.age > o.getAge()) {
            return 1;
        }
        if (this.age < o.getAge()) {
            return -1;
        }
        return 0;
    }
}

public static void main(String[] args) {
    TreeMap<Person, String> pdata = new TreeMap<Person, String>();
    pdata.put(new Person("张三", 30), "zhangsan");
    pdata.put(new Person("李四", 20), "lisi");
    pdata.put(new Person("王五", 10), "wangwu");
    pdata.put(new Person("小红", 5), "xiaohong");
    // 得到key的值的同时得到key所对应的值
    Set<Person> keys = pdata.keySet();
    for (Person key : keys) {
        System.out.println(key.getAge() + "-" + key.getName());

    }
}

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

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

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

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

Queue

Queue 与 Deque 的区别

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

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

Queue 接口	抛出异常	返回特殊值
插入队尾	add (E e)	offer (E e)
删除队首	remove ()	poll ()
查询队首元素	element ()	peek ()

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

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

Deque 接口	抛出异常	返回特殊值
插入队首	addFirst (E e)	offerFirst (E e)
插入队尾	addLast (E e)	offerLast (E e)
删除队首	removeFirst ()	pollFirst ()
删除队尾	removeLast ()	pollLast ()
查询队首元素	getFirst ()	peekFirst ()
查询队尾元素	getLast ()	peekLast ()

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

ArrayDeque 与 LinkedList 的区别

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

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

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

说一说 PriorityQueue

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

这里列举其相关的一些要点：

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

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

什么是 BlockingQueue？

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

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

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

BlockingQueue 的实现类有哪些？

Java 中常用的阻塞队列实现类有以下几种：

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

ArrayBlockingQueue 和 LinkedBlockingQueue 有什么区别？

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

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

Map（重要）

HashMap 和 Hashtable 的区别

• 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的, 因为 Hashtable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
• 效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；
• 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
• 初始容量大小和每次扩充容量大小的不同： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2 n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的 tableSizeFor() 方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小, 后面会介绍到为什么是 2 的幂次方。
• 底层数据结构： JDK 1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间（后文中我会结合源码对这一过程进行分析）。Hashtable 没有这样的机制。

HashMap 和 HashSet 区别

如果你看过 HashSet 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject() 是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

HashMap	HashSet
实现了 Map 接口	实现 Set 接口
存储键值对	仅存储对象
调用 put() 向 map 中添加元素	调用 add() 方法向 Set 中添加元素
HashMap 使用键（Key）计算 hashcode	HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以 equals() 方法用来判断对象的相等性

HashMap 和 TreeMap 区别

TreeMap 和 HashMap 都继承自 AbstractMap ，但是需要注意的是 TreeMap 它还实现了 NavigableMap 接口和 SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

实现 SortedMap 接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。示例代码如下：

/**
 * @author shuang.kou
 * @createTime 2020年06月15日 17:02:00
 */
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<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person 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.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

输出:

person1
person4
person2
person3

可以看出，TreeMap 中的元素已经是按照 Person 的 age 字段的升序来排列了。

上面，我们是通过传入匿名内部类的方式实现的，你可以将代码替换成 Lambda 表达式实现的方式：

TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
  int num = person1.getAge() - person2.getAge();
  return Integer.compare(num, 0);
});

综上，相比于 HashMap 来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

HashSet 如何检查重复?

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

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

// Returns: true if this set did not already contain the specified element
// 返回值：当 set 中没有包含 add 的元素时返回真
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

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

// Returns : previous value, or null if none
// 返回值：如果插入位置没有元素返回null，否则返回上一个元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
...
}

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

HashMap 的底层实现

JDK 1.8 之前

JDK 1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash 方法相比于 JDK 1.7 hash 方法更加简化，但是原理不变。

  static final int hash(Object key) {
    int h;
    // key.hashCode()：返回散列值也就是hashcode
    // ^：按位异或
    // >>>:无符号右移，忽略符号位，空位都以0补齐
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对比一下 JDK 1.7 的 HashMap 的 hash 方法源码.

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK 1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK 1.8 之后

相比于之前的版本， JDK 1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

TreeMap、TreeSet 以及 JDK 1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

我们来结合源码分析一下 HashMap 链表到红黑树的转换。

1、 putVal 方法中执行链表转红黑树的判断逻辑。

链表的长度大于 8 的时候，就执行 treeifyBin （转换红黑树）的逻辑。

// 遍历链表
for (int binCount = 0; ; ++binCount) {
    // 遍历到链表最后一个节点
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        // 如果链表元素个数大于等于TREEIFY_THRESHOLD（8）
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            // 红黑树转换（并不会直接转换成红黑树）
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

2、treeifyBin 方法中判断是否真的转换为红黑树。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 判断当前数组的长度是否小于 64
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // 如果当前数组的长度小于 64，那么会选择先进行数组扩容
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 否则才将列表转换为红黑树

        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树。

HashMap 的长度为什么是 2 的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。（n 代表数组长度）。这也就解释了 HashMap 的长度为什么是 2 的幂次方。

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余 (%)操作中如果除数是 2 的幂次则等价于与其除数减一的与 (&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。

HashMap 多线程操作导致死循环问题

JDK 1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

为了解决这个问题，JDK 1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在数据覆盖的问题。并发环境下，推荐使用 ConcurrentHashMap 。

一般面试中这样介绍就差不多，不需要记各种细节，个人觉得也没必要记。如果想要详细了解 HashMap 扩容导致死循环问题，可以看看耗子叔的这篇文章：Java HashMap 的死循环。

HashMap 为什么线程不安全？

JDK 1.7 及之前版本，在多线程环境下，HashMap 扩容时会造成死循环和数据丢失的问题。

数据丢失这个在 JDK 1.7 和 JDK 1.8 中都存在，这里以 JDK 1.8 为例进行介绍。

JDK 1.8 后，在 HashMap 中，多个键值对可能会被分配到同一个桶（bucket），并以链表或红黑树的形式存储。多个线程对 HashMap 的 put 操作会导致线程不安全，具体来说会有数据覆盖的风险。

举个例子：

• 两个线程 1,2 同时进行 put 操作，并且发生了哈希冲突（hash 函数计算出的插入下标是相同的）。
• 不同的线程可能在不同的时间片获得 CPU 执行的机会，当前线程 1 执行完哈希冲突判断后，由于时间片耗尽挂起。线程 2 先完成了插入操作。
• 随后，线程 1 获得时间片，由于之前已经进行过 hash 碰撞的判断，所有此时会直接进行插入，这就导致线程 2 插入的数据被线程 1 覆盖了。

Public V put (K key, V value) {
    Return putVal (hash (key), key, value, false, true);
}

Final V putVal (int hash, K key, V value, boolean onlyIfAbsent,
                   Boolean evict) {
    // ...
    // 判断是否出现 hash 碰撞
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中 (此时，这个结点是放在数组中)
    If ((p = tab[i = (n - 1) & hash]) == null)
        Tab[i] = newNode (hash, key, value, null);
    // 桶中已经存在元素（处理 hash 冲突）
    Else {
    // ...
}

还有一种情况是这两个线程同时 put 操作导致 size 的值不正确，进而导致数据覆盖的问题：

1. 线程 1 执行 if (++size > threshold) 判断时，假设获得 size 的值为 10，由于时间片耗尽挂起。
2. 线程 2 也执行 if (++size > threshold) 判断，获得 size 的值也为 10，并将元素插入到该桶位中，并将 size 的值更新为 11。
3. 随后，线程 1 获得时间片，它也将元素放入桶位中，并将 size 的值更新为 11。
4. 线程 1、2 都执行了一次 put 操作，但是 size 的值只增加了 1，也就导致实际上只有一个元素被添加到了 HashMap 中。

Public V put (K key, V value) {
    Return putVal (hash (key), key, value, false, true);
}

Final V putVal (int hash, K key, V value, boolean onlyIfAbsent,
                   Boolean evict) {
    // ...
    // 实际大小大于阈值则扩容
    If (++size > threshold)
        Resize ();
    // 插入后回调
    AfterNodeInsertion (evict);
    Return null;
}

HashMap 常见的遍历方式?

ConcurrentHashMap 和 Hashtable 的区别

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

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

Hashtable :

JDK 1.7 的 ConcurrentHashMap：

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 数组中的每个元素包含一个 HashEntry 数组，每个 HashEntry 数组属于链表结构。

JDK 1.8 的 ConcurrentHashMap：

JDK 1.8 的 ConcurrentHashMap 不再是 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。不过，Node 只能用于链表的情况，红黑树的情况需要使用 **TreeNode**。当冲突链表达到一定长度时，链表会转换成红黑树。

TreeNode 是存储红黑树节点，被 TreeBin 包装。TreeBin 通过 root 属性维护红黑树的根结点，因为红黑树在旋转的时候，根结点可能会被它原来的子节点替换掉，在这个时间点，如果有其他线程要写这棵红黑树就会发生线程不安全问题，所以在 ConcurrentHashMap 中 TreeBin 通过 waiter 属性维护当前使用这棵红黑树的线程，来防止其他线程的进入。

static final class TreeBin<K,V> extends Node<K,V> {
        TreeNode<K,V> root;
        volatile TreeNode<K,V> first;
        Volatile Thread waiter;
        Volatile int lockState;
        // values for lockState
        Static final int WRITER = 1; // set while holding write lock
        Static final int WAITER = 2; // set when waiting for write lock
        Static final int READER = 4; // increment value for setting read lock
...
}

ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

JDK 1.8 之前

首先将数据分为一段一段（这个“段”就是 Segment）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 继承了 ReentrantLock, 所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的个数一旦初始化就不能改变。 Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。

Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。也就是说，对同一 Segment 的并发写入会被阻塞，不同 Segment 的写入是可以并发执行的。

JDK 1.8 之后

Java 8 几乎完全重写了 ConcurrentHashMap，代码量从原来 Java 7 中的 1000 多行，变成了现在的 6000 多行。

ConcurrentHashMap 取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O (N)）转换为红黑树（寻址时间复杂度为 O (log (N))）。

Java 8 中，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。

JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现有什么不同？

• 线程安全实现方式：JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。JDK 1.8 放弃了 Segment 分段锁的设计，采用 Node + CAS + synchronized 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。
• Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK 1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。
• 并发度：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。

ConcurrentHashMap 为什么 key 和 value 不能为 null？

ConcurrentHashMap 的 key 和 value 不能为 null 主要是为了避免二义性。Null 是一个特殊的值，表示没有对象或没有引用。如果你用 null 作为键，那么你就无法区分这个键是否存在于 ConcurrentHashMap 中，还是根本没有这个键。同样，如果你用 null 作为值，那么你就无法区分这个值是否是真正存储在 ConcurrentHashMap 中的，还是因为找不到对应的键而返回的。

拿 get 方法取值来说，返回的结果为 null 存在两种情况：

• 值没有在集合中；
• 值本身就是 null。

这也就是二义性的由来。

具体可以参考 ConcurrentHashMap 源码分析 。

多线程环境下，存在一个线程操作该 ConcurrentHashMap 时，其他的线程将该 ConcurrentHashMap 修改的情况，所以无法通过 containsKey (key) 来判断否存在这个键值对，也就没办法解决二义性问题了。

与此形成对比的是，HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。如果传入 null 作为参数，就会返回 hash 值为 0 的位置的值。单线程环境下，不存在一个线程操作该 HashMap 时，其他的线程将该 HashMap 修改的情况，所以可以通过 contains (key) 来做判断是否存在这个键值对，从而做相应的处理，也就不存在二义性问题。

也就是说，多线程下无法正确判定键值对是否存在（存在其他线程修改的情况），单线程是可以的（不存在其他线程修改的情况）。

如果你确实需要在 ConcurrentHashMap 中使用 null 的话，可以使用一个特殊的静态空对象来代替 null。

Public static final Object NULL = new Object ();

ConcurrentHashMap 能保证复合操作的原子性吗？

ConcurrentHashMap 是线程安全的，意味着它可以保证多个线程同时对它进行读写操作时，不会出现数据不一致的情况，也不会导致 JDK 1.7 及之前版本的 HashMap 多线程操作导致死循环问题。但是，这并不意味着它可以保证所有的复合操作都是原子性的，一定不要搞混了！

复合操作是指由多个基本操作 (如 put、get、remove、containsKey 等)组成的操作，例如先判断某个键是否存在 containsKey (key)，然后根据结果进行插入或更新 put (key, value)。这种操作在执行过程中可能会被其他线程打断，导致结果不符合预期。

例如，有两个线程 A 和 B 同时对 ConcurrentHashMap 进行复合操作，如下：

// 线程 A
If (! Map.ContainsKey (key)) {
Map.Put (key, value);
}
// 线程 B
If (! Map.ContainsKey (key)) {
Map.Put (key, anotherValue);
}

如果线程 A 和 B 的执行顺序是这样：

1. 线程 A 判断 map 中不存在 key
2. 线程 B 判断 map 中不存在 key
3. 线程 B 将 (key, anotherValue) 插入 map
4. 线程 A 将 (key, value) 插入 map

那么最终的结果是 (key, value)，而不是预期的 (key, anotherValue)。这就是复合操作的非原子性导致的问题。

那如何保证 ConcurrentHashMap 复合操作的原子性呢？

ConcurrentHashMap 提供了一些原子性的复合操作，如 putIfAbsent、compute、computeIfAbsent 、computeIfPresent、merge 等。这些方法都可以接受一个函数作为参数，根据给定的 key 和 value 来计算一个新的 value，并且将其更新到 map 中。

上面的代码可以改写为：

// 线程 A
Map.PutIfAbsent (key, value);
// 线程 B
Map.PutIfAbsent (key, anotherValue);

或者：

// 线程 A
Map.ComputeIfAbsent (key, k -> value);
// 线程 B
Map.ComputeIfAbsent (key, k -> anotherValue);

很多同学可能会说了，这种情况也能加锁同步呀！确实可以，但不建议使用加锁的同步机制，违背了使用 ConcurrentHashMap 的初衷。在使用 ConcurrentHashMap 的时候，尽量使用这些原子性的复合操作方法来保证原子性。

Collections 工具类（不重要）

Collections 工具类常用方法:

• 排序
• 查找, 替换操作
• 同步控制 (不推荐，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)

排序操作

Void reverse (List list)//反转
Void shuffle (List list)//随机排序
Void sort (List list)//按自然排序的升序排序
Void sort (List list, Comparator c)//定制排序，由 Comparator 控制排序逻辑
Void swap (List list, int i , int j)//交换两个索引位置的元素
Void rotate (List list, int distance)//旋转。当 distance 为正数时，将 list 后 distance 个元素整体移到前面。当 distance 为负数时，将 list 的前 distance 个元素整体移到后面

查找, 替换操作

Int binarySearch (List list, Object key)//对 List 进行二分查找，返回索引，注意 List 必须是有序的
Int max (Collection coll)//根据元素的自然顺序，返回最大的元素。类比 int min (Collection coll)
Int max (Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由 Comparatator 类控制。类比 int min (Collection coll, Comparator c)
Void fill (List list, Object obj)//用指定的元素代替指定 list 中的所有元素
Int frequency (Collection c, Object o)//统计元素出现次数
Int indexOfSubList (List list, List target)//统计 target 在 list 中第一次出现的索引，找不到则返回-1，类比 int lastIndexOfSubList (List source, list target)
Boolean replaceAll (List list, Object oldVal, Object newVal)//用新元素替换旧元素

同步控制

Collections 提供了多个 synchronizedXxx () 方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。

我们知道 HashSet，TreeSet，ArrayList, LinkedList, HashMap, TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。

最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。

方法如下：

synchronizedCollection (Collection<T>  c) //返回指定 collection 支持的同步（线程安全的）collection。
synchronizedList (List<T> list)//返回指定列表支持的同步（线程安全的）List。
synchronizedMap (Map<K,V> m) //返回由指定映射支持的同步（线程安全的）Map。
synchronizedSet (Set<T> s) //返回指定 set 支持的同步（线程安全的）set。

注意事项

集合判空

《阿里巴巴 Java 开发手册》的描述如下：

判断所有集合内部的元素是否为空，使用 isEmpty () 方法，而不是 size ()==0 的方式。

这是因为 isEmpty () 方法的可读性更好，并且时间复杂度为 O (1)。

绝大部分我们使用的集合的 size () 方法的时间复杂度也是 O (1)，不过，也有很多复杂度不是 O (1) 的，比如 java. Util. Concurrent 包下的某些集合（ConcurrentLinkedQueue、ConcurrentHashMap…）。

下面是 ConcurrentHashMap 的 size () 方法和 isEmpty () 方法的源码。

Public int size () {
    Long n = sumCount ();
    Return ((n < 0 L) ? 0 :
            (n > (long) Integer. MAX_VALUE) ? Integer. MAX_VALUE :
            (int) n);
}
Final long sumCount () {
    CounterCell[] as = counterCells; CounterCell a;
    Long sum = baseCount;
    If (as != null) {
        For (int i = 0; i < as. Length; ++i) {
            If ((a = as[i]) != null)
                sum += a.value;
        }
    }
    Return sum;
}
Public boolean isEmpty () {
    Return sumCount () <= 0 L; // ignore transient negative values
}

集合转 Map

《阿里巴巴 Java 开发手册》的描述如下：

在使用 java. Util. Stream. Collectors 类的 toMap () 方法转为 Map 集合时，一定要注意当 value 为 null 时会抛 NPE 异常。

Class Person {
    Private String name;
    Private String phoneNumber;
     // getters and setters
}

List<Person> bookList = new ArrayList<>();
BookList.Add (new Person ("jack","18163138123"));
BookList.Add (new Person ("martin", null));
// 空指针异常
BookList.Stream (). Collect (Collectors.ToMap (Person:: getName, Person::getPhoneNumber));

下面我们来解释一下原因。

首先，我们来看 java. Util. Stream. Collectors 类的 toMap () 方法，可以看到其内部调用了 Map 接口的 merge () 方法。

public static <T, K, U, M extends Map<K, U>>
Collector<T, ?, M> toMap (Function<? super T, ? extends K> keyMapper,
                            Function<? super T, ? extends U> valueMapper,
                            BinaryOperator<U> mergeFunction,
                            Supplier<M> mapSupplier) {
    BiConsumer<M, T> accumulator
            = (map, element) -> map.Merge (keyMapper.Apply (element),
                                          ValueMapper.Apply (element), mergeFunction);
    return new CollectorImpl<>(mapSupplier, accumulator, mapMerger (mergeFunction), CH_ID);
}

Map 接口的 merge () 方法如下，这个方法是接口中的默认实现。

如果你还不了解 Java 8 新特性的话，请看这篇文章：《Java8 新特性总结》 。

Default V merge (K key, V value,
        BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
    Objects.RequireNonNull (remappingFunction);
    Objects.RequireNonNull (value);
    V oldValue = get (key);
    V newValue = (oldValue == null) ? Value :
               RemappingFunction.Apply (oldValue, value);
    If (newValue == null) {
        Remove (key);
    } else {
        Put (key, newValue);
    }
    Return newValue;
}

merge () 方法会先调用 Objects.RequireNonNull () 方法判断 value 是否为空。

public static <T> T requireNonNull (T obj) {
    If (obj == null)
        Throw new NullPointerException ();
    Return obj;
}

集合遍历

《阿里巴巴 Java 开发手册》的描述如下：

不要在 foreach 循环里进行元素的 remove/add 操作。Remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。

通过反编译你会发现 foreach 语法底层其实还是依赖 Iterator 。不过， remove/add 操作直接调用的是集合自己的方法，而不是 Iterator 的 remove/add 方法

这就导致 Iterator 莫名其妙地发现自己有元素被 remove/add ，然后，它就会抛出一个 ConcurrentModificationException 来提示用户发生了并发修改异常。这就是单线程状态下产生的 fail-fast 机制。

fail-fast 机制：多个线程对 fail-fast 集合进行修改的时候，可能会抛出 ConcurrentModificationException。即使是单线程下也有可能会出现这种情况，上面已经提到过。

相关阅读：什么是 fail-fast 。

Java 8 开始，可以使用 Collection #removeIf () 方法删除满足特定条件的元素, 如

List<Integer> list = new ArrayList<>();
For (int i = 1; i <= 10; ++i) {
    List.Add (i);
}
List.RemoveIf (filter -> filter % 2 == 0); /* 删除 list 中的所有偶数 */
System.Out.Println (list); /* [1, 3, 5, 7, 9] */

除了上面介绍的直接使用 Iterator 进行遍历操作之外，你还可以：

• 使用普通的 for 循环
• 使用 fail-safe 的集合类。java. Util 包下面的所有的集合类都是 fail-fast 的，而 java. Util. Concurrent 包下面的所有的类都是 fail-safe 的。
• ……

集合去重

《阿里巴巴 Java 开发手册》的描述如下：

可以利用 Set 元素唯一的特性，可以快速对一个集合进行去重操作，避免使用 List 的 contains () 进行遍历去重或者判断包含操作。

这里我们以 HashSet 和 ArrayList 为例说明。

// Set 去重代码示例
public static <T> Set<T> removeDuplicateBySet (List<T> data) {

    If (CollectionUtils.IsEmpty (data)) {
        return new HashSet<>();
    }
    return new HashSet<>(data);
}

// List 去重代码示例
public static <T> List<T> removeDuplicateByList (List<T> data) {

    If (CollectionUtils.IsEmpty (data)) {
        return new ArrayList<>();

    }
    List<T> result = new ArrayList<>(data.Size ());
    For (T current : data) {
        If (! Result.Contains (current)) {
            Result.Add (current);
        }
    }
    Return result;
}

两者的核心差别在于 contains () 方法的实现。

HashSet 的 contains () 方法底部依赖的 HashMap 的 containsKey () 方法，时间复杂度接近于 O（1）（没有出现哈希冲突的时候为 O（1））。

private transient HashMap<E,Object> map;
Public boolean contains (Object o) {
    Return map.ContainsKey (o);
}

我们有 N 个元素插入进 Set 中，那时间复杂度就接近是 O (n)。

ArrayList 的 contains () 方法是通过遍历所有元素的方法来做的，时间复杂度接近是 O (n)。

Public boolean contains (Object o) {
    Return indexOf (o) >= 0;
}
Public int indexOf (Object o) {
    If (o == null) {
        For (int i = 0; i < size; i++)
            If (elementData[i]==null)
                Return i;
    } else {
        For (int i = 0; i < size; i++)
            if (o.equals (elementData[i]))
                Return i;
    }
    Return -1;
}

集合转数组

《阿里巴巴 Java 开发手册》的描述如下：

使用集合转数组的方法，必须使用集合的 toArray (T[] array)，传入的是类型完全一致、长度为 0 的空数组。

toArray (T[] array) 方法的参数是一个泛型数组，如果 toArray 方法中没有传递任何参数的话返回的是 Object 类型数组。

String [] s= new String[]{
    "dog", "lazy", "a", "over", "jumps", "fox", "brown", "quick", "A"
};
List<String> list = Arrays.AsList (s);
Collections.Reverse (list);
//没有指定类型的话会报错
S=list.ToArray (new String[0]);

由于 JVM 优化，new String[0] 作为 Collection.ToArray () 方法的参数现在使用更好，new String[0] 就是起一个模板的作用，指定了返回数组的类型，0 是为了节省空间，因为它只是为了说明返回的类型。详见：https://shipilev.net/blog/2016/arrays-wisdom-ancients/

数组转集合

《阿里巴巴 Java 开发手册》的描述如下：

使用工具类 Arrays.AsList () 把数组转换成集合时，不能使用其修改集合相关的方法，它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。

我在之前的一个项目中就遇到一个类似的坑。

Arrays.AsList () 在平时开发中还是比较常见的，我们可以使用它将一个数组转换为一个 List 集合。

String[] myArray = {"Apple", "Banana", "Orange"};
List<String> myList = Arrays.AsList (myArray);
//上面两个语句等价于下面一条语句
List<String> myList = Arrays.AsList ("Apple","Banana", "Orange");

JDK 源码对于这个方法的说明：

/**
  *返回由指定数组支持的固定大小的列表。此方法作为基于数组和基于集合的 API 之间的桥梁，
  * 与 Collection.ToArray ()结合使用。返回的 List 是可序列化并实现 RandomAccess 接口。
  */
public static <T> List<T> asList (T... A) {
    return new ArrayList<>(a);
}

下面我们来总结一下使用注意事项。

1、Arrays.AsList () 是泛型方法，传递的数组必须是对象数组，而不是基本类型。

Int[] myArray = {1, 2, 3};
List myList = Arrays.AsList (myArray);
System.Out.Println (myList.Size ());//1
System.Out.Println (myList.Get (0));//数组地址值
System.Out.Println (myList.Get (1));//报错：ArrayIndexOutOfBoundsException
Int[] array = (int[]) myList.Get (0);
System.Out.Println (array[0]);//1

当传入一个原生数据类型数组时，Arrays.AsList () 的真正得到的参数就不是数组中的元素，而是数组对象本身！此时 List 的唯一元素就是这个数组，这也就解释了上面的代码。

我们使用包装类型数组就可以解决这个问题。

Integer[] myArray = {1, 2, 3};

2、使用集合的修改方法: add ()、remove ()、clear () 会抛出异常。

List myList = Arrays.AsList (1, 2, 3);
MyList.Add (4);//运行时报错：UnsupportedOperationException
MyList.Remove (1);//运行时报错：UnsupportedOperationException
MyList.Clear ();//运行时报错：UnsupportedOperationException

Arrays.AsList () 方法返回的并不是 java. Util. ArrayList ，而是 java. Util. Arrays 的一个内部类, 这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。

List myList = Arrays.AsList (1, 2, 3);
System.Out.Println (myList.GetClass ());//class java. Util. Arrays$ArrayList

下图是 java. Util. Arrays$ArrayList 的简易源码，我们可以看到这个类重写的方法有哪些。

private static class ArrayList<E> extends AbstractList<E>
      Implements RandomAccess, java. Io. Serializable
  {
      ...

      @Override
      Public E get (int index) {
        ...
      }

      @Override
      Public E set (int index, E element) {
        ...
      }

      @Override
      Public int indexOf (Object o) {
        ...
      }

      @Override
      Public boolean contains (Object o) {
         ...
      }

      @Override
      public void forEach (Consumer<? super E> action) {
        ...
      }

      @Override
      public void replaceAll (UnaryOperator<E> operator) {
        ...
      }

      @Override
      public void sort (Comparator<? super E> c) {
        ...
      }
  }

我们再看一下 java. Util. AbstractList 的 add/remove/clear 方法就知道为什么会抛出 UnsupportedOperationException 了。

Public E remove (int index) {
    Throw new UnsupportedOperationException ();
}
Public boolean add (E e) {
    Add (size (), e);
    Return true;
}
Public void add (int index, E element) {
    Throw new UnsupportedOperationException ();
}

Public void clear () {
    RemoveRange (0, size ());
}
Protected void removeRange (int fromIndex, int toIndex) {
    ListIterator<E> it = listIterator (fromIndex);
    For (int i=0, n=toIndex-fromIndex; i<n; i++) {
        It.Next ();
        It.Remove ();
    }
}

那我们如何正确的将数组转换为 ArrayList ?

1、手动实现工具类

//JDK 1.5+
static <T> List<T> arrayToList (final T[] array) {
  final List<T> l = new ArrayList<T>(array. Length);

  For (final T s : array) {
    l.add (s);
  }
  Return l;
}


Integer [] myArray = { 1, 2, 3 };
System.Out.Println (arrayToList (myArray). GetClass ());//class java. Util. ArrayList

2、最简便的方法

List list = new ArrayList<>(Arrays.AsList ("a", "b", "c"))

3、使用 Java 8 的 Stream (推荐)

Integer [] myArray = { 1, 2, 3 };
List myList = Arrays.Stream (myArray). Collect (Collectors.ToList ());
//基本类型也可以实现转换（依赖 boxed 的装箱操作）
Int [] myArray 2 = { 1, 2, 3 };
List myList = Arrays.Stream (myArray 2). Boxed (). Collect (Collectors.ToList ());

4、使用 Guava

对于不可变集合，你可以使用 ImmutableList 类及其 of() 与 copyOf() 工厂方法：（参数不能为空）

List<String> il = ImmutableList.Of ("string", "elements");  // from varargs
List<String> il = ImmutableList.CopyOf (aStringArray);      // from array

对于可变集合，你可以使用 Lists 类及其 newArrayList() 工厂方法：

List<String> l 1 = Lists.NewArrayList (anotherListOrCollection);    // from collection
List<String> l 2 = Lists.NewArrayList (aStringArray);               // from array
List<String> l 3 = Lists.NewArrayList ("or", "string", "elements"); // from varargs

5、使用 Apache Commons Collections

List<String> list = new ArrayList<String>();
CollectionUtils.AddAll (list, str);

6、使用 Java 9 的 List.Of () 方法

Integer[] array = {1, 2, 3};
List<Integer> list = List.Of (array);