--- title: Java集合常见面试题总结 description: 系统梳理Java集合框架常见知识点与高频面试题，覆盖List、Set、Queue、Map及其典型实现如ArrayList、LinkedList、HashSet、HashMap、ConcurrentHashMap、BlockingQueue等，并结合源码讲解扩容机制、时间复杂度、线程安全与fail-fast/fail-safe等关键细节。 category: Java tag: - Java集合 head: - - meta - name: keywords content: Java集合面试题,Collection,List,ArrayList,LinkedList,Set,HashSet,TreeSet,Queue,Deque,ArrayDeque,PriorityQueue,BlockingQueue,HashMap,TreeMap,ConcurrentHashMap,Hashtable,fail-fast,fail-safe,扩容机制 --- 这部分内容摘自 [JavaGuide](https://javaguide.cn/) 下面几篇文章中的重点： - [Java 集合常见面试题总结（上）](https://javaguide.cn/java/collection/java-collection-questions-01.html)（Java 集合基础、`ArrayList`、`LinkedList`、`HashSet`、`ArrayDeque`、`PriorityQueue`、`BlockingQueue` 等） - [Java 集合常见面试题总结（下）](https://javaguide.cn/java/collection/java-collection-questions-02.html)（ `HashMap`、`ConcurrentHashMap` 等） ## 基础概念 ### 简单介绍一下 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 是无序的、可重复的，每个键最多映射到一个值。 ## List ### ⭐️ArrayList 和 Array（数组）的区别？ `ArrayList` 内部基于动态数组实现，比 `Array`（静态数组） 使用起来更加灵活： - `ArrayList`会根据实际存储的元素动态地扩容或缩容，而 `Array` 被创建之后就不能改变它的长度了。 - `ArrayList` 允许你使用泛型来确保类型安全，`Array` 则不可以。 - `ArrayList` 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。`Array` 可以直接存储基本类型数据，也可以存储对象。 - `ArrayList` 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如 `add()`、`remove()`等。`Array` 只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。 - `ArrayList`创建时不需要指定大小，而`Array`创建时必须指定大小。 下面是二者使用的简单对比： `Array`： ```java // 初始化一个 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` ： ```java // 初始化一个 String 类型的 ArrayList ArrayList 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 可以添加 null 值吗？ `ArrayList` 中可以存储任何类型的对象，包括 `null` 值。不过，不建议向`ArrayList` 中添加 `null` 值， `null` 值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。 示例代码： ```java ArrayList listOfStrings = new ArrayList<>(); listOfStrings.add(null); listOfStrings.add("java"); System.out.println(listOfStrings); ``` 输出： ``` [null, java] ``` ### ⭐️ArrayList 插入和删除元素的时间复杂度？ 对于插入： - 头部插入：由于需要将所有元素都依次向后移动一个位置，因此时间复杂度是 O(n)。 - 尾部插入：当 `ArrayList` 的容量未达到极限时，往列表末尾插入元素的时间复杂度是 O(1)，因为它只需要在数组末尾添加一个元素即可；当容量已达到极限并且需要扩容时，则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中，然后再执行 O(1) 的操作添加元素。 - 指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素，因此时间复杂度为 O(n)。 对于删除： - 头部删除：由于需要将所有元素依次向前移动一个位置，因此时间复杂度是 O(n)。 - 尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O(1)。 - 指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。 这里简单列举一个例子： ``` // ArrayList的底层数组大小为10，此时存储了7个元素 +---+---+---+---+---+---+---+---+---+---+ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | | | +---+---+---+---+---+---+---+---+---+---+ 0 1 2 3 4 5 6 7 8 9 // 在索引为1的位置插入一个元素8，该元素后面的所有元素都要向右移动一位 +---+---+---+---+---+---+---+---+---+---+ | 1 | 8 | 2 | 3 | 4 | 5 | 6 | 7 | | | +---+---+---+---+---+---+---+---+---+---+ 0 1 2 3 4 5 6 7 8 9 // 删除索引为1的位置的元素，该元素后面的所有元素都要向左移动一位 +---+---+---+---+---+---+---+---+---+---+ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | | | +---+---+---+---+---+---+---+---+---+---+ 0 1 2 3 4 5 6 7 8 9 ``` ### ⭐️LinkedList 插入和删除元素的时间复杂度？ - 头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。 - 尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。 - 指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，不过由于有头尾指针，可以从较近的指针出发，因此需要遍历平均 n/4 个元素，时间复杂度为 O(n)。 这里简单列举一个例子：假如我们要删除节点 9 的话，需要先遍历链表找到该节点。然后，再执行相应节点指针指向的更改，具体的源码可以参考：[LinkedList 源码分析](https://javaguide.cn/java/collection/linkedlist-source-code.html) 。  ### LinkedList 为什么不能实现 RandomAccess 接口？ `RandomAccess` 是一个标记接口，用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）。由于 `LinkedList` 底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现 `RandomAccess` 接口。 ### ArrayList 与 LinkedList 区别? - **是否保证线程安全：** `ArrayList` 和 `LinkedList` 都是不同步的，也就是不保证线程安全； - **底层数据结构：** `ArrayList` 底层使用的是 **`Object` 数组**；`LinkedList` 底层使用的是 **双向链表** 数据结构（JDK1.6 之前为循环链表，JDK1.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 接口 ```java public interface RandomAccess { } ``` 查看源码我们发现实际上 `RandomAccess` 接口中什么都没有定义。所以，在我看来 `RandomAccess` 接口不过是一个标识罢了。标识什么？ 标识实现这个接口的类具有随机访问功能。 在 `binarySearch()` 方法中，它要判断传入的 list 是否 `RandomAccess` 的实例，如果是，调用`indexedBinarySearch()`方法，如果不是，那么调用`iteratorBinarySearch()`方法 ```java public static int binarySearch(List extends Comparable super T>> list, T key) { if (list instanceof RandomAccess || list.size() Fail-fast systems are designed to immediately stop functioning upon encountering an unexpected condition. This immediate failure helps to catch errors early, making debugging more straightforward. 快速失败的思想即针对可能发生的异常进行提前表明故障并停止运行，通过尽早的发现和停止错误，降低故障系统级联的风险。 在`java.util`包下的大部分集合是不支持线程安全的，为了能够提前发现并发操作导致线程安全风险，提出通过维护一个`modCount`记录修改的次数，迭代期间通过比对预期修改次数`expectedModCount`和`modCount`是否一致来判断是否存在并发操作，从而实现快速失败，由此保证在避免在异常时执行非必要的复杂代码。 对应的我们给出下面这样一段在示例，我们首先插入`100`个操作元素，一个线程迭代元素，一个线程删除元素，最终输出结果如愿抛出`ConcurrentModificationException`： ```java // 使用线程安全的 CopyOnWriteArrayList 避免 ConcurrentModificationException List list = new CopyOnWriteArrayList<>(); CountDownLatch countDownLatch = new CountDownLatch(2); // 添加元素 for (int i = 0; i < 100; i++) { list.add(i); } Thread t1 = new Thread(() -> { // 迭代元素 (注意：Integer 是不可变的，这里的 i++ 不会修改 list 中的值) for (Integer i : list) { i++; // 这行代码实际上没有修改list中的元素 } countDownLatch.countDown(); }); Thread t2 = new Thread(() -> { System.out.println("删除元素1"); list.remove(Integer.valueOf(1)); // 使用 Integer.valueOf(1) 删除指定值的对象 countDownLatch.countDown(); }); t1.start(); t2.start(); countDownLatch.await(); ``` 我们在初始化时插入了`100`个元素，此时对应的修改`modCount`次数为`100`，随后线程 2 在线程 1 迭代期间进行元素删除操作，此时对应的`modCount`就变为`101`。 线程 1 在随后`foreach`第 2 轮循环发现`modCount` 为`101`，与预期的`expectedModCount(值为100因为初始化插入了元素100个)`不等，判定为并发操作异常，于是便快速失败，抛出`ConcurrentModificationException`：  对此我们也给出`for`循环底层迭代器获取下一个元素时的`next`方法，可以看到其内部的`checkForComodification`具有针对修改次数比对的逻辑： ```java public E next() { //检查是否存在并发修改 checkForComodification(); //...... //返回下一个元素 return (E) elementData[lastRet = i]; } final void checkForComodification() { //当前循环遍历次数和预期修改次数不一致时，就会抛出ConcurrentModificationException if (modCount != expectedModCount) throw new ConcurrentModificationException(); } ``` 而`fail-safe`也就是安全失败的含义，它旨在即使面对意外情况也能恢复并继续运行，这使得它特别适用于不确定或者不稳定的环境： > Fail-safe systems take a different approach, aiming to recover and continue even in the face of unexpected conditions. This makes them particularly suited for uncertain or volatile environments. 该思想常运用于并发容器，最经典的实现就是`CopyOnWriteArrayList`的实现，通过写时复制的思想保证在进行修改操作时复制出一份快照，基于这份快照完成添加或者删除操作后，将`CopyOnWriteArrayList`底层的数组引用指向这个新的数组空间，由此避免迭代时被并发修改所干扰所导致并发操作安全问题，当然这种做法也存在缺点，即进行遍历操作时无法获得实时结果：  对应我们也给出`CopyOnWriteArrayList`实现`fail-safe`的核心代码，可以看到它的实现就是通过`getArray`获取数组引用然后通过`Arrays.copyOf`得到一个数组的快照，基于这个快照完成添加操作后，修改底层`array`变量指向的引用地址由此完成写时复制： ```java public boolean add(E e) { final ReentrantLock lock = this.lock; lock.lock(); try { //获取原有数组 Object[] elements = getArray(); int len = elements.length; //基于原有数组复制出一份内存快照 Object[] newElements = Arrays.copyOf(elements, len + 1); //进行添加操作 newElements[len] = e; //array指向新的数组 setArray(newElements); return true; } finally { lock.unlock(); } } ``` ## 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 定制排序 ```java ArrayList arrayList = new ArrayList(); 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() { @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 方法实现按年龄来排序 ```java // person对象没有实现Comparable接口，所以必须实现，这样才不会出错，才可以使treemap中的数据按顺序排列 // 前面一个例子的String类已经默认实现了Comparable接口，详细可以查看String类的API文档，另外其他 // 像Integer类等都已经实现了Comparable接口，所以不需要另外实现了 public class Person implements Comparable { 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 pdata = new TreeMap(); 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 keys = pdata.keySet(); for (Person key : keys) { System.out.println(key.getAge() + "-" + key.getName()); } } ``` Output： ``` 5-小红 10-王五 20-李四 30-张三 ``` ### 比较 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` 是在 JDK1.6 才被引入的，而`LinkedList` 早在 JDK1.2 时就已经存在。 - `ArrayDeque` 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 `LinkedList` 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。 从性能的角度上，选用 `ArrayDeque` 来实现队列要比 `LinkedList` 更好。此外，`ArrayDeque` 也可以用于实现栈。 ### 说一说 PriorityQueue `PriorityQueue` 是在 JDK1.5 中被引入的, 其与 `Queue` 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。 这里列举其相关的一些要点： - `PriorityQueue` 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据 - `PriorityQueue` 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。 - `PriorityQueue` 是非线程安全的，且不支持存储 `NULL` 和 `non-comparable` 的对象。 - `PriorityQueue` 默认是小顶堆，但可以接收一个 `Comparator` 作为构造参数，从而来自定义元素优先级的先后。 `PriorityQueue` 在面试中可能更多的会出现在手撕算法的时候，典型例题包括堆排序、求第 K 大的数、带权图的遍历等，所以需要会熟练使用才行。 ### 什么是 BlockingQueue？ `BlockingQueue` （阻塞队列）是一个接口，继承自 `Queue`。`BlockingQueue`阻塞的原因是其支持当队列没有元素时一直阻塞，直到有元素；还支持如果队列已满，一直等到队列可以放入新元素时再放入。 ```java public interface BlockingQueue extends Queue { // ... } ``` `BlockingQueue` 常用于生产者-消费者模型中，生产者线程会向队列中添加数据，而消费者线程会从队列中取出数据进行处理。  ### BlockingQueue 的实现类有哪些？  Java 中常用的阻塞队列实现类有以下几种： 1. `ArrayBlockingQueue`：使用数组实现的有界阻塞队列。在创建时需要指定容量大小，并支持公平和非公平两种方式的锁访问机制。 2. `LinkedBlockingQueue`：使用单向链表实现的可选有界阻塞队列。在创建时可以指定容量大小，如果不指定则默认为`Integer.MAX_VALUE`。和`ArrayBlockingQueue`不同的是， 它仅支持非公平的锁访问机制。 3. `PriorityBlockingQueue`：支持优先级排序的无界阻塞队列。元素必须实现`Comparable`接口或者在构造函数中传入`Comparator`对象，并且不能插入 null 元素。 4. `SynchronousQueue`：同步队列，是一种不存储元素的阻塞队列。每个插入操作都必须等待对应的删除操作，反之删除操作也必须等待插入操作。因此，`SynchronousQueue`通常用于线程之间的直接传递数据。 5. `DelayQueue`：延迟队列，其中的元素只有到了其指定的延迟时间，才能够从队列中出队。 6. …… 日常开发中，这些队列使用的其实都不多，了解即可。 ### ⭐️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，之后每次扩充，容量变为原来的 2n+1。`HashMap` 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 `Hashtable` 会直接使用你给定的大小，而 `HashMap` 会将其扩充为 2 的幂次方大小（`HashMap` 中的`tableSizeFor()`方法保证，下面给出了源代码）。也就是说 `HashMap` 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。 - **底层数据结构：** JDK1.8 以后的 `HashMap` 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间（后文中我会结合源码对这一过程进行分析）。`Hashtable` 没有这样的机制。 - **哈希函数的实现**：`HashMap` 对哈希值进行了高位和低位的混合扰动处理以减少冲突，而 `Hashtable` 直接使用键的 `hashCode()` 值。 **`HashMap` 中带有初始容量的构造函数：** ```java public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } ``` 下面这个方法保证了 `HashMap` 总是使用 2 的幂作为哈希表的大小。 ```java /** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } ``` ### 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` 有了对集合内元素的搜索的能力。 `NavigableMap` 接口提供了丰富的方法来探索和操作键值对: 1. **定向搜索**: `ceilingEntry()`, `floorEntry()`, `higherEntry()`和 `lowerEntry()` 等方法可以用于定位大于等于、小于等于、严格大于、严格小于给定键的最接近的键值对。 2. **子集操作**: `subMap()`, `headMap()`和 `tailMap()` 方法可以高效地创建原集合的子集视图，而无需复制整个集合。 3. **逆序视图**:`descendingMap()` 方法返回一个逆序的 `NavigableMap` 视图，使得可以反向迭代整个 `TreeMap`。 4. **边界操作**: `firstEntry()`, `lastEntry()`, `pollFirstEntry()`和 `pollLastEntry()` 等方法可以方便地访问和移除元素。 这些方法都是基于红黑树数据结构的属性实现的，红黑树保持平衡状态，从而保证了搜索操作的时间复杂度为 O(log n)，这让 `TreeMap` 成为了处理有序集合搜索问题的强大工具。 实现`SortedMap`接口让 `TreeMap` 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。示例代码如下： ```java /** * @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 treeMap = new TreeMap<>(new Comparator() { @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()); }); } } ``` 输出: ```plain person1 person4 person2 person3 ``` 可以看出，`TreeMap` 中的元素已经是按照 `Person` 的 age 字段的升序来排列了。 上面，我们是通过传入匿名内部类的方式实现的，你可以将代码替换成 Lambda 表达式实现的方式： ```java TreeMap treeMap = new TreeMap<>((person1, person2) -> { int num = person1.getAge() - person2.getAge(); return Integer.compare(num, 0); }); ``` **综上，相比于`HashMap`来说， `TreeMap` 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。** ### HashSet 如何检查重复? 以下内容摘自我的 Java 启蒙书《Head first java》第二版： > 当你把对象加入`HashSet`时，`HashSet` 会先计算对象的`hashcode`值来判断对象加入的位置，同时也会与其他加入的对象的 `hashcode` 值作比较，如果没有相符的 `hashcode`，`HashSet` 会假设对象没有重复出现。但是如果发现有相同 `hashcode` 值的对象，这时会调用`equals()`方法来检查 `hashcode` 相等的对象是否真的相同。如果两者相同，`HashSet` 就不会让加入操作成功。 在 JDK1.8 中，`HashSet`的`add()`方法只是简单的调用了`HashMap`的`put()`方法，并且判断了一下返回值以确保是否有重复元素。直接看一下`HashSet`中的源码： ```java // 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()`方法中也能看到如下说明： ```java // Returns : previous value, or null if none // 返回值：如果插入位置没有元素返回null，否则返回上一个元素 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { ... } ``` 也就是说，在 JDK1.8 中，实际上无论`HashSet`中是否已经存在了某元素，`HashSet`都会直接插入，只是会在`add()`方法的返回值处告诉我们插入前是否存在相同元素。 ### ⭐️HashMap 的底层实现 #### JDK1.8 之前 JDK1.8 之前 `HashMap` 底层是 **数组和链表** 结合在一起使用也就是 **链表散列**。HashMap 通过 key 的 `hashcode` 经过扰动函数处理过后得到 hash 值，然后通过 `(n - 1) & hash` 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。 `HashMap` 中的扰动函数（`hash` 方法）是用来优化哈希值的分布。通过对原始的 `hashCode()` 进行额外处理，扰动函数可以减小由于糟糕的 `hashCode()` 实现导致的碰撞，从而提高数据的分布均匀性。 **JDK 1.8 HashMap 的 hash 方法源码:** JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。 ```java static final int hash(Object key) { int h; // key.hashCode()：返回散列值也就是hashcode // ^：按位异或 // >>>:无符号右移，忽略符号位，空位都以0补齐 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` 对比一下 JDK1.7 的 HashMap 的 hash 方法源码. ```java 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); } ``` 相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。 所谓 **“拉链法”** 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。  #### JDK1.8 之后 相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树。 这样做的目的是减少搜索时间：链表的查询效率为 O(n)（n 是链表的长度），红黑树是一种自平衡二叉搜索树，其查询效率为 O(log n)。当链表较短时，O(n) 和 O(log n) 的性能差异不明显。但当链表变长时，查询性能会显著下降。  **为什么优先扩容而非直接转为红黑树？** 数组扩容能减少哈希冲突的发生概率（即将元素重新分散到新的、更大的数组中），这在多数情况下比直接转换为红黑树更高效。 红黑树需要保持自平衡，维护成本较高。并且，过早引入红黑树反而会增加复杂度。 **为什么选择阈值 8 和 64？** 1. 泊松分布表明，链表长度达到 8 的概率极低（小于千万分之一）。在绝大多数情况下，链表长度都不会超过 8。阈值设置为 8，可以保证性能和空间效率的平衡。 2. 数组长度阈值 64 同样是经过实践验证的经验值。在小数组中扩容成本低，优先扩容可以避免过早引入红黑树。数组大小达到 64 时，冲突概率较高，此时红黑树的性能优势开始显现。 > TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。 我们来结合源码分析一下 `HashMap` 链表到红黑树的转换。 **1、 `putVal` 方法中执行链表转红黑树的判断逻辑。** 链表的长度大于 8 的时候，就执行 `treeifyBin` （转换红黑树）的逻辑。 ```java // 遍历链表 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` 方法中判断是否真的转换为红黑树。** ```java final void treeifyBin(Node[] tab, int hash) { int n, index; Node e; // 判断当前数组的长度是否小于 64 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // 如果当前数组的长度小于 64，那么会选择先进行数组扩容 resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { // 否则才将列表转换为红黑树 TreeNode hd = null, tl = null; do { TreeNode 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` 存取高效并减少碰撞，我们需要确保数据尽量均匀分布。哈希值在 Java 中通常使用 `int` 表示，其范围是 `-2147483648 ~ 2147483647`前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但是，问题是一个 40 亿长度的数组，内存是放不下的。所以，这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。 **这个算法应该如何设计呢？** 我们首先可能会想到采用 % 取余的操作来实现。但是，重点来了：“**取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作**（也就是说 `hash%length==hash&(length-1)` 的前提是 length 是 2 的 n 次方）。” 并且，**采用二进制位操作 & 相对于 % 能够提高运算效率**。 除了上面所说的位运算比取余效率高之外，我觉得更重要的一个原因是：**长度是 2 的幂次方，可以让 `HashMap` 在扩容的时候更均匀**。例如: - length = 8 时，length - 1 = 7 的二进制位`0111` - length = 16 时，length - 1 = 15 的二进制位`1111` 这时候原本存在 `HashMap` 中的元素计算新的数组位置时 `hash&(length-1)`，取决 hash 的第四个二进制位（从右数），会出现两种情况： 1. 第四个二进制位为 0，数组位置不变，也就是说当前元素在新数组和旧数组的位置相同。 2. 第四个二进制位为 1，数组位置在新数组扩容之后的那一部分。 这里列举一个例子： ```plain 假设有一个元素的哈希值为 10101100 旧数组元素位置计算： hash = 10101100 length - 1 = 00000111 & ----------------- index = 00000100 (4) 新数组元素位置计算： hash = 10101100 length - 1 = 00001111 & ----------------- index = 00001100 (12) 看第四位（从右数）： 1.高位为 0：位置不变。 2.高位为 1：移动到新位置（原索引位置+原容量）。 ``` ⚠️注意：这里列举的场景看的是第四个二进制位，更准确点来说看的是高位（从右数），例如 `length = 32` 时，`length - 1 = 31`，二进制为 `11111`，这里看的就是第五个二进制位。 也就是说扩容之后，在旧数组元素 hash 值比较均匀（至于 hash 值均不均匀，取决于前面讲的对象的 `hashcode()` 方法和扰动函数）的情况下，新数组元素也会被分配的比较均匀，最好的情况是会有一半在新数组的前半部分，一半在新数组后半部分。 这样也使得扩容机制变得简单和高效，扩容后只需检查哈希值高位的变化来决定元素的新位置，要么位置不变（高位为 0），要么就是移动到新位置（高位为 1，原索引位置+原容量）。 最后，简单总结一下 `HashMap` 的长度是 2 的幂次方的原因： 1. 位运算效率更高：位运算(&)比取余运算(%)更高效。当长度为 2 的幂次方时，`hash % length` 等价于 `hash & (length - 1)`。 2. 可以更好地保证哈希值的均匀分布：扩容之后，在旧数组元素 hash 值比较均匀的情况下，新数组元素也会被分配的比较均匀，最好的情况是会有一半在新数组的前半部分，一半在新数组后半部分。 3. 扩容机制变得简单和高效：扩容后只需检查哈希值高位的变化来决定元素的新位置，要么位置不变（高位为 0），要么就是移动到新位置（高位为 1，原索引位置+原容量）。 ### ⭐️HashMap 多线程操作导致死循环问题 JDK1.7 及之前版本的 `HashMap` 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。 为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但是还是不建议在多线程下使用 `HashMap`，因为多线程下使用 `HashMap` 还是会存在数据覆盖的问题。并发环境下，推荐使用 `ConcurrentHashMap` 。 一般面试中这样介绍就差不多，不需要记各种细节，个人觉得也没必要记。如果想要详细了解 `HashMap` 扩容导致死循环问题，可以看看耗子叔的这篇文章：[Java HashMap 的死循环](https://coolshell.cn/articles/9606.html)。 ### ⭐️HashMap 为什么线程不安全？ JDK1.7 及之前版本，在多线程环境下，`HashMap` 扩容时会造成死循环和数据丢失的问题。 数据丢失这个在 JDK1.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 覆盖了。 ```java 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` 中。 ```java 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 常见的遍历方式? [HashMap 的 7 种遍历方式与性能分析！](https://mp.weixin.qq.com/s/zQBN3UvJDhRTKP6SzcZFKw) **🐛 修正（参见：[issue#1411](https://github.com/Snailclimb/JavaGuide/issues/1411)）**： 这篇文章对于 parallelStream 遍历方式的性能分析有误，先说结论：**存在阻塞时 parallelStream 性能最高, 非阻塞时 parallelStream 性能最低** 。 当遍历不存在阻塞时, parallelStream 的性能是最低的： ```plain Benchmark Mode Cnt Score Error Units Test.entrySet avgt 5 288.651 ± 10.536 ns/op Test.keySet avgt 5 584.594 ± 21.431 ns/op Test.lambda avgt 5 221.791 ± 10.198 ns/op Test.parallelStream avgt 5 6919.163 ± 1116.139 ns/op ``` 加入阻塞代码`Thread.sleep(10)`后, parallelStream 的性能才是最高的: ```plain Benchmark Mode Cnt Score Error Units Test.entrySet avgt 5 1554828440.000 ± 23657748.653 ns/op Test.keySet avgt 5 1550612500.000 ± 6474562.858 ns/op Test.lambda avgt 5 1551065180.000 ± 19164407.426 ns/op Test.parallelStream avgt 5 186345456.667 ± 3210435.590 ns/op ``` ### ⭐️ConcurrentHashMap 和 Hashtable 的区别 `ConcurrentHashMap` 和 `Hashtable` 的区别主要体现在实现线程安全的方式上不同。 - **底层数据结构：** JDK1.7 的 `ConcurrentHashMap` 底层采用 **分段的数组+链表** 实现，在 JDK1.8 中采用的数据结构跟 `HashMap` 的结构一样，数组+链表/红黑二叉树。`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，竞争会越来越激烈效率越低。 下面，我们再来看看两者底层数据结构的对比图。 **Hashtable** : 

https://www.cnblogs.com/chengxiao/p/6842045.html>

extends Node { TreeNode root; volatile TreeNode 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 线程安全的具体实现方式/底层具体实现 #### JDK1.8 之前  首先将数据分为一段一段（这个“段”就是 `Segment`）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。 **`ConcurrentHashMap` 是由 `Segment` 数组结构和 `HashEntry` 数组结构组成**。 `Segment` 继承了 `ReentrantLock`,所以 `Segment` 是一种可重入锁，扮演锁的角色。`HashEntry` 用于存储键值对数据。 ```java static class Segment extends ReentrantLock implements Serializable { } ``` 一个 `ConcurrentHashMap` 里包含一个 `Segment` 数组，`Segment` 的个数一旦**初始化就不能改变**。 `Segment` 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。 `Segment` 的结构和 `HashMap` 类似，是一种数组和链表结构，一个 `Segment` 包含一个 `HashEntry` 数组，每个 `HashEntry` 是一个链表结构的元素，每个 `Segment` 守护着一个 `HashEntry` 数组里的元素，当对 `HashEntry` 数组的数据进行修改时，必须首先获得对应的 `Segment` 的锁。也就是说，对同一 `Segment` 的并发写入会被阻塞，不同 `Segment` 的写入是可以并发执行的。 #### JDK1.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`。JDK1.8 放弃了 `Segment` 分段锁的设计，采用 `Node + CAS + synchronized` 保证线程安全，锁粒度更细，`synchronized` 只锁定当前链表或红黑二叉树的首节点。 - **Hash 碰撞解决方法** : JDK 1.7 采用拉链法，JDK1.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 源码分析](https://javaguide.cn/java/collection/concurrent-hash-map-source-code.html) 。 多线程环境下，存在一个线程操作该 `ConcurrentHashMap` 时，其他的线程将该 `ConcurrentHashMap` 修改的情况，所以无法通过 `containsKey(key)` 来判断否存在这个键值对，也就没办法解决二义性问题了。 与此形成对比的是，`HashMap` 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。如果传入 null 作为参数，就会返回 hash 值为 0 的位置的值。单线程环境下，不存在一个线程操作该 HashMap 时，其他的线程将该 `HashMap` 修改的情况，所以可以通过 `contains(key)`来做判断是否存在这个键值对，从而做相应的处理，也就不存在二义性问题。 也就是说，多线程下无法正确判定键值对是否存在（存在其他线程修改的情况），单线程是可以的（不存在其他线程修改的情况）。 如果你确实需要在 ConcurrentHashMap 中使用 null 的话，可以使用一个特殊的静态空对象来代替 null。 ```java public static final Object NULL = new Object(); ``` 最后，再分享一下 `ConcurrentHashMap` 作者本人 (Doug Lea)对于这个问题的回答： > The main reason that nulls aren't allowed in ConcurrentMaps (ConcurrentHashMaps, ConcurrentSkipListMaps) is that ambiguities that may be just barely tolerable in non-concurrent maps can't be accommodated. The main one is that if `map.get(key)` returns `null`, you can't detect whether the key explicitly maps to `null` vs the key isn't mapped. In a non-concurrent map, you can check this via `map.contains(key)`, but in a concurrent one, the map might have changed between calls. 翻译过来之后的，大致意思还是单线程下可以容忍歧义，而多线程下无法容忍。 ### ⭐️ConcurrentHashMap 能保证复合操作的原子性吗？ `ConcurrentHashMap` 是线程安全的，意味着它可以保证多个线程同时对它进行读写操作时，不会出现数据不一致的情况，也不会导致 JDK1.7 及之前版本的 `HashMap` 多线程操作导致死循环问题。但是，这并不意味着它可以保证所有的复合操作都是原子性的，一定不要搞混了！ 复合操作是指由多个基本操作(如`put`、`get`、`remove`、`containsKey`等)组成的操作，例如先判断某个键是否存在`containsKey(key)`，然后根据结果进行插入或更新`put(key, value)`。这种操作在执行过程中可能会被其他线程打断，导致结果不符合预期。 例如，有两个线程 A 和 B 同时对 `ConcurrentHashMap` 进行复合操作，如下： ```java // 线程 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 中。 上面的代码可以改写为： ```java // 线程 A map.putIfAbsent(key, value); // 线程 B map.putIfAbsent(key, anotherValue); ``` 或者： ```java // 线程 A map.computeIfAbsent(key, k -> value); // 线程 B map.computeIfAbsent(key, k -> anotherValue); ``` 很多同学可能会说了，这种情况也能加锁同步呀！确实可以，但不建议使用加锁的同步机制，违背了使用 `ConcurrentHashMap` 的初衷。在使用 `ConcurrentHashMap` 的时候，尽量使用这些原子性的复合操作方法来保证原子性。