最近带团队做代码评审我发现一个很有意思的现象很多能熟练写出业务代码的同学聊到 Java 集合框架时还是停留在“会用 API”的层面。问他们 ArrayList 扩容一次翻几倍、HashMap 为什么默认负载因子是 0.75、HashSet 去重到底依赖什么往往答不上来。恰好我最近在整理 Java 基础面试的复习资料把集合这块重新过了一遍所以这篇就把我对 Java 集合知识点的理解做一个系统梳理。这篇内容适合准备 Java 面试的人、做代码重构的人以及想把自己脑子里的集合知识体系整理得更完整的人。我不打算只罗列接口和实现类那网上到处都有。我重点讲三件事集合框架到底为什么这么设计、核心实现类的底层原理、实际开发中怎么选型才不踩坑。看完之后你再看那些“八股文”都会觉得通透很多。1. 集合框架的整体设计先搞懂 Java 集合到底解决什么问题1.1 编程里的集合和高等数学里的集合有什么不一样很多人第一次听说“集合”是在大一高等数学上册里数学上定义的集合是指“确定且互异对象的整体”研究的是元素是否属于某个集合、集合之间的交并补关系。Java 里的集合虽然也叫 Set但本质完全是另一回事——它是一套用来存放对象的容器解决的是对象怎么存、怎么取、怎么遍历、怎么排序的问题侧重点是数据结构。不过这两者有个重要的共通点数学集合要求元素“互异”Java 的 Set 也要求元素“不重复”。理解这个点之后再去想 HashSet 怎么实现去重、TreeSet 怎么维持有序思路就会顺很多。很多人学集合时觉得东西太多记不住就是因为没先分清“容器”和“数据结构”这两个视角结果把接口、实现类、并发集合一股脑混在一起背。1.2 Collection 和 Map两大家族各管一摊Java 集合框架的顶层可以分成两大家族Collection 和 Map。Collection 是单元素集合的根接口下面又分三个分支List有序、可重复元素按插入顺序排列可以通过下标访问。典型实现是 ArrayList、LinkedList。Set无序、不可重复重点解决“去重”问题。典型实现是 HashSet、LinkedHashSet、TreeSet。Queue队列主要用于“先进先出”或按优先级处理元素。典型实现是 ArrayDeque、PriorityQueue。Map 是另一个独立家族不继承 Collection它存的是键值对重点解决“按 key 找 value”的问题。典型实现是 HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap。为什么 Map 要单独设计成一个家族因为键值对这种模型没法用单元素序列来表达。一个 Map.Entry 里有 key 和 value 两个对象和 List 里存的单个对象不是一个维度。而且 Map 的很多操作比如按 key 遍历、按 key 哈希定位、对 key 排序都和单元素集合完全不同。把两者分开接口职责更清晰用起来也更顺手。另外所有集合类都实现了 Iterable 接口也就是说凡是能用增强 for 循环的集合底层都实现了这个接口。这里有个小知识foreach 语法糖在编译后其实是基于 iterator 实现的所以如果一个类没实现 Iterable它是没法用增强 for 遍历的。这也是为什么 ArrayList、HashSet 这些类都有 iterator() 方法。1.3 抽象类的作用为了少写重复代码集合框架里还有一层很容易被忽略的设计抽象类。比如 AbstractList、AbstractSet、AbstractMap。你去看 ArrayList 的源码会发现它继承自 AbstractList而很多方法比如 add、remove、set 在 AbstractList 里已经有骨架实现了子类只需要补上个别抽象方法。这就是典型的“模板方法模式”父类定义好算法骨架子类实现具体细节。比如 AbstractList 里已经实现了 iterator()它依赖子类提供的 get()、size()、add() 等方法子类不需要重复造轮子。面试官问“集合框架的设计有哪些值得借鉴”这其实是个很加分的回答点。面试官想听的往往不是你能背几个耗时对比而是你有没有从框架设计者的角度去思考为什么要抽象一层接口为什么要搞抽象类为什么 ArrayList 要继承 AbstractList 而不是直接实现 List理解了这层之后你才能说自己是“学过”集合框架而不是“看过”集合框架。2. 逐个拆解核心实现类知道底层数据结构就不会记混2.1 List 接口ArrayList 和 LinkedList 到底怎么选List 最常用的两个实现就是 ArrayList 和 LinkedList。ArrayList 底层是 Object 数组。无参构造创建时底层是个空数组第一次 add 才会分配默认容量 10。扩容时新容量 旧容量 (旧容量 1)也就是每次扩容 1.5 倍。比如容量 10 扩容到 1515 扩容到 22依此类推。扩容的本质是新建一个更大数组再用 System.arraycopy 把原数据搬过去。所以如果你能预估数据量最好在构造时就指定初始容量避免频繁扩容损失性能。LinkedList 底层是双向链表每个节点维护前驱和后继引用。它不像 ArrayList 需要连续内存插入删除只要能找到节点确实省去了数组平移的开销。但问题是按索引访问做不到 O(1)必须从头部或尾部逐步遍历。实际开发里很多人用 LinkedList 以为“插入删除快”但业务场景里绝大多数操作是遍历和随机访问LinkedList 反而更慢加上每个节点额外存储两个引用内存占用也更大。所以选型建议其实很简单场景推荐大量随机访问、尾插为主ArrayList需要频繁在头部/中间插入删除若不要求索引随机访问优先 ArrayDeque / LinkedList需要当栈使用ArrayDeque 更推荐需要当队列使用ArrayDeque 更推荐注意LinkedList 虽然实现了 List 接口也能当 Deque 用但不代表它适合所有场景。我见过不少项目里把一个 LinkedList 当成“万能容器”遍历几百次性能肉眼可见地慢换成 ArrayList 之后明显改善。2.2 Set 接口为什么 HashSet 无序TreeSet 有序Set 的核心是去重但它下面三个实现类的风格完全不同。HashSet 底层其实就是一个 HashMapadd 的元素作为 keyvalue 固定为一个 Object 占位。判断元素是否重复的标准是 hashCode 和 equals先看 hashCode 是否相同相同再走 equals。所以如果你存自定义对象就必须正确重写这两个方法否则两个字段值完全一样的对象也会被当成不同元素存进去。LinkedHashSet 是 HashSet 的子类底层用 LinkedHashMap 实现多了一条双向链表用来维护插入顺序。它牺牲一点性能换来迭代时能按插入顺序输出。适合对顺序有要求、但不想用 TreeSet 排序的场景。TreeSet 底层是 TreeMap是红黑树结构。它不依赖 hashCode而是按元素的自然顺序或构造时传入的 Comparator 来排序。每次插入都要比较所以时间复杂度是 O(log n)。TreeSet 里不允许 null因为红黑树排序时没法比较 null 的大小。如果你把比较器设置允许 null那可以商量否则会直接抛 NullPointerException。这三个结构对比一张表就很清晰实现类底层结构迭代顺序时间复杂度HashSetHashMap无序基本按哈希桶顺序增删查 O(1)LinkedHashSetLinkedHashMap按插入顺序增删查 O(1)略慢于 HashSetTreeSetTreeMap红黑树按自然顺序或 Comparator增删查 O(log n)2.3 Queue 和 Deque队列场景用得少但面试常考Queue 日常业务里用得相对少一点但在任务调度、生产者消费者、滑动窗口这些场景里很关键。ArrayDeque 底层是循环数组既支持先进先出也支持双端操作。它实现 Deque 接口可以当作栈用而且比 java.util.Stack 更推荐。注意ArrayDeque 不允许放 null 元素因为它用 null 来标记“槽位为空”。栈如果允许 null判断空栈时就会和“存在 null 元素”冲突所以干脆禁止。PriorityQueue 底层是二叉堆默认是小顶堆。你放进去元素后poll 出来的总是当前优先级最高的元素但元素在队列内部的存储顺序并不是排序后的形态而是堆结构。PriorityQueue 初始容量默认是 11扩容时如果旧容量小于 64容量翻倍大于等于 64扩容 1.5 倍。它同样不允许 null 元素因为堆调整时需要比较大小null 没法参与比较。很多面试题会问“让你实现一个 Top K 最大元素方案”PriorityQueue 就是默认答案。固定一个大小为 K 的小顶堆每次新元素比堆顶大就把堆顶替换掉时间复杂度是 O(n log K)比每次全量排序高效得多。2.4 Map 接口你真正需要熟练掌握的 Map 家族HashMap最常用底层是“数组 链表 红黑树”允许一个 null key 和多个 null value不保证迭代顺序。这是整个集合框架里的重中之重下一节我会单独展开。LinkedHashMap继承 HashMap内部额外维护一条双向链表。默认按插入顺序迭代构造时如果把 accessOrder 设为 true就按访问顺序迭代。基于这个特性LinkedHashMap 可以用来实现 LRU 缓存重写 removeEldestEntry 方法就能在超过容量时淘汰最久没访问的 Entry。TreeMap底层红黑树key 按自然顺序或 Comparator 排序。它实现了 NavigableMap 接口支持 subMap、headMap、tailMap 这些范围查询。注意 TreeMap 不允许 null key原因和 TreeSet 一样排序时没法比较。Hashtable这是历史遗留类方法用 synchronized 修饰保证线程安全但现在几乎不推荐使用。因为它锁的粒度太粗并发场景性能差而且它的迭代器是 fail-fast 的不是真正的强一致。现在并发场景用 ConcurrentHashMap 替代。ConcurrentHashMap并发版的 HashMap。JDK7 用分段锁JDK8 放弃了分段锁改用 CAS 配合 synchronized 锁桶头节点锁粒度更细读操作大部分不需要加锁。它不允许 null key 和 null value这个和 HashMap 不同。原因是在并发环境下无法区分“这个 key 不存在”和“这个 key 对应的 value 是 null”容易产生二义性。3. HashMap 源码级核心面试高频日常开发也容易踩坑3.1 底层结构数组、链表、红黑树三者怎么配合HashMap 底层是一个 Node 数组每个数组槽位叫桶。放元素时先算 key 的哈希定位到具体桶如果桶里没有元素直接放如果桶里已经有元素发生了哈希冲突就把新节点追加到链表末尾。JDK8 里链表长度超过阈值时会尝试转红黑树。具体条件是桶中链表长度大于等于 8且整个数组长度大于等于 64。两个条件同时满足才树化。如果链表长度到了 8但数组长度还不到 64HashMap 会优先扩容而不是转树因为扩容后哈希冲突会缓解链表长度自然变短。树化之后如果因为删除元素导致红黑树节点数少到 6会退化为链表。注意阈值 8 和 6 之间留了 7 的缓冲避免频繁树化和退化来回摇摆。为什么树化阈值选 8源码注释里给了个概率解释在随机哈希、负载因子 0.75 的情况下桶中链表长度达到 8 的概率已经极低大约亿分之六。所以正常情况下链表就够用了转红黑树只是“防御性编程”防止黑客构造大量哈希冲突的 key 导致性能从 O(1) 劣化到 O(n)。3.2 哈希寻址过程高位异或和位运算put 一个元素时HashMap 并不是直接用 key.hashCode() 作为桶下标。它会先做一次扰动把 hashCode 的高 16 位和低 16 位异或。代码是(h key.hashCode()) ^ (h 16)。为什么要做这一步因为桶下标用的是数组长度减一后做按位与比如(n - 1) hash。当数组长度比较小时直接拿 hash 和它做与运算高位的所有信息都会丢失只有低位参与计算。如果 hashCode 的低位分布不均匀冲突概率就会很高。把高 16 位异或到低 16 位相当于让高位信息也参与取模分散性更好。这也是 HashMap 的一个高频面试题为什么 HashMap 的容量是 2 的幂因为只有 n 是 2 的幂时(n - 1) hash才等价于hash % n而且位运算比取模快得多。为了在所有情况下都保持这个性质HashMap 的构造方法会把传入的初始容量调整成大于等于该值的最小 2 的幂。这个操作叫 tableSizeFor。3.3 负载因子 0.75 和扩容机制HashMap 的默认初始容量是 16默认负载因子是 0.75。扩容的临界值 threshold 容量 * 负载因子。默认情况下16 * 0.75 12也就是说元素个数达到 12 时HashMap 就会扩容成 32紧接着 threshold 变成 24以此类推。为什么负载因子要选 0.75这是时间复杂度和空间复杂度的一个折中。负载因子太高比如 1.0内存能省一些但哈希冲突会变多链表变长查询效率下降负载因子太低比如 0.5冲突少了但数组大部分空间是空的频繁扩容也很浪费。0.75 是在常见哈希函数下经过权衡后比较均衡的一个值也是默认值。如果你明确容器里放的元素很多可以在构造时指定更小的负载因子或者直接用容量估算公式而不是等着反复扩容。JDK8 扩容时元素位置重新计算有个很巧妙的规律因为容量翻倍刚好是二进制左移一位元素要么还在原来的下标位置要么从原来下标位置移动到“原下标 旧容量”的位置。比如旧容量 16元素原来在桶 3扩容成 32 后它只可能在 3 或者 19判断依据是 key 的 hash 值在旧容量对应那一位上是 0 还是 1。这个规律让扩容时不需要重新计算每个 key 的哈希只需要看新增的那个 bit 位就够了JDK8 就用了这个优化把扩容过程的性能提了一截。这里还要提一个经典坑JDK7 的 HashMap 扩容时用的是头插法多个线程同时对同一 HashMap 扩容时链表可能形成环形结构get 时就会进入死循环。JDK8 改成了尾插法解决了环的问题但 HashMap 依然不是线程安全的。并发场景下多个线程同时 put 可能导致覆盖、数据丢失必须用 ConcurrentHashMap。3.4 容量为什么是 2 的幂以及初始化容量的隐藏细节前面提到了(n - 1) hash高效的前提是 n 为 2 的幂。所以就算你在构造时传了 17HashMap 也会通过 tableSizeFor 调整成 32。这里有个很容易踩的坑new HashMap(7)不是说你真的能放下 7 个元素不扩容。它内部会把容量调整成 8然后 threshold 8 * 0.75 6。也就是说你插入第 7 个元素时HashMap 就触发扩容了。正确预估容量的做法是new HashMap((int) (expectedSize / 0.75f) 1)。比如你预计放 10 个元素那么最好设置初始容量为(int)(10 / 0.75f) 1 14HashMap 再调整成 16threshold 变成 12插入 10 个元素就不会触发扩容。很多资深一点的开发会用 Guava 的Maps.newHashMapWithExpectedSize其实本质也是那个公式。这个细节面试官也爱考能说出来说明你真正看过源码。4. 迭代、排序与并发这些实际操作里的坑我也踩过4.1 fail-fast 机制和 ConcurrentModificationExceptionArrayList、HashMap 这些集合里都有一个 modCount 字段记录集合被修改的次数。迭代器创建时会把这个值存到 expectedModCount 里。迭代过程中如果集合被第三方修改比如另一个线程在 put 数据modCount 和 expectedModCount 不一致迭代器就会立刻抛出 ConcurrentModificationException。这个机制叫 fail-fast宁可快速失败也不让迭代在错误状态中继续跑下去避免后续读到脏数据。它并不保证一定发生只是尽力检测并发修改所以不能依赖它来做并发控制。很多人踩过这个坑在 for-each 循环里直接调 list.remove()。表面看是 remove 后立刻 break有时不报错但很多情况下都会抛 ConcurrentModificationException。因为 for-each 底层用的就是迭代器而 ArrayList 的 remove() 改变了 modCount迭代器的 expectedModCount 没有同步更新。正确的删除方式有三种使用迭代器的iterator.remove()使用 JDK8 的removeIf或者先收集要删的元素循环结束后再统一删除。其中removeIf最简洁内部已经处理好了迭代器同步。4.2 集合排序Comparable 和 Comparator 别搞混排序是集合用得非常多的操作。List 排序用Collections.sort(list)或list.sort(comparator)。如果元素实现了 Comparable 接口比如 Integer、String可以直接排如果是自定义对象就传一个 Comparator。Comparable 是“类自己知道自己怎么排序”一个类只能实现一种排序规则。Comparator 是“外部写一个比较器”可以灵活定义按年龄排、按姓名排、按长度排等不同规则。两者这个区别面试经常考。还有一点是排序稳定性。Java 的Collections.sort()对对象使用的是 TimSort它是稳定排序也就是说排序前相等的元素排序后相对顺序不会变。这在实际业务里很有用比如先按日期排再按优先级排稳定性能保证日期相同的数据之间仍然保持优先级顺序。4.3 线程安全集合到底怎么选集合的线程安全问题很容易被低估。ArrayList 不是线程安全的HashMap 也不是。最简单的加线程安全方式是用Collections.synchronizedList(list)、Collections.synchronizedMap(map)这类包装类它们在每个方法上加了同步锁。但注意复合操作还是要自己加锁。比如 contains 之后再 put两个线程完全可能在中间穿插执行光靠方法级别同步是防不住的。CopyOnWriteArrayList 适合读多写少的场景写时复制底层数组读不需要加锁但每次写操作都会复制整个数组写成本很高。如果你写操作很频繁不建议用。ConcurrentHashMap 是并发场景下 Map 的首选。JDK8 之后它的并发控制粒度已经细化到桶级别大量写入不会互相干扰且 size、isEmpty 这类读操作基本无锁性能很好。至于 Hashtable除非是在维护老项目否则真的没有理由在新代码里用它。4.4 可变对象做 key 的坑改一下字段就找不到了这一点我特别想提。很多人把对象放进 HashSet或者作为 HashMap 的 key然后又去修改对象的属性。结果这个对象的 hashCode 变了但它的存储桶还是按旧 hashCode 算出来的get 的时候按新 hashCode 去查自然就查不到了。有个朋友曾经在项目里维护一个缓存key 用的是一个自定义业务对象结果对象状态变了几次之后缓存大面积 miss最后排查了半天才发现是这个问题。规避方案很简单在 Set 中存放的元素、在 Map 中用作 key 的对象尽量设计成不可变的或者不要在放入集合后修改其 hashCode 相关字段。如果一定要修改那就先 remove 再改再 add千万别直接在集合里改。5. 集合选型与性能实践实际开发中我是这么用的5.1 一张选型决策表我平时做代码评审时经常直接让同事用这张表做决策业务场景推荐选择需要按下标随机访问尾部追加为主ArrayList需要频繁在头部插入删除且当队列/栈用ArrayDeque需要双端操作且内存要求不苛刻LinkedList需要去重不要求顺序HashSet需要去重且按插入顺序访问LinkedHashSet需要去重且按自然/自定义顺序排序TreeSet普通键值对缓存、索引HashMap需要保持插入顺序或实现 LRU 的键值对LinkedHashMap需要按 key 排序做范围查询TreeMap高并发读写的 MapConcurrentHashMap读多写少的 ListCopyOnWriteArrayList这张表不是死规则但绝大多数场景用它选不会错得太离谱。5.2 初始容量和容量预估别小看频繁扩容的开销集合扩容对性能影响很大尤其是数据量大的时候。ArrayList 扩容会触发数组复制HashMap 扩容除了复制节点还要重新计算桶下标代价更高。如果你在循环里往一个无参构造的 ArrayList 插入 10 万条数据中间会触发很多次扩容虽然次数是指数级减少的但累积的 arraycopy 开销仍然可观。所以预估数据规模时尽量使用带初始容量的构造器。ArrayList 用new ArrayList(expectedSize)HashMap 用new HashMap((int) (expectedSize / 0.75f) 1)。这里要注意直接new HashMap(expectedSize)并不等于“能放下 expectedSize 个元素不扩容”因为真正决定扩容的是 threshold而不是容量本身。5.3 不可变集合和空集合细节里藏着不少坑Java 9 引入了List.of、Set.of、Map.of这些方法返回的是不可变集合不能 add、remove也不能修改元素。它们比Arrays.asList严格得多。Arrays.asList返回的是一个固长列表能修改元素但不能 add 和 remove否则直接抛 UnsupportedOperationException。而且Arrays.asList的底层还是原来的数组改列表元素会同步改数组这个特性很多人不知道。返回空集合的时候推荐用Collections.emptyList()、emptySet()、emptyMap()而不是new ArrayList()因为前者返回的是单例省去新建对象。虽然节省的对象开销很小但代码里写着也显得更专业。5.4 集合间操作和转换常用的几个高效写法集合之间求交集、差集、并集很多人第一反应是遍历其实 JDK 已经提供了方法listA.retainAll(listB)求交集listA变成 A 和 B 的交集。listA.removeAll(listB)求差集listA变成 A 中去除 B 之后的元素。listA.addAll(listB)求并集不去重注意会改变listA。数组转集合用Arrays.asList(array)但要注意它返回的并不是 ArrayList 的真正形态而是 Arrays 内部的一个私有类长度固定。集合转数组用list.toArray(new Object[0])JDK8 之后推荐传入长度为 0 的数组Java 会根据集合大小重新分配。保护类集合也很重要。如果你返回的是一个内部集合不想让调用方随意修改可以包一层Collections.unmodifiableList(list)。一旦有代码尝试修改就会抛异常。这比“约定好别改”可靠得多。6. 面试高频题与速查表背不背源码就看这几个问题集合相关的面试题翻来覆去其实就那么几个方向。这里整理一份速查每个问题后面给的是最关键的答案点方便你在面试前快速过一遍问题关键答案点ArrayList 和 LinkedList 区别底层数据结构、随机访问复杂度、插入删除复杂度、内存占用ArrayList 扩容规则默认容量 10扩容 1.5 倍底层 arraycopyHashMap 底层结构JDK8 数组 链表 红黑树解决哈希冲突HashMap 为什么是 2 的幂(n-1)hash等价于取模扩容时元素位置只在原位和原位oldCap 之间负载因子 0.75 原因时间与空间的折中泊松分布下链表长度到 8 概率极低链表什么时候转红黑树链表长度 8 且数组长度 64HashMap 为什么线程不安全并发 put 会覆盖数据JDK7 扩容可能环形链表JDK8 也丢数据Hashtable 和 HashMap 区别线程安全、null key/value 限制、性能、迭代器行为ConcurrentHashMap 怎么保证线程安全JDK8 CAS synchronized 锁桶头不允许 nullHashSet 如何保证去重底层 HashMapkey 用 hashCode 和 equals 判断重复TreeMap 如何保证有序红黑树按自然顺序或 Comparator 比较LinkedHashMap 如何实现 LRUaccessOrdertrue重写 removeEldestEntry 淘汰最老节点fail-fast 和 fail-safe 区别迭代中检测 modCountfail-safe 使用副本读到的不保证新数据Comparable 和 Comparator 区别类内实现 vs 外部实现一个类不能多套排序规则为什么重写 equals 必须重写 hashCode保持 hashCode 一致否则 HashSet、HashMap 去重失效这里再多说一个我会重点追问的点你能不能在纸上把 HashMap put 一个 key 的完整流程画出来从计算 hash、定位桶、创建节点、链表追加、树化判断、到最后的扩容检查整条链路走通比背十道题都有用。我面试时最常问的一句话是“往 HashMap 里 put 一个对象这个对象到底存到哪里扩容时它又是怎么被找到的”能把这个过程画明白的人集合这块基本不用担心。如果你在准备面试我最后一条建议是不要死记源码行号。源码只是个载体真正重要的是它背后的权衡和取舍。比如为什么用位运算而不是取模、为什么负载因子不是 1.0、为什么树化还要等数组长度到 64这些问题想明白了哪怕面试官换个刁钻角度问你也能用同样的逻辑推出来。我在实际项目中用集合的习惯也在慢慢变化。以前赶业务的时候随手就是一个 HashMap很少想初始容量和负载因子。后来排查线上性能毛刺发现很多次都是集合频繁扩容导致的才意识到一个简单的构造参数对高并发系统的影响可以这么大。所以我现在写代码凡是能预估规模的集合都会顺手把初始容量带上。这个习惯看着小长期下来省掉的不仅是扩容开销还有一堆排查奇怪的性能事故的时间。