Dai Wei

集合面试的下篇聚焦 Map 体系与并发容器：HashMap 的哈希设计、树化与线程安全问题，ConcurrentHashMap 两版实现的演进，以及并发语境下的 null 语义与复合操作陷阱。这一篇的问题几乎全是高频考点。 考察地图 Map 对比：HashMap vs Hashtable、HashMap vs HashSet、HashMap vs TreeMap。考察选型语义与继承体系。 HashMap 原理：底层结构、容量为什么是 2 的幂、线程不安全的具体表现。考察哈希表设计功底，是集合面试的「流量担当」。 并发容器：ConcurrentHashMap vs Hashtable、JDK 7 到 JDK 8 的实现演进、null 禁令、复合操作原子性。考察并发设计的权衡思路。 建议自行查阅：HashMap 的多种遍历方式及性能对比、Collections 工具类方法清单——偏记忆性内容，知道结论即可，不建议投入深抠。 Map 对比HashMap 和 Hashtable 的区别？结论：Hashtable 是方法级 synchronized 的古老线程安全实现，已被淘汰；Ha...

集合面试的上篇围绕三条主线：框架体系的选型逻辑、List 两大实现的底层差异与扩容机制、Set 与 Queue 家族的排序和去重语义。题目按主题分组，每题给出结论、原理与追问方向。 考察地图 框架体系：List/Set/Queue/Map 的区别、集合如何选型。考察对集合整体设计语言的把握，属于开场必答题。 List：ArrayList 与数组、ArrayList 与 LinkedList、扩容机制、fail-fast 与 fail-safe。考察对数组和链表两种底层结构及复杂度分析的理解。 Set：Comparable 与 Comparator、HashSet/LinkedHashSet/TreeSet 异同。考察排序契约与哈希去重的底层依赖。 Queue：Queue 与 Deque、ArrayDeque 与 LinkedList、PriorityQueue。考察队列 API 语义与堆结构。 建议自行查阅：Vector 与 Stack 的区别（已被淘汰）、ArrayList 能否存 null、各实现类底层数据结构清单——偏记...

集合 API 用起来简单，但「视图语义、fail-fast、null 处理」这几类坑常年制造线上的 NPE 与 CME。本文按「坑的现象 → 原理 → 正确写法」逐条拆解高频陷阱。 判空：用 isEmpty() 而不是 size()==0现象：size()==0 语义没错，但在部分集合上是性能坑，数据量大时判空接口明显变慢。 原理：大多数集合的 size() 维护了计数器，是 O(1)；但并非全部。ConcurrentLinkedQueue 为了无锁化没有维护精确计数，size() 要遍历整条链表数节点，复杂度 O(n)，而 isEmpty() 只需判断头节点是否为空，近似 O(1)。并发环境下 size() 统计到的还可能是过期快照，精确性也不可靠。 正确写法：统一用 collection.isEmpty()，可读性和复杂度都更好，也不依赖具体实现是否维护了 size 字段。 Arrays.asList：返回的不是你以为的 ArrayList现象一：Arrays.asList(1, 2, 3).add(4) 运行期抛 UnsupportedOperati...

红黑树是一种用颜色规则维持「近似平衡」的二叉搜索树：它不追求严格等高，而是用五条性质把最长路径限制在最短路径的两倍以内，从而让查找、插入、删除稳定保持 O(log n)，同时把调整代价压到足够低。这正是它被 TreeMap、Linux 内核广泛采用的原因。 它解决什么问题二叉搜索树的性能完全由形状决定，而形状由插入顺序决定。最坏情况是按升序或降序连续插入——树退化成一条斜链，查找从 O(log n) 跌回 O(n)，有序性带来的优势荡然无存。 要堵住这个漏洞，思路是在更新时主动修形。AVL 树选择了最强硬的方案：每个节点左右子树高度差不得超过 1。代价是插入删除可能触发沿路径向上的多次旋转，写得越多，维护越贵。红黑树给出了另一个答案：放宽平衡标准，只要求「最长路径不超过最短路径的两倍」。这个近似平衡足够把高度钉在 O(log n)，又宽松到大多数插入只需变色、少数才旋转，一次插入最多两次旋转。读性能略让，写性能大赚——这是它在工程界击败 AVL 的根本原因。 核心原理五条性质 每个节点非红即黑； 根节点是黑色； 所有空叶子（NIL）视为黑色； 红节点的两个孩子必须是黑色，即不...

并查集用接近常数的均摊代价回答”两个元素是否同组、合并后还剩几个集合”，是动态连通性问题与 Kruskal 最小生成树的标配。本文拆解它的森林模型、两种关键优化与建模套路。 它解决什么问题大量问题只关心”分组”而不关心”路径”：两个用户是否在同一个社交圈、加入一条边之后图里还剩几个连通块、无向图里这条边会不会构成环。每次用 BFS/DFS 现场搜索要 O(V+E)，而真实场景里关系不断合并、查询海量，搜索派的成本很快失控。并查集换一种思路：把连通关系预先维护在结构里，查询时只需比对两个元素的”集体身份”。 核心原理把每个集合组织成一棵树，树根充当整个集合的代表元。parent[x] 记录 x 的父节点，根的父节点是它自己；初始时 n 个元素各自成树，即 n 个集合。find(x) 沿父指针一路爬到根，根就是 x 所在集合的身份；union(a, b) 先各自 find 找根，根相同说明已连通，否则把一棵树挂到另一棵的根下。判断连通等价于 find(a) == find(b)；统计连通分量则维护一个计数器，每次真正合并成功才减一。 理解演进路径有助于记住设计动机：Qu...

Trie 把字符串集合组织成按字符延伸的路径，公共前缀只存一份，让前缀类查询的开销只与前缀长度相关、与词典规模解耦。本文讲清它的结构直觉、增删查流程、空间优化与工程落地。 它解决什么问题哈希表擅长回答”这个词在不在”，却不擅长”所有以 app 开头的词有哪些”——除了全表扫描几乎无路可走。搜索建议、分词切分、路由匹配的共同点是：查询单位不是完整字符串，而是前缀。Trie 让前缀成为结构里一条显式的路径，前缀操作的代价不再随词典膨胀。 核心原理根节点不代表任何字符，只是入口；从根向下的每条边对应一个字符，根到任意节点的路径拼出一个前缀。节点上挂一个终止标记，区分”这里只是某词的前缀”与”这里恰好是一个完整单词”——插入 app、apple、apply 之后，三者共享 a→p→p 这条路径，第三个 p 上的标记表明 app 自身也是词，而第四个字母处再分出 l、e 两支。公共前缀在结构上只存一份，这是 Trie 一切性质的根源：前缀越密集，共享越充分，空间和时间上的收益就越大。 深入机制插入、查找与前缀匹配设词长 L：插入沿路径逐字符下行，缺节点就建，O(L)；search 要求...

树是表达层级关系的通用结构：n 个节点恰好由 n-1 条边连接，任意两点间只有唯一路径，且不存在环。本文聚焦二叉树的性质、三种特殊形态的定义边界、四种遍历方式的统一框架，以及由遍历序列还原整棵树的充要条件。 它解决什么问题数组和链表只能表达「一个挨一个」的线性关系，而现实中大量数据天然是层级的：文件系统的目录、HTML 的 DOM、编译器的语法树、索引中的键值分布。树用父子引用把这种一对多关系直接编码进结构里，让每个节点只需记住自己的后代。 在树家族中，二叉树是研究的起点：每个节点最多两个孩子，且左右位置不可颠倒。加上「左子树所有键小于根、右子树所有键大于根」这一约束，就得到二叉搜索树（BST），查找路径每次可以排除一半数据，平均复杂度 O(log n)。但 BST 的形状取决于插入顺序——按升序连续插入会退化成一条斜链，查找跌回 O(n)。这正是 AVL、红黑树等自平衡结构存在的理由，也是理解 B/B+ 树之前必须跨过的门槛。 核心原理二叉树的三条数学性质设根节点深度为 0、层数为 1： 第 i 层最多有 2^(i-1) 个节点，等比增长决定了「宽」； 深度为 ...

跳表在一条有序链表上叠若干层稀疏索引，用随机化层高代替旋转与变色，换来期望 O(log n) 的查找和远低于平衡树的实现复杂度。Redis 的有序集合 ZSet 正是靠它支撑排序、排名与范围查询。 它解决什么问题有序链表插入只要 O(1)，但查找必须从头扫到尾，O(n)。如果业务既要求数据随时有序，又要求查找、范围遍历都快，平衡树是经典答案——但红黑树的旋转与变色规则复杂到很少有人能徒手写对。跳表提出了一个概率化的替代方案：不追求严格平衡，靠随机性让索引高度在期望意义上保持在 log 级别，实现简单得多，性能却同样稳定。 核心原理跳表的最底层是一条包含全部元素的有序链表，上面每一层都是下一层的稀疏子集，越往上节点越少。查找从最高层开始：当前层的下一个节点小于目标就向右走，否则下降一层；到底层时，最后一个走过的位置的下一个节点就是答案候选。这个过程像在路网里先上高速、再转国道、最后进街巷，每一层都把搜索范围砍掉一大块。 层高不是精心规划的，而是随机抛出来的：新节点一定占据底层，之后以概率 p 决定是否再升一层，连续成功就持续升高。以 p = 1/2 为例，第...

LRU（Least Recently Used）在缓存满时淘汰最久未被访问的条目。要让读写都是 O(1)，必须组合两种结构：哈希表解决按键定位，双向链表解决新旧次序的维护与尾部淘汰。它既是高频面试题，也是理解真实缓存系统（LinkedHashMap、Caffeine、Redis）的起点。 它解决什么问题缓存容量永远有限，而访问流无限。缓存写满后新数据还要进来，就必须决定淘汰谁。理想答案是”未来最久才会被用到的那个”，但程序无法预知未来，只能找代理指标。LRU 用过去近似未来：刚被访问的数据大概率还会再被访问（时间局部性），最久没被碰的优先出局。这个启发式简单有效，成为本地缓存、操作系统页面置换、数据库 Buffer Pool 的常见默认策略。 实现层面的挑战在于：淘汰决策需要完整的”新旧次序”，而读写路径又要求按键快速定位——单一结构同时满足不了这两个需求。 核心原理单一结构为什么都不够只用哈希表：get/put 是 O(1)，但哈希表不记录任何时间信息，容量满时无从得知哪个 key 最久未用。只用链表：可以按访问时间排序（头新尾旧），淘汰尾部是 O(1)，但每次按...

二叉堆把「完全二叉树」和「数组」两件武器叠在一起：完全树保证高度恒为 O(log n)，数组存储让父子跳转变成 O(1) 的下标运算，于是「反复取极值」这一高频需求被压到取堆顶 O(1)、插入删除 O(log n)。它是优先队列的事实标准实现。 它解决什么问题设想一类场景：数据源源不断地到来，而你反复需要当前的最大值或最小值——任务调度取优先级最高者、定时器找最近到期者、排行榜维护前 K 名。用无序数组，取极值要 O(n) 扫一遍；用有序数组，取极值 O(1) 但每次插入要 O(n) 挪动元素腾位置；用平衡二叉搜索树，两头都是 O(log n)，但实现重、常数大，而且杀鸡用了牛刀——你根本不需要全序，只需要知道「谁是老大」。 堆精准命中这个缺口：只维护「父不弱于子」的偏序关系，放弃兄弟之间、跨子树之间的顺序承诺。约束越弱，维护越便宜。需要注意一个常见的以讹传讹：堆在概念上并不要求是完全二叉树（斐波那契堆、二项堆就不是），只是二叉堆选择用完全二叉树实现，而完全树又恰好能无损地拍平进数组——下面说的堆，默认指二叉堆。 核心原理堆序性质：只管父子，不管全局 大顶堆：任意节点的值不小...