1.数组和集合的区别:

-1.数组是固定长度的,创建后就无法改变,集合是动态的,可以动态添加和删除元素;
-2.数组可以包含基本数据类型和对象,集合只能包含对象;
-3.数组可以直接访问元素,集合需要遍历,使用迭代器或者其他方法访问元素;

2.常用的集合类:

-1.ArrayList:动态数组,实现类List接口,支持动态增长;
-2.LinkedList:双向链表,也实现了List接口,支持快速的插入与删除;
-3.HashMap:基于哈希表的Map实现,存储键值对,通过键快速查找值;
-4.HashSet:基于HashMap实现的Set集合,用于存储为一元素;
-5.TreeMap:基于红黑树实现的有序集Map集合,可以按照键的顺序排序;
-6.LinkedHashMap:基于哈希表的双向链表实现的Map集合,保持插入和访问顺序;
-7.PriorityQueue:优先队列,可以按照比较器后或者元素的自然顺序排序;

3,介绍java中的集合(具体图解看小林):

-1.List是有序的Collection,使用此接口可以精准控制每个元素的插入位置,用户能根据索引访问List中的元素;常用的实现类有:LinkedList,ArrayList,Vector,Stack;
–1.ArrayList是容量可变的非线程安全列表,底层是使用数组实现;当集合扩容时,会创建更大的数组,并把原数组复制到新数组;支持对元素的快速随机访问,但插入和删除速度慢;
–2.LinkedList本质时一个双向链表,与ArrayList相比插入删除更快,但随机访问很慢;

-2.Set不允许存在重复的元素,与List不同,Set中元素是无序的;常用的实现类有:HashSet,LinkedHashSet,TreeSet;
–1.HashSet: HashSet 是 基于哈希表（HashMap）实现的 Set 集合，它的核心特点是 元素不重复、无序。HashSet 不保证元素的存储顺序，也不会按照插入顺序或大小排序。判断元素是否重复时，依赖 hashCode() + equals() 方法：先通过 hashCode 定位桶，再通过 equals 精确比较。如果这两个方法没有正确重写，可能会出现“逻辑重复但实际存进去了”的问题。在性能方面，HashSet 的 增删查平均时间复杂度是 O(1)，是三种 Set 中效率最高的，适合对顺序没有要求、但需要快速查找的场景;
–2.LinkedHashSet:LinkedHashSet 是 HashSet 的子类，底层是 HashMap + 双向链表。它在 HashSet 的基础上，额外维护了一条 双向链表，用于记录元素的插入顺序，因此 元素不重复，但有序（按插入顺序）。去重规则仍然完全依赖 hashCode() 和 equals()。性能上，LinkedHashSet 相比 HashSet 略慢一点（因为要维护链表），但时间复杂度仍然接近 O(1)。当你 既想要 Set 去重，又希望遍历顺序可控 时，LinkedHashSet 是非常合适的选择
–3.TreeSet:TreeSet 是 基于红黑树（自平衡二叉搜索树）实现的 Set 集合，最大的特点是 自动排序。TreeSet 中的元素会按照 自然顺序（Comparable） 或 自定义比较器（Comparator） 排序存储，因此 元素不重复且有序（按排序规则）。
它判断元素是否重复，不再依赖 equals，而是依赖 compareTo / compare 返回值是否为 0。由于底层是红黑树，TreeSet 的 增删查时间复杂度是 O(log n)，性能不如 HashSet，但可以获得有序性，并支持诸如 first()、last()、subSet()、headSet() 等排序相关操作

-3.Map是一个键值对集合,存储键,值和之间的映射;Key无序,唯一;value不要求有序,允许重复;Map没有继承与Collection接口,从Map集合中检索元素时,只要给出键对象,就会返回对应的值对象;主要实现类:TreeMap,HashMap,HashTable,LinkedHashMap,ConcurrentHashMap;
–1.HashMap:HashMap 是 最常用的 Map 实现类，特点是 key 不重复、无序、非线程安全。底层结构在 JDK 8 之后是 数组 + 链表 + 红黑树。当哈希冲突较多、链表长度超过阈值（默认 8）并且数组长度达到 64 时，链表会转为红黑树，以提高查询效率。
判断 key 是否重复，依赖 hashCode() + equals()。HashMap 允许 一个 null key 和 多个 null value，在单线程环境下性能最好，增删查平均时间复杂度 O(1)
–2.LinkedHashMap:LinkedHashMap 是 HashMap 的子类，所以底层和HashMap一样但是在 HashMap 的基础上 维护了一条双向链表。它可以保证 遍历顺序，默认是 插入顺序，也可以通过构造参数设置为 访问顺序（常用于 LRU 缓存实现）。
除顺序特性外，LinkedHashMap 的行为与 HashMap 基本一致：非线程安全、允许一个 null key。相比 HashMap，性能略低，但换来了可预测的遍历顺序。
–3.HashTable:Hashtable 是 早期 JDK 提供的 Map 实现，现在已基本不推荐使用。数组和链表组成的;它的最大特点是 线程安全，因为所有公开方法都使用了 synchronized 修饰，导致 并发性能非常差。
Hashtable 不允许 null key，也不允许 null value，否则会抛出 NullPointerException。在设计理念和性能上都已被 ConcurrentHashMap 取代，更多是为了兼容老代码。
–4.TreeMap:TreeMap 是 基于红黑树实现的有序 Map。它会按照 key 的自然顺序 或 自定义 Comparator 进行排序存储，因此 key 有序、value 无序。判断 key 是否重复，依赖 compareTo / compare 返回 0，而不是 equals。
–5.ConcurrentHashMap:ConcurrentHashMap 是 高并发场景下的 Map 首选实现，特点是 线程安全且高性能。底层Node数组+链表+红黑树实现;
JDK 7：采用 分段锁（Segment），不同段并发操作;
JDK 8+：采用 CAS + synchronized + Node/红黑树，锁粒度更细;
ConcurrentHashMap 不允许 null key 和 null value（避免并发下歧义）。

4.Java中线程安全的集合:

-1.在java.util包中的线程安全的类主要2个,其他都是非线程安全的;
–1.Vector: Vector 的线程安全是通过 synchronized 关键字 实现的。在 Vector 中，几乎所有对共享数据进行操作的公共方法（如 add()、get()、remove()）都被声明为 synchronized 方法，这意味着同一时刻只能有一个线程进入这些方法，其他线程必须阻塞等待，从而保证对内部数组操作的原子性和数据一致性。这种实现方式属于 方法级别的互斥锁（对象锁），锁的是当前 Vector 实例（this）。虽然实现简单、可靠，但锁的粒度较大，即使是只读操作也需要加锁，导致并发性能较差，在高并发场景下容易成为性能瓶颈
–2.Hashtable: Hashtable 同样是通过 synchronized 关键字 来保证线程安全的。它对几乎所有公共方法（如 put()、get()、remove()）都进行了同步控制，使得多个线程在访问和修改底层哈希表结构时，必须依次获得对象锁，避免了并发修改导致的数据不一致问题。这种方式属于 对整个哈希表加锁的粗粒度同步，本质上是串行化所有访问操作。相比之下，现代并发集合（如 ConcurrentHashMap）通过分段锁或 CAS 等机制实现更细粒度的并发控制，因此 Hashtable 在线程安全性虽高，但并发性能较低，已逐渐被淘汰。

-2.在java.util.concurrent包提供的都是线程安全的集合:
并发Map:
-1.ConcurrentHashMap: ConcurrentHashMap 是高并发场景下最常用的 Map，实现线程安全的方式不是对整个 Map 加锁，而是通过 CAS + synchronized（JDK8 之后） 的细粒度锁机制，只在必要的桶或节点上加锁，允许多个线程同时读写不同位置的数据，从而大幅提升并发性能。它允许并发读操作几乎无锁进行，但不允许 key 或 value 为 null
-2.ConcurrtentSkipListMap:ConcurrentSkipListMap 是基于 跳表（Skip List） 实现的线程安全有序 Map，内部通过 CAS + 乐观并发控制 保证线程安全。它支持按 key 排序、范围查询等操作，在并发环境下性能稳定，适合替代 TreeMap 的并发版本
并发Set:
-1.ConcurrentSkipListSet:是线程安全的有序集合,底层时使用ConcurrentSkipListMap实现
-2.CopyOnWriteArraySet: CopyOnWriteArraySet 底层基于 CopyOnWriteArrayList 实现线程安全，所有写操作（add、remove）都会先复制一份底层数组，再在新数组上修改，读操作不加锁。适合 读多写少 的场景，但写操作成本较高，且无法保证元素的实时可见性
并发List:
–1.CopyOnWriteArrayList:CopyOnWriteArrayList 采用 写时复制（Copy-On-Write） 思想来实现线程安全。读操作直接访问旧数组，无需加锁；写操作通过 ReentrantLock 加锁并复制数组后再修改，保证线程安全和读性能。非常适合读多写少的并发场景
并发Queue:
–1.ConcurrentLinkedQueue:ConcurrentLinkedQueue 是基于 链表结构 的无界非阻塞队列，采用 CAS（无锁算法） 实现线程安全。多个线程可以同时入队和出队，不会发生阻塞，适合高并发、对实时性要求较高的场景
–2.BlockingQueue:BlockingQueue 是一组 支持阻塞操作的队列接口，当队列为空时，获取元素的线程会阻塞；当队列已满时，插入元素的线程会阻塞。其常见实现（如 ArrayBlockingQueue、LinkedBlockingQueue）通常基于 ReentrantLock + Condition 实现线程安全与线程间协作
并发Deque:
–1.LinkedBlockingDeque: LinkedBlockingDeque 是一个支持双端操作的阻塞队列，内部通常使用 ReentrantLock（部分实现使用两把锁）来保证线程安全，支持在队列两端进行阻塞式的插入和移除操作，适合生产者–消费者模型
–2.ConcurrentLinkedDeque: ConcurrentLinkedDeque 是基于链表的 非阻塞双端队列，通过 CAS 实现线程安全，支持高并发环境下在队列头尾同时进行操作，不会发生线程阻塞，吞吐量高

什么是 CAS（核心思想）

CAS 是一种 无锁并发控制机制，全称是 Compare And Swap（比较并交换）。
它的核心思想是：

只有当内存中的值等于预期值时，才把它修改为新值，否则什么都不做。

可以抽象为一个原子操作：

1
2
3
4
5
if (memoryValue == expectedValue) {
    memoryValue = newValue;
    return true;
}
return false;

这个比较 + 修改过程 由 CPU 保证原子性，不会被线程切换打断

什么是 ReentrantLock

ReentrantLock 是一种 显式锁（手动加锁 / 解锁），属于 互斥锁，功能比 synchronized 更强大。

“可重入”指的是：

同一个线程可以多次获取同一把锁，而不会发生死锁。

1
2
3
4
lock.lock();
lock.lock();   // 同一线程可以再次获取
lock.unlock();
lock.unlock();

5.Collection和Collections的区别:

-1.Collection是Java集合框架中的一个接口,他是所有集合类的基础接口;有许多实现类;
-2.Collections是Java提供的一个工具类;提供了一系列静态方法对集合操作;包含了排序,查找,替换,反转等,可以对实现了Collection接口的集合操作;

6.集合遍历的方法:

-1.普通for循环:

1
2
3
4
5
6
7
8
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

-2.增强for循环(for-each循环):

1
2
3
for (String s : list) {
    System.out.println(s);
}

-3.iterator迭代器:

1
2
3
4
5
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String s = iterator.next();
    System.out.println(s);
}

-4.ListIterator列表迭代器:

1
2
3
4
5
ListIterator<String> listIterator = list.listIterator();
while (listIterator.hasNext()) {
    String s = listIterator.next();
    System.out.println(s);
}

反向遍历:

1
2
3
while (listIterator.hasPrevious()) {
    System.out.println(listIterator.previous());
}

-5.使用for-each方法:

1
list.forEach(System.out::println);

-6.StreamApI:

1
2
3
list.stream()
    .filter(s -> s.startsWith("A"))
    .forEach(System.out::println);

7.List:

常用的非线程安全的List集合:
-1.ArrayList: 基于动态数组实现
-2.LinkedList: 基于双向链表实现

常用的线程安全的List集合:
-1.Vector: 与ArrayList类似也是基于动态数组实现;
-2.CopyOnwriteArrayList:

一、什么是动态数组（核心定义）

动态数组（Dynamic Array） 是一种 基于连续内存空间的线性数据结构，它的逻辑长度可以随着元素数量的变化而自动增长（或收缩）。

本质： 数组 + 扩容策略 + 拷贝机制

扩容的本质操作

当容量不足时：

  1. 申请一块更大的连续内存
  2. 创建新数组
  3. 将旧数组元素拷贝到新数组
  4. 让引用指向新数组
  5. 释放旧数组（由 GC 完成）

8.List是否能边遍历边修改元素?

在java中,取决于遍历方式和具体实现类;
-1.普通for遍历;
-2.线程安全的List,例如CopyOnWriteArrayList,采用写时复制机制,在遍历的同时可以修改操作不抛出异常,但可能读到旧的数据,因为修改操作是在新的副本上运行的;
-3.for-each循环遍历: 会破坏迭代器的内部状态,for-each底层是基于迭代器是一线的;会导致迭代器的预期结构和实际的不一样;
-4.迭代器遍历: 可以删除元素,但要替换元素,对于不可变对象(如Integer,String),必须通过ListIterator的set方法而不是直接通过List的Set方法,不然会抛出异常

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

1.ArrayList提供了remove(index)方法,删除后,后续元素会向前移动填补空缺,如果删除末尾时间复杂度为O(1),中间为O(n);
2.LinkedList也提供了remove方法,但是是遍历到下标位置,再修改链表指针删除,时间复杂度为O(n),n为删除元素下标,如果是头尾节点则为O(1);
3.CopyOnWriteArrayList也是通过remove方法,在写时会创建一个新的数组,所以时间复杂度取决于数组的复制速度,通常为O(n),n为数组长度;但在并发时不会影响读操作,有较好的并发性能;

10.ArrayList和LinkedList的区别,哪个是线程安全的?

1.底层数据结构不同: ArrayList 底层是基于 动态数组 实现的，元素在内存中是连续存储的；当容量不足时，会触发扩容并进行数组拷贝。LinkedList 底层是基于 双向链表 实现的，每个节点都包含前驱指针、后继指针以及数据本身，元素在内存中不是连续存储的
2.插入和删除操作效率不同: ArrayList 在插入或删除元素时，若发生在中间位置，需要对后续元素进行整体移动，因此时间复杂度为 O(n)；而 LinkedList 在已经定位到节点的前提下，插入和删除只需要修改节点之间的引用关系，时间复杂度为 O(1),在频繁增删的场景下更有优势，但是不支持随机访问,除了头节点,插入和删除复杂度也是O(n);
3.随机访问的效率不同: ArrayList 支持通过下标直接访问元素，由于底层是数组结构，可以根据索引快速定位，随机访问效率为 O(1)；LinkedList 不支持直接按索引访问，每次访问都需要从头或尾开始遍历链表，随机访问效率为 O(n)
4.空间占有: ArrayList 只存储元素本身，但由于扩容机制会预留一定的空闲空间，可能造成一定的空间浪费；LinkedList 的每个节点除了存储数据外，还需要额外存储前驱和后继指针，因此单个元素的空间开销更大，整体空间利用率相对较低
5.使用场景: ArrayList 更适合 查询频繁、随机访问多、插入删除较少 的场景；LinkedList 更适合 插入和删除操作频繁 的场景
6.线程安全: 这两个集合都不是线程安全的,Vector是线程安全的;

11.ArrayList和Vector的区别:

两者都是通过动态数组实现的,但是在线程安全性,性能和功能细节上还有区别;

1. 线程安全性：
ArrayList 是 非线程安全 的，在多线程并发访问并且存在修改操作时，可能出现数据不一致的问题；Vector 是 线程安全 的，它的大多数方法都使用了 synchronized 关键字进行同步，因此在多线程环境下可以保证操作的原子性，但同步范围较大。

2. 性能差异：
由于 ArrayList 没有内置的同步机制，在单线程或通过外部控制并发的场景下，性能明显优于 Vector；而 Vector 每个方法都进行同步控制,要加锁释放锁，即使在单线程环境下也会产生不必要的锁开销，导致整体性能较低。

3. 扩容机制不同：
ArrayList 在容量不足时，默认会扩容为原容量的 1.5 倍左右，扩容过程相对平滑；Vector 在扩容时可以通过 capacityIncrement 指定每次扩容的增量，若未指定，默认扩容为 原容量的 2 倍，扩容幅度较大。

4. 使用场景：
在 单线程或通过外部同步保证线程安全 的场景下，应优先选择 ArrayList 以获得更高的性能；在需要线程安全但并发度不高的场景下，Vector 可以使用，但在实际开发中更推荐使用 CopyOnWriteArrayList 或其他并发集合来替代 Vector。

12.将ArrayList变成线程安全的方法:

1.使用Collections类的synchronizedList()方法;

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

2.使用CopyOnWriteArrayList类代替;

1
List<String> list = new CopyOnWriteArrayList<>();

3.使用Vector类代替;

1
2
List<String> list = new ArrayList<>();
Vector<String> vector = new Vector<>(list);

13.ArrayList线程不安全的原因;(具体看小林)

高并发时:

1.部分值为null:

2.索引越界异常:

3.size和add的数量不一致:

14.ArrayList的扩容机制:

一、底层结构与初始容量

ArrayList 底层通过一个 Object[] elementData 数组来存储元素。
当使用无参构造方法创建 ArrayList 时，并不会立即分配一个固定大小的数组，而是先指向一个 空数组；只有在第一次调用 add() 方法时，才会真正创建数组。此时如果未显式指定容量，默认初始容量为 10。

1
2
List<Integer> list = new ArrayList<>(); // 此时还没有真正分配长度为 10 的数组
list.add(1); // 第一次 add 时才分配数组

二、扩容触发时机

每次调用 add(E e) 添加元素时，ArrayList 都会先判断当前数组容量是否足够存放新元素。如果发现：

1
当前 size + 1 > elementData.length

说明数组容量不足，就会触发扩容操作。这个判断在内部通过 ensureCapacityInternal() 方法完成。

三、扩容规则（增长策略）

当需要扩容时，ArrayList 并不是简单地只扩大 1 个空间，而是按一定比例增长。
默认的扩容策略是：新容量 = 旧容量 + 旧容量 / 2（约 1.5 倍）。

例如：

  • 原容量为 10 → 新容量为 15
  • 原容量为 15 → 新容量为 22
  • 原容量为 22 → 新容量为 33

这种设计可以在 减少扩容次数 和 避免一次性浪费过多内存 之间取得平衡。

四、扩容过程（数组拷贝）

扩容的核心步骤包括：

  1. 计算新数组的容量大小
  2. 创建一个新的 Object 数组
  3. 将旧数组中的元素复制到新数组中
  4. 将 elementData 指向新数组

这个过程本质上是一次 数组拷贝操作（System.arraycopy），时间复杂度为 O(n)，这也是为什么频繁扩容会影响性能。

五、指定容量对性能的影响

如果在创建 ArrayList 时就能预估元素数量，建议使用 带初始容量的构造方法：

1
List<Integer> list = new ArrayList<>(1000);

总结:
ArrayList 通过“容量不足触发扩容 → 按 1.5 倍增长 → 拷贝旧数组到新数组”的方式实现动态扩容，这种机制在保证访问效率的同时，兼顾了内存利用率，但在高并发或大量插入场景下需要格外注意性能和线程安全问题。

15.CopyOnWriteArrayList如何实现线程安全的:

CopyOnWriteArrayList 通过 “写时复制（Copy-On-Write）+ 读写分离” 的设计来实现线程安全，其核心思想是：读操作不加锁，写操作通过加锁并复制新数组来完成，从而保证并发安全性和可见性。下面从实现机制上详细说明。

一、核心思想：写时复制（Copy-On-Write）

CopyOnWriteArrayList 内部同样使用一个数组来存储元素，但在写操作（add、remove、set 等）时，并不是直接修改原数组，而是：

  1. 先将当前数组复制一份（创建新数组）
  2. 在新数组上完成修改操作
  3. 再将内部引用一次性指向新数组

这样可以保证：

  • 正在读取旧数组的线程不受任何影响
  • 读写操作互不干扰

二、写操作如何保证线程安全

写操作内部使用 ReentrantLock 进行加锁，保证同一时间只有一个线程可以进行写操作。

简化后的 add() 逻辑如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] oldArray = getArray();
        int len = oldArray.length;
        Object[] newArray = Arrays.copyOf(oldArray, len + 1);
        newArray[len] = e;
        setArray(newArray);   // 原子性替换引用
        return true;
    } finally {
        lock.unlock();
    }
}

关键点：

  • 写操作互斥执行（避免并发写冲突）
  • 修改发生在新数组上
  • 引用切换是原子的

三、读操作为什么不需要加锁

CopyOnWriteArrayList 的读操作（get、size、iterator 等）：

  • 直接读取内部数组引用
  • 不进行任何加锁操作

这是安全的原因在于：

  • 内部数组引用使用 volatile 修饰，保证内存可见性
  • 数组本身在读期间不会被修改（写操作永远操作新数组）

因此，读线程看到的始终是一个 稳定、不变的数组快照。

四、迭代器的线程安全特性

CopyOnWriteArrayList 的迭代器是 弱一致性（Weakly Consistent） 的：

  • 迭代器基于创建时的数组快照
  • 迭代过程中允许其他线程修改集合
  • 不会抛出 ConcurrentModificationException

但需要注意：

  • 迭代器 看不到之后发生的修改
  • 适合对实时一致性要求不高的场景

16.List<>泛型填写基本数据类型报错原因:

一、Java 泛型的本质限制

Java 泛型只支持 引用数据类型（Reference Type），不支持基本数据类型。
这是因为 泛型是在编译阶段通过类型擦除实现的，编译后泛型信息会被擦除为 Object 或上界类型，而基本数据类型并不是 Object 的子类，无法参与这种机制。

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

二、基本数据类型不是 Object 的子类

在 Java 的类型体系中：

  • int、double、char 等是基本数据类型
  • Integer、Double、Character 等是它们对应的 包装类

而泛型在运行时会被擦除为类似：

1
List<Object>

由于 int 不能向上转型为 Object，因此 编译器不允许基本类型作为泛型参数。

三、自动装箱并不能解决泛型定义问题

虽然 Java 支持 自动装箱 / 拆箱：

1
2
int a = 10;
Integer b = a;   // 自动装箱

但自动装箱只发生在 赋值和方法调用阶段，不会发生在泛型类型声明阶段，因此下面的写法依然非法：

1
List<int> list = new ArrayList<>(); // 编译错误

16.List和数组如何互相转换:

一.数组->List

1. 使用 Arrays.asList()（最常用）

1
2
3
4
5
6
7
8
9
10
import java.util.Arrays;
import java.util.List;

public class Test1 {
    public static void main(String[] args) {
        String[] arr = {"A", "B", "C"};
        List<String> list = Arrays.asList(arr);
        System.out.println(list);
    }
}

注意事项：

  • 返回的 List 是一个 固定长度的 List
  • 不支持 add()、remove()，否则会抛 UnsupportedOperationException
  • 对数组的修改会影响 List，反之亦然（共享同一份数据）

二、List → 数组

1. 使用 toArray()（无参）

1
2
3
4
5
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");

Object[] arr = list.toArray();

特点：

  • 返回的是 Object[]
  • 需要强转，不推荐在泛型场景下使用

2. 使用 toArray(T[] a)（推荐）

1
2
3
4
5
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");

String[] arr = list.toArray(new String[0]);

特点：

  • 返回类型安全的数组
  • 常用写法，推荐使用

三、基本数据类型数组与 List 的转换

⚠️ 基本类型数组不能直接转成 List<基本类型>

1
2
int[] arr = {1, 2, 3};
List<int> list = Arrays.asList(arr); // ❌ 错误

正确方式是使用包装类型：

1
2
Integer[] arr = {1, 2, 3};
List<Integer> list = Arrays.asList(arr);

或者手动转换：

1
2
3
4
5
int[] arr = {1, 2, 3};
List<Integer> list = new ArrayList<>();
for (int i : arr) {
    list.add(i);
}

17.Set

Java集合中List和Set的区别:

都是Collection的核心接口,最主要区别就是是否允许元素重复和是否保证有序;

如何对Set排序

要实现Set的排序,核心是要选待排序特性的Set实现类,或者把普通Set转为有序结构

TreeSet底层是红黑树,插入时自动排序,支持自然排序(元素实现Comparable)和自定义Comparator排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Student implements Comparable<Student> {
    String name;
    int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int compareTo(Student o) {
        return this.age - o.age; // 按年龄升序
    }
    
    @Override
    public String toString() {
        return name + ":" + age;
    }

}


public class Demo2 {
    public static void main(String[] args) {
        TreeSet<Student> set = new TreeSet<>();
        set.add(new Student("Tom", 20));
        set.add(new Student("Jerry", 18));
        set.add(new Student("Lucy", 22));

        System.out.println(set);
        // [Jerry:18, Tom:20, Lucy:22]
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Comparator;
import java.util.TreeSet;

public class Demo3 {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1; // 降序
            }
        });

        set.add(1);
        set.add(3);
        set.add(2);
    
        System.out.println(set); // [3, 2, 1]
    }

}

18.Map

1.常用的Map集合(非线程安全)
1.HashMap: HashMap 是最常用的非线程安全 Map，底层由数组 + 链表 + 红黑树（JDK 8 以后）组成，元素存储无序，允许一个 null key 和多个 null value，在哈希分布均匀的情况下，插入和查询的时间复杂度接近 O(1)，但在多线程环境下可能出现数据覆盖、死循环等并发问题，因此需要额外同步控制
2.LinkedHashMap: LinkedHashMap 继承自 HashMap，在其基础上通过维护一条双向链表来记录元素顺序，默认按插入顺序排序，也可以按访问顺序排序，支持 null key 和 null value，性能略低于 HashMap，但可以保证遍历顺序稳定，常用于需要保持顺序或实现 LRU 缓存的场景
3.TreeMap: TreeMap 是一个基于红黑树实现的有序 Map，会按照 key 的自然顺序或自定义 Comparator 进行排序，不允许 null key，但允许 null value，插入、删除和查询的时间复杂度为 O(log n)，适合需要排序、范围查询（如区间查找）的业务场景

2.常用的Map集合(线程安全)
1.Hashtable: Hashtable 是早期 JDK 提供的线程安全 Map，通过在方法上使用 synchronized 实现同步，底层为数组 + 链表结构，不允许 null key 和 null value，由于锁粒度大、并发性能差，在实际开发中已基本被淘汰
2.ConcurrentHashMap: ConcurrentHashMap 是高并发环境下推荐使用的线程安全 Map，JDK 8 采用数组 + 链表 + 红黑树结构，并结合 CAS 和 synchronized 实现桶级别加锁，不允许 null key 和 null value，在保证线程安全的同时大幅提升并发性能，广泛用于缓存和多线程共享数据场景

19.遍历Map集合的方法:

1. 使用 keySet() 遍历

通过 map.keySet() 获取所有 key，再根据 key 调用 map.get(key) 获取 value，逻辑直观但会进行一次额外的查找，效率相对较低，适合需要单独操作 key 的场景。

1
2
3
4
5
6
7
8
9
Map<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

for (String key : map.keySet()) {
    Integer value = map.get(key);
    System.out.println(key + " = " + value);
}

2. 使用 entrySet() 遍历（推荐）

通过 map.entrySet() 获取键值对集合，使用 Map.Entry 同时访问 key 和 value，避免重复查找，性能最好，是最常用、最推荐的遍历方式。

1
2
3
4
5
Map<String, Integer> map = new HashMap<>();

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

3. 使用 Iterator 迭代器遍历

通过 Iterator 遍历 entrySet() 或 keySet()，并且可以在遍历过程中安全地调用 iterator.remove() 删除元素，适合需要边遍历边删除的场景。

1
2
3
4
5
6
7
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    if (entry.getKey().equals("B")) {
        iterator.remove();
    }
}

4. 使用 forEach() 方法（JDK 8+）

通过 Map.forEach() 结合 Lambda 表达式遍历 Map，代码简洁直观，适合只读或简单业务逻辑处理，不适合在遍历过程中修改 Map 结构。

1
2
3
map.forEach((key, value) -> {
    System.out.println(key + " = " + value);
});

5. 使用 Stream API 遍历

通过 entrySet().stream() 进行流式遍历，适合结合过滤、排序、聚合等操作，但对于单纯遍历来说可读性和性能优势并不明显。

1
2
3
4
5
map.entrySet()
   .stream()
   .forEach(entry ->
       System.out.println(entry.getKey() + " = " + entry.getValue())
   );

20.HashMap实现原理

数据结构是数组+链表+红黑树，通过对 key 的 hashCode() 进行扰动计算得到 hash 值，再利用位运算 (n-1) & hash 定位数组下标，当多个 key 映射到同一位置时形成 链表，链表过长且数组容量足够时会转换为 红黑树 以提升查找效率，元素在数量超过阈值 capacity × loadFactor 时触发 扩容并重新分布节点，整个过程中通过 hash + equals 判断 key 是否相同，从而在保证性能的同时完成键值对的高效存取。

HashMap链表转换后为什么用红黑树不用平衡二叉树:

首先，红黑树在保证近似平衡的同时，维护成本更低。红黑树通过“颜色规则”保证最长路径不超过最短路径的 2 倍，虽然不如 AVL 树严格平衡，但已经足以将查找复杂度稳定在 O(log n)，而插入和删除时所需的旋转次数明显少于 AVL 树，这非常适合 HashMap 中频繁的插入操作。

其次，HashMap 的树结构并不是用来做范围有序查询的，而只是为了避免链表过长导致的 O(n) 查询问题，因此不需要 AVL 树那种高度严格的平衡性。红黑树在“性能足够好”的前提下，能减少结构调整的成本，更符合 HashMap 的使用目标。

再次，Java 标准库中已有成熟、稳定的红黑树实现经验（如 TreeMap、TreeSet），在 HashMap 中复用红黑树逻辑可以降低实现复杂度和维护风险，而 AVL 树在 JDK 中并没有现成的通用实现。

最后，从工程实践角度看，链表树化发生的概率本身就很低（需要大量 hash 冲突），红黑树在极端情况下提供稳定性能即可，没有必要为少数场景付出 AVL 树更高的维护成本。

一句话总结（面试版）：

HashMap 使用红黑树而不是平衡二叉树，是因为红黑树在保证 O(log n) 查找性能的同时，插入删除旋转更少、维护成本更低，更适合 HashMap 这种以插入为主、只需要“足够平衡”的数据结构

21.解决哈希冲突的方法

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

22.HashMap的线程安全问题

HashMap不是线程安全的,

1️⃣ 数据覆盖（丢失更新）

多个线程同时执行 put() 操作，可能在判断桶为空或 key 不存在时发生竞态条件，导致后写入的线程覆盖前一个线程的数据，最终出现 部分数据丢失，表现为 Map 中元素数量少于预期。

2️⃣ 读到 null 或脏数据

在并发写入过程中，一个线程还未完成节点插入，另一个线程已经执行 get()，由于写操作没有内存可见性保证，可能出现 key 已存在但 value 为 null，或读取到未完全初始化的对象。

3️⃣ size 不准确

size++ 不是原子操作，在多线程同时插入元素时会发生竞争，导致 size 的最终值 小于实际插入次数，从而影响扩容判断和业务逻辑。

23.Java中HashMap中get一个元素的过程:

HashMap 的 get 方法通过计算 hash 定位桶，先比较首节点，再根据桶结构遍历链表或红黑树，依靠 hash + equals 精确定位目标节点。

get()方法实现主要依赖于内部的,getNode()方法:

getNode() 内部实现流程（重点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab;
    Node<K,V> first, e;
    int n;
    K k;

    if ((tab = table) != null &&
        (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {

        // 1️⃣ 判断首节点
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k)))) {
            return first;
        }

        // 2️⃣ 桶为红黑树
        if (first instanceof TreeNode) {
            return ((TreeNode<K,V>)first).getTreeNode(hash, key);
        }

        // 3️⃣ 桶为链表
        for (e = first.next; e != null; e = e.next) {
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                return e;
            }
        }
    }
    return null;
}

getNode() 执行过程逐步解析

1️⃣ 判断 HashMap 是否可用

  • table 不为 null
  • 数组长度大于 0
  • 对应桶不为空

否则直接返回 null。

2️⃣ 比较桶中首节点

  • 先比 hash
  • 再比 key（== 或 equals）

👉 命中直接返回，避免不必要的遍历

3️⃣ 判断是否为红黑树结构

1
first instanceof TreeNode
  • 是 → 调用红黑树的查找逻辑（O(log n)）
  • 否 → 说明是链表

4️⃣ 遍历链表

  • 从 first.next 开始遍历
  • 对每个节点：
    • 先比 hash
    • 再比 key
  • 找到即返回

5️⃣ 未找到返回 null

遍历结束仍未命中，则说明 key 不存在。

关键细节（面试爱问）

1️⃣ 为什么先比较 hash？

  • hash 冲突概率低
  • 比 equals 性能高

2️⃣ 为什么先判断首节点？

  • 大多数桶只有一个元素
  • 减少遍历，提高性能

3️⃣ 为什么 null key 不会 NPE？

  • hash(null) 返回 0
  • key 比较时用 ==

24.HashMap中的put过程(具体图解看小林)

先通过扰动函数计算 hash，再通过 (n-1)&hash 定位桶，桶为空直接插入；桶不为空则判断 key 是否存在,存在则直接替换对应的value，不存在则在链表或红黑树中插入；当链表长度超过 8 且数组长度大于 64 时转为红黑树；最后 size++，当负载因子超过阈值(键值对数量即size与数组长度比值大于阈值,默认是0.75)则触发扩容,创建一个新的两倍大的数组,将旧的数组中的键值对重新计算存储到新的数组中,更新HashMap的数组引用和阈值参数

25.HashMap的get方法注意点

1.空指针异常 当HashMap没有初始化,用null作为键调用get方法会报错;但是初始化之后是可以的,因为HashMap允许null作为键

2.线程安全 HashMap不是线程安全的, 当一个线程使用get方法时,另一个线程修改了结构,则可能导致读取到错误的结果;

26.为什么HashMap一般用String作key

因为String对象是不可变的,一旦创建就不能被修改,确保了key的稳定性;如果key可变,可能会导致hashcode和equals方法的不一致;

HashMap中key允许为null但是只能有一个,但是value为null可以有很多;当key为空时,直接令哈希值为0,不走key.hashCode()方法计算

HashMap 的 size 只要是「新增键值对」，不管是放在桶上（数组位置）还是放在链表 / 红黑树里，都会 size++；
如果只是覆盖已有 key 的 value，size 不会增加。

27.重写HashMap的equals和hashcode方法需要注意什么?

当o1.equals(o2) 那么两者的哈希值一定要相同;
当o1.hashCode() == o2.hashCode() , o1 不一定要equals o2;

28.重写equals方法不当会有什么问题?

hashmap比较元素时,会先比较哈希值,再equals比较;
如果重写equals方法,不重写hashCode方法,会导致两个哈希值相同的元素但是equals不为true; hashmap会存储两个相同元素;于hashmap只能有唯一的key冲突;

29.HashMap在多线程中会出现的问题

HashMap 不是线程安全的，在多线程下可能出现：数据丢失、覆盖、size 不准确、死循环（JDK7）:JDK1.7之前使用头插法插入元素,在扩容时可能导致环形链表的出现,以后使用尾插法插入,不会导致死循环

30.HashMap的扩容机制

HashMap 在元素个数超过 threshold（capacity × loadFactor）时触发扩容，扩容时容量变为原来的两倍。扩容过程中不会重新计算 hash，而是通过判断 (hash & oldCap) 决定元素是在原位置还是移动到原索引加 oldCap 的位置，从而高效完成元素迁移。整个扩容过程时间复杂度为 O(n)，且在多线程环境下是不安全的

当容量从：

1
2
oldCap = 16 (0001 0000)
newCap = 32 (0010 0000)

只有 1 位发生变化（高了一位）

这正是后面元素“是否移动”的判断基础。

扩容后元素是如何移动的？（重点）

⚠️ HashMap 扩容不会重新算 hash，这是最精妙的地方

1️⃣ 核心判断公式（必背）

1
(hash & oldCap) == 0
  • 如果 hash & 0001 0000 == 0
    • 新索引 = 旧索引
  • 如果 hash & 0001 0000 == 1
    • 新索引 = 旧索引 + 16

📌 这就是 HashMap 扩容“只挪一半元素”的根本原因

HashMap 扩容时容量始终扩大为原来的两倍，这是因为下标计算使用 (n-1)&hash，要求容量必须是 2 的幂。扩容过程中不会重新计算 hash，而是通过判断 (hash & oldCap) 决定元素是在原位置还是移动到原索引加 oldCap 的位置，从而高效完成元素迁移

31.HashMap存20个元素会扩容几次

在默认初始容量 16、负载因子 0.75 的情况下，HashMap 的扩容阈值是 12，当插入第 13 个元素时触发一次扩容，容量变为 32，新的阈值是 24，因此存储 20 个元素只会扩容 1 次

32.ConcurrentHashMap怎么实现的?

一、一句话总览（面试先声）

JDK 8 的 ConcurrentHashMap 通过「CAS + synchronized + 分段思想（逻辑分段）」实现高并发安全：读操作无锁，写操作只锁桶或节点，扩容可并发进行，从而在保证线程安全的同时兼顾性能。

JDK 8 的 ConcurrentHashMap 通过 CAS + synchronized 实现线程安全。读操作基于 volatile 变量无锁完成；写操作在桶为空时通过 CAS 插入，在发生冲突时只锁定桶头节点；扩容通过 ForwardingNode 支持多线程协作完成；size 使用类似 LongAdder 的方式统计，从而在保证线程安全的同时具备高并发性能

二、为什么不用 HashMap + synchronized？

HashMap 的问题你已经知道了：

  • put / resize 无锁
  • size 不准确
  • 扩容会破坏结构

Hashtable 的问题：

  • 所有方法都 synchronized
  • 全表锁，性能极差

📌 ConcurrentHashMap 的目标：

既要线程安全，又要高并发性能

33.分段锁怎么加锁的?

在ConcurrentHashMap中,将整个数据结构分为多个Segment,每个Segment都有自己的锁,不同的Segment之间的操作互不影响,从而提高并发性能; ConcurrentHashMap中分段锁用了ReentrantLock,是一个可重入的锁;

34.已经用了synchronized,为什么还要用CAS

synchronized 负责“互斥”，CAS 负责“无锁原子更新”，两者解决的问题不同；
ConcurrentHashMap 同时使用 CAS + synchronized，是为了在高并发下既保证线程安全，又尽量减少加锁范围和竞争

1️⃣ synchronized 解决的是：互斥 + 复合操作安全

  • 保证同一时刻只有一个线程进入临界区
  • 适合：
    • 链表遍历 + 插入
    • 红黑树调整
    • resize 复杂逻辑

📌 但缺点是：

  • 阻塞
  • 上下文切换
  • 竞争激烈时性能下降

2️⃣ CAS 解决的是：单变量的原子更新（无锁）

1
compareAndSwap(expected, newValue)
  • 成功：立即返回
  • 失败：重试
  • 不阻塞线程

📌 但 CAS 的局限：

  • 只能操作一个变量
  • 逻辑复杂就不适合
  • 有 ABA 问题（JUC 内部已处理）

三、为什么“已经有 synchronized，还要 CAS”？

核心原因：性能 + 竞争概率

四、ConcurrentHashMap 中的典型场景分析（非常关键）

场景 1️⃣：桶为空时 put（最高频场景）

1
2
3
if (tabAt(tab, i) == null) {
    casTabAt(tab, i, null, new Node<>(...));
}

如果用 synchronized 会怎样？

1
2
3
4
synchronized (table) {
    if (table[i] == null)
        table[i] = new Node<>(...);
}

❌ 问题：

  • 每次 put 都要加锁
  • 多线程同时 put 不同桶，也互相阻塞
  • 吞吐量大幅下降

用 CAS 的好处

  • 不加锁
  • 不阻塞
  • 失败只说明“有人先一步插入”
  • 高并发下性能极高

📌 这一步用 synchronized 是“杀鸡用牛刀”

CAS是乐观锁,synchronized是悲观锁;