# Java集合面试题
大家好，我是小林。
Java 集合是面试里几乎必考的一块，而且这块的题目有个特点：入门容易，但深挖起来没有底。很多人用 ArrayList 和 HashMap 用了好几年，但面试被问到"HashMap 为什么用红黑树而不是平衡二叉树""ConcurrentHashMap 在 JDK 1.7 和 1.8 的实现有什么区别"时，就开始说不清楚了。集合类看起来只是工具，但背后涉及的数据结构、哈希算法、并发机制，才是面试真正在考的东西。
这篇文章整理了 Java 集合框架面试中最常被问到的问题，涵盖 List、Set、Map 以及 Queue 的常见实现，重点包括 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 的底层原理，再去看线程安全相关的集合类，这样理解起来会顺很多。
# 概念
# 数组与集合区别，用过哪些？
数组和集合的区别：
- 数组是固定长度的数据结构，一旦创建长度就无法改变，而常见的 ArrayList、HashSet 等集合支持动态增删元素。不过，Arrays.asList() 返回的列表是固定大小的，并不是所有集合都能增删。
- 数组可以包含基本数据类型和对象，而集合只能包含对象。
- 数组通过下标访问元素，List 也支持 get(index) 访问；Set 没有下标，Map 则通过 key 查找 value。能不能随机访问、访问有多快，要看具体实现。
我用过的一些 Java 集合类：
- ArrayList： 动态数组，实现了List接口，支持动态增长。
- LinkedList： 双向链表，实现了 List 和 Deque 接口，头尾插入、删除很快，按下标操作则需要先遍历定位。
- HashMap： 基于哈希表的Map实现，存储键值对，通过键快速查找值。
- HashSet： 基于HashMap实现的Set集合，用于存储唯一元素。
- TreeMap： 基于红黑树实现的有序Map集合，可以按照键的顺序进行排序。
- LinkedHashMap： 基于哈希表和双向链表实现的Map集合，保持插入顺序或访问顺序。
- PriorityQueue： 优先队列，保证队头是优先级最高的元素，但遍历整个队列并不保证有序。
# 说说Java中的集合？
List是有序的Collection，使用此接口能够精确的控制每个元素的插入位置，用户能根据索引访问List中元素。常用的实现List的类有LinkedList，ArrayList，Vector，Stack。
- ArrayList 是容量可变的非线程安全列表，其底层使用数组实现。当集合扩容时，会创建更大的数组，并把原数组复制到新数组。ArrayList 支持对元素的快速随机访问，在尾部追加/删除元素效率很高，但在中间位置插入/删除需要搬移元素，代价较高。
- LinkedList 本质是一个双向链表，支持高效的头尾插入/删除和作为双端队列使用。需要注意的是："LinkedList 插入/删除比 ArrayList 更快"是一个常见误区：其 O(1) 的前提是已经持有目标节点的引用；如果要在任意位置插入/删除，仍需先 O(n) 遍历链表找到位置，加上每个节点都需要独立分配、对 CPU 缓存不友好，实测大多数场景下 LinkedList 反而比 ArrayList 慢，这也是现在主流建议优先使用 ArrayList 的原因。
Set 不允许存在重复的元素，但是否有序取决于实现类：HashSet 不保证顺序，LinkedHashSet 保留插入顺序，TreeSet 按比较规则排序。常用的实现有HashSet，LinkedHashSet和TreeSet。
- HashSet通过HashMap实现，HashMap的Key即HashSet存储的元素，所有Key都是用相同的Value，一个名为PRESENT的Object类型常量。使用Key保证元素唯一性，但不保证有序性。由于其底层的 HashMap 本身就是非线程安全的，因此 HashSet 也是非线程安全的。
- LinkedHashSet继承自HashSet，通过LinkedHashMap实现，使用双向链表维护元素插入顺序。
- TreeSet通过TreeMap实现的，添加元素到集合时按照比较规则将其插入合适的位置，保证插入后的集合仍然有序。
Map 是一个键值对集合，存储键、值和之间的映射。Key 唯一，value 可以重复；遍历顺序由实现类决定，比如 HashMap 不保证顺序，TreeMap 按 key 排序。Map 没有继承于 Collection 接口，从 Map 集合中检索元素时，只要给出键对象，就会返回对应的值对象。主要实现有TreeMap、HashMap、Hashtable、LinkedHashMap、ConcurrentHashMap
- HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（"拉链法"解决冲突），JDK1.8 以后在解决哈希冲突时有了较大的变化：以 JDK 8 的
put为例，当桶中已有至少 8 个节点，再插入一个新节点（插入后长度至少为 9），且哈希表数组长度 ≥ 64 时，才会将该链表转化为红黑树，以减少搜索时间；如果数组长度 < 64，则只会触发扩容而不做树化。 - LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
- Hashtable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的
- TreeMap：红黑树（自平衡的排序二叉树）
- ConcurrentHashMap：Node数组+链表+红黑树实现，线程安全的（jdk1.8以前Segment锁，1.8以后volatile + CAS 或者 synchronized）
# Java中的线程安全的集合是什么？
在 java.util 包中，常见的老牌线程安全集合有 Vector 和 Hashtable，Stack 继承自 Vector，也带有同步能力。另外，还可以用 Collections.synchronizedList()、synchronizedMap() 等方法包装普通集合。
- Vector：线程安全的动态数组，其内部方法基本都经过synchronized修饰，如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。Vector 内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。
- Hashtable：线程安全的哈希表，Hashtable 的加锁方法是给每个方法加上 synchronized 关键字，这样锁住的是整个 Table 对象，不支持 null 键和值，由于同步导致的性能开销，所以已经很少被推荐使用，如果要保证线程安全的哈希表，可以用ConcurrentHashMap。
java.util.concurrent 包还提供了多种线程安全的集合：
并发Map：
- ConcurrentHashMap：它与 Hashtable 的主要区别是二者加锁粒度的不同，在 JDK 1.7，ConcurrentHashMap 加的是分段锁，也就是 Segment 锁，每个 Segment 含有整个 table 的一部分，这样不同分段之间的并发操作就互不影响。在 JDK 1.8，它取消了 Segment，直接在 table 元素（桶的头节点）上加锁，使加锁粒度进一步缩小到单个桶级别。对于 put 操作，如果 Key 对应的数组槽位为 null，则通过 CAS 操作（Compare and Swap）将新节点写入该槽位；如果槽位不为 null（即已存在链表头或红黑树根节点），则对该头节点使用
synchronized加锁，然后遍历桶中的数据执行替换或新增。如果该 put 操作使得当前桶的链表长度超过阈值，则将其转换为红黑树，从而提高查找效率。 - ConcurrentSkipListMap：实现了一个基于SkipList（跳表）算法的可排序的并发集合，SkipList是一种可以在对数预期时间内完成搜索、插入、删除等操作的数据结构，通过维护多个指向其他元素的“跳跃”链接来实现高效查找。
并发Set：
- ConcurrentSkipListSet：是线程安全的有序的集合。底层是使用ConcurrentSkipListMap实现。
- CopyOnWriteArraySet：是线程安全的Set实现，它基于 CopyOnWriteArrayList 实现，按元素的添加顺序遍历，通过 equals 判断重复，更适合元素较少、读多写少的场景。有意思的是，CopyOnWriteArraySet和HashSet虽然都继承于共同的父类AbstractSet；但是，HashSet是通过“散列表”实现的，而CopyOnWriteArraySet则是通过“动态数组(CopyOnWriteArrayList)”实现的，并不是散列表。
并发List：
- CopyOnWriteArrayList：它是 ArrayList 的线程安全的变体，其中改变数组内容的写操作通常通过复制底层数组来实现，允许存储 null 元素。即当对象进行写操作时，使用了Lock锁做同步处理，内部拷贝了原数组，并在新数组上进行添加操作，最后将新数组替换掉旧数组；若进行的读操作，则直接返回结果，操作过程中不需要进行同步。
并发 Queue：
- ConcurrentLinkedQueue：是一个适用于高并发场景下的队列，它通过无锁的方式(CAS)，实现了高并发状态下的高性能。它不提供阻塞等待，队列为空时 poll() 返回 null。BlockingQueue 是一类接口，是否更快要看具体实现和使用场景，不能直接比较。
- BlockingQueue：与 ConcurrentLinkedQueue 的使用场景不同，BlockingQueue 的主要功能并不是在于提升高并发时的队列性能，而在于简化多线程间的数据共享。BlockingQueue 提供一种读写阻塞等待的机制，即如果消费者速度较快，则 BlockingQueue 则可能被清空，此时消费线程再试图从 BlockingQueue 读取数据时就会被阻塞。反之，如果生产线程较快，则 BlockingQueue 可能会被装满，此时，生产线程再试图向 BlockingQueue 队列装入数据时，便会被阻塞等待。
并发 Deque：
- LinkedBlockingDeque：是一个线程安全的双端队列实现。它的内部使用链表结构，每一个节点都维护了一个前驱节点和一个后驱节点。LinkedBlockingDeque 的入队、出队共用一把 ReentrantLock，通过条件变量等待队列非空或未满；等待时会释放锁，让其他线程继续入队或出队。
- ConcurrentLinkedDeque：ConcurrentLinkedDeque是一种基于链接节点的无限并发链表。可以安全地并发执行插入、删除和访问操作。当许多线程同时访问一个公共集合时，ConcurrentLinkedDeque是一个合适的选择。
# Collections和Collection的区别
- Collection 是 Java 集合框架中的一个接口，是 List、Set、Queue 等接口的上层接口，Map 不继承它。它定义了一组通用的操作和方法，如添加、删除、遍历等，用于操作和管理一组对象。List、Set、Queue 都是它的子接口，ArrayList、HashSet 等才是具体实现类。
- Collections（注意有一个s）是Java提供的一个工具类，位于java.util包中。它提供了一系列静态方法，用于对集合进行操作和算法。Collections类中的方法包括排序、查找、替换、反转、随机化等等。这些方法可以对实现了Collection接口的集合进行操作，如List和Set。
# 集合遍历的方法有哪些？
在Java中，集合的遍历方法主要有以下几种：
- 普通 for 循环： 可以使用带有索引的普通 for 循环来遍历 List。
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
for (int i = 0; i < list.size(); i++) {
String element = list.get(i);
System.out.println(element);
}
- 增强 for 循环（for-each循环）： 用于循环访问数组或集合中的元素。
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
for (String element : list) {
System.out.println(element);
}
- Iterator 迭代器： 可以使用迭代器来遍历集合，特别适用于需要删除元素的情况。
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()) {
String element = iterator.next();
System.out.println(element);
}
- ListIterator 列表迭代器： ListIterator是迭代器的子类，可以双向访问列表并在迭代过程中修改元素。
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
ListIterator<String> listIterator= list.listIterator();
while(listIterator.hasNext()) {
String element = listIterator.next();
System.out.println(element);
}
- 使用 forEach 方法： Java 8引入了 forEach 方法，可以对集合进行快速遍历。
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.forEach(element -> System.out.println(element));
- Stream API： Java 8的Stream API提供了丰富的功能，可以对集合进行函数式操作，如过滤、映射等。
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.stream().forEach(element -> System.out.println(element));
这些是常用的集合遍历方法，根据情况选择合适的方法来遍历和操作集合。
需要注意，LinkedList 不适合用 get(i) 配合普通 for 循环遍历，因为每次 get 都要重新定位节点，整轮遍历可能达到 O(n²)。用增强 for 或 Iterator 才是 O(n)。forEach 和 Stream 主要是写法更简洁，并不代表一定比普通循环更快。
# fail-fast 是什么？线程安全的集合遍历就一定能看到最新数据吗？
fail-fast 就是“快速失败”：遍历时发现集合被意外修改，就尽早抛出 ConcurrentModificationException，帮助我们发现错误。
以 ArrayList 为例，集合用 modCount 记录结构修改，迭代器创建时保存 expectedModCount。调用 next 等方法时，如果两个值不一致，就说明迭代器之外有人改了结构。
这里要注意两点：
- 单线程也可能触发：比如在增强 for 里调用 list.remove，和有没有多个线程无关。
- 它不是线程安全机制：检查只是尽力而为，不保证一定抛异常，更不能靠“没有异常”判断并发操作安全。
并发集合的遍历也不一定看到最新的完整数据，常见的有两种方式：
- CopyOnWriteArrayList 的快照迭代：读取迭代器创建时的数组，之后的增删不会反映在本轮遍历里。
- ConcurrentHashMap 的弱一致迭代：允许一边遍历一边更新，不会因为并发更新抛 CME，但可能看到部分更新，不是某一时刻整个 Map 的快照。
所以，线程安全保证的是规定操作的并发安全，不等于遍历结果具有整体快照或实时一致性。
# 不可修改集合和不可变集合有什么区别？
不可修改，通常指不能通过当前引用调用 add、remove、set 等方法；不可变则强调对象状态不会再变化，这两个说法不能直接画等号。
比如 Collections.unmodifiableList 返回的是原列表的只读视图，原列表改了，视图也会跟着变：
List<String> source = new ArrayList<>(Arrays.asList("a", "b"));
List<String> view = Collections.unmodifiableList(source);
source.add("c");
System.out.println(view); // [a, b, c]
// view.add("d"); // 抛 UnsupportedOperationException
如果不希望原集合后续的增删影响结果，可以先复制，再包装：
List<String> snapshot = Collections.unmodifiableList(new ArrayList<>(source));
JDK 9 的 List.of、JDK 10 的 List.copyOf 也能创建不可修改列表，并且不允许 null 元素。List.copyOf 不会随着原集合的后续增删而变化。
但这些方式都不会自动深拷贝元素。如果里面放的是可变 User 对象，仍然可以修改 User 的字段。要做到整个对象结构都不可变，还需要元素本身不可变，或者按需求做防御性拷贝。
# List
常见的List集合（非线程安全）：
ArrayList基于动态数组实现，它允许快速的随机访问，即通过索引访问元素的时间复杂度为 O (1)。在添加和删除元素时，如果操作位置不是列表末尾，可能需要移动大量元素，性能相对较低。适用于需要频繁随机访问元素，而对插入和删除操作性能要求不高的场景，如数据的查询和展示等。LinkedList基于双向链表实现，头尾插入、删除是 O(1)；通过已经定位的迭代器插入、删除，也只需要调整节点指针。但 add(index, element)、remove(index) 需要先找到节点，最坏是 O(n)，不能笼统地说它在中间增删就比 ArrayList 快。
常见的List集合（线程安全）：
Vector和ArrayList类似，也是基于数组实现。Vector中的方法大多是同步的，这使得它在多线程环境下可以保证数据的一致性，但在单线程环境下，由于同步带来的开销，性能会略低于ArrayList。CopyOnWriteArrayList在对列表进行修改（如添加、删除元素）时，会创建一个新的底层数组，将修改操作应用到新数组上，而读操作仍然在原数组上进行，这样可以保证读操作不会被写操作阻塞，实现了读写分离，提高了并发性能。适用于读操作远远多于写操作的并发场景，如事件监听列表等，在这种场景下可以避免大量的锁竞争，提高系统的性能和响应速度。
# 讲一下java里面list的几种实现，几种实现有什么不同？
在Java中，List接口是最常用的集合类型之一，用于存储元素的有序集合。以下是Java中常见的List实现及其特点：
- Vector 是 Java 早期提供的线程安全的动态数组，如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。Vector 内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。
- ArrayList 是应用更加广泛的动态数组实现，它本身不是线程安全的，所以性能要好很多。与 Vector 近似，ArrayList 也是可以根据需要调整容量，不过两者的调整逻辑有所区别：Vector 默认按 2 倍扩容（如果构造时指定了
capacityIncrement，则按该值线性增长），而 ArrayList 则是增加 50%（即 1.5 倍）。 - LinkedList 顾名思义是 Java 提供的双向链表，所以它不需要像上面两种那样调整容量，它也不是线程安全的。
这几种实现具体在什么场景下应该用哪种？
- Vector 和 ArrayList 作为动态数组，其内部元素以数组形式顺序存储的，所以非常适合随机访问的场合。除了尾部插入和删除元素，往往性能会相对较差，比如我们在中间位置插入一个元素，需要移动后续所有元素。
- 而 LinkedList 在头尾操作，或者通过已经定位的迭代器增删节点时，只需要调整指针；按下标增删仍然要先遍历。选择时还要考虑节点的额外内存和数组更好的缓存局部性，多数普通列表场景优先考虑 ArrayList。
# list可以一边遍历一边修改元素吗？
在 Java 中，List在遍历过程中是否可以修改元素取决于遍历方式和具体的List实现类，以下是几种常见情况：
- 使用普通 for 循环遍历：可以用 set 替换元素；如果要删除，注意后面的元素会前移，直接 i++ 容易漏掉元素，可以倒序遍历，或者删除后调整索引。
import java.util.ArrayList;
import java.util.List;
public class ListTraversalAndModification {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
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);
}
}
- 使用 foreach 循环遍历：一般不建议在
foreach循环中直接修改集合结构（add/remove），因为foreach底层基于迭代器实现，集合结构被修改后，迭代器下一次调用next()时会检测到modCount != expectedModCount，从而抛出ConcurrentModificationException异常。注意：对 ArrayList 来说，"替换元素值"（即list.set(i, newValue)）并不会改变modCount，所以这种替换不会触发它的迭代器检查；成功增删元素则会改变结构。不过 fail-fast 只是尽力检测，并不保证每次修改都一定抛异常。下面是一个会抛 CME 的反例：
import java.util.ArrayList;
import java.util.List;
public class ListTraversalAndModification {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
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
}
}
System.out.println(list);
}
}
- 使用迭代器遍历时：如果需要在遍历过程中删除元素，应使用
Iterator.remove()；如果需要替换元素，使用ListIterator.set()是最通用、最推荐的做法。直接调用List.set(index, value)虽然不会抛 CME（因为它不改变结构），但通过ListIterator.set()更符合"遍历中修改"的惯用写法，可读性也更好。
import java.util.ArrayList;
import java.util.ListIterator;
public class ListTraversalAndModification {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
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]
}
}
对于 CopyOnWriteArrayList，可以在遍历时调用列表自身的 add、remove 等方法，迭代器仍然读创建时的快照，不会抛 ConcurrentModificationException。不过它的迭代器不支持 remove、set、add，会抛 UnsupportedOperationException。Vector 和 synchronizedList 并没有这种快照机制，不能把这个结论推广到所有线程安全的 List。
如果只是按条件删除，支持该操作的集合还可以直接使用 removeIf，比如 list.removeIf(num -> num % 2 == 0)，通常比自己维护下标更清楚。
# list如何快速删除某个指定下标的元素？
ArrayList提供了remove(int index)方法来删除指定下标的元素，该方法在删除元素后，会将后续元素向前移动，以填补被删除元素的位置。如果删除的是列表末尾的元素，时间复杂度为 O (1)；如果删除的是列表中间的元素，时间复杂度为 O (n)，n 为列表中元素的个数，因为需要移动后续的元素。示例代码如下：
import java.util.ArrayList;
import java.util.List;
public class ArrayListRemoveExample {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
// 删除下标为1的元素
list.remove(1);
System.out.println(list);
}
}
LinkedList的remove(int index)方法也可以用来删除指定下标的元素。它需要先遍历到指定下标位置，然后修改链表的指针来删除元素。最坏时间复杂度为 O(n)，n 为集合元素总数；它会根据下标离头还是尾更近，选择从哪一端开始遍历。不过，如果已知要删除的元素是链表的头节点或尾节点，可以直接通过修改头指针或尾指针来实现删除，时间复杂度为 O (1)。示例代码如下：
import java.util.LinkedList;
import java.util.List;
public class LinkedListRemoveExample {
public static void main(String[] args) {
List<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
// 删除下标为1的元素
list.remove(1);
System.out.println(list);
}
}
CopyOnWriteArrayList的remove方法同样可以删除指定下标的元素。由于CopyOnWriteArrayList在写操作时会创建一个新的数组，所以删除操作的时间复杂度取决于数组的复制速度，通常为 O (n)，n 为数组的长度。但在并发环境下，它的删除操作不会影响读操作，具有较好的并发性能。示例代码如下：
import java.util.concurrent.CopyOnWriteArrayList;
public class CopyOnWriteArrayListRemoveExample {
public static void main(String[] args) {
CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
list.add(1);
list.add(2);
list.add(3);
// 删除下标为1的元素
list.remove(1);
System.out.println(list);
}
}
# Arraylist和LinkedList的区别，哪个集合是线程安全的？
ArrayList和LinkedList都是Java中常见的集合类，它们都实现了List接口。
- 底层数据结构不同：ArrayList 使用动态数组实现，通过索引可以快速定位到元素。LinkedList 使用双向链表实现，每个节点都存储了元素本身以及指向前一个和后一个节点的指针，通过节点之间的指针关联来访问和操作元素。
- 插入和删除操作的效率不同：ArrayList 在尾部进行插入和删除操作时效率较高，因为不需要移动其他元素；但如果是在中间或开头插入、删除，就需要移动后面的所有元素，效率会比较低。LinkedList 在头部和尾部进行插入、删除操作时效率很高，只需要调整节点的指针即可；但如果是在中间位置操作，需要先从头或尾遍历链表找到目标位置，时间复杂度也是 O (n)，不过找到位置后只需要调整指针，不需要像 ArrayList 那样移动大量元素，所以在某些特定场景下还是有优势的，而且 LinkedList 实现了 Deque 接口，还可以当作双端队列、栈来使用。
- 随机访问的效率不同：ArrayList 支持通过索引直接快速访问元素，时间复杂度为 O (1)。LinkedList 不支持随机访问，想要获取某个位置的元素，必须从头节点或尾节点开始逐个遍历，时间复杂度为 O (n)。
- 空间占用：ArrayList 使用数组保存元素引用，虽然会有一定的容量浪费（比如实际元素没装满数组），但不需要为每个元素额外分配链表节点，元素对象本身也不一定连续存放。无参构造在 JDK 8 中会延迟分配实际的存储数组。LinkedList 每个节点除了存储元素引用，还需要额外存储两个指针（指向前一个和后一个节点），所以在存储相同数量元素的情况下，LinkedList 的空间占用通常会比 ArrayList 更大一些。
- 使用场景：ArrayList 更适合需要频繁随机访问元素，或者主要在尾部进行插入、删除操作的场景。LinkedList 更适合需要频繁在头部或尾部进行插入、删除操作，或者需要作为双端队列、栈使用的场景；如果是通过迭代器直接操作已知位置的节点，在中间插入、删除时也能发挥它调整指针快的优势。
- 线程安全：这两个集合都不是线程安全的，如果在多线程环境下使用，需要自己加锁保证线程安全，或者使用线程安全的 List 集合，比如 Vector、Collections.synchronizedList () 包装的 List，或者 CopyOnWriteArrayList。
# arraylist和vector 区别是什么？
ArrayList 和 Vector 都是 Java 中常用的动态数组实现，用于存储和操作对象集合，但它们在设计上有几个关键区别，主要体现在线程安全性、性能和功能细节上。
首先是线程安全性，这是最核心的区别。Vector 是线程安全的，它的大部分方法（比如 add、remove、get 等）都被 synchronized 修饰，这能保证单个同步方法的线程安全，但遍历、先判断再操作等复合逻辑，仍然可能需要在整个操作外层加锁。而 ArrayList 没有任何同步机制，是非线程安全的，在多线程并发修改时可能会出现数据不一致的问题，比如抛出 ConcurrentModificationException 异常。
正因为同步机制的存在，两者在性能上也有差异。由于 Vector 的方法需要加锁释放锁，在单线程环境下，它的操作效率通常比 ArrayList 低。所以如果是单线程场景，或者能自己保证线程安全的情况下，ArrayList 是更优的选择，性能更好。
另外，在扩容机制上，两者也有所不同。当集合元素数量超过当前容量时，都会自动扩容。Vector 默认的扩容策略是翻倍（如果没有指定容量增量的话），比如初始容量 10，满了之后会扩容到 20。而 ArrayList 默认扩容为原来的 1.5 倍（newCapacity = oldCapacity + (oldCapacity >> 1)），通常按这个比例增长，如果最小所需容量更大，就直接满足最小需求，相对来说扩容幅度更小，能在一定程度上节省内存空间。Vector 可以通过构造方法指定容量增量 capacityIncrement（按固定数值线性增长），灵活控制扩容幅度，而 ArrayList 没有这个功能。
总的来说，选择两者时主要看是否需要线程安全：如果是多线程环境且需要内置同步支持，可能会用到 Vector；但现在更多时候会用 ArrayList，因为它性能更好，而且在需要线程安全时，可以通过 Collections.synchronizedList () 方法将 ArrayList 包装成线程安全的集合，灵活性更高。
# ArrayList线程安全吗？把ArrayList变成线程安全有哪些方法？
不是线程安全的，ArrayList变成线程安全的方式有：
- 使用Collections类的synchronizedList方法将ArrayList包装成线程安全的List：
List<String> synchronizedList = Collections.synchronizedList(arrayList);
- 使用CopyOnWriteArrayList类代替ArrayList，它是一个线程安全的List实现：
CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>(arrayList);
- 使用Vector类代替ArrayList，Vector是线程安全的List实现：
Vector<String> vector = new Vector<>(arrayList);
包装成 synchronizedList 后，单个方法调用有同步保护，但遍历和复合操作还需要自己保证整体同步，而且所有访问都应该经过包装后的列表，不能绕过它操作原 ArrayList。
List<String> list = Collections.synchronizedList(new ArrayList<>());
synchronized (list) {
for (String value : list) {
System.out.println(value);
}
}
synchronized (list) {
if (!list.contains("a")) {
list.add("a");
}
}
注意锁的是返回的 list 对象，并且迭代器也应该在同步块里创建。CopyOnWriteArrayList 适合读多写少；如果是写入很多、需要复合操作的场景，统一加锁的列表通常更合适。
# 为什么ArrayList不是线程安全的，具体来说是哪里不安全？
ArrayList 的问题在于：**检查容量、写入元素、更新 size 这几个步骤没有同步保护，整个 add 操作不是原子的。**并发时可能出现元素被覆盖、size 不准确、索引越界，扩容竞争还可能让部分位置出现 null。
以 JDK 8 的 add 为例：
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
大体可以分为三步：
- 判断当前容量是否够用，不够就创建更大的数组并复制数据；
- 取得写入位置，并更新 size；
- 把元素写入数组。
注意，size++ 是后缀自增，表达式返回旧值作为下标，更新 size 发生在数组赋值完成之前，不能简单理解成“先写元素，再执行 size++”。
下面用几个例子说明：
- 元素覆盖、size 少算：两个线程都读到 size 为 5，都选择下标 5 写入，并把 size 更新为 6。结果本来添加了两个元素，却可能只保留一个。
- 索引越界：size 为 9，数组容量为 10，两个线程都通过了容量检查。线程 1 写入下标 9，并把 size 更新为 10；线程 2 随后执行写入表达式，取得下标 10，此时没有重新检查容量，就可能越界。
- 扩容时数据丢失或出现 null：一个线程复制旧数组，另一个线程还在向旧数组写入。如果新数组没复制到这次写入，随后又替换了数组引用，那么这次写入就可能丢失，新数组对应位置也可能保留 null。
所以，不能只把 size 改成 volatile 就认为安全了。volatile 解决可见性，不能让 size++ 和整个 add 过程变成原子操作。并发读写时需要统一加锁，或者选择合适的线程安全集合。
# ArrayList 和 LinkedList 的应用场景？
- ArrayList：适合普通列表、按下标访问、遍历，以及主要在尾部追加的场景。尾部追加的均摊时间复杂度是 O(1)，但单次扩容需要 O(n) 复制，所以“大小经常变化”并不代表 ArrayList 就不适合。
- LinkedList：适合头尾增删，或者通过已经定位的 ListIterator 连续增删节点的场景。如果每次都按下标定位，中间增删仍然是 O(n)，还要承担节点分配和额外指针的开销。
- 如果只是实现栈或双端队列：通常可以优先考虑 ArrayDeque，它用数组保存元素，头尾操作均摊 O(1)，也没有每个链表节点的额外开销。不过它不允许 null，也不是线程安全的。
# ArrayList的扩容机制说一下
ArrayList 底层是数组，size 是实际元素个数，capacity 是数组能容纳的元素个数，这两个概念要分清楚。
以 JDK 8 为例：
- 无参构造时，先使用一个共享的空数组，第一次 add 时才分配容量为 10 的数组。
- 如果通过 new ArrayList<>(20) 指定容量，会直接创建容量为 20 的数组，但 size 仍然是 0，不能马上调用 get(0) 或 set(0, value)。
- 容量不足时，通常计算 oldCapacity + (oldCapacity >> 1)，也就是原容量的约 1.5 倍。
- 如果新容量仍然小于本次所需容量，比如一次 addAll 很多元素，就以最小所需容量为准，并处理最大数组长度和溢出问题。
- 最后通过 Arrays.copyOf 创建新数组、复制原数组中的引用，再让 elementData 指向新数组。
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
1.5 倍主要是在空间浪费和复制次数之间做权衡：增长太小会频繁扩容，增长太大又会空出很多位置。移位只是计算方式，不能把“为了使用移位”当作选择这个比例的主要原因。
如果提前知道数据量，可以通过构造方法或 ensureCapacity 预留容量，减少复制。删除元素后不会自动缩容；如果确实需要释放多余容量，可以调用 trimToSize，但反复缩容、扩容也会增加开销。
# 线程安全的 List， CopyonWriteArraylist是如何实现线程安全的
CopyOnWriteArrayList底层也是通过一个数组保存数据，使用volatile关键字修饰数组，保证当前线程对数组对象重新赋值后，其他线程可以及时感知到。
private transient volatile Object[] array;
下面以 JDK 8 的 add 源码为例，写入时使用 ReentrantLock，避免多个写线程同时复制并覆盖结果。不同 JDK 版本的锁实现可能不同，但“写入串行化、复制数组、发布新数组”的思路一致。
public boolean add(E e) {
//获取锁
final ReentrantLock lock = this.lock;
//加锁
lock.lock();
try {
//获取到当前List集合保存数据的数组
Object[] elements = getArray();
//获取该数组的长度（这是一个伏笔，同时len也是新数组的最后一个元素的索引值）
int len = elements.length;
//将当前数组拷贝一份的同时，让其长度加1
Object[] newElements = Arrays.copyOf(elements, len + 1);
//将加入的元素放在新数组最后一位，len不是旧数组长度吗，为什么现在用它当成新数组的最后一个元素的下标？建议自行画图推演，就很容易理解。
newElements[len] = e;
//替换引用，将数组的引用指向给新数组的地址
setArray(newElements);
return true;
} finally {
//释放锁
lock.unlock();
}
}
看到源码可以知道写入新元素时，首先会先将原来的数组拷贝一份并且让原来数组的长度+1后就得到了一个新数组，新数组里的元素和旧数组的元素一样并且长度比旧数组多一个长度，然后将新加入的元素放置都在新数组最后一个位置后，用新数组的地址替换掉老数组的地址就能得到最新的数据了。
在我们执行替换地址操作之前，读取的是老数组的数据，数据是有效数据；执行替换地址操作之后，读取的是新数组的数据，同样也是有效数据，这样可以避免读写之间的锁竞争，更适合读多写少的场景；如果写入频繁，反复复制数组反而会增加开销。
现在我们来看读操作，它先取得当前数组引用，再从该数组读取元素，不需要获取写锁：
public E get(int index) {
return get(getArray(), index);
}
这里还有几个容易被追问的点：
- 迭代器读的是快照：创建迭代器时取得的数组不会被后续写操作修改，因此本轮遍历看不到之后的增删。后续新发起的 get 会读取当时已发布的数组，但并不保证多次读取组成一个整体快照。
- 复制的是引用：新旧数组里的元素对象仍然可能是同一个。集合线程安全，并不代表元素对象里的字段也线程安全。
- 适合读多写少：写操作通常要复制 O(n) 个引用；迭代器还可能持有旧数组，因此会增加内存占用。监听器列表、较少更新的配置列表比较合适，频繁写入的大列表不合适。
# List<>里面填基本数据类型为什么会报错？
List<> 等泛型集合类要求填充的必须是引用类型（对象类型），而不能直接使用基本数据类型（如 int、char、double 等），否则会编译报错。
这是因为 Java 的泛型机制在设计时就只支持引用类型，不支持基本数据类型。例如，下面的代码会报错：
// 错误示例：List 中直接使用基本数据类型 int
List<int> list = new ArrayList<>(); // 编译报错
解决的办法是，使用基本数据类型对应的包装类。因此，正确的写法是：
// 正确示例：使用包装类 Integer
List<Integer> list = new ArrayList<>();
list.add(10); // 自动装箱：int -> Integer
int num = list.get(0); // 自动拆箱：Integer -> int
这么设计的原因是：
- 泛型的类型擦除机制：Java 泛型的类型参数在编译后会被擦除为上界，没有显式上界时就是
Object，而Object只能接收引用类型，不能接收基本数据类型。 - 历史原因：Java 最初设计时基本数据类型和引用类型是严格区分的，泛型是后期（JDK 1.5）才引入的特性，为了兼容已有的类型系统，选择只支持引用类型。
通过使用包装类，结合 Java 的自动装箱（基本类型 → 包装类）和自动拆箱（包装类 → 基本类型）机制，可以很方便地在泛型集合中操作基本数据类型的数据。
# List和数组如何互相转换？
List 转数组
主要有两种方式，核心是用 List 的toArray()方法，重点注意「泛型和类型匹配」：
- 无参 toArray ()（返回 Object []，不推荐）
List<String> strList = new ArrayList<>();
strList.add("a");
strList.add("b");
// 返回Object[]，强转可能报错
Object[] objArr = strList.toArray();
这种方式返回的是 Object 数组，若强转成 String [] 会抛 ClassCastException，仅适合不确定数组类型的场景，基本不用。
- 带参 toArray (T [] a)（推荐，指定类型）
List<String> strList = new ArrayList<>();
strList.add("a");
strList.add("b");
// 方式1：传入指定长度的数组
String[] strArr1 = strList.toArray(new String[strList.size()]);
// 方式2：传入空数组，由方法创建合适长度的数组
String[] strArr2 = strList.toArray(new String[0]);
// 自定义对象List转数组
List<User> userList = new ArrayList<>();
userList.add(new User("张三", 20));
User[] userArr = userList.toArray(new User[0]);
这是最常用的方式，传入对应类型的数组，List 会把元素复制到该数组中，若传入的数组长度不足，会自动创建新数组，两种写法都正确，不必把某一种写法说成在所有 JDK 和场景下都更快。JDK 11 起还可以写 strList.toArray(String[]::new)。
数组转 List
核心是用Arrays.asList()，但要注意「返回的 List 固定大小、与原数组共享数据」和「基本类型数组的坑」：
- 普通对象数组转 List（常用）
String[] strArr = {"a", "b", "c"};
// 返回固定大小的List（属于Arrays内部类，不可add/remove）
List<String> strList1 = Arrays.asList(strArr);
// 若需要可变List，包装一层ArrayList
List<String> strList2 = new ArrayList<>(Arrays.asList(strArr));
strList2.add("d"); // 正常执行
Arrays.asList() 返回的是 java.util.Arrays.ArrayList，和常用的 java.util.ArrayList 不是同一个类。它不支持改变大小，但支持 set 替换元素，而且与原数组共享数据：
strList1.set(0, "x");
System.out.println(strArr[0]); // x，原数组也变了
strArr[1] = "y";
System.out.println(strList1); // [x, y]
如果需要自由增删，并且不希望列表的结构变化影响原数组，就像上面一样再套一层 new ArrayList<>(...)。不过这仍然只是复制元素引用，不是深拷贝。
- 基本类型数组转 List（避坑）
// 错误示例：int[]转List会变成List<int[]>，而非List<Integer>
int[] numArr = {1, 2, 3};
List<int[]> wrongList = Arrays.asList(numArr);
// 正确方式1：手动装箱（JDK8-）
List<Integer> numList1 = new ArrayList<>();
for (int num : numArr) {
numList1.add(num);
}
// 正确方式2：Stream流（JDK8+）
List<Integer> numList2 = Arrays.stream(numArr).boxed().collect(Collectors.toList());
基本类型数组（int []、long []）直接用Arrays.asList()会把整个数组当成一个元素，必须手动装箱或用 Stream 流转换为包装类（Integer）的 List。
# ArrayList 的 subList 是复制了一份新列表吗？
不是，subList 返回的是原列表一段范围的视图，范围是左闭右开，也就是包含 fromIndex，不包含 toIndex。
List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "d"));
List<String> sub = list.subList(1, 3);
sub.set(0, "B");
System.out.println(list); // [a, B, c, d]
sub.clear();
System.out.println(list); // [a, d]
通过 sub 修改会影响原列表。如果创建视图后，又绕过视图对原 ArrayList 做 add、remove 等结构修改，继续使用原来的 sub 就可能抛 ConcurrentModificationException，不要依赖它还能正常工作。
另外，一个很小的 subList 也可能持有整个原列表的引用，让大数组无法被回收。如果需要独立保存一段数据，可以写：
List<String> copy = new ArrayList<>(list.subList(0, 1));
这会复制列表中的元素引用，元素对象本身仍然共享。
# List 中的 remove(1) 删除的是下标还是元素？
删除的是下标 1，因为 List 的 remove 有两个重载：
- remove(int index)：按下标删除，返回被删除的元素。
- remove(Object value)：删除第一个匹配的元素，返回是否删除成功。
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 1));
list.remove(1);
System.out.println(list); // [1, 1]，删除了下标 1 的元素 2
list.remove(Integer.valueOf(1));
System.out.println(list); // [1]，删除了第一个值为 1 的元素
所以，整数列表中按值删除时，要显式传 Integer，或者把参数转成 Object。想删除所有值为 1 的元素，则可以用 list.removeIf(value -> Integer.valueOf(1).equals(value))。
# Set
# Java 集合中 List 和 Set区别是什么？
Java 里 List 和 Set 作为 Collection 的核心子接口，最核心的区别就是「是否允许元素重复」和「是否支持位置索引」，原理和使用场景也因此完全不同。
先说说 List，它是按位置组织的集合，允许元素重复。通常尾部追加时会保留添加顺序，但也可以按下标插入或排序，所以不一定始终等于最初的添加顺序。ArrayList、LinkedList 允许多个 null，但 List.of 等实现不允许 null。
比如往 ArrayList 里依次加 1、2、1，遍历出来还是 1、2、1，能通过下标（索引）直接访问元素，像 get (0) 就能拿到第一个元素，这是 List 独有的特性。底层实现比如 ArrayList 靠数组、LinkedList 靠双向链表，都是为了维护顺序和支持下标操作，适合需要按顺序存取、频繁根据位置访问元素的场景，比如购物车列表、订单明细这类要保留添加顺序的场景。
再看 Set，它的核心是「元素唯一」，不允许重复，HashSet / LinkedHashSet 最多只能存一个 null 值（TreeSet 默认不允许 null，因为排序时调用 compare 会抛 NPE），至于顺序则取决于具体实现，HashSet 不保证顺序，LinkedHashSet 保留插入顺序，TreeSet 按比较规则排序。
比如往 HashSet 里加 1、2、1，最终只会存 1 和 2，重复的 1 会被过滤掉。Set 判断元素重复的依据是 equals () 和 hashCode () 方法（HashSet、LinkedHashSet），或者元素的自然排序 / 自定义比较器（TreeSet），它没有下标，没法通过索引访问元素，只能遍历。适合需要去重的场景，比如用户标签、商品分类、抽奖名单（避免同一个用户重复中奖）这类不允许重复元素的场景。
补充一点特殊实现的差异：List 里的 Vector 是线程安全的，但性能差，现在基本不用；Set 里的 LinkedHashSet 既保证元素唯一，又能保留添加顺序，TreeSet 则会按元素大小排序，而 ArrayList、HashSet 都是非线程安全的。
# HashSet 怎么保证元素不重复？自定义对象为什么有时去重失败？
HashSet 底层用 HashMap 保存元素，元素作为 key，value 统一使用一个占位对象 PRESENT。
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
如果 Map 中已经有相同的 key，put 会返回原来的 PRESENT，add 就返回 false；如果是新 key，put 返回 null，add 返回 true。
判断相同元素时，先计算 hash 定位，再比较引用是否相同或 equals 是否相等。只有 hashCode 相同还不够，哈希冲突并不代表元素重复。
自定义对象去重失败，常见原因有两个：
- 没有重写 equals 和 hashCode，默认按对象身份判断，两个字段一样的新对象仍然可能被当成不同元素。
- 只重写 equals，没有配套重写 hashCode，逻辑相等的对象可能因为 hash 不同而没有被识别出来。
如果按用户 id 去重，就让两个方法都基于 id。存入后也不要修改参与这两个方法的字段，否则 contains、remove 可能找不到元素，Set 的去重行为也可能被破坏。
# 如何对Set排序？
Set 接口本身不规定排序规则。需要排序时，可以使用 TreeSet，或者先转成 List 再排序。比较数字时建议用 Integer.compare 等方法，直接相减可能溢出，导致比较结果错误。
TreeSet 底层是红黑树，插入时自动排序，支持「自然排序」（元素实现 Comparable）和「自定义 Comparator 排序」。
import java.util.TreeSet;
import java.util.Comparator;
import java.util.LinkedHashSet;
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;
}
// 按年龄升序，同龄时再按姓名排序
@Override
public int compareTo(User o) {
int result = Integer.compare(this.age, o.age);
return result != 0 ? result : this.name.compareTo(o.name);
}
@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) {
int result = Integer.compare(u2.age, u1.age); // 年龄降序
return result != 0 ? result : u1.name.compareTo(u2.name);
}
});
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 即可，它的基本增删查在哈希分布良好时平均是 O(1)，而 TreeSet 是 O(log n)：
import java.util.LinkedHashSet;
public class LinkedHashSetDemo {
public static void main(String[] args) {
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 + " ");
}
}
}
# Set集合有什么特点？如何实现key无重复的？
- set集合特点：Set集合中的元素是唯一的，不会出现重复的元素。
- set实现原理：Set 集合通过内部的数据结构来实现元素的无重复，不同实现去重方式不同：
- HashSet / LinkedHashSet：底层是哈希表，插入元素时先用
hashCode()定位桶，再用equals()比较是否已存在相同元素，存在则不再插入； - TreeSet：底层是红黑树，插入元素时不调用
hashCode/equals，而是用Comparable.compareTo()（自然排序）或自定义Comparator.compare()的返回值是否为 0 来判断是否重复。
- HashSet / LinkedHashSet：底层是哈希表，插入元素时先用
# 有序的Set是什么？记录插入顺序的集合是什么？
- "有序" 的 Set 有 TreeSet 和 LinkedHashSet，但两者"有序"的含义并不一样：
- TreeSet 基于红黑树实现，元素按"自然顺序（natural ordering，即
Comparable.compareTo()定义的顺序）"或自定义Comparator排序存储，属于"按值排序"。 - LinkedHashSet 基于哈希表 + 双向链表实现，链表记录了元素的插入顺序，遍历时按插入顺序输出，属于"保留插入顺序"（注意：这不是"自然顺序"，和元素值的大小无关）。
- TreeSet 基于红黑树实现，元素按"自然顺序（natural ordering，即
- 记录插入顺序的集合通常指的是 LinkedHashSet，它既保证元素唯一，又能按插入顺序遍历，当你需要"去重 + 保留添加顺序"时它是首选。
# TreeSet 为什么会把两个不同的对象当成重复元素？
因为 TreeSet 判断重复看的是 compareTo 或 Comparator.compare 的结果是否为 0，不是看两个对象是不是同一个引用，也不是直接调用 equals。
比如只按年龄排序，两个人即使姓名不同，只要年龄一样，比较结果就是 0，TreeSet 就只会保留其中一个。
TreeSet<String> set = new TreeSet<>(Comparator.comparingInt(String::length));
set.add("ab");
set.add("cd");
System.out.println(set.size()); // 1，因为两个字符串长度相同
如果长度相同时还要保留不同字符串，就需要加第二个比较条件：
Comparator<String> comparator = Comparator.comparingInt(String::length)
.thenComparing(Comparator.naturalOrder());
TreeSet<String> set = new TreeSet<>(comparator);
比较器的“相等”最好和 equals 的“相等”一致，才能符合 Set 的通用约定。如果只是想把所有元素排个序，不想让比较器影响去重规则，可以先转成 List 再排序。
TreeMap 也一样，比较结果为 0 的 key 会被当成同一个 key，后插入的 value 会替换之前的 value。
# Map
常见的Map集合（非线程安全）：
HashMap是基于哈希表实现的Map，它根据键的哈希值来存储和获取键值对，JDK 1.8 中使用数组 + 链表 + 红黑树来实现。HashMap是非线程安全的，在多线程环境下可能出现数据不一致的问题。需要区分两个时代：JDK 1.7 使用头插法 + 并发扩容时可能形成环形链表，进而触发get()时的死循环；JDK 1.8 改为尾插法后已经避免了旧版头插迁移导致的典型环形链表问题，但多线程put()仍存在数据覆盖和丢失等线程安全问题。LinkedHashMap继承自HashMap，它在HashMap的基础上，使用双向链表维护了键值对的插入顺序或访问顺序，使得迭代顺序与插入顺序或访问顺序一致。由于它继承自HashMap，在多线程并发访问时，同样会出现与HashMap类似的线程安全问题。TreeMap是基于红黑树实现的Map，它可以对键进行排序，默认按照自然顺序排序，也可以通过指定的比较器进行排序。TreeMap是非线程安全的，在多线程环境下，如果多个线程同时对TreeMap进行插入、删除等操作，可能会破坏红黑树的结构，导致数据不一致或程序出现异常。
常见的Map集合（线程安全）：
Hashtable是早期 Java 提供的线程安全的Map实现，它的实现方式与HashMap类似，但在方法上使用了synchronized关键字来保证线程安全。通过在每个可能修改Hashtable状态的方法上加上synchronized关键字，使得在同一时刻，只能有一个线程能够访问Hashtable的这些方法，从而保证了线程安全。ConcurrentHashMap在 JDK 1.8 以前采用了分段锁等技术来提高并发性能。在ConcurrentHashMap中，将数据分成多个段（Segment），每个段都有自己的锁。在进行插入、删除等操作时，只需要获取相应段的锁，而不是整个Map的锁，这样可以允许多个线程同时访问不同的段，提高了并发访问的效率。在 JDK 1.8 以后是通过 volatile + CAS 或者 synchronized 来保证线程安全的。
# 如何对map进行快速遍历？
如果同时需要 key 和 value，通常优先使用 entrySet() 或 map.forEach()，不用遍历 key 后再调用一次 get。Stream 更适合过滤、映射等处理，并不保证遍历更快。
- 使用for-each循环和entrySet()方法：这是一种较为常见和简洁的遍历方式，它可以同时获取
Map中的键和值
import java.util.HashMap;
import java.util.Map;
public class MapTraversalExample {
public static void main(String[] args) {
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中的键，可以使用keySet()方法，这种方式相对简单，性能也较好。
import java.util.HashMap;
import java.util.Map;
public class MapTraversalExample {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);
map.put("key3", 3);
// 使用for-each循环和keySet()遍历Map的键
for (String key : map.keySet()) {
System.out.println("Key: " + key);
}
}
}
- 使用迭代器：通过获取Map的entrySet()或keySet()的迭代器，也可以实现对Map的遍历，这种方式在需要删除元素等操作时比较有用。
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
public class MapTraversalExample {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);
map.put("key3", 3);
// 使用迭代器遍历Map
Iterator<Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Entry<String, Integer> entry = iterator.next();
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
}
}
- 使用 Lambda 表达式和forEach()方法：在 Java 8 及以上版本中，可以使用 Lambda 表达式和
forEach()方法来遍历Map，这种方式更加简洁和函数式。
import java.util.HashMap;
import java.util.Map;
public class MapTraversalExample {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);
map.put("key3", 3);
// 使用Lambda表达式和forEach()方法遍历Map
map.forEach((key, value) -> System.out.println("Key: " + key + ", Value: " + value));
}
}
- 使用Stream API：Java 8 引入的
Stream API也可以用于遍历Map，可以将Map转换为流，然后进行各种操作。
import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;
public class MapTraversalExample {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);
map.put("key3", 3);
// 使用Stream API遍历Map
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));
System.out.println(filteredMap);
}
}
# HashMap实现原理介绍一下？
在 JDK 1.7 及以前，HashMap 数据结构是数组和链表，HashMap通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，因为链表的查询时间是O(n)，所以冲突很严重，一个索引上的链表非常长，效率就很低了。
所以在 JDK 1.8 版本的时候做了优化：以 JDK 8 的 put 为例，TREEIFY_THRESHOLD 为 8：当桶中已有至少 8 个节点，再插入一个新节点（插入后长度至少为 9），且哈希表数组长度 ≥ 64（MIN_TREEIFY_CAPACITY）时，会把链表转换为红黑树，改善长链表的查询效率，通常可以接近 O(log n)；如果数组长度 < 64，则只会触发扩容（resize()），并不会立刻树化。反向地，在 resize() 过程中，若某个桶的节点数 ≤ 6（UNTREEIFY_THRESHOLD），红黑树会被退化回链表。
# HashMap 链表转红黑树、红黑树退化成链表的条件是什么？
以 JDK 8 为例，有三个常见常量：
- TREEIFY_THRESHOLD = 8：树化相关的链表长度阈值。
- MIN_TREEIFY_CAPACITY = 64：允许树化的最小数组容量。
- UNTREEIFY_THRESHOLD = 6：扩容拆分时，退化为链表的节点数阈值。
面试时不能只背“8 转树、6 转链表”，还要说明触发路径：
- 普通 put 追加链表节点时：桶中已有 8 个节点，再加一个达到 9 个，会尝试树化；数组容量小于 64 时先扩容，容量至少为 64 才转成树。compute 等其他写入路径的计数方式有差异，不能把“第 9 个”推广到所有方法。
- 扩容拆分树桶时：分别统计低位、高位两部分的节点数，某一部分不超过 6 个，就将那一部分退化为链表。
- 普通 remove 删除树节点时：还会根据树的结构判断是否退化，不是每删除一个节点都单纯比较“是否小于等于 6”。
为什么不一发生冲突就用树？因为树节点需要保存更多引用，维护成本比普通链表节点高。节点少的时候，链表更简单；冲突严重时再用树，可以兼顾空间和查询效率。
为什么先扩容？数组小时，不同 hash 可能只是因为下标位数不够才挤在同一个桶，扩容后有机会分散。如果所有 key 的 hash 都一样，扩容也不能把它们分开。
另外，红黑树树高是 O(log n)，但不能据此保证 HashMap 的任何树桶查找都一定是 O(log n)。大量 key 的 hash 完全相同，又无法通过 Comparable 区分方向时，查找可能搜索多个分支，仍然可能退化。
# HashMap链表发生转换后为什么不用平衡二叉树？
这里说的“平衡二叉树”通常指 AVL 树，红黑树本身也是一种自平衡二叉搜索树，所以问题实际是在比较红黑树和 AVL 树。
- AVL 树平衡要求更严格：每个节点的左右子树高度差不能超过 1，树通常更矮，适合特别关注查找性能的场景，但增删后可能需要更多平衡调整。
- 红黑树的平衡要求相对宽松：通过颜色和黑高规则限制树高，在保持 O(log n) 树高的同时，兼顾查找与更新成本。
- HashMap 的树只用于处理较长的冲突桶：节点还会不断插入、删除，红黑树能在查找效率和维护成本之间做一个比较合适的权衡。
不能说 AVL 每次修改都要大量旋转，也不能说 HashMap 的增删和查询一定一样多。选择红黑树是通用实现的权衡，不是说它在所有工作负载下都比 AVL 快。
# 了解的哈希冲突解决方法有哪些？
- 链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
- 开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。
- 再哈希法：发生冲突后换用其他哈希函数来确定候选位置。这里要和“扩容后重新分配元素”区分，不同语境下 rehash 的含义可能不同。
- 哈希桶扩容：扩大桶数组并重新分配键值对，有机会减少不同 hash 映射到同一下标的冲突。不过如果原始 hash 完全一样，单纯扩容也无法把它们分开。HashMap 主要使用链接法，扩容和树化是进一步的优化。
# HashMap是线程安全的吗？
hashmap不是线程安全的，hashmap在多线程会存在下面的问题：
- JDK 1.7 HashMap 采用数组 + 链表的数据结构，多线程背景下，在数组扩容的时候，存在 Entry 链死循环和数据丢失问题。
- JDK 1.8 HashMap 采用数组 + 链表 + 红黑树的数据结构，并在扩容时将同一个桶的节点拆成低位链表和高位链表，按原顺序连接，因此解决了 JDK 1.7 头插法在并发扩容时可能形成环形链表、导致死循环的问题。但 JDK 1.8 并没有解决多线程操作 HashMap 时的数据丢失问题：
resize()和put()都没有同步保护，并发扩容可能因多个线程竞争table、清空旧桶或改写节点的next引用而丢失节点；并发put()也可能发生数据覆盖。
如果要保证线程安全，可以通过这些方法来保证：
多线程环境可以使用 Collections.synchronizedMap 包装普通 Map，所有访问都应经过这个包装对象。遍历和复合操作还需要在同一把锁下执行。Hashtable 也能提供同步，但它们的主要操作共用一把对象锁，竞争较多时通常不如 ConcurrentHashMap 适合。
ConcurrentHashmap在JDK1.7和1.8的版本改动比较大，1.7使用Segment+HashEntry分段锁的方式实现，1.8则抛弃了Segment，改为使用CAS+synchronized+Node实现，同样也加入了红黑树，避免链表过长导致性能的问题。
# 在 Java 的 hashmap 中 get一个元素的过程是怎样的？
get方法的作用是传入我们需要获取的节点的key，然后将这个节点的value返回。首先先贴上get方法的代码：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
可以看到，get方法的代码非常的简洁，因为具体的代码都封装在了getNode这个方法里面，get方法只是对它进行了调用。
getNode方法接收两个参数，第一个参数是key的hash值，第二个参数就是key本身。下面我们就来看看getNode方法的源代码（通过注释，对源码进行了逐句解读）：
/**
* Implements Map.get and related methods
*
* @param hash key的hash值
* @param key key值
* @return the node, or null if none
*/
final HashMap.Node<K,V> getNode(int hash, Object key) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
// 以下if语句中判断三个条件：
// 1、HashMap中存储数据的数组table不为null；
// 2、数组table不为null，且长度大于0；
// 3、table已经创建，且通过hash值计算出的节点存放位置有节点存在；
// 若上面三个条件都满足，才表示HashMap中可能有我们需要获取的元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 定位到元素在数组中的位置后，我们开始沿着这个位置的链表或者树开始遍历寻找
// 注：JDK1.8之前，HashMap的实现是数组+链表，到1.8开始变成数组+链表+红黑树
// 首先判断这个位置的第一个节点的key值是否与参数的key值相等，
// 若相等，则这个节点就是我们要找的节点，将其返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 若上面的不满足，则判断第一个节点是否有下一个节点
// 若有，继续判断；若没有，那表示我们要找的节点不存在
if ((e = first.next) != null) {
// 若第一个节点是应该树节点，则通过红黑树的查找算法进行查找
if (first instanceof HashMap.TreeNode)
return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
// 若不是一个树节点，表示当前位置是一个链表，则使用do...while循环遍历查找
do {
// 若查找到某个节点的key值与参数的key值相等，则表示它就是我们要找的节点，将其返回
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中添加键值对，当调用HashMap的put()方法时，会按照以下详细流程执行（JDK8 1.8版本）：
第一步：计算 key 的 hash，如果数组还没有初始化，先初始化数组，再通过
(n - 1) & hash定位桶。
第二步：检查该位置是否为空（即没有键值对存在）
- 如果为空，则直接在该位置创建一个新的 Node 对象来存储键值对。将要添加的键值对作为该 Node 的键和值，并保存在数组的对应位置。新增成功后会统一更新 size 和 modCount，以便记录元素数量和检测结构变化。
第三步：如果该位置已经存在其他键值对，检查该位置的第一个键值对的哈希码和键是否与要添加的键值对相同？
- 如果相同，则表示找到了相同的键，直接将新的值替换旧的值，完成更新操作。
第四步：如果第一个键值对的哈希码和键不相同，则需要遍历链表或红黑树来查找是否有相同的键：
如果键值对集合是链表结构，从链表的头部开始逐个比较键的哈希码和equals()方法，直到找到相同的键或达到链表末尾。
- 如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。
- 如果没有找到相同的键，则将新的键值对添加到链表的尾部。
如果键值对集合是红黑树结构，在红黑树中使用哈希码和equals()方法进行查找。根据键的哈希码，定位到红黑树中的某个节点，然后逐个比较键，直到找到相同的键或达到红黑树末尾。
- 如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。
- 如果没有找到相同的键，则将新的键值对添加到红黑树中。
第五步：判断是否需要将链表转换为红黑树：
- 如果桶中原来已有至少 8 个节点，插入新节点后达到至少 9 个，并且数组长度大于等于 64，就会将链表转换为红黑树；满足上述节点数条件时，如果数组长度小于 64，则先扩容。
第六步：新增节点后更新 size、modCount，检查 size 是否超过 threshold。
- threshold 通常是容量乘以负载因子，默认负载因子为 0.75。只有新增映射才会增加 size；替换已有 key 的 value，不会增加 size，也不会因为这次替换而触发容量扩张。
第七步：扩容操作：
- 创建一个新的两倍大小的数组。
- 遍历旧数组中的每个键值对，根据
(e.hash & oldCap)的结果重新分配到新数组中的位置（要么原位置，要么原位置 + oldCap），无需重新计算 hash。 - 更新HashMap的数组引用和阈值参数。
第八步：完成添加操作。
此外，HashMap是非线程安全的，如果在多线程环境下使用，需要采取额外的同步措施或使用线程安全的ConcurrentHashMap。
# HashMap的put(key,val)和get(key)过程
- put：先计算 hash 并定位桶，数组未初始化时先初始化。空桶直接放入新节点，非空桶按链表或红黑树查找；找到相同 key 就替换 value，没有相同 key 就新增。新增后可能触发树化或扩容，替换已有 value 不会增加 size。
- get：同样先计算 hash 并定位桶，先比较桶头节点，没找到再沿链表或红黑树查找。判断 key 相同，要满足 hash 相同，并且 key 是同一对象，或者 equals 返回 true。找不到返回 null，不会触发树化或扩容。
这里的 hash 不是直接使用 hashCode()，JDK 8 会把高 16 位与低 16 位异或，让高位也能参与桶下标的计算。
# hashmap 调用get方法一定安全吗？
需要区分“能不能正常调用”和“并发访问是否安全”：
- map 本身为 null：调用 get 肯定会抛 NullPointerException。如果已经正常创建 HashMap，get(null) 是合法的，因为它支持 null key。
- 取出的 value 为 null：可能是 key 不存在，也可能是这个 key 映射的 value 就是 null。单线程下可以结合 containsKey 区分；如果把结果直接拆箱成基本类型，也可能抛空指针异常。
- 多线程只有读取：如果 HashMap 已经正确构造、安全发布，而且之后没人修改，多线程读取可以使用。
- 多线程同时读写：没有同步保护就不安全，可能读到旧值、缺失的数据或不一致的结构。JDK 8 的 get 本身没有 modCount 检查，不能把它说成会靠 ConcurrentModificationException 检测并发修改；这个异常主要出现在迭代、遍历等操作中。
Map<String, Integer> map = new HashMap<>();
Integer value = map.get("missing"); // null
// int count = map.get("missing"); // 自动拆箱 null，会抛空指针异常
如果需要并发读写，可以使用 ConcurrentHashMap，或者让所有读写都遵循同一套加锁规则。
# HashMap一般用什么做Key？为啥String适合做Key呢？
常见的 key 有 String、Integer、Long，也可以用自定义对象。关键不在于一定用哪一种类型，而在于 equals、hashCode 实现正确，而且参与这两个方法的字段在存入后保持稳定。
String 很适合做 key，因为它不可变，已经实现了按内容比较的 equals 和 hashCode，还会缓存计算过的哈希值。
如果 key 是一个可变对象，存入后又修改了参与 hashCode 或 equals 的字段，那么之后的 get、remove 可能找不到它。原因是节点还留在原来的桶里，但查询时已经按新的 hash 去定位了。
所以自定义 key 通常使用不可变字段。如果确实要修改这些字段，应先用旧状态的 key 删除映射，再修改并重新插入。
# 为什么HashMap要用红黑树而不是平衡二叉树？
红黑树也是自平衡二叉搜索树，这里通常是在问“为什么不用 AVL 树”。
AVL 对左右子树高度差的约束更严格，查询路径往往更短，但维护平衡的成本也可能更高。红黑树放宽了平衡要求，树高仍然是 O(log n)，适合兼顾查询和频繁更新的通用场景。
HashMap 只在哈希冲突较严重的桶里使用树，并不靠树维护整个 Map 的排序。面试时抓住“防止冲突桶过长”和“查询、更新成本的权衡”这两点就可以，不要把红黑树说成不需要旋转或调整。
# hashmap key可以为null吗？
可以为 null。
- hashMap中使用hash()方法来计算key的哈希值，当key为空时，直接令key的哈希值为0，不走key.hashCode()方法；
- hashMap虽然支持key和value为null，但是null作为key只能有一个，null作为value可以有多个；
- 因为hashMap中，如果key值一样，那么会覆盖相同key值的value为最新，所以key为null只能有一个。
# 重写HashMap的equal和hashcode方法需要注意什么？
准确来说，重写的是 key 对象的 equals() 和 hashCode()，不是 HashMap 自身的方法。
HashMap 先根据 hashCode 计算桶位置，再比较 key 是否相同。重写时需要注意：
- equals 相等，hashCode 必须相同，所以一般要配套重写。
- hashCode 相同，不代表 equals 相等，不同对象可能发生哈希冲突，HashMap 会继续比较 key。
- equals 要满足自反性、对称性、传递性、一致性，并且与 null 比较返回 false。
- 两个方法应基于同一套用于判断对象身份的字段，存入集合后不要修改这些字段。
比如用用户 id 作为唯一标识，就应让 equals 比较 id，hashCode 也基于 id 计算，而不是一个按 id、另一个按姓名。
这些规则同样适用于 HashSet、LinkedHashSet。不过 TreeMap、TreeSet 判断键或元素重复，依赖的是比较结果是否为 0，不能说所有去重集合都依赖 hashCode。
# 重写HashMap的equal方法不当会出现什么问题？
如果只重写 equals，没有配套重写 hashCode，就可能出现两个逻辑上相等的 key 却得到不同的 hash 值。
这样会带来两个常见问题：
- 重复存储：本来应该覆盖同一条映射的两个 key，没有被判断为同一个 key，结果都存进了 Map。
- 查询或删除失败：用一个 equals 相等的新对象去 get、remove，可能因为 hash 不同而找不到原来的映射。
另一种情况是 equals 写得过于宽松，比如只按年龄判断两个用户相等，那么两个同龄用户就可能被当成同一个 key，后插入的 value 覆盖之前的 value。
所以，“漏掉 hashCode”可能导致重复存储，“equals 错把不同对象判为相等”可能导致覆盖，这两个问题要分开说明。
# 列举HashMap在多线程下可能会出现的问题？
- JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。JDK 1.8 扩容时保持拆分后各条链表的相对顺序，避免了这个典型问题，但它仍然不是线程安全的。
- 多线程同时执行 put 操作，如果都判断同一个桶为空，再分别写入桶头，那就可能让前一个节点被后一个节点覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。
# HashMap的扩容机制介绍一下
hashMap默认的负载因子是0.75，即如果hashmap中的元素个数超过了总容量75%，则会触发扩容，扩容分为两个步骤：
- 第1步是对哈希表长度的扩展（2倍）
- 第2步是将旧哈希表中的数据放到新的哈希表中。
因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
如我们从16扩展为32时，具体的变化如下所示：
这里不需要重新调用 key.hashCode()。因为 n 变为 2 倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。
# HashMap的大小为什么是2的n次方大小呢？
HashMap 底层是「数组 + 链表 / 红黑树」的结构，当我们要存一个 key-value 时，第一步就是确定这个 key 存在数组的哪个位置（索引）。
HashMap 用的索引计算公式是：
索引 = hash & (length - 1)
这里的 hash 是经过扰动处理后的 key 的哈希值，length 是数组的容量（也就是我们说的 “大小”）。
这个公式的设计初衷是用位运算替代取模运算（因为位运算直接操作二进制位，速度远快于除法 / 取模），但它能生效的前提，就是 length 必须是 2 的 n 次方 —— 这是所有优化的基础。
下面我们逐个拆解原因，每个原因都配具体例子：
原因 1：保证「位运算等价于取模」，实现高效寻址
我们先看当 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 位截取下来。对非负 hash 来说，结果和 % length 一样；hash 为负时，Java 的 % 可能返回负数，而这个位运算仍然能得到合法的非负下标。
反例对比：如果 length 不是 2 的 n 次方
假设 length = 15（不是 2 的 n 次方），length - 1 = 14，二进制是 00001110（最后一位是 0）。
还是用 hash = 100（二进制 01100100）计算：
01100100 (hash = 100)
& 00001110 (length-1 = 14)
= 00000100 (结果 = 4)
看起来结果还行？但你再试一个 hash = 101（二进制 01100101）：
01100101 (hash = 101)
& 00001110 (length-1 = 14)
= 00000100 (结果还是 4！)
发现问题了吗？因为 length - 1 的最后一位是 0，不管 hash 值的最后一位是 0 还是 1，与运算后都会变成 0—— 这就导致索引的最后一位永远用不到，比如索引 1、3、5、7... 这些位置永远不会存数据，既浪费了数组空间，又大大增加了哈希碰撞的概率（不同的 hash 挤到同一个索引里）。
原因 2：让哈希值的低位更均匀，减少碰撞
刚才的反例已经提到了碰撞问题，这里再深入说一下：
HashMap 会对 key 的原始 hashCode 做扰动处理（比如 JDK1.8 里是 hash = (h = key.hashCode()) ^ (h >>> 16)），目的是让 hash 值的二进制位尽可能均匀分布。
但只有当 length - 1 的二进制是全 1 时，才能 “接住” 这些均匀分布的位。比如 length=16 时，length-1=15（1111），hash 值的低 4 位每一位都能影响最终索引；如果 length=15，length-1=14（1110），最后一位直接失效，相当于少了一位来分散 hash，碰撞概率自然就高了。
原因 3：优化扩容时的元素重分配，不用重新算 hash
HashMap 有个扩容机制：当新增后的元素个数超过 容量 * 负载因子（默认是 0.75）时，数组会扩容为原来的 2 倍。
如果容量始终是 2 的 n 次方，扩容时元素的新索引就不用重新计算完整的 hash，只需要看 hash 值的某一个高位就行 —— 这是 JDK1.8 的核心优化之一。
我们还是用具体例子说明：
- 旧容量 oldCap = 16（2^4），二进制是
00010000。 - 旧索引：假设某个 key 的 hash 值是
20（二进制00010100），旧索引是20 & 15 = 4。 - 扩容后新容量 newCap = 32（2^5），现在要算新索引。
关键逻辑：看 hash & oldCap 的结果
旧容量 oldCap = 16（00010000），我们计算 hash & oldCap：
00010100 (hash = 20)
& 00010000 (oldCap = 16)
= 00010000 (结果 = 16，不为 0)
- 如果结果为 0：说明 hash 值对应 oldCap 的那一位是 0，新索引 = 旧索引（还是 4）。
- 如果结果不为 0：说明那一位是 1，新索引 = 旧索引 + oldCap（4 + 16 = 20）。
你看，整个过程只需要做一次「与运算」，根本不用重新计算 hash，也不用再取模，速度非常快。而且通过这个高位判断，还能把原来挤在同一个旧索引里的元素，均匀拆分到新数组的两个索引位（旧索引和旧索引 + 旧容量），进一步降低了哈希碰撞。
总结
HashMap 的大小设计为 2 的 n 次方，是一个环环相扣的优化设计：
- 保证
hash & (length - 1)等价于取模，用位运算实现高效寻址； - 让
length - 1的二进制全 1，接住 hash 值的均匀分布，减少碰撞； - 为扩容优化铺路，不用重新算 hash，仅通过高位判断就能快速确定新索引。
# 往hashmap存20个元素，会扩容几次？
如果是 JDK 8、new HashMap<>()、默认负载因子 0.75、20 个不同 key，而且没有严重的哈希冲突，那么真正从已有容量向更大容量扩张只有一次：
- 创建 HashMap 时还没分配数组，第一次 put 时初始化为 16，threshold 为 12。
- 放入第 1 到第 12 个不同 key 时，不会因为 size 超过阈值而扩容。
- 放入第 13 个不同 key 后，size 为 13，超过 12，容量从 16 扩到 32，threshold 变为 24。
- 放到第 20 个不同 key 时，没有超过 24，不再扩容。
不过，如果问的是“resize() 调用了几次”，第一次初始化也走 resize()，所以是 两次调用：一次初始化，一次扩容。
还要注意，连续 put 同一个 key 只是在替换 value，不会让 size 不断增长；如果大量 key 挤在同一个桶里，容量不足 64 时，树化判断还会提前触发扩容。因此这道题要先说明初始容量、负载因子和 key 的分布，不能脱离条件回答。
# 预计放 20 个元素，new HashMap<>(20) 就能避免扩容吗？
在默认负载因子下，普通插入 20 个不同 key 通常可以。传入的 20 会向上取到 2 的幂，也就是 32，首次分配数组后 threshold 为 24，放 20 个没有超过阈值。
但 initialCapacity 表示桶容量的提示，不是“保证可以放多少个元素”的数量。比如 new HashMap<>(100) 最终数组容量是 128，默认 threshold 为 96，放第 97 个不同 key 时还是会扩容。
如果预计保存 expectedSize 个元素，可以先按负载因子估算容量，再由 HashMap 向上取整：
int expectedSize = 100;
int initialCapacity = (int) Math.ceil(expectedSize / 0.75d);
Map<String, Integer> map = new HashMap<>(initialCapacity);
这个例子首次分配的数组容量是 256，threshold 是 192。实际项目里还要考虑极端数据量下的溢出和内存开销；严重的桶冲突也可能触发额外扩容。这里主要是在减少因 size 超过阈值造成的扩容。
# 说说hashmap的负载因子
HashMap 负载因子 loadFactor 的默认值是 0.75，当 HashMap 中的元素个数超过了容量的 75% 时，就会进行扩容。
默认负载因子为 0.75，是因为它提供了空间和时间复杂度之间的良好平衡。
负载因子太低会导致大量的空桶浪费空间，负载因子太高会导致大量的碰撞，降低性能。0.75 的负载因子在这两个因素之间取得了良好的平衡。
# Hashmap和Hashtable有什么不一样的？Hashmap一般怎么用？
- 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方法查看某个键是否存在等
# LinkedHashMap 怎么保证有序？怎么用它实现 LRU？
LinkedHashMap 在 HashMap 的基础上，增加了一条贯穿所有节点的双向链表。哈希表负责快速查找，双向链表负责记录遍历顺序。
它支持两种顺序：
- 插入顺序：默认模式，按 key 第一次插入的顺序遍历，更新已有 key 的 value 不会把它移到末尾。
- 访问顺序：构造时把 accessOrder 设置为 true，get、put 等访问已有映射的操作会将对应节点移到末尾，头部就是最久没访问的节点。
实现简单的 LRU，可以使用访问顺序，再重写 removeEldestEntry，超过容量时删除最老的节点：
class LruCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
LruCache(int capacity) {
super(16, 0.75f, true);
if (capacity <= 0) {
throw new IllegalArgumentException("capacity must be positive");
}
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
LruCache<Integer, String> cache = new LruCache<>(2);
cache.put(1, "a");
cache.put(2, "b");
cache.get(1);
cache.put(3, "c");
System.out.println(cache.keySet()); // [1, 3]，2 最久没访问，被淘汰
这里还要注意，LinkedHashMap 不是线程安全的。访问顺序模式下，get 也可能调整链表，属于结构修改，所以并发使用时不能只给 put 加锁。
# TreeMap 和 HashMap 有什么区别？什么场景用 TreeMap？
- 底层结构：HashMap 是哈希表，JDK 8 中桶内可以是链表或红黑树；TreeMap 整个结构就是红黑树。
- 查找方式：HashMap 依赖 hashCode 和 equals；TreeMap 依赖 key 的自然顺序或 Comparator，比较结果为 0 就认为是同一个 key。
- 顺序：HashMap 不保证遍历顺序；TreeMap 按 key 的比较规则排序，并不是按 value 排序，也不是按插入顺序。
- 复杂度：哈希分布良好时，HashMap 的基本操作平均是 O(1)；TreeMap 的 get、put、remove 是 O(log n)。
如果只需要按 key 快速查找，通常选择 HashMap。如果需要排序、范围查询、寻找相邻 key，TreeMap 更合适。
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "a");
map.put(20, "b");
map.put(30, "c");
System.out.println(map.floorKey(25)); // 20，小于等于 25 的最大 key
System.out.println(map.ceilingKey(25)); // 30，大于等于 25 的最小 key
System.out.println(map.subMap(10, true, 30, false)); // {10=a, 20=b}
TreeMap 自然排序不允许 null key；如果自定义比较器能够处理 null，则可以支持。value 可以为 null。它本身也不是线程安全的，需要有序的并发 Map 时，可以考虑 ConcurrentSkipListMap。
# Map 的 keySet、values、entrySet 是一份副本吗？
不是，它们是原 Map 的视图，Map 修改后，视图也会反映变化；通过视图删除映射，也会影响原 Map。
以 HashMap 为例：
Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);
Set<String> keys = map.keySet();
keys.remove("a");
System.out.println(map); // {b=2}
for (Map.Entry<String, Integer> entry : map.entrySet()) {
entry.setValue(entry.getValue() + 1);
}
System.out.println(map); // {b=3}
keySet 是 Set，因为 key 唯一；values 是 Collection，因为 value 可以重复；entrySet 是包含键值对的 Set。通常这些视图支持删除，但不支持直接 add，因为缺少完整的 key-value 信息。
遍历 HashMap 时，如果要删除当前映射，使用视图迭代器的 remove，不要直接调用 map.remove。想要独立保存 key 列表，可以用 new ArrayList<>(map.keySet())，而不是长期保存视图并认为它不再变化。
# ConcurrentHashMap怎么实现的？
JDK 1.7 ConcurrentHashMap
在 JDK 1.7 中它使用的是数组加链表的形式实现的，而数组又分为：大数组 Segment 和小数组 HashEntry。 Segment 是一种可重入锁（ReentrantLock），在 ConcurrentHashMap 里扮演锁的角色；HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素。
JDK 1.7 ConcurrentHashMap 分段锁技术将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。
JDK 1.8 ConcurrentHashMap
在 JDK 1.7 中，ConcurrentHashMap 虽然是线程安全的，但在哈希冲突严重、单个桶链表过长时，查询需要遍历较多节点，而 JDK 1.8 则使用了数组 + 链表/红黑树的方式优化了 ConcurrentHashMap 的实现，具体实现结构如下：
JDK 1.8 ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。添加元素时首先会判断容器是否为空：
- 如果数组还没初始化，则通过 CAS 修改 sizeCtl，让一个线程负责初始化，其他线程等待或重试
- 如果容器不为空，则根据存储的元素计算该位置是否为空。
- 如果根据存储的元素计算结果为空，则利用 CAS 设置该节点；
- 如果根据存储的元素计算结果不为空，则使用 synchronized ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。
归纳起来就是：空桶写入用 CAS，非空桶写入通过 synchronized 协调，读取依赖安全发布和可见性机制。链表桶锁住头节点，树桶锁住 TreeBin 这个包装节点，粒度比 Segment 更细。写入发现桶已经迁移时，还会走协助扩容的流程。
另外，JDK 1.8 引入红黑树，主要改善单个桶冲突较严重时的查询。在能够根据 hash 或比较结果确定查找方向时，可以从长链表的 O(n) 降到 O(log n)；不能把它理解为任何 key 分布下都保证 O(log n)。
# ConcurrentHashMap 的 get 为什么通常不需要加锁？
以 JDK 8 为例，主要依靠安全发布和可见性保证，并不是因为“读取不会出问题”。
- table 是 volatile 引用，桶位置通过带有 volatile 语义的 tabAt 读取；只把数组引用声明成 volatile，并不能自动让每个数组槽位都变成 volatile。
- 节点的 key、hash 是 final，value 和 next 是 volatile，写线程发布节点、更新 value 后，读线程可以按对应的内存语义读取。
- 链表桶可以直接沿 next 查找；遇到扩容标记 ForwardingNode，就转到新数组查找，不需要等待整张表扩容完成。
- 树桶还有 TreeBin 的协调机制，必要时读线程可以沿链表查找，所以不能简单地说整个树桶只靠 volatile 就够了。
get 不需要像 Hashtable 那样获取整张表的对象锁，因此通常能与写操作并行。对于同一个 key，如果一次更新已经完成，之后观察到该更新的读取有对应的可见性保证；如果读写正在同时发生，则读到修改前或修改后的合法结果都有可能。
它也不能让多个 key 的读取成为一个原子快照。如果业务要求同时读取一组 key，并保证它们来自同一次更新，仍然需要额外的整体协调。
# ConcurrentHashMap 怎么扩容？扩容时其他线程还能读写吗？
JDK 8 的 ConcurrentHashMap 支持多个线程协助迁移，避免全部迁移工作都落在一个线程上。
大体过程是：
- 创建通常为原容量两倍的新数组，用 nextTable 记录。
- 通过 transferIndex 分配待迁移的桶区间，让参与线程领取不同的任务。
- 迁移链表或树桶时，按 hash 与旧容量对应位，把节点分到“原下标”和“原下标 + oldCap”。对非空桶的迁移会和该桶的写入协调。
- 某个旧桶迁移完成后，在旧桶放入 ForwardingNode，表示这个桶已经转移到新数组。
- 所有迁移任务完成后，让 table 指向新数组，更新扩容阈值。
扩容过程中，读线程遇到 ForwardingNode 可以继续到新数组查找；put 等写线程遇到这个标记，可以协助迁移，然后重试写入。尚未迁移的桶仍然会按原来的方式读写。
所以扩容不需要把整个 Map 的读写全部暂停，但同一个桶的写入与迁移仍然需要协调，不能说扩容过程完全无锁。
# ConcurrentHashMap 为什么不允许 null key 和 null value？
主要是为了让并发场景下的语义更明确，尤其是 null value。
HashMap 的 get 返回 null，可能表示 key 不存在，也可能表示 value 为 null。单线程里可以再用 containsKey 判断。但在并发环境下，两次调用之间可能已经有其他线程修改了 Map，就不能把这两个结果当成一个原子判断。
ConcurrentHashMap 不允许 null value，就能让 get 返回 null 明确表示“这次读取没有找到映射”，putIfAbsent 等方法的返回值也更容易理解。null key 同样被接口实现禁止，这是一种 API 设计选择，不是说哈希表底层无法为 null key 计算位置。
注意，这并不代表 get 返回 null 后，key 就一直不存在了；下一刻其他线程仍然可能插入。如果要“没有就添加”，应直接使用 putIfAbsent 或 computeIfAbsent。
# ConcurrentHashMap 是线程安全的，先 get 再 put 就一定安全吗？
不一定。单个方法线程安全，不代表多个方法组成的操作也具有原子性。
比如下面这个计数逻辑，两个线程可能同时读到 0，然后都写入 1，最终少算一次：
ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();
// 并发调用下面这行，可能丢失更新
counts.put("java", counts.getOrDefault("java", 0) + 1);
如果是累加，可以使用 merge，让同一个 key 的这次更新具有原子性：
counts.merge("java", 1, Integer::sum);
其他常见场景也有对应方法：
- 没有映射才添加：putIfAbsent。
- 没有映射才计算并添加：computeIfAbsent。
- 只有 value 仍是预期值才替换：replace(key, oldValue, newValue)。
- 只有 key-value 仍匹配才删除：remove(key, value)。
compute、merge 等回调应该保持简短，避免在里面做耗时操作或递归修改同一个 Map，以免阻塞其他更新或触发异常。
另外，如果 value 是一个 ArrayList，ConcurrentHashMap 只保护映射本身，不会让这个 ArrayList 的 add 自动变成线程安全。多个 key 之间的转账、联动更新，也需要额外的业务同步。
# ConcurrentHashMap 的 size 是怎么统计的？并发时能作为判断依据吗？
以 JDK 8 为例，它没有让所有写线程都竞争一个 size 变量，而是使用 baseCount 和 CounterCell 数组分散计数竞争，思路和 LongAdder 类似。
- 竞争较少时，通过 CAS 更新 baseCount。
- 竞争较多时，把更新分散到不同的 CounterCell。
- size 时，将 baseCount 和各个 CounterCell 的值相加。
这样能减少写线程在同一个计数器上的竞争，但相加期间其他线程可能继续增删，所以并发更新时的结果不代表整个 Map 在某个时刻的原子快照。没有并发修改时，可以得到准确数量。
因此，size、isEmpty 更适合统计和监控，不能直接用来做“容量没满就放入”这样的并发控制：即使 size 小于上限，真正 put 前也可能被其他线程抢先插入。需要严格的容量控制时，可以配合锁、信号量，或者使用有界阻塞队列。
# JDK 1.7 中的分段锁是怎么加锁的？
注意：分段锁是 JDK 1.7 ConcurrentHashMap 的实现，JDK 1.8 之后已经废弃了 Segment，改为对桶头节点加 synchronized，参考前面 ConcurrentHashMap 实现一节。
在 JDK 1.7 的 ConcurrentHashMap 中，将整个数据结构分为多个 Segment，每个 Segment 都类似于一个小的 HashMap，每个 Segment 都有自己的锁，不同 Segment 之间的操作互不影响，从而提高并发性能。
对于插入、更新、删除等操作，需要先定位到具体的 Segment，然后再在该 Segment 上加锁，而不是像 Hashtable 那样对整个表加锁。这样可以使得不同 Segment 之间的操作并行进行，提高了并发性能。
# 分段锁是可重入的吗？
JDK 1.7 ConcurrentHashMap中的分段锁是用了 ReentrantLock，是一个可重入的锁。
# 已经用了synchronized，为什么还要用CAS呢？
ConcurrentHashMap使用这两种手段来保证线程安全主要是一种权衡的考虑，在某些操作中使用synchronized，还是使用CAS，取决于具体操作能否用一次原子更新完成，并不是运行时简单根据竞争程度在两种方式之间切换。
比如：在putVal中，如果计算出来的hash槽没有存放元素，那么就可以直接使用CAS来进行设置值，这是因为在设置元素的时候，因为hash值经过了各种扰动后，造成hash碰撞的几率较低，那么我们可以预测使用较少的自旋来完成具体的hash落槽操作。
当桶位已经存在节点（发生 hash 碰撞）时，需要遍历链表或红黑树进行查找、替换或追加节点，操作步骤较多且需要保护整条链/树的结构，CAS 自旋已经不再适合，因此改用 synchronized 锁住桶的头节点来完成这部分逻辑。
# ConcurrentHashMap用了悲观锁还是乐观锁?
悲观锁和乐观锁都有用到。
添加元素时首先会判断容器是否为空：
如果数组还没初始化，则通过 CAS 竞争初始化资格，由一个线程完成初始化。
如果容器不为空，则根据存储的元素计算该位置是否为空。
如果根据存储的元素计算结果为空，则利用 CAS（乐观锁） 设置该节点；
如果根据存储的元素计算结果不为空，则使用 synchronized（悲观锁） ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。
# Hashtable 底层实现原理是什么？
- Hashtable的底层数据结构主要是数组加上链表，数组是主体，链表是解决hash冲突存在的。
- Hashtable是线程安全的，实现方式是Hashtable 的 put、get、remove 等主要访问方法使用 synchronized 关键字，当一个线程访问同步方法，另一个线程也访问的时候，需要等待持有同一把锁的线程释放锁。
# Hashtable线程安全是怎么实现的？
因为它的put，get做成了同步方法，保证了Hashtable的线程安全性，每个操作数据的方法都进行同步控制之后，由此带来的问题任何一个时刻只能有一个线程可以操纵Hashtable，所以其效率比较低。
Hashtable 的 put(K key, V value) 和 get(Object key) 方法的源码：
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;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)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 关键字来保证其线程安全。
在Java中，可以使用synchronized关键字来标记一个方法或者代码块，当某个线程调用该对象的synchronized方法或者访问synchronized代码块时，这个线程便获得了该对象的锁，其他线程暂时无法访问这个方法，只有等待这个方法执行完毕或者代码块执行完毕，这个线程才会释放该对象的锁，其他线程才能执行这个方法或者代码块。
# hashtable 和concurrentHashMap有什么区别
底层数据结构：
- jdk7之前的ConcurrentHashMap底层采用的是分段的数组+链表实现，jdk8之后采用的是数组+链表/红黑树；
- Hashtable采用的是数组+链表，数组是主体，链表是解决hash冲突存在的。
实现线程安全的方式：
- jdk8以前，ConcurrentHashMap采用分段锁，对整个数组进行了分段分割，每一把锁只锁容器里的一部分数据，多线程访问不同数据段里的数据，就不会存在锁竞争，提高了并发访问；jdk8以后，直接采用数组+链表/红黑树，并发控制使用CAS和synchronized操作，更加提高了速度。
- Hashtable：put、get、remove 等主要访问方法共用对象锁来保证线程安全，但是效率非常的低下，当一个线程访问同步方法，另一个线程也访问的时候，需要等待持有同一把锁的线程释放锁。
# 说一下HashMap和Hashtable、ConcurrentMap的区别
ConcurrentMap 是接口，定义了 putIfAbsent、条件删除、条件替换等并发操作；ConcurrentHashMap 是它的常见实现。下面比较的是 HashMap、Hashtable 和 ConcurrentHashMap 三个具体类。
- HashMap线程不安全，效率高一点，可以存储null的key和value，null的key只能有一个，null的value可以有多个。默认初始容量为16，每次扩充变为原来2倍。创建时如果给定了初始容量，则扩充为2的幂次方大小。底层数据结构为数组+链表，插入元素后如果链表长度大于阈值（默认为8），先判断数组长度是否小于64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
- Hashtable线程安全，效率低一点，其内部方法基本都经过synchronized修饰，不可以有null的key和value。默认初始容量为11，每次扩容变为原来的2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组+链表。它基本被淘汰了，要保证线程安全可以用ConcurrentHashMap。
- ConcurrentHashMap 是 Java 中的线程安全哈希表实现，它可以在多线程环境下并发进行读写操作，而不需要像 Hashtable 那样对整个表加锁。与 HashMap 不同，ConcurrentHashMap 不允许 null key 或 null value（会抛 NPE），原因是多线程下 null 无法区分「key 不存在」还是「key 对应的 value 就是 null」。需要区分两个版本：
- JDK 1.7 及以前：基于分段锁实现，将整个哈希表拆成多个 Segment，每个 Segment 相当于一个小型的 HashMap，拥有自己的数组和独立的
ReentrantLock。写操作只需要锁定对应的 Segment，不同 Segment 之间的写入可以并行，读操作基本不需要加锁（依赖 volatile 可见性）。 - JDK 1.8 及以后：取消了 Segment，直接在
table数组的头节点上加锁，底层结构变为 数组 + 链表 / 红黑树，使用volatile + CAS + synchronized组合保证线程安全——空槽位写入走 CAS 乐观更新，哈希碰撞时对桶的头节点synchronized加锁，锁粒度从"段"进一步缩小到"桶"，并发度更高。
- JDK 1.7 及以前：基于分段锁实现，将整个哈希表拆成多个 Segment，每个 Segment 相当于一个小型的 HashMap，拥有自己的数组和独立的
# Queue
# Queue 和 Deque 有什么区别？常用方法有什么区别？
Queue 是队列接口，普通队列通常先进先出，但 PriorityQueue 这类实现按优先级出队。Deque 是双端队列，两端都能插入、删除，可以用来实现队列或栈。
Queue 的几组方法，主要区别是操作失败时怎么处理：
- add 和 offer：都用于添加元素。有界队列满时，add 抛 IllegalStateException，offer 返回 false。
- remove 和 poll：都取出并删除队头。队列空时，remove 抛 NoSuchElementException，poll 返回 null。
- element 和 peek：都查看队头但不删除。队列空时，element 抛 NoSuchElementException，peek 返回 null。
Deque 对应提供 addFirst、addLast、pollFirst、pollLast 等方法。作为队列时从尾部添加、从头部取出；作为栈时在同一端 push、pop。
普通单线程栈或双端队列可以优先考虑 ArrayDeque。它不允许 null，便于用 poll 返回 null 表示队列为空；需要线程安全时，则选择并发队列或在外部加锁。
# PriorityQueue 的底层是什么？遍历结果一定有序吗？
PriorityQueue 底层是数组实现的二叉堆。默认是小顶堆，队头是自然顺序最小的元素，也可以传 Comparator 改变优先级。
- offer、poll：需要上浮或下沉，时间复杂度是 O(log n)。
- peek：直接看堆顶，时间复杂度是 O(1)。
- contains、remove(Object)：要查找具体元素，时间复杂度是 O(n)。
堆只保证父子节点满足堆序，不保证整个数组完全有序，所以 for-each 或迭代器遍历不一定按优先级排序。想按优先级输出，需要不断 poll：
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(3);
queue.offer(1);
queue.offer(2);
while (!queue.isEmpty()) {
System.out.println(queue.poll()); // 依次输出 1、2、3
}
poll 会删除元素，如果还要保留原队列，可以先用 new PriorityQueue<>(queue) 复制一份再处理。PriorityQueue 允许重复元素，不允许 null，也不是线程安全的；并发场景可以考虑 PriorityBlockingQueue。
# BlockingQueue 怎么实现生产者、消费者等待？常见实现怎么选？
BlockingQueue 在普通队列的基础上，提供了等待机制：队列空时，消费者可以等待；有界队列满时，生产者可以等待。
- put：空间不足时等待，直到能放入元素。
- take：没有元素时等待，直到能取出元素。
- offer(element, timeout, unit)、poll(timeout, unit)：最多等待指定时间，超时后分别返回 false 或 null。
常见实现有：
- ArrayBlockingQueue：固定容量的数组队列，入队和出队共用一把锁，适合需要明确容量上限的场景。
- LinkedBlockingQueue：链表队列，入队和出队使用不同的锁，可以提高两端操作的并发度。默认容量是 Integer.MAX_VALUE，实际使用通常应该根据任务量和内存设置上限。
- SynchronousQueue：不保存元素，每次交付都需要与另一端的接收配对，可以理解成直接交接任务。
- PriorityBlockingQueue：按优先级取元素，逻辑上无界；队列空时 take 会等待，但 put 不会因为达到固定容量而等待。
比如固定容量的任务队列：
BlockingQueue<String> queue = new ArrayBlockingQueue<>(100);
queue.put("task"); // 队列满时等待
String task = queue.take(); // 队列空时等待
put、take 可能抛 InterruptedException，实际使用时要按任务约定处理取消或恢复中断状态。与忙循环反复检查队列相比，阻塞队列通过锁和条件等待来协调线程，等待时会释放对应的锁，让其他线程继续完成入队或出队。
BlockingQueue 不允许 null，也没有统一的 close 方法。如果需要停止消费者，可以通过中断或者约定结束标记来实现。
最新的图解文章都在公众号首发，别忘记关注哦！！如果你想加入百人技术交流群，扫码下方二维码回复「加群」。
← Java基础面试题 Java并发编程面试题 →