Dai Wei

集合面试上篇通常覆盖体系结构、接口继承关系，以及 List/Set/Map 最常用实现的差异——这是后续源码题的地图。 核心概念Collection 单列：List 有序可重复、Set 不重复、Queue 队列。Map 双列键值对，不继承 Collection。经典实现：ArrayList/LinkedList、HashSet/TreeSet、HashMap/LinkedHashMap/TreeMap。迭代器 Iterator 与 fail-fast：modCount 检测并发修改。 关键机制与实践选型速记：随机访问、尾部增删 → ArrayList；头尾插删、无随机访问 → LinkedList；去重无序 → HashSet；有序 → TreeSet/LinkedHashSet；键值查找 → HashMap；插入顺序 → LinkedHashMap；排序键 → TreeMap。HashMap 依赖 hashCode/equals；JDK 8 链表+红黑树；负载因子与 2 幂容量。 常见误区与小结 Hash...

集合 API 丰富但坑点多：阿里规约与实战经验强调「可读性 + 正确性 + 并发边界」，很多线上 NPE 与 CME 都源于对集合语义的一知半解。 核心概念判空用 isEmpty() 而非 size()==0（部分并发集合 size() 是 O(n)）。Arrays.asList 返回固定大小列表，不能 add/remove，且基本类型数组会被当作单个元素。subList 是父列表视图，结构性修改父列表会导致子列表行为未定义。Stream toMap 需处理 key 冲突与 null value（否则 NPE）。 关键机制与实践Collectors.toMap(k, v, (a,b)->a) 指定 merge；Optional.ofNullable 过滤 null。foreach 里不要对 ArrayList 直接 remove，用 Iterator.remove。并发场景：ConcurrentHashMap、CopyOnWriteArrayList 各有适用面，不要万能 synchronizedList。集合转数组用 list.toArray(new String[0...

红黑树是带颜色约束的二叉搜索树。节点为红或黑，根和空叶视为黑；红节点不能有红孩子；任一节点到后代空叶的路径包含相同数量黑节点。这些性质使最长路径不超过最短路径约两倍，高度保持 O(log n)。 搜索仍按二叉搜索树比较键。插入先作为普通 BST 叶子加入并染红，以免立刻改变黑高；若父节点为红，则出现连续红，需要根据叔节点颜色处理。叔为红时，父与叔染黑、祖父染红并向上继续；叔为黑时，通过左旋或右旋把折线调整为直线，再旋转祖父并交换颜色。 旋转只改变局部连接而保持中序次序。左旋让右孩子上升、原节点成为其左孩子；右旋对称。删除更复杂：删除黑节点可能导致某条路径少一个黑色，需要借助兄弟节点颜色、兄弟孩子颜色、旋转和重新着色逐层修复。 查找、插入、删除均为 O(log n)，空间为 O(n)。相比 AVL，红黑树平衡条件更宽松，更新时旋转通常较少；AVL 高度更紧，读多写少时可能有优势。它常用于有序映射、集合和内核调度等需要稳定上界的场景。 误区是认为红黑树绝对平衡、只背五条性质却不会检查黑高、把旋转当作交换键值，以及忽略父指针和根引用更新。小结：颜色是编码平衡信息，旋转保持排序，重新...

并查集维护一组互不相交的集合，核心操作只有查找代表元 find 和合并 union。每个元素最初自成集合，parent[x]=x；若两个元素代表元相同，它们已经连通，否则把一棵代表树接到另一棵上。 朴素合并可能形成很长的链。按秩或按大小合并总让较小树接到较大树，控制高度；路径压缩在查找时把沿途节点直接指向根，使后续查询更快。 1234567find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x]union(a,b): ra=find(a); rb=find(b) if ra != rb: attach smaller to larger 同时采用两种优化后，连续 m 次操作的均摊复杂度为 O(m α(n))，反阿克曼函数增长极慢，实践中接近常数；空间为 O(n)。并查集适合无向图连通性、冗余边、岛屿动态合并和 Kruskal 最小生成树。 它擅长合并，却不擅长删除边和回答两点具体路径。若问题要求有向可达、最短路径或集合拆分，需要其他结构。离线问题有时可倒序把删除转化为添加；...

Trie 把字符串的公共前缀合并成路径。根不代表字符，从根沿字符边走到某节点即表示一个前缀；节点还需终止标记，区分“路径存在”和“完整单词存在”。例如插入 app 与 apple 会共享前三个字符。 插入时逐字符寻找孩子，不存在就创建，末节点标记结束；查完整词需路径存在且终止标记为真；查前缀只要求路径存在。若允许重复词或删除，可在节点记录经过数量与结尾数量，删除时递减并在计数归零后释放无用分支。 123456insert(word): node = root for c in word: node.children[c] ||= new Node node = node.children[c] node.end = true 设词长为 L，插入和查询时间为 O(L)，与词典中单词数量无直接线性关系。空间与所有不重复前缀总数有关。若字符集固定且小，孩子可用数组以换取快速索引；字符稀疏时用映射节省空槽；数据巨大还可采用压缩 Trie，把单孩子链合并为字符串片段。 Trie 适合自动补全、词典查询、前缀统计和路由匹配。输出所有前缀结果还需遍历子树，成本至少与结果...

树用父子关系表达层级。二叉树每个节点最多两个孩子，但不一定有序；二叉搜索树要求左子树键更小、右子树更大，因此平均可快速查找，若按有序数据连续插入却可能退化为链表。 遍历决定信息处理顺序：前序先处理根，适合复制和序列化；中序遍历搜索树得到有序序列；后序先汇总孩子，适合计算高度、删除和树形动态规划；层序用队列按深度访问。遍历所有节点都是 O(n)，递归额外空间取决于高度 h。 AVL 树要求每个节点左右子树高度差不超过 1。插入删除破坏平衡后，通过单旋或双旋修复，查找与更新保持 O(log n)，但要维护高度且调整较严格。红黑树条件更宽松，更新常更经济。 B 树让一个节点保存多个键和孩子，显著降低高度，适合磁盘或页式存储；B+ 树通常把完整记录放在叶子，内部节点只做索引，叶子按顺序链接。这样范围扫描从起始叶开始顺链进行，内部节点也能容纳更多分隔键，数据库索引常采用这一思路。 实践比较不能只看大 O：内存指针树可能缓存命中差，外存结构更关心一次 I/O 读取多少键。误区包括把完全二叉树与搜索树混淆、认为搜索树必然 O(log n)、把 B 树叫二叉树，以及忽略重复键规则。...

跳表在有序链表上增加多级稀疏索引。查找从最高层开始向右走，下一节点超过目标时下降一层，直到最底层确认。它像在道路上先走高速再转支路，避免从头逐个扫描。 节点层高通常随机生成：每次以固定概率决定是否再升一层，因此高层节点越来越少。插入前先记录每层最后一个小于目标的前驱，再生成新节点高度，并把它接入对应层；删除同样利用前驱数组，在每层绕过目标节点。随机化不要求维护严格平衡，代码通常比平衡树直接。 12345x = headfor level from max down to 0: while x.next[level] < target: x = x.next[level]candidate = x.next[0] 在合理随机层级下，查找、插入、删除的期望时间为 O(log n)，空间期望 O(n)；最坏情况下所有节点都只有底层，仍可能退化为 O(n)。有序底层链表使范围查询很自然：定位起点后连续向右输出，成本约 O(log n + k)。 Redis 有序集合采用跳表等结构支持按分值范围和排名访问，实际实现还会处理相同分值、跨度与字典映射。工程上需控制最大层数、...

LRU 在容量不足时淘汰最久未被访问的条目。要让读取和写入都接近 O(1)，单用哈希表无法知道新旧顺序，单用链表又不能快速按键定位，因此常组合哈希表与双向链表。 哈希表保存 key -> 节点，链表头表示最近使用，尾表示最久未用。读取命中后把节点从原位置摘下并移到头部；写入已有键时更新值并移头；写入新键时创建头节点，若超过容量，删除尾节点并同步从哈希表移除。双向链表使已知节点的摘除为 O(1)，哑头尾节点可减少边界分支。 1234get(k): node = map[k]; if absent return miss unlink(node); linkAfterHead(node) return node.value 每个操作平均 O(1)，空间 O(capacity)。Java 可利用按访问顺序维护的 LinkedHashMap，并通过淘汰钩子实现，但面试手写仍要展示两个结构的一致性。 工程缓存还要考虑线程安全、过期时间、权重容量、缓存击穿和统计。锁住每次访问会简单但可能竞争；分段或成熟缓存库通常更可靠。LRU 也并非命中率总最佳：一次性顺序扫描可能污染缓存...

二叉堆是一棵完全二叉树，最大堆要求父节点不小于孩子，最小堆相反。它只保证局部偏序，并不是整体有序。完全树可紧凑地放在数组中：零下标时，节点 i 的孩子为 2i+1 和 2i+2。 插入先把新元素放到数组末尾，再与父节点比较并上浮；删除堆顶时，用末尾元素覆盖根，缩短数组，再与更合适的孩子交换并下沉。树高为 O(log n)，因此插入和删除顶都是 O(log n)，读取堆顶为 O(1)。 从无序数组建堆不必逐个插入。可从最后一个非叶节点开始向前下沉，虽然单次下沉最高 O(log n)，但大量底层节点移动很短，合计为 O(n)。堆排序建最大堆后反复把根换到末尾并缩小堆区，时间 O(n log n)、额外空间 O(1)，但通常不稳定。 优先队列是抽象接口，堆是常用实现。Top K、任务调度、多路归并和 Dijkstra 都可使用它。若需更新任意元素优先级，普通堆还需要位置索引，或采取重复入堆并在弹出时丢弃旧记录。 误区是认为遍历堆会得到有序序列、混淆最大 K 与堆方向、把建堆写成 O(n log n)、修改比较器依赖的字段后不重建，以及忘记空堆检查。小结：堆擅长反复取得一个极值，不擅...

哈希表先把键经哈希函数转换为整数，再映射到桶。理想情况下只需定位一个桶，因此查询、插入和删除平均接近 O(1)。哈希函数应稳定、计算快且分布均匀，但不同键映射到同一桶的冲突不可完全避免。 拉链法让每个桶保存链表或树，冲突元素在桶内继续比较；开放寻址法则按探测规则寻找其他空位。负载因子表示元素数与桶数的比例，过高会增加冲突。超过阈值时通常申请更大数组并重新分布元素，扩容单次为 O(n)，但分摊到多次插入后仍可视作摊还常数。 Java HashMap 的键必须遵守 equals 与 hashCode 契约：相等对象必须有相同哈希值，反之不一定成立。可变对象若作为键后改变参与哈希的字段，可能再也无法按新状态找到原条目。JDK 8 的桶在冲突链较长且容量达到条件时可树化，以改善极端查询，但这不意味着所有操作绝对常数。 查询步骤是计算扰动后的哈希、定位桶、再逐个或按树比较哈希和键；因此平均复杂度依赖分布和扩容策略，最坏情况仍需结合实现说明。空间通常为 O(n+桶数)。 常见误区是把哈希等同加密、认为无冲突、忽略扩容停顿、依赖遍历顺序，以及在并发写入时直接共享普通 HashMap。小结：...