Java集合

青云计划

469人浏览 · 2026-05-15 14:55:21

青云计划 · 2026-05-15 14:55:21 发布

对于Java集合，相信大家都不陌生。心想：不就是Java集合嘛，谁不知道，一直在用的什么ArrayList，什么HashSet，什么HashMap，张嘴就来的东西有什么好说的。那么在这里我就提出以下几个问题，看你是否真的了解Java集合了。

在实际开发过程中，明明LinkList在插入的算法复杂度上要优于ArrayList，为什么开发依旧使用ArrayList?
ArrayList为什么扩容机制是多少倍，为什么选择这个倍数，选择更大的倍数或者扩容恰好合适行不行?
HashMap为什么是线程不安全的，而CurrentHashMap为什么是线程安全的？
HashMap在JDK1.7和JDK1.8有什么区别?HashMap为什么要在JDK1.8引入红黑树?
为什么在结点为6的时候红黑树转链表，而在结点为8的时候链表转红黑树之间需要隔一个结点?

相信你看到上述问题，肯定会说，这不就是八股吗?这背一下不就好了。那么我想说的是，这上述问题隐藏着架构和权衡点艺术，相信你看完这篇一定会受益匪浅。

Java集合

Collection

可以将Collection想象成一个可以容纳东西的各种储物柜。其中里面的不同储物柜有着不同的性质。比如说支持有序的List。支持元素不重复的Set等等。

List

对于List相信已经耳熟能详了，比如说在开发过程中用的最多的并且是支持元素有序且可以重复存储的ArrayList。又比如说底层使用的是双向链表，能够快速的进行元素的插入和删除，在刷算法题的时候时候的栈，都有的LinkList的身影。那么这两个集合我们在开发过程当中，以及在面试中可能需要用到什么知识呢？请接着往下看。

ArrayList

说到ArrayList，相信都很熟悉。

面试官问:你说你熟悉Java集合？那你说一下java集合当中的ArrayList吧。

于是你就开始吟唱：ArrayList底层的数据存储是用一片连续的内存的方式，是开发过程当中用到最多的集合，在开发过程当中用的最多的集合。在刚开始创建集合的时候，java会使用懒加载机制，如果没有往集合塞数据，那么此时不会为当前集合分配空间。只有当真正给集合塞数据的时候，才会给其分配10个单位的空间。其扩容的策略是使用1.5倍的扩容机制，当元素数量超过分配的空间的时候会采取1.5倍的扩容机制，在内存中找到一片符合扩容后的空间，将原来的数据搬运过去。。。。

相信上述吟唱相信都不陌生。在面试过程当中吟唱上述内，当然没有问题。但是作为一个未来需要进入大厂的候选人，那么上述的吟唱就显得有点不足了。比如说采用懒加载机制，为什么采用懒加载机制？有什么好处吗？采用扩容的策略为什么是1.5倍，而不是按需分配或者说是2倍，3倍？这个能够让面试官能够看到你对于java集合思考的内容你都没有体现出来，只能说不扣分。就好比跟流水线上的可乐一样，都是可乐，你如何体现你的可乐对于其他可乐的独到之处。那么接下来就是需要对上述的吟唱以及问题进行剖析了。

Java采用懒加载机制有什么好处？

相信各位开发者在j开发过程当中，经常创建一个集合，可能用到了，也可能后续忘记用了。如果不采用懒加载机制，然后经常创建了一个集合，后续忘记用了，那么此时这里的集合就会出现一个耳熟能详的问题：“占着茅坑不拉屎”。问题严重的话就有可能导致OOM（内存泄露）。这里我再解释一下什么是内存泄漏。（我一刚开始的时候以为内存泄漏是在java的内存当中，哪块内存丢了，被黑客或者其他人知道这块内存存储了什么数据，从而导致数据隐私性的问题）实际上的OOM是指应用进程中存在无法回收的内存或使用的内存过多，其它应用进程申请分配内存时系统会优先强制退出当前进程以减轻系统负担，或者当前应用进程再次申请内存时，因系统无法分配更多内存抛异常而退出当前应用进程。一般表现为异常退出当前应用进程（前台闪退或后台系统强制退出当前进程)。那么知道什么是OOM的话对于采用懒加载机制的原因就很显而易见了。

为什么ArrayList的扩容机制采用的是1.5倍，而不是按需分配，或者2倍、3倍呢？

面试官只要根据你的扩容倍数一追问，你要是不会，那么此时一定会慌张。战战兢兢地说1.5倍比较好？2倍、3倍太多了？按需分配太少了？如果有上述问题的，不妨继续看下去。

为什么采用1.5倍而不是按需分配？

众所周知，ArrayList的数据在内存中是通过一片连续的内存数组去存储的。并且对于ArrayList的数据搬家，是需要在内存中开辟一个新的能够容纳数据的连续的内存地址的。

那么如果采用按需分配，比如说，新增一个元素，我就给他分配一个元素。那么此时我举个例子。假如我有1000条数据，我需要插入到ArrayList,采用按需分配的扩容机制。

那么当我开始插入第二条数据的时候，需要将第一条数据取出来，然后去找一个容纳两条数据的空间放进去。
那我插入第三条数据的时候，需要将前两条数据取出来，然后去找一个容纳三条数据的空间放进去。。。。。

相信机智的你一下就能想到，这不就是等差数列的求和嘛？那么此时的时间的复杂度就是 $O(n^2)$ ,那么这个时间复杂度在工业级的开发以效率为王的时代是万万不可的。那么为了增加效率，我用空间换时间行不行？我一次多给一些空间，扩容按照2倍，3倍甚至更高的倍数去扩容行不行？

为什么采用1.5倍而不是2倍、3倍甚至更高的倍数？

通过上述的内容，知道空间如果分配过少的话就会频繁的出现扩容数据搬家的情况。那么分配的空间过多的话会不会有问题呢？聪明的你一下就想到了，分配过多的话，那岂不是内存空间会有很大的浪费嘛？没错，如果我一下分配大量的空间给一个数据量不是很多的集合，就会造成大量的内存空间的浪费。那么为什么是1.5倍？其实这里面存在着权衡的艺术。分配空间过小，就需要频繁的进行搬家，分配空间过大，那么就会造成资源不必要的浪费。其在底层的扩容是通过位运算符进行扩容的。newCapacity = oldCapacity + (oldCapacity >> 1)

同时呢使用1.5倍，数组释放的空闲空间，刚好能被下一次扩容的新数组重复利用，大幅减少内存碎片，内存利用率高。举个例子，初始10个空间占满了，现在需要进行扩容，其在内存的占用的格子为[1_{10]，那么我进行扩容，去新地方占[11}25],此时的内存碎片是用不到的。那么再当我进行扩容，此时需要的空间为22个连续格子，此时释放的[1~10] + [11~25]就能凑出22个格子，直接复用之前的旧的内存区域

那么此时相信你对ArrayList的一些基础知识有了深刻的理解。接下来就需要与其他的内容结合了。比如说多线程。那么对于ArrayList这个集合，其是线程安全的嘛？我这里先说结论，不是线程安全的。为什么？听我娓娓道来。

多线程导致数据丢失(覆盖)的问题

前面说了，ArrayList是有序的，也就是说其插入是按照顺序进行插入的。那么在多线程的情况下就会导致数据丢失的问题。

可以想象两个同学 A、B (线程 A、B) 去食堂占座 (往集合里插入元素)。食堂这一排有 5 个固定座位（对应数组容量 5，座位编号 0~4），现在已经坐满了前 3 个座位，只剩最后 1 个 4 号座位是空的（对应 size=3，数组容量充足，无需扩容）。此时两个同学 A、B 同时过来占座：

A 同学先查看：还有空位（4 号座位），食堂不用额外加新桌子（无需扩容）。
B 同学几乎同时查看：也看到还有空位（4 号座位），也判定不用加新桌子。
A 同学判断座位没有被占之后，把书包（要插入的数据）丢在 4 号座位占座，然后就去打饭了。
但 B 同学之前已经确认过 “有空位”，没有重新检查座位是否已被占用，直接也把书包丢在 4 号座位。
可 4 号座位已经被 A 同学的书包占了，B 同学的书包直接把 A 同学的书包挤掉，对应程序中出现 数据覆盖丢失，A 同学插入的数据（书包）被 B 同学的数据（书包）替换，最终集合中只保留 B 同学的数据。

多线程导致数据越界的问题

可以想象两个同学 A、B (线程 A、B) 去食堂占座 (往集合里插入元素)。食堂这一排只有 10 个固定座位（对应数组容量 10，座位编号 0~9），现在已经坐满了前 9 个座位，只剩最后 1 个 9 号座位是空的（对应 size=9）。

此时两个同学 A、B 同时过来占座：

A 同学先查看：还有空位（9 号座位），食堂不用额外加新桌子（不用扩容）。
B 同学几乎同时查看：也看到还有空位（9 号座位），也判定不用加新桌子。
A 同学直接把书包丢在9 号座位占座，现在 10 个座位全部坐满，没有空位了。
但 B 同学之前已经确认过 “有空位”，直接往9 号座位之后的第 10 号座位放书包。
可食堂根本没有第 10 号座位，书包直接掉地上摔了，对应程序抛出 数组越界异常 ArrayIndexOutOfBoundsException。

LinkList

LinkList相信大家都很熟悉，但是在开发过程当中经常不怎么用。为什么？不是说LinkList对于插入数据在时间复杂度上优于ArrayList嘛？为什么大多数对于插入数据，开发者依旧使用ArrayList去操作呢?导致LinkList对于开发者来说就像一个熟悉的陌生人一样。相信你多多少少有上述问题，接下来听我给你解释。

由于LinkList底层是基于双向链表实现的，那么对于链表这个数据结构来说，相信大家不陌生。理论上插入的时间复杂度是O(1)，对于频繁的进行插入的操作来说，很显然在理论上很友好。那么很多朋友，在面试遇到LinkList对于插入数据在时间复杂度上优于ArrayList，在开发过程中我去使用LinkList行不行？

如果回答可以，那么你的理论上没有问题，因为你知道对于插入数据其时间复杂度为O(1)。但是，其实这样是有问题的，因为你没有考虑到现代的CPU的架构
如果回答不可以，那么聪明的你一定想到了从现代CPU的架构出发。这里有 3 个现实层面的核心问题。
- 首先，LinkedList 插入时间复杂度为 O (1)，有一个致命前提：你已经提前找到了要插入的节点。但实际开发里，绝大多数场景我们都需要先遍历链表找到对应位置，查找节点的时间复杂度是 O (n)，因此整体插入的实际耗时依旧是 O (n)，和 ArrayList 中间插入没有本质差距。
- 其次，现代 CPU 依靠缓存行、空间局部性原理实现高速运算：ArrayList 底层是连续数组，内存地址紧密连续，CPU喜欢顺手牵羊，他会把用到的数据周围的数据一起缓存起来，访问、读取时缓存命中率极高；而 LinkedList 的双向链表节点，在堆内存里是零散分布的，地址完全不连续，CPU 每访问一个节点都要重新加载缓存，频繁触发缓存失效，实际运行速度会远慢于 ArrayList。
- 最后，双向链表每个节点都需要存储前驱、后继两个指针，会产生大量额外内存开销，还会造成内存碎片化；而 ArrayList 是连续内存，内存利用率更高，对 GC 垃圾回收也更友好。
- 补充一下缓存行和空间局部性原理的知识。
  - 缓存行：缓存行是CPU 从内存搬运数据的最小固定单位。同时呢CPU喜欢顺手牵羊，他拿数据不会一个个拿，而是一次性把这个数据 + 它周围连续的 64 字节全部搬进高速缓存，后面再用附近数据，直接从缓存拿，速度极快。
  - 空间局部性：CPU很聪明。只要你访问了某一块数据，它旁边连续的一堆数据，大概率马上也要被用到。

Set

对于 Set 相信大家也并不陌生，可以将 Set 想象成只允许放独一无二物品的储物柜，核心特性是元素无序、不可重复。开发中最常用的就是无序不可重复的HashSet，以及有序不可重复的TreeSet。HashSet底层依托哈希表实现，查询、增删效率极高；TreeSet底层依托红黑树实现，天然支持元素排序。那么这两个集合我们在开发当中，以及在面试中可能需要用到什么知识呢？请接着往下看。

HashSet

面试试问：你熟悉 Java 集合？那你说一下 java 集合当中的 HashSet 吧。

于是你就开始吟唱：HashSet 底层是基于HashMap实现的，底层数据存储采用哈希表****（数组 + 链表 + 红黑树）的方式，是开发过程中用来去重、查询最多的集合。默认初始容量 16，采用2 的幂次扩容机制，负载因子 0.75，当元素数量达到容量 * 负载因子时触发扩容；当链表长度超过 8、数组容量大于 64 时，链表转化为红黑树，优化查询效率……

上述吟唱在面试当中，算是中规中矩。但是作为一个有追求的开发者，你有没有想过以下几个问题？

HashSet 底层为什么选择 HashMap 来实现，而不是直接搞一套自己的数据结构？
HashMap 的负载因子为什么是 0.75？0.5 行不行？1.0 行不行？
HashSet 为什么是无序的？想要有序怎么办？
往 HashSet 中存入自定义对象时，为什么必须同时重写 equals () 和 hashCode ()？只重写一个会引发什么致命 bug？
HashSet 在多线程并发操作下会出现什么问题？
为什么链表转红黑树需要同时满足"链表长度超过8"和"数组容量大于64"两个条件？
为什么红黑树转回链表的阈值是6，而不是7或者8？

如果你对这些问题的答案只是"背八股背的"，那么恭喜你，这篇文档就是为你准备的。让我们继续深入剖析。

HashSet 底层为什么选择 HashMap 来实现？

这个问题其实很有意思。你可以换个角度想：HashSet 只需要存 key，不需要存 value。但 HashMap 是 key-value 键值对的结构，这不是浪费了吗？

答案确实有点"浪费"。打开 HashSet 的源码你会发现，HashSet 内部就是维护了一个 HashMap，而每次 add 元素时，其实是把元素作为 key，一个固定的 Object 对象（PRESENT）作为 value 存进去的。

那为什么不自己搞一套只存 key 的数据结构呢？这就体现了代码复用的智慧。HashSet 需要的去重、快速查找能力，HashMap 已经全部具备了。与其重新造轮子，不如站在巨人的肩膀上。虽然多存了一个无用的 value 引用，但换来的是代码量的大幅减少和维护成本的降低。这种用极小的空间代价换取代码简洁性的做法，正是优秀架构设计的体现。

HashMap 的负载因子为什么是 0.75？0.5 行不行？1.0 行不行？

负载因子决定了 HashMap 在什么时候触发扩容。负载因子 = 元素数量 / 数组容量。

0.5 行不行？ 行，但是太保守了。负载因子 0.5 意味着数组只用了一半就开始扩容，剩下的一半空间全浪费了。这就像你租了一个100平米的房子，住了50个人就觉得太挤要换200平米的，明显不划算。

1.0 行不行？ 也行，但是太极端了。负载因子 1.0 意味着数组塞满了才扩容，此时哈希冲突的概率会非常高，链表会变得很长，查询效率大幅下降。这就像公交车已经挤到贴在一起了，还要继续上人，大家都难受。

为什么是 0.75？ 这是时间和空间权衡的结果。0.75 刚好在空间利用率和查询效率之间找到了一个平衡点。而且从数学角度看，0.75 对应的泊松分布下，链表长度达到 8 的概率已经极低（约千万分之六），这意味着绝大多数情况下哈希冲突都在可控范围内。

HashSet 为什么是无序的？

很多同学都知道 HashSet 是无序的，但你清楚它为什么无序吗？

我们前面说过，HashSet 底层是基于 HashMap 实现的。当你往 HashSet 里 add 一个元素时，HashSet 其实是调用了 HashMap 的 put 方法，把元素作为 key，一个固定的 Object 对象（PRESENT）作为 value 存进去的。

那 HashMap 是怎么决定元素存放在哪个位置的呢？答案是：通过 key 的 hashCode 计算数组下标。

可以想象一个场景：你去图书馆还书，图书管理员不是按照你来的先后顺序把书放在书架上，而是根据书名的拼音首字母，把书放到对应的书架格子里。"Python入门"可能放在 P 区，"Java编程"放在 J 区，"C++指南"放在 C 区。虽然你是按顺序还的书，但书在书架上的位置完全是由书名决定的，而不是由你还书的顺序决定的。

HashSet 就是这个原理。元素存储的位置是由 hashCode 决定的，而不是由插入顺序决定的。所以当你遍历 HashSet 时，拿到的元素顺序自然就和插入顺序不一致了。

那如果你想要一个既去重又保持插入顺序的集合怎么办？答案是使用 LinkedHashSet。它在 HashSet 的基础上额外维护了一个双向链表，记录了元素的插入顺序。就像图书馆管理员不仅根据书名把书放到对应区域，还拿个小本子记录了你还书的顺序，需要的时候可以按照这个顺序把书取出来。

往 HashSet 中存入自定义对象时，为什么必须同时重写 equals () 和 hashCode ()？只重写一个会引发什么致命 bug？

这个问题在实际开发中非常常见，也是很多隐藏 bug 的根源。

我们先来了解一下 HashSet 判断元素是否重复的流程：

首先计算元素的 hashCode，找到对应的数组下标（桶的位置）
如果这个桶是空的，说明没有冲突，直接放进去
如果这个桶已经有元素了（哈希冲突），则用 equals 方法逐个比较，判断是否是同一个元素

现在问题来了：如果只重写其中一个方法会怎样？

场景一：只重写 equals，不重写 hashCode

假设你定义了一个 Student 类，只重写了 equals 方法，认为学号相同的两个学生是同一个学生，但没有重写 hashCode。

public class Student {
    private String studentId;
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Student student = (Student) obj;
        return Objects.equals(studentId, student.studentId);
    }
    // 没有重写 hashCode，使用 Object 默认的实现
}

此时会发生什么？Object 默认的 hashCode 是根据对象的内存地址计算的。也就是说，即使两个 Student 对象的学号相同（equals 返回 true），但因为它们是两个不同的对象，内存地址不同，hashCode 也不同。

结果就是：HashSet 会根据不同的 hashCode 把这两个"相同"的学生放到不同的桶里，去重功能完全失效。你的 Set 里会出现两个学号一模一样的学生，这显然是个致命 bug。

场景二：只重写 hashCode，不重写 equals

public class Student {
    private String studentId;
    
    @Override
    public int hashCode() {
        return Objects.hash(studentId);
    }
    // 没有重写 equals，使用 Object 默认的实现
}

Object 默认的 equals 是比较内存地址（==）。此时两个学号相同的 Student 对象，虽然 hashCode 相同（会落在同一个桶里），但 equals 比较的是内存地址，返回 false。

结果就是：HashSet 会认为这是两个不同的元素，去重功能依然失效。

正确做法：同时重写 equals 和 hashCode

public class Student {
    private String studentId;
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Student student = (Student) obj;
        return Objects.equals(studentId, student.studentId);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(studentId);
    }
}

这里有一个非常重要的约定（Java 规范中明确说明的）：如果两个对象 equals 返回 true，那么它们的 hashCode 必须相同。 反之则不一定，hashCode 相同的对象，equals 不一定返回 true（这就是哈希冲突）。

这个约定是 HashSet 正常工作的基石。违背了这个约定，HashSet 的去重机制就会形同虚设。

HashSet 在多线程并发操作下会出现什么问题？

很多同学知道 ArrayList 线程不安全，但往往忽略了 HashSet 同样不是线程安全的。因为 HashSet 底层就是 HashMap，HashMap 有的并发问题，HashSet 一个都跑不掉。

问题一：数据丢失（元素覆盖）

可以想象两个同学 A、B（线程 A、B）同时往一个只能放唯一物品的储物柜（HashSet）里放物品。他们计算出了同一个格子编号，然后同时往里放。A 先放了物品"苹果"，B 几乎同时也放了物品"香蕉"。由于没有加锁，B 的物品直接把 A 的物品覆盖掉了。最终柜子里只有"香蕉"，"苹果"凭空消失了。

问题二：集合结构错乱（size 不准确）

HashSet 内部维护了一个 size 变量来记录元素数量。在多线程并发 add 时，可能出现以下情况：

线程 A 读取到当前 size = 5
线程 B 也读取到当前 size = 5
线程 A 成功添加元素，将 size 更新为 6
线程 B 也成功添加元素，将 size 更新为 6

但实际上添加了两个元素，size 应该是 7，结果却是 6。这就导致 size 的值和实际元素数量不一致，后续基于 size 的操作都会出现异常。

问题三：扩容时的结构破坏

当 HashSet 底层 HashMap 触发扩容时，需要将所有元素重新计算位置并迁移到新的数组中。如果此时有其他线程同时在添加元素，可能会导致元素被放错位置，甚至出现链表断裂、元素丢失等严重问题。

问题四：遍历时 ConcurrentModificationException

一个线程在遍历 HashSet，另一个线程同时修改了集合（add 或 remove），遍历时就会抛出 ConcurrentModificationException 异常。这是 Java 集合的 fail-fast 机制，目的是防止遍历到不一致的数据。

解决方案：

如果需要在多线程环境下使用 HashSet，有以下几种方案：

使用 Collections.synchronizedSet(new HashSet<>())：给整个集合加一把大锁，简单但性能差
使用 ConcurrentHashMap.newKeySet()：基于 ConcurrentHashMap 实现的线程安全 Set，性能更好
使用 CopyOnWriteArraySet：基于 CopyOnWriteArrayList 实现，适合读多写少的场景
为什么链表转红黑树需要同时满足"链表长度超过8"和"数组容量大于64"？

这个问题在后面的 HashMap 部分会详细展开，先卖个关子，耐心往下看～

为什么红黑树转回链表的阈值是6？

这个问题同样在后面的 HashMap 部分会有详细解答，让我们继续深入 HashMap 的世界。

TreeSet

讲完了 HashSet，我们把目光转向 Set 家族的另一员大将——TreeSet。

前面在 Set 的简介中提到过：TreeSet 底层依托红黑树实现，天然支持元素排序。那 TreeSet 到底强在哪里？它和 HashSet 又该如何选择？

TreeSet 底层红黑树，它到底是怎么实现排序的？

你可以把 TreeSet 想象成一个自动分拣的快递柜。每当你往里面放一个包裹，柜子里的智能系统会自动按照包裹的大小、重量或者你自定义的规则，把包裹放到合适的位置。等你取件的时候，包裹已经是按照顺序排列好的了。

TreeSet 底层使用的是红黑树（一种自平衡二叉搜索树）。红黑树的特性是：左子树的所有节点都小于根节点，右子树的所有节点都大于根节点。每当你往 TreeSet 中 add 一个元素，红黑树会根据元素的比较结果，自动找到正确的位置插入，并保持树的平衡。

所以，TreeSet 的排序能力不是靠"存完再排序"，而是插入时就排好了序。遍历 TreeSet 时，按照中序遍历的顺序取出元素，天然就是有序的。

TreeSet 排序的两种方式：自然排序 vs 自定义排序

TreeSet 支持两种排序方式：

方式一：自然排序（元素实现 Comparable 接口）

TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(1);
treeSet.add(2);
// 遍历结果：1, 2, 3

Integer、String 等 Java 内置类型都实现了 Comparable 接口，所以可以直接用 TreeSet 排序。

但如果你存的是自定义对象，比如 Student 类，就必须让 Student 实现 Comparable 接口：

public class Student implements Comparable<Student> {
    private String name;
    private int age;
    
    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.age, other.age); // 按年龄排序
    }
}

方式二：自定义排序（传入 Comparator 比较器）

如果你不想修改 Student 类，或者想按照不同的规则排序（比如有时按年龄，有时按姓名），可以在创建 TreeSet 时传入一个 Comparator：

TreeSet<Student> treeSet = new TreeSet<>(Comparator.comparing(Student::getName));
treeSet.add(new Student("张三", 20));
treeSet.add(new Student("李四", 18));
// 遍历结果：按姓名排序

这种方式更加灵活，同一个类可以有多套排序规则。

TreeSet 和 HashSet 该如何选择？

这是面试中的经典问题。我们可以从以下几个维度对比：

对比维度	HashSet	TreeSet
底层结构	哈希表（数组 + 链表 + 红黑树）	红黑树
是否有序	无序	有序（按元素比较结果排序）
增删查时间复杂度	O(1)（平均）	O(log n)
元素要求	需正确实现 equals 和 hashCode	需实现 Comparable 或传入 Comparator
null 元素	允许一个 null	不允许 null（无法比较大小）

选择建议：

如果你只需要去重，不在乎顺序，选 HashSet，因为 O(1) 的查询效率远高于 TreeSet 的 O(log n)
如果你需要去重 + 排序，或者需要快速获取最大 / 最小元素（first() / last()），选 TreeSet
如果你需要去重 + 保持插入顺序（不是排序），选 LinkedHashSet
TreeSet 不允许存 null，为什么？

很多同学在使用 TreeSet 时会踩到这个坑：往 TreeSet 中 add 一个 null，直接抛出 NullPointerException。

原因很简单：TreeSet 插入元素时，需要调用 compareTo 或 compare 方法来比较大小，确定插入位置。而 null 是无法参与比较的。你让一个 null 和另一个元素比大小，它怎么说？

反观 HashSet，它只关心 hashCode 和 equals，null 的 hashCode 是 0，equals 也只和 null 本身相等，所以 HashSet 可以容纳一个 null。

TreeSet 的一个隐藏坑：排序字段相同时元素被"吃掉"

这是实际开发中最容易踩的坑之一。

假设你创建了一个 TreeSet，按照 Student 的年龄排序：

TreeSet<Student> treeSet = new TreeSet<>(Comparator.comparing(Student::getAge));
treeSet.add(new Student("张三", 20));
treeSet.add(new Student("李四", 20)); // 年龄也是 20

你满心以为会存进两个学生，但遍历时发现只有一个！为什么？

因为 TreeSet 判断元素是否重复的标准不是 equals，而是compareTo 返回 0。当两个学生的年龄都是 20 时，compareTo 返回 0，TreeSet 就认为这是同一个元素，第二个学生直接被"吃掉"了。

解决方案： 在 compareTo 中增加次级排序条件：

TreeSet<Student> treeSet = new TreeSet<>(
    Comparator.comparing(Student::getAge)
              .thenComparing(Student::getName) // 年龄相同时按姓名排序
);

或者更简单地，在比较器中加上唯一标识（如 ID）作为兜底：

TreeSet<Student> treeSet = new TreeSet<>(
    Comparator.comparing(Student::getAge)
              .thenComparing(Student::getId) // 确保比较结果不会为 0
);

这个坑在开发中非常隐蔽，而且很难 debug。记住：TreeSet 的去重依据是排序比较结果，不是 equals。

Map

对于 Map 相信你已经非常熟悉了，可以将 Map 想象成快递柜，每个柜子都有一个编号（key），柜子里面存放着你的包裹（value）。通过编号可以快速找到对应的包裹，这就是 Map 的核心特性：键值对映射、通过 key 快速查找 value。

开发中最常用的就是 HashMap，以及支持有序的 LinkedHashMap，支持排序的 TreeMap。那么这些集合在开发过程当中，以及在面试中可能需要用到什么知识呢？请接着往下看。

HashMap

面试官问：你熟悉 Java 集合？那你说一下 HashMap 吧。

于是你就开始吟唱：HashMap 底层采用数组 + 链表 + 红黑树的结构，通过 key 的 hashCode 计算数组下标，默认初始容量 16，负载因子 0.75，当元素数量超过容量 * 负载因子时触发扩容，扩容为原来的 2 倍。JDK1.7 使用头插法，JDK1.8 改为尾插法，并且在链表长度超过 8 且数组容量大于 64 时将链表转为红黑树……

这段吟唱，说实话，能拿个及格分。但是，如果你想让面试官眼前一亮，你得能回答出背后的"为什么"。

HashMap 的底层结构，为什么是数组 + 链表 + 红黑树？

我们可以把 HashMap 想象成一个巨大的快递柜，数组就是快递柜的一排排格子，每个格子有一个编号（数组下标）。当我们存放快递（key-value 对）的时候，会通过一个"计算规则"（hashCode）来决定这个快递应该放在哪个格子里。

但问题来了，快递柜的格子数量是有限的，而快递数量是无限的。那么必然会出现多个快递被分配到同一个格子的情况，这就是哈希冲突。

怎么办呢？HashMap 的做法是：既然一个格子放不下多个快递，那就在每个格子上挂一个小袋子（链表），所有被分配到同一个格子的快递都放到这个小袋子里。查询的时候，先根据 key 找到对应的格子，然后在小袋子里一个个比对，找到对应的快递。

但是，如果哈希冲突特别严重，一个小袋子里挂了太多快递，那么每次查询都需要遍历整个小袋子，时间复杂度就从 O(1) 退化到了 O(n)。这显然是不可接受的。

于是 JDK1.8 引入了红黑树。当小袋子里的快递数量超过一定阈值（8个）时，就把小袋子升级为一个小型的自动分拣柜（红黑树），这样查询时间复杂度就从 O(n) 优化到了 O(log n)。

所以 HashMap 的底层结构可以总结为：数组提供 O(1) 的快速定位，链表解决哈希冲突，红黑树在冲突严重时保证查询效率。

JDK1.7 和 JDK1.8 的 HashMap 有什么区别？为什么要在 1.8 引入红黑树？

JDK1.7 的 HashMap 只有数组 + 链表的结构。在大多数情况下，哈希分布比较均匀，链表长度不会太长，查询效率是可以接受的。

但是，如果遇到恶意攻击或者极端情况，大量 key 的 hashCode 计算后都落在同一个数组下标，链表就会变得非常长。想象一下，一个快递柜的小袋子里挂了 1000 个快递，每次取件都要翻遍整个袋子，这效率能接受吗？

所以在 JDK1.8 引入了红黑树，本质上是一种防御性优化。在正常情况下，链表和红黑树的性能差异不大；但在极端情况下，红黑树能保证查询时间复杂度不会退化到 O(n)。

为什么链表转红黑树需要同时满足"链表长度超过8"和"数组容量大于64"？

这个问题问得很好。你可能会想，既然链表长度超过 8 就转红黑树，那直接转不就行了，为什么要加一个"数组容量大于64"的限制？

这里面的核心思想是：不要轻易引入红黑树，因为红黑树的维护成本很高。

红黑树虽然查询效率高，但插入、删除时需要不断调整树的平衡（旋转、变色），这些操作的开销远比链表大。所以 HashMap 的设计者认为：如果数组容量还很小（小于64），说明整个 HashMap 的规模还不大，此时更优的策略是扩容而不是树化。

扩容可以把原来集中在一个链表上的元素分散到更多的数组格子上，从根本上减少冲突。只有当数组已经足够大（大于64），但某个格子的链表还是很长时，才说明这些 key 的哈希分布确实有问题，此时才需要引入红黑树。

这个设计体现了架构设计中一个非常重要的原则：不要过度优化，先尝试更简单、更轻量的方案。

为什么红黑树转回链表的阈值是 6？为什么转树阈值 8 和转链阈值 6 之间要隔一个？

如果你仔细思考，会发现这其实是一个防抖动设计。

假设转树阈值和转链阈值都是 8，那么当链表长度为 8 时转为红黑树，然后插入一个元素变成 9，删除一个元素又变成 8，再删除又变成 7……此时就会在红黑树和链表之间来回切换，频繁进行树化和链化操作，性能反而更差。

所以设计者在 8 和 6 之间留了一个缓冲区间（7）。当链表长度为 7 时，既不会树化也不会链化，保持当前状态。这样就避免了在临界点附近频繁切换数据结构。

至于为什么选择 6 而不是 7，我的理解是：如果阈值是 7，那么当红黑树中有 7 个节点时，删除一个变成 6 就转链表，但插入一个又变成 8 又转树，还是不够稳定。选择 6 可以让缓冲区间更宽，减少切换频率。

HashMap 为什么是线程不安全的？

HashMap 在多线程环境下会出现很多问题，主要有以下几个：

数据覆盖问题

想象两个同学 A 和 B 同时往快递柜里放快递。他们通过相同的计算规则（hashCode）算出了同一个格子编号，然后同时往那个格子里放快递。

A 同学先把快递放进去，然后 B 同学几乎同时也把快递放进去。由于没有加锁，B 同学的快递直接把 A 同学的快递给覆盖掉了。A 同学的快递就这样凭空消失了。

扩容时的死循环问题（JDK1.7）

在 JDK1.7 中，HashMap 扩容时使用的是头插法。多线程扩容时，链表的节点指针可能会形成环，导致后续查询时陷入死循环。

JDK1.8 改为尾插法，解决了死循环问题，但数据覆盖的问题依然存在。所以结论是：HashMap 无论在哪一个版本，都不是线程安全的。

ConcurrentHashMap

面试官问：HashMap 线程不安全，那在多线程环境下应该用什么？

你答：ConcurrentHashMap。

面试官追问：那你说说 ConcurrentHashMap 为什么是线程安全的？

这个时候，如果你只是回答"因为它加了锁"，那就太浅了。让我们深入剖析一下。

ConcurrentHashMap 为什么是线程安全的？

我们可以把 ConcurrentHashMap 想象成一个大型物流分拣中心。

JDK1.7 的实现方式：

整个分拣中心被划分成了多个区域（Segment），每个区域有自己的快递柜。当多个工人（线程）同时操作时，只要他们操作的是不同的区域，就不会互相干扰。只有当两个工人要操作同一个区域时，才需要排队。

这种设计叫做分段锁（Segment Lock）。它把一个大锁拆成了多个小锁，大大减少了锁竞争。

说明： Segment1 被线程A锁住，线程C想操作同一个 Segment 只能排队。线程B操作不同的 Segment2，互不影响。

JDK1.8 的实现方式：

JDK1.8 对 ConcurrentHashMap 进行了重构，放弃了 Segment 的设计，改用更细粒度的 CAS + synchronized。

每个数组格子（桶）都有自己的锁。当线程要操作某个桶时，只需要锁住这个桶就行，不会影响其他桶的操作。

对于插入操作，先使用 CAS（Compare And Swap，一种无锁的原子操作）尝试插入，如果 CAS 失败（说明有其他线程在操作），再使用 synchronized 锁住当前桶。

这种设计比 JDK1.7 的分段锁更加精细，锁的粒度更小，并发性能更好。

说明： JDK1.8 锁的粒度从 Segment（一段）细化到了单个桶。线程操作不同桶时完全并行，只有操作同一个桶时才需要竞争锁。

JDK1.7 和 JDK1.8 的 ConcurrentHashMap 有什么区别？

对比维度	JDK1.7	JDK1.8
底层结构	数组 + Segment + 链表	数组 + 链表 + 红黑树
锁机制	Segment 分段锁	CAS + synchronized
锁粒度	一个 Segment 包含多个桶	单个桶级别
最大并发度	Segment 数量（默认16）	理论无限制

可以看出，JDK1.8 的 ConcurrentHashMap 在并发度和性能上都有了质的提升。

为什么 JDK1.8 的底层结构从 Segment 变成了数组 + 链表 + 红黑树？

这里涉及两个变化，我们分开来看。

变化一：为什么去掉 Segment？

这个问题前面已经讲了，核心是锁粒度的问题。Segment 把整个数组分成 16 段，最多只能 16 个线程并发。去掉 Segment 后，锁直接细化到单个桶，并发度大幅提升。

变化二：为什么引入红黑树？

JDK1.8 的 HashMap 引入了红黑树，ConcurrentHashMap 也跟着引入，原因是防止极端情况下的性能退化。

想象一下，如果恶意构造大量 hashCode 相同的 key，全部落在同一个桶里，链表就会变得非常长。查询这个桶时，时间复杂度就从 O(1) 退化到了 O(n)。

JDK1.7 的 Segment 结构下，一个 Segment 里有多个桶。如果某个桶的链表特别长，整个 Segment 都会被拖累。而 JDK1.8 去掉 Segment 后，虽然锁粒度更细了，但单个桶的性能问题依然需要解决。

所以 ConcurrentHashMap 在 JDK1.8 引入了红黑树：当链表长度超过 8 且数组容量大于 64 时，链表转红黑树。这样即使哈希冲突严重，查询时间复杂度也能控制在 O(log n)，不会退化到 O(n)。

这就像从"16 个分拣区域"升级为"每个快递柜格子上都有一把独立的锁"，工人之间的干扰降到了最低。

LinkedHashMap

相信你对 LinkedHashMap 也有所耳闻。可以将 LinkedHashMap 想象成带编号序列的快递柜，除了能像普通快递柜一样通过编号快速找到包裹外，还能按照存入的顺序依次取出包裹。

LinkedHashMap 在 HashMap 的基础上，为每个节点增加了前驱和后继指针，维护了一个双向链表。这个链表记录了元素的插入顺序（或者访问顺序），使得 LinkedHashMap 具备了迭代有序的特性。

它的核心应用场景是什么？LRU 缓存（最近最少使用缓存）。

通过重写 removeEldestEntry 方法，可以在插入新元素时自动删除最久未使用的元素。很多缓存框架的底层都使用了 LinkedHashMap 来实现 LRU 策略。

TreeMap

TreeMap 可以想象成按字母顺序排列的快递柜，每个快递都会按照 key 的大小自动排列。取出快递时，可以按照 key 的升序或降序依次取出。

TreeMap 底层基于红黑树实现，天然支持排序操作。查询、插入、删除的时间复杂度都是 O(log n)。

它的适用场景是：需要按照 key 排序，或者需要快速获取某个范围内（subMap、headMap、tailMap）的元素。

其他集合

Queue 和 Deque

Queue（队列）可以想象成食堂排队的队伍，遵循**先进先出（FIFO）**的原则。先来的同学先打到饭，后来的同学排在后面。

Deque（双端队列）则更加灵活，可以从两端进行插入和删除。可以把它想象成一个两头都能进出的通道，既可以从前面进后面出，也可以从后面进前面出。

Deque 有一个特殊的能力：可以作为栈来使用。当只从一端进行插入和删除时，Deque 就退化成了栈（LIFO，后进先出）。

常用的实现类有：

LinkedList：基于双向链表，可以作为 List、Queue、Deque 使用
ArrayDeque：基于数组实现的双端队列，性能优于 LinkedList
PriorityQueue：基于堆实现的优先队列，每次取出的都是优先级最高（或最低）的元素

PriorityQueue

PriorityQueue 可以想象成VIP 通道。虽然大家都是排队，但是 VIP 客户可以优先办理业务。

PriorityQueue 底层使用**二叉堆（默认是最小堆）**实现。每次插入元素时，堆会自动调整结构，保证堆顶元素始终是最小（或最大）的。

典型应用场景：

Top K 问题（找出最大的 K 个元素）
任务调度（优先级高的任务优先执行）
Dijkstra 最短路径算法

CopyOnWriteArrayList

相信你对 CopyOnWriteArrayList 这个集合感到陌生。可以将 CopyOnWriteArrayList 想象成一个公告栏。每当有人要修改公告内容时，管理员不会直接在原公告栏上涂改，而是先拿一块新的空白公告栏，把旧内容抄过去，加上新内容，然后把旧公告栏撤下来，换上新公告栏。

这就是 CopyOnWriteArrayList 的核心思想：写时复制（Copy On Write）。

写入操作：每次 add、set、remove 时，都会先复制一份底层数组的副本，在副本上进行修改，修改完成后再用新数组替换旧数组。
读取操作：直接读取当前数组，不加锁。
为什么需要 CopyOnWriteArrayList？

前面说过，ArrayList 是线程不安全的。如果要在多线程环境下使用一个 List，你可能会想到 Collections.synchronizedList。但它的问题是：读和读之间也会互相阻塞。

想象一个场景：100 个读者在看同一本书，如果给书加一把锁，那同时只能有一个人看，其他人必须排队。这显然是不合理的，因为看书（读取）并不会损坏书的内容。

CopyOnWriteArrayList 解决了这个问题：读不加锁，写时复制。多个线程可以同时读取，不会互相阻塞。只有写入时才需要加锁，而且写入操作是在副本上进行的，不会影响正在读取的线程。

CopyOnWriteArrayList 有什么缺点？

听起来很完美，对吧？但天下没有免费的午餐。CopyOnWriteArrayList 有两个明显的缺点：

内存占用翻倍

每次写入都会复制一份完整的数组副本。如果数组很大，频繁写入会导致大量内存被占用。就像公告栏有 1000 条通知，每次新增一条通知都要重新抄一份 1000 条的公告栏，这成本可不低。

数据不一致（弱一致性）

读取操作读取的是写入前的旧数组。也就是说，当你正在读取时，其他线程可能已经修改了数据，但你读到的还是旧数据。这就像你正在看公告栏的时候，管理员换了新公告，但你眼睛盯着的还是旧的那块，不会自动切换。

适用场景

基于以上特点，CopyOnWriteArrayList 最适合的场景是：读多写少。

典型应用：

事件监听器列表（监听器很少增删，但触发事件时会频繁遍历）
白名单 / 黑名单配置（配置更新频率低，但校验时会频繁读取）
缓存配置列表

一句话总结：如果你的 List 大部分时间在读，偶尔写一次，CopyOnWriteArrayList 是你的好帮手；如果写入频繁，还是老老实实用 Collections.synchronizedList 或者其他并发集合吧。

集合选型建议

讲了这么多集合，相信你已经眼花缭乱了。在实际开发中，如何选择合适的集合呢？我给你整理了一张选型指南：

场景	推荐集合	原因
频繁随机访问	ArrayList	连续内存，O(1) 访问
频繁中间插入/删除	ArrayList（数据量不大时）	CPU 缓存友好，实际性能不差
去重	HashSet	O(1) 查询，高效去重
需要保持插入顺序的去重	LinkedHashSet	去重 + 有序
需要排序的去重	TreeSet	天然有序
键值对映射	HashMap	O(1) 查询，最常用
需要保持插入顺序的键值对	LinkedHashMap	映射 + 有序
需要按 key 排序的键值对	TreeMap	映射 + 排序
多线程环境	ConcurrentHashMap	细粒度锁，高并发
读多写少的多线程 List	CopyOnWriteArrayList	读不加锁，写时复制
FIFO 队列	ArrayDeque / LinkedList	先进先出
栈	ArrayDeque	后进先出，性能优于 Stack
优先级队列	PriorityQueue	按优先级取出
LRU 缓存	LinkedHashMap	可自动淘汰最久未使用元素