学习时整理，如有错误，欢迎指正

集合

1、常见集合

1、List（有序、可重复、带索引）

实现类：ArrayList、LinkedList、Vector、Stack

• ArrayList：底层动态数组、非线程安全；随机访问快，中间增删慢；扩容新建更大数组 + 拷贝迁移。
• LinkedList：底层双向链表；随机访问慢，增删快。

2、Set（元素不可重复）

• HashSet：底层包装HashMap，元素作为 key，value 固定为常量PRESENT；无序、线程不安全。
• LinkedHashSet：继承HashSet，底层LinkedHashMap，双向链表保留插入顺序。
• TreeSet：底层TreeMap，自动对元素排序。

3、Map（键‑值对，key 唯一，不继承 Collection）

• HashMap(JDK1.8)：数组 + 链表 + 红黑树；链表≥8 转为红黑树，提升查询速度；线程不安全。
• LinkedHashMap：继承 HashMap；增加双向链表，维持插入顺序，可实现 LRU。
• HashTable：数组 + 链表；线程安全。
• TreeMap：底层红黑树，按键排序。
• ConcurrentHashMap(JDK1.8)：数组 (Node)+ 链表 + 红黑树；CAS + synchronized锁桶节点实现线程安全；JDK7 是 Segment 分段锁。

2、线程安全集合

1、java.util 包（老式，不推荐优先使用）

该包下只有 2 个原生线程安全集合，其余 List、Set、HashMap 全部线程不安全。

1. Vector 底层为动态数组，所有方法被 synchronized 修饰，锁整个对象，同步开销大，性能较差，属于过时类。线程安全的列表优先选择 CopyOnWriteArrayList。
2. Hashtable 哈希表结构，所有方法添加 synchronized，锁住整张哈希表；不允许存储 null key、null value；无红黑树优化。现已过时，并发哈希场景优先使用 ConcurrentHashMap。

补充工具类：Collections.synchronizedList/Set/Map() 该方法为非线程安全集合包装一层同步锁，生成线程安全集合。底层为方法级 synchronized，锁集合对象本身，并发性能偏低。

2、java.util.concurrent（J.U.C）并发包，现代推荐线程安全集合

Map（并发键值对）

1. ConcurrentHashMap（最常用）

• JDK1.7：Segment 分段锁，将哈希表划分为多个分段，不同分段可并发访问。
• JDK1.8：取消 Segment 结构，采用 CAS + synchronized 锁住单个桶头节点 (Node)，锁粒度更小。
• 底层结构：数组 + 链表 + 红黑树；不允许存入 null 键、null 值。

​ 2、ConcurrentSkipListMap 跳表实现，有序并发 Map，用来替代线程安全版的 TreeMap。

Set（并发集合）

1. CopyOnWriteArraySet：无序集合；底层基于CopyOnWriteArrayList实现，采用写时复制机制。
2. ConcurrentSkipListSet：有序集合；底层包装ConcurrentSkipListMap。

List（并发列表）

CopyOnWriteArrayList 写时复制机制：add、set、remove 等写操作加锁，复制一份全新数组，在新数组上完成修改，最后用新数组替换旧数组；读操作不加锁，直接读取旧数组快照。 特点：读快写慢；适合读多写少场景；遍历属于 fail‑safe，不会抛出并发修改异常。

Queue 队列

1. ConcurrentLinkedQueue：CAS 无锁实现的高性能无界非阻塞队列。读写操作不会造成线程阻塞，高并发场景吞吐性能优秀。
2. BlockingQueue（阻塞队列，接口）：自带阻塞等待机制。队列为空时读线程阻塞；队列已满时写线程阻塞；多用于生产者‑消费者模型。 常用实现类：ArrayBlockingQueue、LinkedBlockingQueue

Deque 双端队列

1. LinkedBlockingDeque：带锁的阻塞双端队列，同一时刻仅允许一个线程执行操作。
2. ConcurrentLinkedDeque：CAS 无锁实现的无界并发双端队列，适合多线程并发访问。

3、集合遍历

1. 普通 for 循环（带索引）

仅List 可用，Set、Map 没有索引，不能用。

for (int i = 0; i < list.size(); i++) {
    String element = list.get(i);
}

优点：可以拿到下标，支持正向、倒序遍历；遍历中可删除 (倒序)。 缺点：只能遍历 List；ArrayListget(i)快，LinkedListget(i)效率很低 O (n)。

2. 增强 for‑循环 for‑each

底层本质是Iterator 迭代器，所有 Collection 集合 (List、Set) 都能用。

for (String element : list) {
    
}

缺点：遍历过程不能使用集合 remove/add，否则抛出ConcurrentModificationException快速失败异常；无法获取元素索引。

3.Iterator 迭代器

适用于所有 Collection（List、Set）。

Iterator<String> iterator = list.iterator();
while(iterator.hasNext()) {
    String element = iterator.next();
}

重点优势：遍历删除元素必须使用迭代器自己的 remove ()，不会报并发修改异常。

4.ListIterator（List 专属迭代器）

Iterator 的子类，只能用于 List。 额外能力：

• 双向遍历：hasNext()/next()向后；hasPrevious()/previous()向前
• 遍历过程可以 add、set 修改元素 缺点：Set、Map 不能使用。

5.forEach () 方法（JDK8）

集合默认方法，传入 Lambda 表达式。

list.forEach(element -> System.out.println(element));

底层：也是迭代器。 缺点：遍历中不能删除元素，异常；无法 break、continue 跳出循环。

6.Stream 流遍历（JDK8）

list.stream().forEach(element -> System.out.println(element));

优势：遍历同时可以做过滤、映射、排序等链式操作；还有并行流parallelStream()。

Map 遍历补充（面试常问） Map 不属于 Collection，不能直接用上面方式：

1. entrySet()遍历键值对（推荐）
2. keySet()遍历 key，再 get (key) 拿 value（效率低）
3. values()只遍历 value
4. map.forEach((k,v)->{}) JDK8 Lambda

LIST

1、常见种类

线程不安全：

1、ArrayList

ArrayList基于动态数组实现，它允许快速的随机访问，即通过索引访问元素的时间复杂度为 O (1)。在添加
和删除元素时，如果操作位置不是列表末尾，可能需要移动⼤量元素，性能相对较低。适⽤于需要频繁随机
访问元素，⽽对插⼊和删除操作性能要求不⾼的场景，如数据的查询和展⽰等。扩容增加50%。

2、LinkListed

LinkedList基于双向链表实现，在插⼊和删除元素时，只需修改链表的指针，不需要移动⼤量元素，时间
复杂度为 O (1)。但随机访问元素时，需要从链表头或链表尾开始遍历，时间复杂度为 O (n)。适⽤于需要频
繁进⾏插⼊和删除操作的场景，如队列、栈等数据结构的实现，以及需要在列表中间频繁插⼊和删除元素的
情况

线程安全：

1、Vector

Vector 底层也是动态数组，查询速度快。它是 Java 早期提供的线程安全集合，绝大多数方法都被 synchronized 关键字修饰，以此保证多线程环境下的数据安全。 所有方法加锁带来了不小的性能开销，单线程运行时效率低于 ArrayList；扩容策略为容量翻倍，内存利用率较低。目前 Vector 属于过时的集合，一般不推荐使用。增加一倍

2、CopyOnWriteArrayList

CopyOnWriteArrayList 位于 java.util.concurrent 并发包，底层基于数组，核心机制为写时复制。 执行 add、remove、set 这类写操作时，不会直接修改原有数组，而是复制一份全新的数组副本，在新数组中完成修改，最后再将数组引用指向新数组；读操作直接访问原数组，不需要加锁，做到读写分离。 遍历集合不会抛出并发修改异常。缺点是每次写操作都要复制数组，写开销较大；读取得到的是旧数组快照，只能保证最终一致性，无法实时读到最新修改的数据。 适用场景：读多写少的并发场景，例如事件监听列表。

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

在 Java 中，List 遍历过程能否修改，取决于遍历方式以及 List 的具体实现类。这里修改分为两类：修改元素的值；新增、删除元素（改变集合结构）。

1、普通 for 循环（下标遍历） 可以遍历过程修改元素，使用list.set()修改元素值没有问题。 如果执行删除操作，建议倒序遍历删除，防止元素前移导致下标错乱、漏删元素。

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
for (int i = 0; i < list.size(); i++) {
    list.set(i, list.get(i) * 2);
}
System.out.println(list);

2、foreach 增强 for 循环 foreach 底层基于 Iterator 迭代器实现。遍历途中调用集合 add ()、remove () 改变集合结构，就会修改modCount，抛出ConcurrentModificationException并发修改异常。 即使只执行list.set()修改元素内容，虽然不一定报错，但依然不推荐这种写法。

3、Iterator 迭代器 仅允许使用迭代器自带的iterator.remove()方法删除元素，不能调用集合对象的 remove 方法；普通 Iterator 没有 set 修改元素的能力。

4、ListIterator 列表迭代器（List 专属） 属于 Iterator 的子类，可以双向遍历；遍历的时候可以使用set()修改元素，也可以调用add()新增元素，不会抛出并发修改异常。

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
ListIterator<Integer> iterator = list.listIterator();
while (iterator.hasNext()) {
    Integer num = iterator.next();
    if (num.equals(2)) {
        iterator.set(4);
    }
}
System.out.println(list);

5、CopyOnWriteArrayList（线程安全 List） 它采用写时复制，属于 fail‑safe 安全失败机制。遍历的时候执行新增、删除、修改不会抛出并发修改异常。但是遍历读取到的数据是旧数组的快照，有可能读取不到本次修改之后的最新数据，只能保证最终一致性。

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

ArrayList

调用remove(int index)删除指定下标元素。删除完成后后面所有元素向前移动补齐空位。

• 删除末尾元素：时间复杂度 O (1)
• 删除中间、头部元素：时间复杂度 O (n)，需要移动大量元素

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.remove(1);
System.out.println(list);

LinkedList

同样可以调用remove(int index)；但是链表没有随机访问能力，需要从头或者尾部遍历找到对应下标节点，因此按下标删除时间复杂度 O (n)。 如果删除头节点、尾节点，不需要遍历，直接修改指针即可，时间复杂度 O (1)。

List<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.remove(1);
System.out.println(list);

CopyOnWriteArrayList

remove(index)删除时会复制一份全新数组，再完成删除操作，时间复杂度 O (n)。写操作不会阻塞读操作，适合并发场景。

CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.remove(1);
System.out.println(list);

4、ArrayList 和 LinkedList 的区别，哪个集合是线程安全的？

ArrayList 和 LinkedList 都是 Java 中常见的集合类，它们都实现了 List 接口。

1、底层数据结构不同：

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

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

ArrayList 在尾部进行插入和删除操作时效率较高，因为不需要移动其他元素；但如果是在中间或开头插入、删除，就需要移动后面的所有元素，效率会比较低。LinkedList 在头部和尾部进行插入、删除操作时效率很高，只需要调整节点的指针即可；但如果是在中间位置操作，需要先从头或尾遍历链表找到目标位置，时间复杂度也是 O (n)，不过找到位置后只需要调整指针，不需要像 ArrayList 那样移动大量元素，所以在某些特定场景下还是有优势的，而且 LinkedList 实现了 Deque 接口，还可以当作双端队列、栈来使用。

3、随机访问的效率不同：

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

4、空间占用：ArrayList 在创建时会分配一段连续的内存空间，虽然会有一定的容量浪费（比如实际元素没装满数组），但只需要存储元素本身。LinkedList 每个节点除了存储元素，还需要额外存储两个指针（指向前一个和后一个节点），所以在存储相同数量元素的情况下，LinkedList 的空间占用通常会比 ArrayList 更大一些。

5、使用场景：

ArrayList 更适合需要频繁随机访问元素，或者主要在尾部进行插入、删除操作的场景。LinkedList 更适合需要频繁在头部或尾部进行插入、删除操作，或者需要作为双端队列、栈使用的场景；如果是通过迭代器直接操作已知位置的节点，在中间插入、删除时也能发挥它调整指针快的优势。

6、线程安全：

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

5、ArrayList 和 Vector 区别是什么？

ArrayList 和 Vector 都是 Java 中常用的动态数组实现，用于存储和操作对象集合，但它们在设计上有几个关键区别，主要体现在线程安全性、性能和功能细节上。

1、线程安全性

Vector 是线程安全的，它的大部分方法（比如 add、remove、get 等）都被 synchronized 修饰，这意味着多线程环境下操作 Vector 时，不需要额外处理同步问题。而 ArrayList 没有任何同步机制，是非线程安全的，在多线程并发修改时可能会出现数据不一致的问题，比如抛出 ConcurrentModificationException 异常。

正因为同步机制的存在，两者在性能上也有差异。由于 Vector 的方法需要加锁释放锁，在单线程环境下，它的操作效率通常比 ArrayList 低。所以如果是单线程场景，或者能自己保证线程安全的情况下，ArrayList 是更优的选择，性能更好。

2、扩容机制

当集合元素数量超过初始容量时，都会自动扩容。Vector 默认的扩容策略是翻倍（如果没有指定增长因子的话），比如初始容量 10，满了之后会扩容到 20。而 ArrayList 在 JDK 1.8 及之后，默认是扩容为原来的 1.5 倍，相对来说扩容的幅度更小，能在一定程度上节省内存空间。当然，Vector 也可以通过构造方法指定增长因子，灵活控制扩容幅度，而 ArrayList 没有这个功能。

总的来说，选择两者时主要看是否需要线程安全：如果是多线程环境且需要内置同步支持，可能会用到 Vector；但现在更多时候会用 ArrayList，因为它性能更好，而且在需要线程安全时，可以通过 Collections.synchronizedList () 方法将 ArrayList 包装成线程安全的集合，灵活性更高。

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

ArrayList不是线程安全的。 将 ArrayList 转为线程安全集合一共有三种常用方式：

1、使用Collections.synchronizedList()包装 ArrayList

List<String> synchronizedList = Collections.synchronizedList(arrayList);

2、使用并发包下CopyOnWriteArrayList替换 ArrayList

CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>(arrayList);

3、使用Vector替换 ArrayList（属于过时方案，不推荐）

Vector<String> vector = new Vector<>(arrayList);

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

并发调用add()添加元素的时候会产生三类问题：

1. 集合出现null空元素
2. 抛出数组索引越界异常ArrayIndexOutOfBoundsException
3. size实际计数和添加元素的总数量不一致

add 核心源码：

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

add操作分为三步：

1. 判断是否需要扩容，需要则扩容
2. 在size下标位置赋值元素
3. size++集合长度加一

关键点：size++不是原子操作，分为取值、+1、回写三步。

问题产生原理：

1. 出现 null 值 两个线程同时判断不需要扩容；线程 1 赋值下标 9，还未执行size++，线程 2 又向下标 9 赋值；随后两个线程先后执行 size++；最终下标 10 位置无元素，出现 null。
2. 索引越界异常 两个线程同时跳过扩容校验，此时数组容量已满；线程 1 完成赋值，size 变成 10；线程 2 再尝试向下标 10 写入元素，超出数组最大下标，抛出越界异常。
3. size 计数与添加数量不符 两个线程读取到同一个 size 值，各自完成 + 1 后，覆盖回写 size，导致一次 add 计数丢失。

8、ArrayList 和 LinkedList 的应用场景

ArrayList 适合频繁访问、随机查询、遍历集合元素的场景。底层为数组，索引访问 O (1) 查询速度快。推荐用于查询多、增删少、集合大小变动不频繁的业务。

LinkedList 适合频繁在头部、尾部进行插入删除的场景；也可以当做队列、双端队列、栈使用。按下标中间增删效率并没有优势。适合集合大小经常变动、头尾增删频繁的业务。

9、ArrayList 的扩容机制

当调用add添加元素，现有元素个数等于内部数组容量时触发扩容。

1. 计算新容量：新容量 = 原容量 + 原容量右移一位，也就是扩容至原来的1.5 倍

int newCapacity = oldCapacity + (oldCapacity >> 1);

1. 创建一块容量更大的新数组
2. 通过数组拷贝Arrays.copyOf，将旧数组所有元素复制进新数组
3. 将 ArrayList 内部数组引用指向新数组，扩容结束，继续添加元素

扩容会产生数组拷贝开销。大批量添加数据时，建议初始化时指定初始容量，减少多次扩容。 选择 1.5 倍扩容，好处是利用移位运算，无需浮点运算，效率更高。

10、CopyOnWriteArrayList 如何实现线程安全

1. 内部存储数组被volatile修饰：private transient volatile Object[] array;，保证数组引用修改后对其他线程立即可见。
2. 写操作（add/remove/set）加互斥锁ReentrantLock，保证同一时刻只能有一个线程执行修改操作，防止并发修改带来的数据错乱。
3. 写时复制：修改时不会直接改动原数组，先拷贝生成一份全新数组；在新数组完成修改；最后把内部数组引用切换指向新数组。
4. 读操作不加锁：读取永远访问旧数组快照；读写互不阻塞，实现读写分离。

缺点：每次写操作复制完整数组，内存开销大；读取到的是旧快照，只能保证最终一致性，不能做到实时一致性。

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

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

Java 泛型只支持引用类型（对象），不支持基本数据类型。 原因：

1. 泛型存在类型擦除，编译后泛型会被擦除成Object；Object 只能存放对象，无法接收int、long这类基本类型。
2. 历史兼容问题：基本类型与引用类型体系相互独立，泛型是 JDK1.5 后期新增特性，没有对基本类型提供支持。

解决办法：使用对应的包装类，依靠自动装箱、拆箱完成转换。

List<Integer> list = new ArrayList<>();
list.add(10);       //自动装箱 int → Integer
int num = list.get(0); //自动拆箱 Integer → int

12、list与数组间的转化

List 转数组

核心方法：toArray()，一共有两种重载方式。

1、无参方法 list.toArray()

Object[] objArr = strList.toArray();

• 返回值为 Object[] 类型
• 不能向下强转，例如 String[] arr = (String[])list.toArray()，运行时抛出类型转换异常 ClassCastException
• 使用场景极少，开发不推荐

2、带泛型参数 toArray(T[] a)（推荐写法）

List<String> strList = new ArrayList<>();
strList.add("a");
strList.add("b");

//写法1：传入和集合大小相等的数组
String[] strArr1 = strList.toArray(new String[strList.size()]);
//写法2：传入空数组，JDK1.8之后会自动优化，性能更好
String[] strArr2 = strList.toArray(new String[0]);

原理：

• 如果传入数组长度 ≥ list 元素个数：元素就复制到传入的数组里
• 如果传入数组长度 < list 元素个数：方法内部会新建一个对应类型、大小等于 list 长度的数组并返回

自定义对象转换示例：

List<User> userList = new ArrayList<>();
userList.add(new User("张三",20));
User[] userArr = userList.toArray(new User[0]);

---

数组转 List

核心工具：Arrays.asList()，这里有两个高频坑点。

String[] arr = {"a","b","c"};
List<String> list = Arrays.asList(arr);

注：

1、返回的 List 不是 java.util.ArrayList

Arrays.asList() 返回的是 Arrays 的内部静态类，底层还是原数组。

• 支持get()、set()查询修改元素
• 不支持 add ()、remove ()，调用就抛出 UnsupportedOperationException

如果后续需要增删元素，必须包装一层new ArrayList<>()

List<String> list = new ArrayList<>(Arrays.asList(arr));

2、基本类型数组不能直接用 Arrays.asList ()

int[] nums = {1,2,3};
//错误写法：会把整个int[]数组当成1个元素
List<int[]> list = Arrays.asList(nums);

Arrays.asList接收可变参数，可变参数要求是引用类型。int[]本身是一个对象，所以会被当作单个元素存入集合。

正确方案（JDK8+ Stream 流转为包装类集合）：

int[] nums = {1,2,3};
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());

SET

1、set与list区别

List 与 Set 都是 Collection 接口下的子接口。最核心区别就是元素是否允许重复以及是否保证存取顺序。

List

1. 允许元素重复，可以存放多个相同对象；
2. 有序：存取顺序一致，也就是存入顺序就是遍历顺序；
3. 支持下标索引，可以通过get(index)根据位置获取元素；
4. 允许存放多个null；
5. 常见实现类：ArrayList、LinkedList、Vector；
6. 使用场景：需要保留添加顺序，频繁按下标查询；例如订单列表、购物车。

Set

1. 元素不可重复，集合内部只会保留一份相同元素；
2. 默认不保证存取顺序；
   • HashSet：无序；
   • LinkedHashSet：有序（保留插入顺序）；
   • TreeSet：按元素大小排序；
3. 没有索引，不能通过下标获取元素，只能遍历；
4. 最多存放一个 null；
5. 判断重复规则：
   • HashSet、LinkedHashSet：依靠hashCode() + equals()；
   • TreeSet：依靠compareTo() / Comparator 比较器；
6. 常见实现类：HashSet、LinkedHashSet、TreeSet；
7. 使用场景：需要对数据去重；例如抽奖名单、标签集合。

补充：ArrayList、HashSet 都是非线程安全；Vector 线程安全（过时）。

2、如何对 Set 排序

Set 本身没有统一排序能力，有两种主流方案：

1：使用 TreeSet（插入的时候自动排序）

底层基于红黑树，添加元素时自动完成排序。

• 自然排序：元素实现Comparable接口，重写compareTo()方法；
• 自定义排序：创建 TreeSet 时传入Comparator比较器。

//自然排序‑基础类型
TreeSet<Integer> numSet = new TreeSet<>();
numSet.add(3);
numSet.add(1);
numSet.add(2);
//输出结果：1 2 3
//自定义比较器降序
TreeSet<User> userSet = new TreeSet<>(Comparator.comparingInt(User::getAge).reversed());

注意：TreeSet 去重规则是比较器返回 0 即判定重复，不会再调用 equals。

2：LinkedHashSet —— 保存插入顺序（不是值排序）

如果你只想要保证遍历顺序等于添加顺序，而不是按元素大小排序，使用LinkedHashSet，底层哈希表 + 双向链表。

LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("b");
set.add("a");
set.add("c");
//输出顺序：b a c

3：HashSet 转 List 再排序（临时排序）

HashSet 无序，如果后期才需要排序，可以转为 List，使用 Collections.sort () 或者 Stream 排序。

HashSet<Integer> hashSet = new HashSet<>(Arrays.asList(3,1,2));
List<Integer> list = new ArrayList<>(hashSet);
Collections.sort(list);

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

答案： Set 集合中的元素是唯一的，集合里面不会出现重复的元素。

Set 去重实现原理： Set 底层依靠哈希表、红黑树这类结构实现元素无重复。往 Set 添加元素的时候：

1. 首先调用元素的hashCode()方法，计算哈希值，确定元素存放的桶位置。
2. 找到对应桶之后，再调用equals()方法，和桶中已经存在的元素逐一比较。
3. 如果equals返回 true，代表元素已经存在，放弃插入；
4. 如果equals返回 false，代表没有重复，就将新元素存入集合。 依靠 hashCode() + equals() 双重判断，最终保证集合元素唯一性。

补充考点（面试加分）：

• HashSet 底层就是封装了一个 HashMap；存入的元素作为 HashMap 的 key，value 统一是一个固定的 Object 常量。利用 HashMap key 不可重复的特性，天然实现 Set 去重。

---

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

答案： 有序的 Set 主要有两个：TreeSet 和 LinkedHashSet，但是二者 “有序” 的含义完全不一样。

1. TreeSet：底层基于红黑树实现，保证元素的自然排序（升序），或者自定义比较器的排序；不保存插入顺序。
2. LinkedHashSet：底层 = 哈希表 + 双向链表。双向链表用来维护元素先后关系，可以保留元素的插入顺序。

记录插入顺序的集合是 LinkedHashSet，它既保证元素唯一，又可以维持元素添加时的先后顺序。

快速区分记忆：

• HashSet：无序、无重复
• TreeSet：排序有序、无重复
• LinkedHashSet：插入有序、无重复

MAP

1、常见 Map 集合总结

非线程安全

1. HashMap

底层基于哈希表实现，JDK1.8 结构：数组 + 链表 + 红黑树。根据 key 的哈希值存放键值对，查询效率高。 非线程安全；并发扩容时，多线程同时修改哈希表结构，会造成死循环、数据丢失、数据错乱。

2. LinkedHashMap

继承 HashMap，底层在哈希表基础上额外维护一条双向链表。 可以保证遍历顺序：默认是插入顺序，也可以开启访问顺序 (LRU)。 同样非线程安全，并发场景下和 HashMap 存在一样的并发问题。

3. TreeMap

底层基于红黑树实现。可以对 key 进行排序，默认自然升序排序；也可以传入 Comparator 自定义排序规则。 非线程安全，并发增删节点会破坏红黑树结构，引发异常。

线程安全

1. Hashtable

Java 早期线程安全 Map。几乎所有方法都加上synchronized，锁对象是整个哈希表。同一时刻只允许一个线程操作。 缺点：锁粒度太大，并发性能差，目前已经过时，开发不推荐使用。

2. ConcurrentHashMap

• JDK1.7：分段锁 Segment。把整个集合拆分成多个分段，每个分段拥有独立锁；线程只锁住自己操作的分段，不同分段线程可并发执行，提升并发吞吐量。
• JDK1.8 及以后：抛弃分段锁；采用volatile + CAS + synchronized，锁粒度缩小到哈希桶（链表 / 红黑树根节点），并发性能进一步提升。

2、Map 的 5 种遍历方式

方式 1：entrySet + foreach（最推荐，同时拿 key‑value，性能高）

Map<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key + " = " + value);
}

优点：一次取出键值对，不需要二次查询 map。

方式 2：keySet + foreach（只遍历 key，再 get 取值）

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

缺点：get(key)会多一次哈希查找；数据量大时性能低于 entrySet。适合只需要 key 的场景。

方式 3：迭代器 Iterator 遍历（遍历途中删除元素首选）

Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()){
    Map.Entry<String, Integer> entry = iterator.next();
    //遍历中删除元素，只能用迭代器remove()
    //iterator.remove();
    System.out.println(entry.getKey()+"="+entry.getValue());
}

注意：foreach 遍历集合时不能调用 map.remove ()，会报并发修改异常，删除优先选迭代器。

方式 4：forEach + Lambda（JDK8+，代码最简洁）

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

方式 5：Stream 流遍历（JDK8+，适合遍历同时做过滤、转换等操作）

map.entrySet().stream()
        .forEach(entry -> System.out.println(entry.getKey() + "=" + entry.getValue()));

//示例：过滤值大于1的元素生成新map
Map<String,Integer> newMap = map.entrySet().stream()
        .filter(entry->entry.getValue()>1)
        .collect(Collectors.toMap(Map.Entry::getKey,Map.Entry::getValue));

3、HashMap 实现原理（JDK1.7、JDK1.8完整对比）

HashMap 是基于哈希表实现的键值对集合，核心依靠哈希算法定位元素存储位置，解决哈希冲突实现数据存储。

JDK 1.7 底层结构：数组 + 单向链表

通过 key 的哈希值计算数组下标，将键值对存入对应槽位（桶）。当多个 key 哈希值相同、发生哈希冲突时，冲突元素以单向链表形式挂载在同一个桶位下方。如果冲突严重、链表过长，遍历查询效率会退化为 O(n)，性能较差。

JDK 1.8 底层结构：数组 + 单向链表 + 红黑树（核心优化）

为了解决链表过长查询慢的问题，JDK1.8 引入红黑树优化：

1、当桶位链表长度超过8 且 数组容量大于等于64，链表转换为红黑树，查询时间复杂度从 O(n) 优化为 O(log n)，大幅提升查询性能；

2、当红黑树节点数量 小于等于6 时，红黑树重新退化为链表，减少树结构维护开销。

若链表长度达到8但数组容量不足64，不会树化，只会触发数组扩容。

4、HashMap 链表树化为什么选用红黑树，不使用平衡二叉树（AVL树）？

1、AVL 树是严格平衡二叉树，要求任意节点左右子树高度差不超过1，插入、删除节点极易触发大量左旋、右旋平衡操作，调整开销极大。

2、红黑树只保证黑色节点高度平衡，不要求完全严格平衡，增删节点触发旋转次数极少，维护成本远低于 AVL 树。

3、HashMap 树化是低频场景，只有链表极度过长才会触发，不需要极致平衡；红黑树 O(log n) 的查询速度完全够用。

4、HashMap 增删、查询操作频率持平，红黑树牺牲极小查询性能，换取极低的增删开销，综合性能远优于 AVL 树，更适合哈希表场景。

5、常见哈希冲突解决方法

1、链地址法（拉链法）：将哈希冲突的元素挂载在同一个桶位的链表或红黑树上，是 HashMap 采用的方案。

2、开放寻址法：冲突后向后寻找空闲槽位存储元素，包含线性探测、二次探测、双重散列三种方式，典型应用为 ThreadLocalMap。

3、再哈希法：发生冲突时，使用新的哈希函数重新计算哈希值，直到找到空槽位。

4、哈希扩容法：扩大哈希数组容量，重新哈希分配所有元素，从根源减少冲突概率。

6、HashMap 是否线程安全？多线程存在什么问题？

HashMap 是非线程安全集合，多线程并发操作会出现数据异常。

JDK 1.7 并发问题：采用数组+链表、头插法扩容。多线程同时扩容会导致链表成环，调用 get 方法出现死循环（扩容迁移链表节点时，会反转链表顺序），同时存在数据丢失问题。

JDK 1.8 并发问题：改为尾插法，解决了扩容死循环问题。但多线程并发 put 时，会出现数据覆盖，导致元素丢失、数据不一致。

7、HashMap 线程安全替代方案

1、Hashtable：早期线程安全集合，所有方法加 synchronized，锁整个哈希表，并发性能极差，已过时不推荐。

2、Collections.synchronizedMap：通过同步包装实现线程安全，同样是全局锁，并发效率低。

3、ConcurrentHashMap（高并发首选）

JDK1.7：采用 Segment分段锁 + HashEntry，将集合分为多个分段，每个分段独立加锁，不同分段可并发访问，提升并发性能。

JDK1.8：舍弃分段锁，采用 volatile + CAS + synchronized，锁粒度细化到单个哈希桶节点，同时引入红黑树，彻底解决链表过长性能问题，并发性能大幅提升。

8、get () 获取元素流程（JDK1.8）

核心源码

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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 ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && ((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 {
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

完整要点

1. get方法只是入口，实际查找逻辑交给getNode(hash(key),key)，传入 key 的哈希值与 key 本身。
2. 三重判断校验：存储数组table不为null；数组长度大于 0；通过哈希计算出来的桶位置上存在节点，不满足直接返回null。
3. 使用(n‑1)&hash计算数组桶下标，取出桶上第一个节点。
4. 比对头节点：hash 值相等，并且 key 满足引用相等== 或者equals()内容相等，匹配成功直接返回该节点。
5. 头节点不匹配并且存在后继节点：
   • 当前桶是红黑树节点：调用getTreeNode()走红黑树查找；
   • 当前桶是链表节点：do‑while循环遍历整条链表，逐个比对 hash 与 key。
6. 遍历结束后没有找到目标 key，返回null。

判断规则：先比较 hash 值，再比较 key。

9、put () 添加元素流程（JDK1.8）

1. 根据 key 的哈希码，通过(n‑1)&hash计算数组桶索引位置。
2. 如果目标桶位置为空：新建Node对象存放键值对，放入桶中；modCount修改次数 + 1，用于迭代时检测并发修改。
3. 桶上已经存在节点：判断桶首节点 hash 与 key 和待添加元素一致，相同则直接覆盖旧 value，完成更新。
4. 首节点 key 不一致，则向下遍历容器：
   • 链表：从头逐个比对 hash 和 equals；找到相同 key 就覆盖 value；无重复元素，1.8尾部追加节点。
   • 红黑树：在树内查找 key；找到相同 key 覆盖；找不到就新增树节点。
5. 链表长度判断：链表长度≥8，且数组容量≥64，链表转为红黑树；数组长度不足 64 则不树化。
6. 负载因子校验（默认 0.75）：当size > 数组长度 × 0.75，触发扩容。
7. 扩容操作：创建容量为原来 2 倍的新数组；旧数组所有节点重新计算哈希，迁移到新数组；更新数组引用和扩容阈值。
8. 添加完成。

补充：HashMap 是非线程安全集合，多线程环境建议使用ConcurrentHashMap。

注：

put 与 get 过程一句话概括

存储元素：put 调用hashCode()算出哈希值，定位 bucket 桶位置；超过负载因子自动扩容为原来两倍；发生哈希冲突用链表保存冲突元素；链表长度大于等于 8 转为红黑树提升查询速度。

查询元素：get 调用hashCode()算出哈希值定位桶；再通过equals()确定目标 key；冲突时遍历链表或者红黑树查找元素。

10、get 方法是否一定安全？

结论：不安全，分为单线程、多线程两种场景

1. 单线程：若 HashMap 对象本身为null，调用get()抛出空指针异常；HashMap 初始化完成后，允许null作为 key。
2. 多线程：HashMap 无锁，一个线程执行 put/remove 修改集合结构，另一个线程调用 get 读取，可能读到脏数据，也会抛出ConcurrentModificationException并发修改异常；高并发场景选用ConcurrentHashMap。

11、HashMap 一般用什么做 Key？为什么 String 最适合做 Key？

适合做 Key 的类型：String、Integer、Long 等不可变类。

为什么 String 最适合：

1、不可变：String 一旦创建无法修改，保证 key 的 hashCode 永远固定、不会变。

2、稳定性极强：如果 key 是可变对象，修改属性后 hashCode 会改变。存的时候是旧哈希值，取的时候是新哈希值，桶位不一致，导致找不到数据、数据丢失、脏数据。

3、重写了 equals 和 hashCode：规范、稳定、符合 HashMap 键匹配规则。

总结：不可变 = hashCode 永久固定 = 存取桶位一致 = HashMap 准确无误。

12、HashMap 为什么用红黑树，不用平衡二叉树（AVL）？

平衡二叉树（AVL）特点：严格平衡

任意节点左右子树高度差 ≤ 1，树结构极度规整。

缺点：插入、删除节点极易破坏平衡，需要频繁左旋、右旋调整结构，维护成本极高。

红黑树特点：弱平衡、非严格平衡

规则：整树最长路径不超过最短路径的 2 倍。

1、不追求绝对平衡，增删节点触发调整、旋转次数极少。

2、牺牲极小的查询性能，大幅降低增删平衡开销。

3、HashMap 树化是低频场景，只有链表超长才树化，不需要极致平衡。

4、HashMap 增、删、查频率基本持平，红黑树综合性能远优于 AVL。

13、HashMap 的 key 可以为 null 吗？原理？

key 可以为 null，且只能有一个 null key；value 可以多个 null。

底层原理：

HashMap 的 hash() 方法做了空判断：

如果 key == null，直接返回 hash 值为 0，不会执行 key.hashCode()，避免空指针异常。

为什么只能一个 null key：

后续再次存入 null 键，hash 值同样为 0，key 判定相等，会覆盖旧 value，所以 null 键唯一。

14、重写 equals 和 hashCode 需要遵循什么规则？

HashMap 存 key 靠 hashCode 找桶，靠 equals 判断 key 是否真正相同。

强制规范（面试必背）：

1、equals 相等 → hashCode 必须相等

如果 o1.equals(o2) 为 true，那么 o1.hashCode() == o2.hashCode() 必须成立。

2、hashCode 相等 → equals 不一定相等

哈希冲突场景：不同对象哈希值相同，但内容不同。

15、只重写 equals 不重写 hashCode 会出现什么严重问题？

会造成 HashMap 逻辑重复 key、数据不覆盖、数据错乱

故障过程：

1、两个对象逻辑相等（equals=true），但 hashCode 不同。

2、存的时候根据不同 hashCode 进入不同桶位。

3、HashMap 认为两个 key 不一样，不会覆盖。

4、最终集合中存在逻辑相同、实际共存的重复 key，完全违背 HashMap 唯一键规则。

16、HashMap 多线程下会出现哪些问题？

HashMap 全程非线程安全

JDK1.7 问题（头插法）

1、多线程扩容导致链表成环

2、get 遍历环形链表 死循环、CPU 100%

3、并发扩容导致数据丢失

JDK1.8 优化（尾插法）

链表顺序不变，彻底解决环形链表、死循环问题

1.7、1.8 共有致命问题

多线程并发 put，索引相同会发生数据覆盖，后线程覆盖前线程数据，导致元素丢失。

17、HashMap 扩容机制详细流程

默认负载因子：0.75

触发条件：元素数量 size > 数组容量 × 0.75

扩容两步走：

1、新建一个 原容量2倍 的新数组

2、迁移旧数组所有元素到新数组

JDK1.8 核心优化：不需要重新计算 hash

扩容后元素新索引只有两种情况：

判断：hash & 旧容量

1、结果为 0 → 新索引 = 原索引

2、结果不为 0 → 新索引 = 原索引 + 旧容量

优化好处：

1、省去大量 hash 重算时间，扩容速度极快

2、原本冲突在同一桶的节点，均匀分散到两个桶，减少哈希冲突

18、HashMap 容量为什么必须是 2 的 n 次方？（超级详细）

HashMap 索引公式：index = hash & (length - 1)

必须是 2 的幂，有三大核心原因：

原因一：位运算等价取模，效率极高

length 为 2ⁿ 时，length-1 二进制低位全部为 1。

hash & (length-1) 等价于 hash % length，位运算远快于取模运算。

原因二：保证索引分布均匀，减少哈希冲突

如果不是 2 的幂，length-1 二进制末尾存在 0，会导致：

部分索引位置永远无法存放数据，数组空间浪费，大量 hash 挤在少数桶位，冲突暴增。

原因三：JDK1.8 扩容优化的前置条件

只有容量是 2 的倍数，扩容才能通过hash&oldCap 快速判断新索引，不用重算哈希。

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

初始容量：16

默认负载因子：0.75

初始阈值：16 × 0.75 = 12

1、存入 1~12 个元素：未超阈值，不扩容

2、存入第13个元素：超过阈值，触发扩容 1 次

3、扩容后容量 32，新阈值 24

4、13~20 均小于 24，不再扩容

最终结论：扩容 1 次

20、说说 hashmap 的负载因子

答案： HashMap 负载因子 loadFactor 的默认值是 0.75。当 HashMap 中的元素个数超过了容量的 75% 时，就会进行扩容。 默认负载因子为 0.75，是因为它提供了空间和时间复杂度之间的良好平衡。 负载因子太低会导致大量的空桶浪费空间，负载因子太高会导致大量的碰撞，降低性能。0.75 的负载因子在这两个因素之间取得了良好的平衡。

扩容二进制示例：

00010100 (hash = 20)
& 00010000 (oldCap = 16)
= 00010000 (结果 = 16，不为 0)

---

21、Hashmap 和 Hashtable 有什么不一样的？Hashmap 一般怎么用？

答案：

1. HashMap 线程不安全，效率高一点，可以存储 null 的 key 和 value，null 的 key 只能有一个，null 的 value 可以有多个。默认初始容量为 16，每次扩充变为原来 2 倍。创建时如果给定了初始容量，则扩充为 2 的幂次方大小。底层数据结构为数组 + 链表，插入元素后如果链表长度大于阈值（默认为 8），先判断数组长度是否小于 64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
2. HashTable 线程安全，效率低一点，其内部方法基本都经过 synchronized 修饰，不可以有 null 的 key 和 value。默认初始容量为 11，每次扩容变为原来的 2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组 + 链表。它基本被淘汰了，要保证线程安全可以用 ConcurrentHashMap。

HashMap 怎么用：

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

---

22、ConcurrentHashMap 怎么实现的？

答案：

JDK 1.7 ConcurrentHashMap

在 JDK 1.7 中它使用的是数组加链表的形式实现的，而数组又分为：大数组 Segment 和小数组 HashEntry。 Segment 是一种可重入锁（ReentrantLock），在 ConcurrentHashMap 里扮演锁的角色；HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素。 JDK 1.7 分段锁技术将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

JDK 1.8 ConcurrentHashMap

JDK 1.8 则使用了数组 + 链表 / 红黑树的方式优化了 ConcurrentHashMap 的实现。 ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。添加元素时首先会判断容器是否为空：

1. 如果为空则使用 volatile 加 CAS 来初始化。
2. 如果容器不为空，则根据存储的元素计算该位置是否为空。
3. 如果根据存储的元素计算结果为空，则利用 CAS 设置该节点；
4. 如果根据存储的元素计算结果不为空，则使用 synchronized ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

一句话归纳：ConcurrentHashMap 通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。 而且 JDK 1.8 使用的是红黑树优化了之前的固定链表，那么当数据量比较大的时候，查询性能也得到了很大的提升，从之前的 O (n) 优化到了 O (logn) 的时间复杂度。

---

23、分段锁怎么加锁的？

答案： 在 ConcurrentHashMap 中，将整个数据结构分为多个 Segment，每个 Segment 都类似于一个小的 HashMap，每个 Segment 都有自己的锁，不同 Segment 之间的操作互不影响，从而提高并发性能。 在 ConcurrentHashMap 中，对于插入、更新、删除等操作，需要先定位到具体的 Segment，然后再在该 Segment 上加锁，而不是像传统的 HashMap 一样对整个数据结构加锁。这样可以使得不同 Segment 之间并行执行，提高并发性能。

---

24、分段锁是可重入的吗？

答案： JDK 1.7 ConcurrentHashMap 中的分段锁是用了 ReentrantLock，ReentrantLock 是一个可重入的锁，所以分段锁是可重入锁。

---

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

答案： ConcurrentHashMap 使用这两种手段来保证线程安全主要是一种权衡的考虑，在某些操作中使用 synchronized，还是使用 CAS，主要是根据锁竞争程度来判断的。 比如：在 putVal 中，如果计算出来的 hash 槽没有存放元素，那么就可以直接使用 CAS 来进行设置值，这是因为在设置元素的时候，因为 hash 值经过了各种扰动后，造成 hash 碰撞的几率较低，那么我们可以预测使用较少的自旋来完成具体的 hash 落槽操作。 当发生了 hash 碰撞的时候说明容量不够用了或者已经有大量线程访问了，因此这时候使用 synchronized 来处理 hash 碰撞比 CAS 效率要高，因为发生了 hash 碰撞大概率来说是线程竞争比较强烈。

---

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

答案： 悲观锁和乐观锁都有用到。 添加元素时首先会判断容器是否为空：

1. 如果为空则使用 volatile 加 CAS （乐观锁） 来初始化。
2. 如果容器不为空，则根据存储的元素计算该位置是否为空。
3. 如果根据存储的元素计算结果为空，则利用 CAS（乐观锁） 设置该节点；
4. 如果根据存储的元素计算结果不为空，则使用 synchronized（悲观锁） ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

27、HashTable 底层实现原理是什么？

答案： Hashtable 的底层数据结构主要是数组加上链表，数组是主体，链表用来解决 hash 冲突。 HashTable 是线程安全的，实现方式是 Hashtable 的所有公共方法均采用synchronized关键字。当一个线程访问同步方法，另一个线程也访问的时候，就会陷入阻塞或者轮询的状态。

---

28、HashTable 线程安全是怎么实现的？

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

synchronized底层原理： 当某个线程调用该对象的synchronized方法时，这个线程便获得了该对象的锁，其他线程暂时无法访问这个方法。只有等待这个方法执行完毕、线程释放锁之后，其他线程才能执行该同步方法。

核心源码片段

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;
}

---

27、hashtable 和 concurrentHashMap 有什么区别？

答案：

1. 底层数据结构

• Hashtable：数组 + 链表。数组为主体，链表解决哈希冲突，无红黑树优化。
• ConcurrentHashMap
  • JDK7：分段数组 + 链表（Segment 分段锁）
  • JDK8：数组 + 链表 / 红黑树

2. 线程安全实现方式

• Hashtable：所有方法上加对象锁synchronized；锁住整个 Hashtable 对象；同一时间仅允许一个线程操作，并发效率很低。
• ConcurrentHashMap
  • JDK7：分段锁 Segment。容器被切分成多个片段；写操作只锁定当前访问的 Segment 片段，不同分段之间线程互不阻塞，提升并发度。
  • JDK8：弃用 Segment；采用CAS + synchronized，锁粒度降到桶头节点，进一步提高并发性能。

---

28、说一下 HashMap 和 Hashtable、ConcurrentMap 的区别

答案：

HashMap

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

HashTable

线程安全，效率低一点，其内部方法基本都经过synchronized修饰；不可以存储 null 的 key 和 value。 默认初始容量为 11，每次扩容变为原来的2n+1。创建时给定了初始容量，会直接使用给定的大小，不会转为 2 的幂次。 底层数据结构为数组 + 链表。它基本被淘汰了；多线程场景优先选用ConcurrentHashMap。

ConcurrentHashMap（线程安全哈希表）

它可以在多线程环境下并发地进行读写操作，不需要像 Hashtable 一样每次读写都锁住整张表。

• JDK7：采用分段锁，哈希表被拆分成多个 Segment 段，每个 Segment 相当于一个小型 HashMap，自带独立锁。读操作不需要上锁；写操作只锁定对应的 Segment 片段，而非整个哈希表，大幅提高并发性能。
• JDK8：底层升级数组 + 链表 / 红黑树；依靠CAS + synchronized对头节点加锁实现线程安全，锁粒度更小，并发性能更高。