Java集合面试被问懵了？这份万字攻略让你从ArrayList到ConcurrentHashMap全拿下！

大家好，我是小林。

Java 集合是面试里几乎必考的一块，而且这块的题目有个特点：入门容易，但深挖起来没有底。

很多人用 ArrayList 和 HashMap 用了好几年，但面试被问到"HashMap 为什么用红黑树而不是平衡二叉树"、"ConcurrentHashMap 在 JDK 1.7 和 1.8 的实现有什么区别"时，就开始说不清楚了。

集合类看起来只是工具，但背后涉及的数据结构、哈希算法、并发机制，才是面试真正在考的东西。

这篇文章整理了 Java 集合框架面试中最常被问到的问题，涵盖 List、Set、Map 三大体系，重点包括 ArrayList 和 LinkedList 的差异、HashMap 的底层实现和扩容机制、ConcurrentHashMap 的线程安全方案，以及 HashSet、TreeMap、LinkedHashMap 这些常用实现类的原理和使用场景。

有几块内容在面试里被问得特别多，建议重点花时间：

• HashMap：put 过程、扩容机制、为什么初始容量是 2 的幂次方、链表转红黑树的条件，这些几乎每次都会问，而且很容易被追问到细节。
• ConcurrentHashMap：JDK 1.7 的分段锁和 JDK 1.8 的 CAS + synchronized 方案的区别，是并发面试里的高频考点。
• ArrayList 的线程安全问题：为什么不安全、具体会出现哪些问题、有哪些替代方案，这个看起来简单但答起来很容易流于表面。
• equals 和 hashCode 的关系：这两个方法为什么要配套重写，放到 HashMap 和 HashSet 里会有什么影响，基础但经常被忽略。

如果你是第一次系统准备这块，建议先搞清楚 ArrayList 和 HashMap 的底层原理，再去看线程安全相关的集合类，这样理解起来会顺很多。

---

一、先搞懂基础概念

数组和集合有什么区别？

这是面试入门题，但很多人答不到点子上。

核心区别有三点：

1. 长度不同：数组是固定长度的，一旦创建就无法改变；集合是动态长度的，可以根据需要动态增加或减少元素。
2. 存储类型不同：数组可以包含基本数据类型和对象，而集合只能包含对象。
3. 访问方式不同：数组可以直接通过索引访问元素，而集合需要通过迭代器或其他方法访问。

我用过的 Java 集合类：

• ArrayList：动态数组，实现了 List 接口，支持动态增长。
• LinkedList：双向链表，也实现了 List 接口，支持快速的插入和删除操作。
• HashMap：基于哈希表的 Map 实现，存储键值对，通过键快速查找值。
• HashSet：基于 HashMap 实现的 Set 集合，用于存储唯一元素。
• TreeMap：基于红黑树实现的有序 Map 集合，可以按照键的顺序进行排序。
• LinkedHashMap：基于哈希表和双向链表实现的 Map 集合，保持插入顺序或访问顺序。
• PriorityQueue：优先队列，可以按照比较器或元素的自然顺序进行排序。

说说 Java 中的集合体系？

Java 集合框架主要分为三大块：

List（有序、可重复）

List 是有序的 Collection，使用此接口能够精确的控制每个元素的插入位置，用户能根据索引访问 List 中元素。

• ArrayList：容量可变的非线程安全列表，底层使用数组实现。当集合扩容时，会创建更大的数组，并把原数组复制到新数组。支持快速随机访问，尾部追加/删除效率高，但中间位置插入/删除需要搬移元素。
• LinkedList：本质是双向链表，支持高效的头尾插入/删除和作为双端队列使用。

💡 注意："LinkedList 插入/删除比 ArrayList 更快"是一个常见误区！其 O(1) 的前提是已经持有目标节点的引用；如果要在任意位置插入/删除，仍需先 O(n) 遍历链表找到位置，加上每个节点都需要独立分配、对 CPU 缓存不友好，实测大多数场景下 LinkedList 反而比 ArrayList 慢。

• Vector：线程安全的动态数组，内部方法基本都经过 synchronized 修饰，不推荐在单线程环境使用。
• Stack：继承自 Vector，实现了一个后进先出的栈。

Set（无序、唯一）

Set 不允许存在重复的元素，与 List 不同，Set 中的元素是无序的。

• HashSet：通过 HashMap 实现，HashMap 的 Key 即 HashSet 存储的元素，所有 Key 都使用相同的 Value（一个名为 PRESENT 的 Object 类型常量）。使用 Key 保证元素唯一性，但不保证有序性。
• LinkedHashSet：继承自 HashSet，通过 LinkedHashMap 实现，使用双向链表维护元素插入顺序。
• TreeSet：通过 TreeMap 实现，添加元素时按照比较规则将其插入合适的位置，保证插入后的集合有序。

Map（键值对映射）

Map 是一个键值对集合，存储键、值和之间的映射。Key 无序、唯一；value 不要求有序，允许重复。

• HashMap：JDK 1.8 之前是数组+链表，JDK 1.8 以后引入红黑树优化。
• LinkedHashMap：继承自 HashMap，增加双向链表保持键值对的插入顺序或访问顺序。
• Hashtable：数组+链表组成，线程安全但效率低，已基本被淘汰。
• TreeMap：红黑树（自平衡的排序二叉树）。
• ConcurrentHashMap：Node 数组+链表+红黑树实现，线程安全。

Collections 和 Collection 的区别？

很多人面试时被这个问题问懵，因为它们名字太像了。

Collection 是 Java 集合框架中的一个接口，它是所有集合类的基础接口。它定义了一组通用的操作和方法，如添加、删除、遍历等。Collection 接口有许多实现类，如 List、Set 和 Queue 等。

Collections（注意有个 s）是 Java 提供的一个工具类，位于 java.util 包中。它提供了一系列静态方法，用于对集合进行操作和算法，如排序、查找、替换、反转、随机化等。

一句话总结：Collection 是接口，Collections 是工具类。

集合遍历的方法有哪些？

Java 中集合的遍历方法主要有以下几种：

1. 普通 for 循环：可以使用带有索引的普通 for 循环来遍历 List。
2. 增强 for 循环（for-each）：用于循环访问数组或集合中的元素，语法简洁。
3. Iterator 迭代器：可以使用迭代器来遍历集合，特别适用于需要删除元素的情况。
4. ListIterator 列表迭代器：ListIterator 是迭代器的子类，可以双向访问列表并在迭代过程中修改元素。
5. forEach 方法：Java 8 引入了 forEach 方法，可以对集合进行快速遍历。
6. Stream API：Java 8 的 Stream API 提供了丰富的功能，可以对集合进行函数式操作，如过滤、映射等。

---

二、List 集合高频面试题

ArrayList 和 LinkedList 的区别？

这个问题几乎是面试必问，要从多个维度来回答。

底层数据结构不同：

• ArrayList 使用动态数组实现，通过索引可以快速定位到元素。
• LinkedList 使用双向链表实现，每个节点都存储了元素本身以及指向前一个和后一个节点的指针。

插入和删除操作的效率不同：

• ArrayList 在尾部进行插入和删除操作时效率较高，不需要移动其他元素；但如果是在中间或开头插入、删除，就需要移动后面的所有元素。
• LinkedList 在头部和尾部进行插入、删除操作时效率很高，只需要调整节点的指针即可；但如果是在中间位置操作，需要先从头或尾遍历链表找到目标位置。

不过需要注意，LinkedList 实现了 Deque 接口，还可以当作双端队列、栈来使用。

随机访问的效率不同：

• ArrayList 支持通过索引直接快速访问元素，时间复杂度为 O(1)。
• LinkedList 不支持随机访问，想要获取某个位置的元素，必须从头节点或尾节点开始逐个遍历，时间复杂度为 O(n)。

空间占用不同：

• ArrayList 在创建时会分配一段连续的内存空间，虽然会有一定的容量浪费，但只需要存储元素本身。
• LinkedList 每个节点除了存储元素，还需要额外存储两个指针，所以在存储相同数量元素的情况下，LinkedList 的空间占用通常比 ArrayList 更大。

线程安全：
这两个集合都不是线程安全的。如果在多线程环境下使用，需要自己加锁保证线程安全，或者使用线程安全的 List 集合，比如 Vector、Collections.synchronizedList() 包装的 List，或者 CopyOnWriteArrayList。

ArrayList 和 LinkedList 的应用场景？

ArrayList 适用于：

• 需要频繁访问集合元素的场景
• 按索引查找、遍历和随机访问元素的操作较多
• 集合大小不经常改变
• 典型场景：数据的查询和展示、购物车列表等

LinkedList 适用于：

• 频繁进行插入和删除操作的场景
• 集合大小经常改变
• 需要作为双端队列、栈使用
• 通过迭代器直接操作已知位置的节点
• 典型场景：消息队列、任务调度队列等

ArrayList 的扩容机制说一下

ArrayList 在添加元素时，如果当前元素个数已经达到了内部数组的容量上限，就会触发扩容操作。

扩容步骤：

1. 计算新的容量：一般情况下，新的容量会扩大为原容量的 1.5 倍（JDK 9 起 grow 的实现被重构并提取到 ArraysSupport.newLength，但 1.5 倍这个比例本身没有变化），然后检查是否超过了最大容量限制。
2. 创建新的数组：根据计算得到的新容量，创建一个新的更大的数组。
3. 将元素复制：将原来数组中的元素逐个复制到新数组中。
4. 更新引用：将 ArrayList 内部指向原数组的引用指向新数组。
5. 完成扩容：扩容完成后，可以继续添加新元素。

为什么是 1.5 倍？

因为 1.5 可以充分利用移位操作，减少浮点数运算时间和运算次数。1.5 倍扩容相当于 oldCapacity + (oldCapacity >> 1)，只需要一次右移运算。

性能优化建议：

ArrayList 的扩容操作涉及到数组的复制和内存的重新分配，所以在频繁添加大量元素时，扩容操作可能会影响性能。可以在初始化 ArrayList 时预分配足够大的容量，避免频繁触发扩容操作。

// 预估会存放 1000 个元素
List<String> list = new ArrayList<>(1000);

ArrayList 和 Vector 的区别？

ArrayList 和 Vector 都是动态数组实现，但有几个关键区别：

线程安全性（最核心的区别）：

• Vector 是线程安全的，大部分方法都被 synchronized 修饰，多线程环境下不需要额外处理同步问题。
• ArrayList 没有任何同步机制，是非线程安全的，在多线程并发修改时可能出现数据不一致。

性能差异：

• 由于 Vector 需要加锁释放锁，在单线程环境下，操作效率通常比 ArrayList 低。
• ArrayList 性能更好，如果是单线程场景，或者能自己保证线程安全的情况下，ArrayList 是更优选择。

扩容机制不同：

• Vector 默认按 2 倍扩容（如果构造时指定了 capacityIncrement，则按该值线性增长）。
• ArrayList 默认增加 50%（即 1.5 倍）。
• Vector 可以通过构造方法指定容量增量 capacityIncrement，灵活控制扩容幅度，ArrayList 没有这个功能。

总结：选择时主要看是否需要线程安全。现在更多时候会用 ArrayList，因为它性能更好，而且在需要线程安全时，可以通过 Collections.synchronizedList() 方法将 ArrayList 包装成线程安全的集合，灵活性更高。

ArrayList 线程安全吗？变成线程安全有哪些方法？

ArrayList 不是线程安全的。

变成线程安全的方式有以下几种：

方法一：使用 Collections.synchronizedList() 包装

List<String> syncList = Collections.synchronizedList(new ArrayList<>());

方法二：使用 CopyOnWriteArrayList

List<String> cowList = new CopyOnWriteArrayList<>();

方法三：使用 Vector（不推荐）

List<String> vectorList = new Vector<>();

为什么 ArrayList 不是线程安全的？具体哪里不安全？

在高并发添加数据下，ArrayList 会暴露三个问题：

1. 部分值为 null（我们并没有 add null 进去）
2. 索引越界异常
3. size 与我们 add 的数量不符

来看 ArrayList 的 add 方法代码：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

大体可以分为三步：

1. 判断数组需不需要扩容，如果需要的话，调用 grow 方法进行扩容；
2. 将数组的 size 位置设置值（因为数组的下标是从 0 开始的）；
3. 将当前集合的大小加 1。

问题一：部分值为 null 是怎么产生的？

当线程 1 走到扩容那里发现当前 size 是 9，而数组容量是 10，所以不用扩容，这时候 CPU 让出执行权，线程 2 也进来了，发现 size 是 9，而数组容量是 10，所以不用扩容。这时候线程 1 继续执行，将数组下标索引为 9 的位置 set 值了，还没有来得及执行 size++，这时候线程 2 也来执行了，又把数组下标索引为 9 的位置 set 了一遍，这时候两个先后进行 size++，导致下标索引 10 的地方就为 null 了。

问题二：索引越界异常是怎么产生的？

线程 1 走到扩容那里发现当前 size 是 9，数组容量是 10 不用扩容，CPU 让出执行权，线程 2 也发现不用扩容，这时候数组的容量就是 10。而线程 1 set 完之后 size++，这时候线程 2 再进来 size 就是 10，数组的大小只有 10，而你要设置下标索引为 10 的就会越界（数组的下标索引从 0 开始）。

问题三：size 与 add 数量不符是怎么产生的？

这个基本上每次都会发生。因为 size++ 本身就不是原子操作，可以分为三步：获取 size 的值、将 size 的值加 1、将新的 size 值覆盖掉原来的。线程 1 和线程 2 拿到一样的 size 值加完了同时覆盖，就会导致一次没有加上，所以肯定不会与我们 add 的数量保持一致。

List 可以一边遍历一边修改元素吗？

这取决于遍历方式和具体的 List 实现类。

情况一：使用普通 for 循环遍历

可以在遍历过程中修改元素，只要修改的索引不超出 List 的范围即可。

list.add(1);
list.add(2);
list.add(3);

// 使用普通for循环遍历并修改元素
for (int i = 0; i < list.size(); i++) {
    list.set(i, list.get(i) * 2);
}
System.out.println(list); // 输出: [2, 4, 6]

情况二：使用 foreach 循环遍历

一般不建议在 foreach 循环中直接修改集合结构（add/remove），因为 foreach 底层基于迭代器实现，集合结构被修改后，迭代器下一次调用 next() 时会检测到 modCount != expectedModCount，从而抛出 ConcurrentModificationException 异常。

注意：“替换元素值”（即 list.set(i, newValue)）并不会改变 modCount，所以 list.set() 本身不会抛 CME；但 list.add() / list.remove() 会。

下面是一个会抛 CME 的反例：

list.add(1);
list.add(2);
list.add(3);
list.add(4);

// 在foreach中调用list.add/remove会抛出ConcurrentModificationException
for (Integer num : list) {
    if (num == 2) {
        list.remove(num); // 修改了结构，下一次迭代会抛CME
    }
}

情况三：使用迭代器遍历时

如果需要在遍历过程中删除元素，应使用 Iterator.remove()；如果需要替换元素，使用 ListIterator.set() 是最通用、最推荐的做法。

list.add(1);
list.add(2);
list.add(3);

// 使用 ListIterator 遍历并修改元素
ListIterator<Integer> iterator = list.listIterator();
while (iterator.hasNext()) {
    Integer num = iterator.next();
    if (num.equals(2)) {
        // 使用 ListIterator 的 set 方法修改（替换）元素
        iterator.set(4);
    }
}
System.out.println(list); // 输出: [1, 4, 3]

情况四：线程安全的 List

对于线程安全的 List，如 CopyOnWriteArrayList，由于其采用了写时复制的机制，在遍历的同时可以进行修改操作，不会抛出 ConcurrentModificationException 异常，但可能会读取到旧的数据，因为修改操作是在新的副本上进行的。

List 如何快速删除某个指定下标的元素？

ArrayList：

list.add(1);
list.add(2);
list.add(3);

// 删除下标为1的元素
list.remove(1);
System.out.println(list); // 输出: [1, 3]

ArrayList 提供了 remove(int index) 方法，该方法在删除元素后，会将后续元素向前移动。如果删除的是列表末尾的元素，时间复杂度为 O(1)；如果删除的是列表中间的元素，时间复杂度为 O(n)。

LinkedList：

list.add(1);
list.add(2);
list.add(3);

// 删除下标为1的元素
list.remove(1);
System.out.println(list); // 输出: [1, 3]

LinkedList 需要先遍历到指定下标位置，然后修改链表的指针来删除元素，时间复杂度为 O(n)。不过，如果已知要删除的元素是链表的头节点或尾节点，可以直接通过修改头指针或尾指针来实现删除，时间复杂度为 O(1)。

CopyOnWriteArrayList：

list.add(1);
list.add(2);
list.add(3);

// 删除下标为1的元素
list.remove(1);
System.out.println(list); // 输出: [1, 3]

由于 CopyOnWriteArrayList 在写操作时会创建一个新的数组，所以删除操作的时间复杂度取决于数组的复制速度，通常为 O(n)。但在并发环境下，它的删除操作不会影响读操作，具有较好的并发性能。

讲讲 Java 里面 List 的几种实现，有什么不同？

ArrayList（最常用）

• 应用更加广泛的动态数组实现，不是线程安全的，性能要好很多
• 可以根据需要调整容量，默认增加 50%（即 1.5 倍）
• 适合随机访问频繁的场景

Vector（早期提供）

• 线程安全的动态数组，如果不需要线程安全，并不建议选择
• 内部是使用对象数组来保存数据，可以自动增加容量
• Vector 默认按 2 倍扩容（如果构造时指定了 capacityIncrement，则按该值线性增长）

LinkedList（双向链表）

• Java 提供的双向链表，不需要像上面两种那样调整容量
• 不是线程安全的
• 进行节点插入、删除高效，但随机访问性能差

List 里面填基本数据类型为什么会报错？

List<> 等泛型集合类要求填充的必须是引用类型（对象类型），而不能直接使用基本数据类型（如 int、char、double 等），否则会编译报错。

// ❌ 编译报错
List<int> list = new ArrayList<>();

// ✅ 正确写法
List<Integer> list = new ArrayList<>();

这么设计的原因是：

1. 泛型的类型擦除机制：Java 泛型在编译后会被擦除为 Object 类型，而 Object 只能接收引用类型，不能接收基本数据类型。
2. 历史原因：Java 最初设计时基本数据类型和引用类型是严格区分的，泛型是后期（JDK 1.5）才引入的特性，为了兼容已有的类型系统，选择只支持引用类型。

通过使用包装类，结合 Java 的自动装箱（基本类型 → 包装类）和自动拆箱（包装类 → 基本类型）机制，可以很方便地在泛型集合中操作基本数据类型的数据。

List 和数组如何互相转换？

List 转数组：

主要有两种方式，核心是用 List 的 toArray() 方法：

方式一：无参 toArray()（返回 Object[]，不推荐）

List<String> list = Arrays.asList("a", "b", "c");
Object[] arr = list.toArray();
// 这种方式返回的是 Object 数组，若强转成 String[] 会抛 ClassCastException

方式二：带参 toArray(T[] a)（推荐，指定类型）

List<String> list = Arrays.asList("a", "b", "c");
String[] arr = list.toArray(new String[0]);
// 传入对应类型的数组，List 会把元素复制到该数组中
// 推荐传空数组，JDK 会优化长度

数组转 List：

核心是用 Arrays.asList()，但要注意两个坑：

坑一：返回的 List 不可变

String[] arr = {"a", "b", "c"};
List<String> list = Arrays.asList(arr);
// list.add("d"); // ❌ 会抛 UnsupportedOperationException
// Arrays.asList() 返回的是 Arrays 的内部类，不支持添加/删除操作

// 想修改就套一层 ArrayList
List<String> mutableList = new ArrayList<>(Arrays.asList(arr)); // ✅

坑二：基本类型数组的坑

int[] numArr = {1, 2, 3};
List<int[]> numList1 = Arrays.asList(numArr); // ❌ 会把整个数组当成一个元素！

// ✅ 正确方式1：手动装箱
List<Integer> numList2 = new ArrayList<>();
for (int num : numArr) {
    numList2.add(num);
}

// ✅ 正确方式2：Stream 流（JDK8+）
List<Integer> numList3 = Arrays.stream(numArr)
    .boxed()
    .collect(Collectors.toList());

基本类型数组（int[]、long[]）直接用 Arrays.asList() 会把整个数组当成一个元素，必须手动装箱或用 Stream 流转换为包装类的 List。

线程安全的 List，CopyOnWriteArrayList 是如何实现线程安全的？

CopyOnWriteArrayList 底层也是通过一个数组保存数据，使用 volatile 关键字修饰数组，保证当前线程对数组对象重新赋值后，其他线程可以及时感知到。

写入操作：加了一把互斥锁 ReentrantLock 以保证线程安全。

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // 获取到当前 List 集合保存数据的数组
        Object[] elements = getArray();
        // 获取该数组的长度
        int len = elements.length;
        // 将当前数组拷贝一份的同时，让其长度加1
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 将加入的元素放在新数组最后一位
        newElements[len] = e;
        // 替换引用，将数组的引用指向给新数组的地址
        setArray(newElements);
        return true;
    } finally {
        // 释放锁
        lock.unlock();
    }
}

写入原理总结：

写入新元素时，首先会将原来的数组拷贝一份并且让原来数组的长度+1，得到一个新数组，新数组里的元素和旧数组的元素一样并且长度比旧数组多一个长度，然后将新加入的元素放置在新数组最后一个位置后，用新数组的地址替换掉老数组的地址就能得到最新的数据了。

在我们执行替换地址操作之前，读取的是老数组的数据，数据是有效数据；执行替换地址操作之后，读取的是新数组的数据，同样也是有效数据，而且使用该方式能比读写都加锁要更加的效率。

读取操作：读是没有加锁的，所以读是一直都能读。

public E get(int index) {
    return get(getArray(), index);
}

适用场景：读多写少的并发场景，如事件监听列表等。

---

三、Set 集合高频面试题

Set 集合有什么特点？如何实现 key 无重复的？

Set 集合特点：Set 集合中的元素是唯一的，不会出现重复的元素。

不同实现的去重方式：

HashSet / LinkedHashSet：底层是哈希表

• 插入元素时先用 hashCode() 定位桶
• 再用 equals() 比较是否已存在相同元素
• 存在则不再插入

TreeSet：底层是红黑树

• 插入元素时不调用 hashCode/equals
• 而是用 Comparable.compareTo()（自然排序）或自定义 Comparator.compare() 的返回值是否为 0 来判断是否重复

List 和 Set 区别是什么？

最核心的区别就是「是否允许元素重复」和「是否保证有序」。

List：有序、可重复

• 元素的存储顺序和添加顺序一致
• 允许元素重复，甚至可以存多个 null 值
• 能通过下标（索引）直接访问元素，像 get(0) 就能拿到第一个元素
• 底层实现：ArrayList 靠数组、LinkedList 靠双向链表
• 适合场景：购物车列表、订单明细这类要保留添加顺序的场景

Set：唯一、无序（默认）

• 核心是「元素唯一」，不允许重复
• HashSet / LinkedHashSet 最多只能存一个 null 值（TreeSet 默认不允许 null，因为排序时调用 compare 会抛 NPE）
• 默认不保证元素的存储顺序（除了 TreeSet、LinkedHashSet 这类特殊实现）
• 没有下标，没法通过索引访问元素，只能遍历
• 适合场景：用户标签、商品分类、抽奖名单（避免同一个用户重复中奖）

有序的 Set 是什么？记录插入顺序的集合是什么？

“有序” 的 Set 有 TreeSet 和 LinkedHashSet，但两者"有序"的含义并不一样：

TreeSet：按值排序

• 基于红黑树实现
• 元素按"自然顺序"（natural ordering，即 Comparable.compareTo() 定义的顺序）或自定义 Comparator 排序存储
• 属于"按值排序"

LinkedHashSet：保留插入顺序

• 基于哈希表 + 双向链表实现
• 链表记录了元素的插入顺序，遍历时按插入顺序输出
• 属于"保留插入顺序"（注意：这不是"自然顺序"，和元素值的大小无关）

记录插入顺序的集合通常指的是 LinkedHashSet，它既保证元素唯一，又能按插入顺序遍历，当你需要"去重 + 保留添加顺序"时它是首选。

如何对 Set 排序？

Java 里 Set 本身默认不保证有序，但要实现 Set 的排序，核心是选带排序特性的 Set 实现类，或把普通 Set 转成有序结构。

方式一：TreeSet（自动排序）

TreeSet 底层是红黑树，插入时自动排序，支持「自然排序」和「自定义 Comparator 排序」。

import java.util.TreeSet;
import java.util.Comparator;

public class SetSortDemo {
    
    // 1. 基本类型/字符串（自然排序）
    public static void testTreeSetBasic() {
        TreeSet<Integer> numSet = new TreeSet<>();
        numSet.add(3);
        numSet.add(1);
        numSet.add(2);
        // 遍历输出：1 2 3（自动按自然顺序升序）
        for (Integer num : numSet) {
            System.out.print(num + " ");
        }
    }
    
    // 2. 自定义对象（实现Comparable接口）
    static class User implements Comparable<User> {
        private String name;
        private int age;
        
        public User(String name, int age) {
            this.name = name;
            this.age = age;
        }
        
        // 重写compareTo，按年龄升序排序
        @Override
        public int compareTo(User o) {
            return this.age - o.age;
        }
        
        @Override
        public String toString() {
            return name + ":" + age;
        }
    }
    
    // 3. 自定义对象（传入Comparator，按年龄降序）
    public static void testTreeSetCustom() {
        TreeSet<User> userSet = new TreeSet<>(new Comparator<User>() {
            @Override
            public int compare(User u1, User u2) {
                return u2.age - u1.age; // 降序
            }
        });
        
        userSet.add(new User("张三", 20));
        userSet.add(new User("李四", 25));
        userSet.add(new User("王五", 22));
        // 遍历输出：李四:25 王五:22 张三:20（按年龄降序）
        for (User user : userSet) {
            System.out.println(user);
        }
    }
    
    // 4. LinkedHashSet：保留添加顺序（不按值排序）
    public static void testLinkedHashSet() {
        LinkedHashSet<String> strSet = new LinkedHashSet<>();
        strSet.add("b");
        strSet.add("a");
        strSet.add("c");
        // 遍历输出：b a c（和添加顺序一致）
        for (String str : strSet) {
            System.out.print(str + " ");
        }
    }
}

方式二：LinkedHashSet（保留插入顺序）

如果只是想按「插入顺序」遍历，不用按元素值排序，用 LinkedHashSet 即可，性能比 TreeSet 高。

LinkedHashSet<String> strSet = new LinkedHashSet<>();
strSet.add("b");
strSet.add("a");
strSet.add("c");
// 遍历输出：b a c（严格按添加顺序）
for (String str : strSet) {
    System.out.print(str + " ");
}

---

四、Map 集合高频面试题

HashMap 实现原理介绍一下？

JDK 1.7 之前：
HashMap 数据结构是数组和链表，通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上（"拉链法"解决冲突）。因为链表的查询时间是 O(n)，所以冲突很严重时效率就很低。

JDK 1.8 优化：
当某个桶的链表长度 ≥ 8（TREEIFY_THRESHOLD）且哈希表数组长度 ≥ 64（MIN_TREEIFY_CAPACITY）时，会把链表转换为红黑树，把该桶的查找时间复杂度从 O(n) 降低到 O(log n)；如果数组长度 < 64，则只会触发扩容（resize()），并不会立刻树化。

反向地，在 resize() 过程中，若某个桶的节点数 ≤ 6（UNTREEIFY_THRESHOLD），红黑树会被退化回链表。

HashMap 是线程安全的吗？

HashMap 不是线程安全的，在多线程会存在下面的问题：

JDK 1.7 的问题：
采用数组 + 链表的数据结构，多线程背景下，在数组扩容的时候，存在 Entry 链死循环和数据丢失问题。

JDK 1.8 的问题：
采用数组 + 链表 + 红黑二叉树的数据结构，优化了 1.7 中数组扩容的方案，解决了 Entry 链死循环和数据丢失问题。但是多线程背景下，put 方法存在数据覆盖的问题。

如果要保证线程安全，可以通过这些方法：

• 多线程环境可以使用 Collections.synchronizedMap 同步加锁的方式
• 还可以使用 Hashtable
• 同步的方式显然性能不达标，而 ConcurrentHashMap 更适合高并发场景使用

在 Java 的 HashMap 中 get 一个元素的过程是怎样的？

get 方法的作用是传入我们需要获取的节点的 key，然后将这个节点的 value 返回。

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode 方法接收两个参数：key 的 hash 值和 key 本身。

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    
    // 判断：数组table不为null、长度大于0、计算出的节点位置有节点存在
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        
        // 首先判断第一个节点的key值是否与参数的key值相等
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        
        // 判断第一个节点是否有下一个节点
        if ((e = first.next) != null) {
            // 若是树节点，则通过红黑树的查找算法进行查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            
            // 若是链表，则使用do...while循环遍历查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 若没有找到对应的节点，返回null
    return null;
}

HashMap 的 put 过程介绍一下

HashMap 的 put() 方法用于向 HashMap 中添加键值对，JDK 1.8 版本的流程如下：

第一步： 根据要添加的键的哈希码计算在数组中的位置（索引）。

第二步： 如果为空，则直接在该位置创建一个新的 Node 对象来存储键值对。将修改次数（modCount）加 1。

第三步： 如果该位置已经存在其他键值对，检查该位置的第一个键值对的哈希码和键是否与要添加的键值对相同？

• 如果相同，则表示找到了相同的键，直接将新的值替换旧的值。

第四步： 如果键值对集合是链表结构，从链表的头部开始逐个比较键的哈希码和 equals() 方法。

• 如果找到了相同的键，则使用新的值取代旧的值。
• 如果没有找到相同的键，则将新的键值对添加到链表的尾部。

第五步： 如果键值对集合是红黑树结构，在红黑树中使用哈希码和 equals() 方法进行查找。

• 如果找到了相同的键，则使用新的值取代旧的值。
• 如果没有找到相同的键，则将新的键值对添加到红黑树中。

第六步： 如果链表长度超过阈值，且 HashMap 的数组长度大于等于 64，则会将链表转换为红黑树。

第七步： 如果键值对的数量（size）与数组的长度的比值大于阈值，则需要进行扩容操作。

• 创建一个新的两倍大小的数组。
• 遍历旧数组中的每个键值对，根据 (e.hash & oldCap) 的结果重新分配到新数组中的位置。
• 更新 HashMap 的数组引用和阈值参数。

第八步： 完成添加操作。

HashMap 的 put(key,val) 和 get(key) 过程总结

存储对象时：
将 K/V 传给 put 方法时，它调用 hashCode 计算 hash 从而得到 bucket 位置，进一步存储。HashMap 在每次 put 后会检查整个表的元素数量（size），当 size > 容量 × loadFactor（默认 16 × 0.75 = 12）时触发扩容，新容量为原来的 2 倍。

获取对象时：
将 K 传给 get，它调用 hashCode 计算 hash 从而得到 bucket 位置，并进一步调用 equals() 方法确定键值对。如果发生碰撞，HashMap 通过链表将产生碰撞冲突的元素组织起来。在 Java 8 中，如果一个 bucket 中碰撞冲突的元素超过某个限制（默认是 8），则使用红黑树来替换链表。

HashMap 调用 get 方法一定安全吗？

不是，调用 get 方法有几点需要注意的地方：

空指针异常（NullPointerException）：
这里要区分两种情况：

1. 如果 HashMap 变量本身是 null（还没 new），那么调用它的任何方法都会抛 NPE。
2. 如果 HashMap 已经正常初始化，那么用 null 作为 key 调用 get(null) / put(null, v) 都是合法的，不会抛 NPE，因为 HashMap 明确支持 null 键（key 为 null 时哈希值会被直接设为 0 放入 0 号桶）。

线程安全：
HashMap 本身不是线程安全的。如果在多线程环境中，没有适当的同步措施，同时对 HashMap 进行读写操作可能会导致不可预测的行为。例如，在一个线程中调用 get 方法读取数据，而另一个线程同时修改了结构（如增加或删除元素），可能会导致读取操作得到错误的结果或抛出 ConcurrentModificationException。

HashMap 一般用什么做 Key？为啥 String 适合做 Key 呢？

用 String 做 key，因为 String 对象是不可变的，一旦创建就不能被修改，这确保了 Key 的稳定性。如果 Key 是可变的，可能会导致 hashCode 和 equals 方法的不一致，进而影响 HashMap 的正确性。

HashMap 为什么用红黑树而不是平衡二叉树？

平衡二叉树（AVL 树）的问题：
追求一种"完全平衡"状态：任何结点的左右子树的高度差不会超过 1。这个要求太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的规则，进而都需要通过左旋和右旋来进行调整。

红黑树的优势：
不追求"完全平衡"，而是追求一种"弱平衡"状态：整个树最长路径不会超过最短路径的 2 倍。虽然牺牲了一部分查找的性能效率，但是能够换取一部分维持树平衡状态的成本。红黑树在插入、删除等操作，不会像平衡树那样频繁地破坏规则，所以不需要频繁调整。

HashMap key 可以为 null 吗？

可以为 null。

1. HashMap 中使用 hash() 方法来计算 key 的哈希值，当 key 为空时，直接令 key 的哈希值为 0，不走 key.hashCode() 方法。
2. HashMap 虽然支持 key 和 value 为 null，但是 null 作为 key 只能有一个，null 作为 value 可以有多个。
3. 因为 HashMap 中，如果 key 值一样，那么会覆盖相同 key 值的 value 为最新，所以 key 为 null 只能有一个。

重写 HashMap 的 equals 和 hashCode 方法需要注意什么？

HashMap 使用 Key 对象的 hashCode() 和 equals 方法去决定 key-value 对的索引。当我们试着从 HashMap 中获取值的时候，这些方法也会被用到。如果这些方法没有被正确地实现，两个不同 Key 也许会产生相同的 hashCode() 和 equals() 输出，HashMap 将会认为它们是相同的，然后覆盖它们。

遵循规则：

1. 如果 o1.equals(o2)，那么 o1.hashCode() == o2.hashCode() 总是为 true。
2. 如果 o1.hashCode() == o2.hashCode()，并不意味着 o1.equals(o2) 会为 true。

重写 HashMap 的 equals 方法不当会出现什么问题？

HashMap 在比较元素时，会先通过 hashCode 进行比较，相同的情况下再通过 equals 进行比较。

所以 equals 相等的两个对象，hashCode 一定相等。hashCode 相等的两个对象，equals 不一定相等（比如散列冲突的情况）。

重写了 equals 方法，不重写 hashCode 方法时，可能会出现 equals 方法返回为 true，而 hashCode 方法却返回 false。这样的一个后果会导致在 HashMap 等类中存储多个一模一样的对象，导致出现覆盖存储的数据的问题，这与 HashMap 只能有唯一的 key 的规范不符合。

HashMap 的扩容机制介绍一下

HashMap 默认的负载因子是 0.75，即如果 HashMap 中的元素个数超过了总容量 75%，则会触发扩容。

扩容分两个步骤：

1. 第 1 步：对哈希表长度的扩展（2 倍）
2. 第 2 步：将旧哈希表中的数据放到新的哈希表中

因为我们使用的是 2 次幂的扩展（指长度扩为原来 2 倍），所以，元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。

这个设计非常巧妙，既省去了重新计算 hash 值的时间，而且同时，由于新增的 1bit 是 0 还是 1 可以认为是随机的，因此 resize 的过程，均匀地把之前的冲突的节点分散到新的 bucket 了。

HashMap 的大小为什么是 2 的 n 次方大小呢？

HashMap 底层是「数组 + 链表 / 红黑树」的结构，当我们要存一个 key-value 时，第一步就是确定这个 key 存在数组的哪个位置（索引）。

HashMap 用的索引计算公式是：

index = hash & (length - 1)

这里的 hash 是经过扰动处理后的 key 的哈希值，length 是数组的容量。

这个公式的设计初衷是用位运算替代取模运算（因为位运算直接操作二进制位，速度远快于除法 / 取模），但它能生效的前提，就是 length 必须是 2 的 n 次方。

原因一：位运算等价于取模

假设 length = 16（即 2^4），那么 length - 1 = 15，二进制是 00001111（低 4 位全是 1）。
再假设 key 的 hash 值是 100，二进制是 01100100。

现在计算 hash & (length - 1)：

01100100  (hash = 100)
& 00001111  (length - 1 = 15)
= 00000100  (结果 = 4)

这个结果和 100 % 16（取模）的结果完全一样，都是 4。

当 length 是 2 的 n 次方时，length - 1 的二进制低 n 位全是 1，高位全是 0。此时做「与运算」，相当于直接把 hash 值的低 n 位截取下来，这在数学上就等价于「对 length 取模」。

原因二：如果不是 2 的 n 次方，会导致索引浪费

假设 length = 15（不是 2 的 n 次方），length - 1 = 14，二进制是 00001110（最后一位是 0）。

再试一个 hash = 101（二进制 01100101）：

01100101  (hash = 101)
& 00001110  (length - 1 = 14)
= 00000100  (结果还是 4！)

发现问题了吗？因为 length - 1 的最后一位是 0，不管 hash 值的最后一位是 0 还是 1，与运算后都会变成 0 —— 这就导致索引的最后一位永远用不到，比如索引 1、3、5、7… 这些位置永远不会存数据，既浪费了数组空间，又大大增加了哈希碰撞的概率。

原因三：扩容优化

HashMap 有个扩容机制：当元素个数达到 容量 × 负载因子（默认是 0.75）时，数组会扩容为原来的 2 倍。

如果容量始终是 2 的 n 次方，扩容时元素的新索引就不用重新计算完整的 hash，只需要看 hash 值的某一个高位就行。

旧容量 oldCap = 16，新容量 = 32。我们计算 hash & oldCap：

• 如果结果为 0：说明 hash 值对应 oldCap 的那一位是 0，新索引 = 旧索引。
• 如果结果不为 0：说明那一位是 1，新索引 = 旧索引 + oldCap。

整个过程只需要做一次「与运算」，根本不用重新计算 hash，也不用再取模，速度非常快。

HashMap 总结

HashMap 的大小设计为 2 的 n 次方，是一个环环相扣的优化设计：

1. 保证 hash & (length - 1) 等价于取模，用位运算实现高效寻址；
2. 让 length - 1 的二进制全 1，接住 hash 值的均匀分布，减少碰撞；
3. 为扩容优化铺路，不用重新算 hash，仅通过高位判断就能快速确定新索引。

往 HashMap 存 20 个元素，会扩容几次？

当插入 20 个元素时，HashMap 的扩容过程如下：

初始容量：16

• 插入第 1 到第 12 个元素时，不需要扩容。
• 插入第 13 个元素时，达到负载因子限制，需要扩容。此时，HashMap 的容量从 16 扩容到 32。

扩容后的容量：32

• 插入第 14 到第 24 个元素时，不需要扩容。

因此，总共会进行一次扩容。

说说 HashMap 的负载因子

HashMap 负载因子 loadFactor 的默认值是 0.75，当 HashMap 中的元素个数超过了容量的 75% 时，就会进行扩容。

默认负载因子为 0.75，是因为它提供了空间和时间复杂度之间的良好平衡。

• 负载因子太低会导致大量的空桶浪费空间
• 负载因子太高会导致大量的碰撞，降低性能

0.75 的负载因子在这两个因素之间取得了良好的平衡。

HashMap 和 Hashtable 有什么不一样？

HashMap：

• 线程不安全，效率高
• 可以存储 null 的 key 和 value，null 的 key 只能有一个，null 的 value 可以有多个
• 默认初始容量为 16，每次扩充变为原来 2 倍
• 创建时如果给定了初始容量，则扩充为 2 的幂次方大小
• 底层数据结构为数组+链表，插入元素后如果链表长度大于阈值（默认为 8），先判断数组长度是否小于 64，如果小于，则扩充数组，反之将链表转化为红黑树

Hashtable：

• 线程安全，效率低，内部方法基本都经过 synchronized 修饰
• 不可以有 null 的 key 和 value
• 默认初始容量为 11，每次扩容变为原来的 2n+1
• 创建时给定了初始容量，会直接用给定的大小
• 底层数据结构为数组+链表
• 它基本被淘汰了，要保证线程安全可以用 ConcurrentHashMap

怎么用：
HashMap 主要用来存储键值对，可以调用 put 方法向其中加入元素，调用 get 方法获取某个键对应的值，也可以通过 containsKey 方法查看某个键是否存在等。

常见的 Map 集合有哪些？

非线程安全：

HashMap
基于哈希表实现的 Map，根据键的哈希值来存储和获取键值对，JDK 1.8 中使用数组 + 链表 + 红黑树来实现。是非线程安全的，在多线程环境下可能出现数据不一致的问题。

需要区分两个时代：

• JDK 1.7 使用头插法 + 并发扩容时可能形成环形链表，进而触发 get() 时的死循环
• JDK 1.8 改为尾插法后已经不会再出现死循环，但多线程 put() 仍存在数据覆盖和丢失等线程安全问题

LinkedHashMap
继承自 HashMap，在 HashMap 的基础上，使用双向链表维护了键值对的插入顺序或访问顺序，使得迭代顺序与插入顺序或访问顺序一致。

TreeMap
基于红黑树实现的 Map，可以对键进行排序，默认按照自然顺序排序，也可以通过指定的比较器进行排序。是非线程安全的。

线程安全：

Hashtable
早期 Java 提供的线程安全的 Map 实现，实现方式与 HashMap 类似，但在方法上使用了 synchronized 关键字来保证线程安全。

ConcurrentHashMap
在 JDK 1.8 以前采用了分段锁等技术来提高并发性能。在 ConcurrentHashMap 中，将数据分成多个段（Segment），每个段都有自己的锁。在 JDK 1.8 以后是通过 volatile + CAS 或者 synchronized 来保证线程安全的。

如何对 Map 进行快速遍历？

方式一：使用 for-each 循环和 entrySet() 方法（推荐）

Map<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);
map.put("key3", 3);

// 使用for-each循环和entrySet()遍历Map
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

方式二：使用 for-each 循环和 keySet() 方法

// 如果只需要遍历 Map 中的键
for (String key : map.keySet()) {
    System.out.println("Key: " + key + ", Value: " + map.get(key));
}

方式三：使用迭代器

// 适用于需要删除元素等操作时
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

方式四：使用 Lambda 表达式和 forEach() 方法（JDK 8+）

// 更加简洁和函数式
map.forEach((key, value) -> System.out.println("Key: " + key + ", Value: " + value));

方式五：使用 Stream API（JDK 8+）

// 可以结合过滤、映射等操作
map.entrySet().stream()
    .forEach(entry -> System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue()));

// 还可以进行其他操作，如过滤、映射等
Map<String, Integer> filteredMap = map.entrySet().stream()
    .filter(entry -> entry.getValue() > 1)
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

ConcurrentHashMap 怎么实现的？

JDK 1.7：分段锁（Segment + HashEntry）

ConcurrentHashMap 采用数组加链表的形式实现，而数组又分为：大数组 Segment 和小数组 HashEntry。

• Segment 是一种可重入锁（ReentrantLock），在 ConcurrentHashMap 里扮演锁的角色
• HashEntry 则用于存储键值对数据
• 一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组

分段锁技术将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

JDK 1.8：volatile + CAS + synchronized

主要通过 volatile + CAS 或者 synchronized 来实现线程安全。添加元素时首先会判断容器是否为空：

1. 如果为空则使用 volatile 加 CAS 来初始化
2. 如果容器不为空，则根据存储的元素计算该位置是否为空
3. 如果结果为空，则利用 CAS 设置该节点
4. 如果结果不为空，则使用 synchronized，然后遍历桶中的数据，并替换或新增节点到桶中
5. 最后再判断是否需要转为红黑树

如果把上面的执行用一句话归纳的话，就相当于是 ConcurrentHashMap 通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。

而且 JDK 1.8 使用的是红黑树优化了之前的固定链表，当数据量比较大的时候，查询性能也得到了很大的提升，从之前的 O(n) 优化到了 O(logn) 的时间复杂度。

JDK 1.7 中的分段锁是怎么加锁的？

在 JDK 1.7 的 ConcurrentHashMap 中，将整个数据结构分为多个 Segment，每个 Segment 都类似于一个小的 HashMap，每个 Segment 都有自己的锁，不同 Segment 之间的操作互不影响，从而提高并发性能。

对于插入、更新、删除等操作，需要先定位到具体的 Segment，然后再在该 Segment 上加锁，而不是像 Hashtable 那样对整个表加锁。这样可以使得不同 Segment 之间的操作并行进行，提高了并发性能。

分段锁是可重入的吗？

JDK 1.7 ConcurrentHashMap 中的分段锁是用了 ReentrantLock，是一个可重入的锁。

已经用了 synchronized，为什么还要用 CAS 呢？

ConcurrentHashMap 使用这两种手段来保证线程安全主要是一种权衡的考虑。

putVal 中的选择：

• 如果计算出来的 hash 槽没有存放元素，就可以直接使用 CAS 来进行设置值。这是因为在设置元素的时候，因为 hash 值经过了各种扰动后，造成 hash 碰撞的几率较低，我们可以预测使用较少的自旋来完成具体的 hash 落槽操作。

• 当桶位已经存在节点（发生 hash 碰撞）时，需要遍历链表或红黑树进行查找、替换或追加节点，操作步骤较多且需要保护整条链/树的结构，CAS 自旋已经不再适合，因此改用 synchronized 锁住桶的头节点来完成这部分逻辑。

ConcurrentHashMap 用了悲观锁还是乐观锁？

悲观锁和乐观锁都有用到。

添加元素时的流程：

1. 如果容器为空，则使用 volatile 加 CAS（乐观锁）来初始化
2. 如果容器不为空，则根据存储的元素计算该位置是否为空
3. 如果计算结果为空，则利用 CAS（乐观锁）设置该节点
4. 如果计算结果不为空，则使用 synchronized（悲观锁），然后遍历桶中的数据，并替换或新增节点到桶中

Hashtable 底层实现原理是什么？

Hashtable 的底层数据结构主要是数组加上链表，数组是主体，链表是解决 hash 冲突存在的。

Hashtable 是线程安全的，实现方式是 Hashtable 的所有公共方法均采用 synchronized 关键字，当一个线程访问同步方法，另一个线程也访问的时候，就会陷入阻塞或者轮询的状态。

Hashtable 线程安全是怎么实现的？

因为它的 put、get 做成了同步方法，保证了 Hashtable 的线程安全性，每个操作数据的方法都进行同步控制之后，由此带来的问题：任何一个时刻只能有一个线程可以操纵 Hashtable，所以其效率比较低。

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    Entry entry = (Entry)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    addEntry(hash, key, value, index);
    return null;
}

public synchronized V get(Object key) {
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

可以看到，Hashtable 是通过使用了 synchronized 关键字来保证其线程安全。

Hashtable 和 ConcurrentHashMap 有什么区别？

底层数据结构：

• jdk7 之前的 ConcurrentHashMap 底层采用的是分段的数组+链表实现，jdk8 之后采用的是数组+链表/红黑树
• Hashtable 采用的是数组+链表，数组是主体，链表是解决 hash 冲突存在的

实现线程安全的方式：

• jdk8 以前，ConcurrentHashMap 采用分段锁，对整个数组进行了分段分割，每一把锁只锁容器里的一部分数据，多线程访问不同数据段里的数据，就不会存在锁竞争
• jdk8 以后，直接采用数组+链表/红黑树，并发控制使用 CAS 和 synchronized 操作
• Hashtable：所有的方法都加了锁来保证线程安全，但是效率非常低

说一下 HashMap 和 Hashtable、ConcurrentHashMap 的区别

HashMap：

• 线程不安全，效率高
• 可以存储 null 的 key 和 value，null 的 key 只能有一个，null 的 value 可以有多个
• 默认初始容量为 16，每次扩充变为原来 2 倍
• 底层数据结构为数组+链表+红黑树（JDK 1.8）

Hashtable：

• 线程安全，效率低，内部方法基本都经过 synchronized 修饰
• 不可以有 null 的 key 和 value
• 默认初始容量为 11，每次扩容变为原来的 2n+1
• 它基本被淘汰了，要保证线程安全可以用 ConcurrentHashMap

ConcurrentHashMap：

• Java 中的线程安全哈希表实现，可以在多线程环境下并发进行读写操作
• 不允许 null key 或 null value（会抛 NPE），原因是多线程下 null 无法区分「key 不存在」还是「key 对应的 value 就是 null」
• JDK 1.7：基于分段锁实现，将整个哈希表拆成多个 Segment
• JDK 1.8：取消了 Segment，直接在 table 数组的头节点上加锁，使用 volatile + CAS + synchronized 组合保证线程安全

了解的哈希冲突解决方法有哪些？

1. 链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
2. 开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。
3. 再哈希法（Rehashing）：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。
4. 哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

列举 HashMap 在多线程下可能会出现的问题？

1. JDK 1.7 中的环形链表：HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK 1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。

2. 数据覆盖：多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。

Java 中的线程安全的集合是什么？

在 java.util 包中的线程安全的类主要 2 个，其他都是非线程安全的。

Vector：线程安全的动态数组，其内部方法基本都经过 synchronized 修饰，如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。

Hashtable：线程安全的哈希表，Hashtable 的加锁方法是给每个方法加上 synchronized 关键字，这样锁住的是整个 Table 对象，不支持 null 键和值，由于同步导致的性能开销，所以已经很少被推荐使用。

java.util.concurrent 包提供的都是线程安全的集合：

并发 Map：

• ConcurrentHashMap：与 Hashtable 的主要区别是加锁粒度不同。在 JDK 1.7，加的是分段锁（Segment 锁），每个 Segment 含有整个 table 的一部分。在 JDK 1.8，取消了 Segment，直接在 table 元素（桶的头节点）上加锁，使加锁粒度进一步缩小到单个桶级别。
• ConcurrentSkipListMap：实现了一个基于 SkipList（跳表）算法的可排序的并发集合。

并发 Set：

• ConcurrentSkipListSet：是线程安全的有序的集合，底层是使用 ConcurrentSkipListMap 实现。
• CopyOnWriteArraySet：是线程安全的 Set 实现，可以通过 CopyOnWriteArrayList 来理解。

并发 List：

• CopyOnWriteArrayList：它是 ArrayList 的线程安全的变体，其中所有写操作都通过对底层数组进行全新复制来实现。

并发 Queue：

• ConcurrentLinkedQueue：适用于高并发场景下的队列，通过无锁的方式（CAS）实现。
• BlockingQueue：主要功能在于简化多线程间的数据共享，提供一种读写阻塞等待的机制。

并发 Deque：

• LinkedBlockingDeque：线程安全的双端队列实现，内部使用链表结构。
• ConcurrentLinkedDeque：基于链接节点的无限并发链表。

---

觉得有用？点个在看再走吧 👍

欢迎转发给正在准备面试的朋友，一起拿下 Java 集合！