LeetCode 1242. 多线程网络爬虫
目录
题目描述
题意分析
输入输出和单线程版本完全一致：给一个起始 URL 和一个只能按需调用的
getUrls(url)接口，返回所有从起始页可达且与起始页同主机名的 URL，顺序任意。唯一的不同是题目明确要求用多线程实现。
为什么值得并发：
getUrls模拟的是网络请求，是高延迟的 I/O 操作，而两次请求之间没有依赖——只要知道了某个页面的地址，抓它就不需要等别的页面抓完。这是典型的 I/O 密集型可并行场景，加速比不受 CPU 核数限制。
并发引入了两个单线程版本不存在的问题。第一是共享去重表的竞态：两个线程同时发现同一个新 URL，如果「查是否存在」和「写入」不是原子的，这个页面会被抓两次。第二是终止判定：单线程版本靠「队列空」判断结束，但并发下「队列空」不代表结束——可能所有线程都还在等
getUrls返回，马上就会产生新任务。
主机名规则与单线程版一致：
http://之后到下一个/之前，题目保证协议前缀固定且无端口号。
边界：起始页无外链、全部外链为外域、图中存在环和多路径汇聚、
getUrls返回大量重复链接。
解法：并发 BFS
核心思路
先明确算法骨架没有变：仍然是从起点出发的可达性遍历，扩展时按主机名过滤，靠一张全局去重表保证每个页面只抓一次。改动全部集中在「谁来执行扩展」和「怎么知道全都做完了」。
朴素的并发写法是「主线程维护队列，起一批 worker 从队列取任务」。它的麻烦在于终止：worker 取不到任务时不能直接退出，因为别的 worker 可能正要往队列里塞新任务；用有界通道还会引入死锁——所有 worker 都阻塞在「往满通道里写」时，就没人再来消费了。
换个角度：这个遍历天然是递归形状的——处理一个页面，就派生出若干个「处理它的某个新邻居」的子任务，子任务再派生孙任务。与其自己维护队列，不如直接把「派生子任务并等它们结束」交给运行时。Java 用
ForkJoinPool+RecursiveAction，invokeAll会等所有子任务完成才返回；Go 用sync.WaitGroup配合每发现一个新页面就go一个协程，wg.Wait()在计数归零时返回。两者都把终止判定变成了「派生计数归零」，不需要显式的空队列检测。
这里的不变量是：
visited中的每个 URL 都有且只有一个任务所有者，并且该任务已经运行、已经登记待启动，或已经完成。必须原子完成的是「判断 URL 未访问并取得所有权」；真正启动线程可以稍后发生，但在这段间隙内，当前父任务必须仍被终止机制计数，不能让主线程误判为全部完成。
Java 中，
ConcurrentHashMap.newKeySet()的add原子地授予所有权，只有成功者把子任务加入自己的私有任务列表；父任务随后用invokeAll启动并等待整批子任务。Go 没有直接使用并发集合，因此用一把sync.Mutex保护「查重、写入、wg.Add(1)」三个动作；解锁后再启动协程。此时父协程尚未执行延迟的Done，所以计数不可能在启动间隙归零。两种写法都把慢速getUrls留在同步区域之外。
wg.Add(1)的位置也有讲究：必须在启动协程之前、在父任务还没结束时调用。如果放到子协程内部，父协程可能先跑完wg.Done()让计数提前归零，Wait直接返回，抓取还没做完就返回了残缺结果。
解题步骤
- 先算出起始页的主机名并存为常量。这个值被所有线程只读共享，没有写入就没有竞态，不需要任何同步。
- 把起始 URL 预先放进
visited，再为它派生第一个任务。先入集合再派生，是为了防止某个页面链回起点时起点被第二次派生。
- 每个任务的职责固定为三步：对自己的 URL 调一次
getUrls，逐个检查邻居，对新的同域邻居派生子任务。慢调用getUrls必须在任何锁之外执行，这是并发版本能真正加速的前提。
- 邻居检查的顺序是「先比主机名，再抢占去重表」。先过滤后标记，
visited最终就直接是答案；反过来会把外域 URL 写进结果。
- 抢占用原子操作完成。Java 直接依赖
ConcurrentHashMap.newKeySet()的add返回值；Go 在同一个临界区完成「查 map、写 map、wg.Add(1)」，然后释放锁并启动协程。这样一个 URL 一旦进入visited，终止计数中已经有对应任务；慢调用仍然不持锁。
- 等待全部完成。Java 里
invokeAll(tasks)让当前任务阻塞直到所有直接子任务结束，递归展开后根任务的invoke返回即代表整棵任务树完成；Go 里主协程wg.Wait()，计数在每个walk的defer wg.Done()中递减，归零即全部完成。
- 处理异常退出。Java 用
finally关闭专用线程池，任务异常由pool.invoke向调用方传播，不会把尚未完成的集合当作正常答案返回。Go 题目接口没有错误返回值；defer wg.Done()保证任何正常返回路径都会注销任务。若生产接口增加错误返回，应记录或传播错误，同时仍让Done执行，不能静默返回部分结果。
- 全部结束后把
visited转成切片/列表返回。此时已经没有并发写入，可以安全地遍历。
getHost从下标 7（http://之后）开始找第一个/：找到就截取到它之前，找不到说明 URL 没有路径部分，返回从 7 到末尾的整段。
以
startUrl = "http://a.com/x"走一遍，图为：getUrls("http://a.com/x")返回["http://a.com/y", "http://b.com/z", "http://a.com/x"]，getUrls("http://a.com/y")返回["http://a.com/x", "http://a.com/w"]，getUrls("http://a.com/w")返回空。
getHost("http://a.com/x")：从下标 7 的字符 'a' 开始扫，第一个/在下标 12，得到"a.com"。visited = {http://a.com/x}，为起点派生任务 T1，等待计数为 1。
T1 调用
getUrls拿到三个链接。http://a.com/y主机名是a.com，同域；抢占visited成功，计数加到 2，派生 T2。http://b.com/z主机名b.com，与a.com不等，跳过，不进visited。http://a.com/x同域，但抢占失败（起点已在集合中），忽略——这一步挡住了自环。T1 的邻居处理完毕，其计数递减。
T2 调用
getUrls拿到两个链接。http://a.com/x抢占失败，忽略。http://a.com/w是新的同域页面，抢占成功，派生 T3。T2 结束。
T3 的外链为空，直接结束。此时所有派生任务都已完成、计数归零，
Wait返回。结果是visited的三个元素：http://a.com/x、http://a.com/y、http://a.com/w。整个过程中getUrls恰好被调用三次，每个可达同域页面一次。
关键在于 T2 和 T3 可能与其他任务并发执行，但由于「抢占成功者才派生」这条不变量，无论线程调度顺序如何，每个 URL 都只会被派生一次，结果集合完全确定（只是元素顺序不确定，而题目允许任意顺序）。
代码实现
// 抢占式去重：只有把 URL 抢进并发集合的线程才派生子任务，invokeAll 负责终止判定。
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
String host = getHost(startUrl);
Set<String> visited = ConcurrentHashMap.newKeySet();
visited.add(startUrl);
ForkJoinPool pool = new ForkJoinPool();
try {
pool.invoke(new CrawlTask(startUrl, host, htmlParser, visited));
} finally {
pool.shutdown();
}
return new ArrayList<>(visited);
}
private static class CrawlTask extends RecursiveAction {
private final String url;
private final String host;
private final HtmlParser parser;
private final Set<String> visited;
CrawlTask(String url, String host, HtmlParser parser, Set<String> visited) {
this.url = url;
this.host = host;
this.parser = parser;
this.visited = visited;
}
@Override
protected void compute() {
List<CrawlTask> tasks = new ArrayList<>();
for (String next : parser.getUrls(url)) {
if (!host.equals(getHost(next))) {
continue;
}
if (visited.add(next)) {
tasks.add(new CrawlTask(next, host, parser, visited));
}
}
invokeAll(tasks);
}
}
private static String getHost(String url) {
int start = 7;
int slash = url.indexOf('/', start);
if (slash == -1) {
return url.substring(start);
}
return url.substring(start, slash);
}
}
// 互斥锁保护「查 + 写 + 登记任务」，慢调用 GetUrls 留在锁外；WaitGroup 归零即全部完成。
import "sync"
func crawl(startUrl string, htmlParser HtmlParser) []string {
host := getHost(startUrl)
var mu sync.Mutex
visited := map[string]struct{}{startUrl: {}}
var wg sync.WaitGroup
var walk func(u string)
walk = func(u string) {
defer wg.Done()
for _, next := range htmlParser.GetUrls(u) {
if getHost(next) != host {
continue
}
mu.Lock()
if _, ok := visited[next]; ok {
mu.Unlock()
continue
}
visited[next] = struct{}{}
wg.Add(1)
mu.Unlock()
go walk(next)
}
}
wg.Add(1)
go walk(startUrl)
wg.Wait()
res := make([]string, 0, len(visited))
for u := range visited {
res = append(res, u)
}
return res
}
func getHost(url string) string {
for i := 7; i < len(url); i++ {
if url[i] == '/' {
return url[7:i]
}
}
return url[7:]
}
复杂度分析
- 时间复杂度：若 URL 平均长度为 L，总工作量是 $O((V + E) \cdot L)$，其中 V 为可达同域页面数、E 为这些页面返回的外链总数；每个页面抓取一次，每条链接做主机名提取和哈希操作。并发降低的是墙钟时间，不改变总工作量；它受线程/连接上限、图的关键路径和
getUrls延迟共同影响，不能仅用图深度给出无条件保证。
- 空间复杂度：$O(V \cdot L)$，L 为 URL 平均长度。
visited存下全部可达同域 URL；同时存活的任务数不超过 V，每个任务只持有一个 URL 引用和几个共享对象的引用。
关键点总结
- 并发版本要改的从来不是算法，而是三件事：共享状态的原子性、慢调用与临界区的分离、终止条件的判定方式。把这三点拆开讲，比笼统地说「加锁」更能体现对并发的理解。
- 「查重 + 标记」必须是一个原子操作。
contains后再add在并发下是经典的检查后使用漏洞，两个线程会同时通过检查。常见做法是使用并发集合的原子插入、sync.Map.LoadOrStore，或用互斥锁包住检查与写入。
- 锁的临界区里绝不能放 I/O。
getUrls一旦被锁住，所有线程串行等待，并发退化成加了锁开销的单线程——这是面试官最常挖的坑。
- 用「所有已登记任务完成」代替「队列为空」做终止判定。队列空只是瞬时状态，不代表没有在途任务；
WaitGroup用计数表达该条件，invokeAll则通过父任务等待全部子任务形成结构化终止。
wg.Add必须在启动协程之前、父协程Done之前调用。放在子协程内部会导致计数提前归零、Wait提前返回、结果残缺，而且这类 bug 有很强的随机性，本地跑十次可能都不复现。
- 有界通道加固定 worker 池在这类「任务会派生任务」的场景下容易死锁：所有 worker 都阻塞在往满通道写入时，就没有消费者了。要么用无界队列 + 显式的在途计数，要么直接用结构化并发，后者在白板上更短也更难写错。
- 面试视角：当前 Go 写法会按页面派生协程，适合题目规模；生产环境若要限制并发度，应由固定 worker 池或独立调度器消费任务，并继续维护在途任务数。不要让持有并发名额的递归任务同步等待新的名额，否则所有 worker 都可能互相等待而死锁。
易错点总结
- 错误写法：用普通
HashSet做去重表 → 多个线程同时写入会破坏内部结构，走查里的http://a.com/x被 T1、T2 同时读写时可能丢失元素甚至抛出ConcurrentModificationException，返回结果不完整。
- 错误写法：
if (!visited.contains(next)) { visited.add(next); ... }分两步做 → 两个线程可能同时通过contains检查，同一个页面被派生两次，getUrls被重复调用，环状图上可能无限膨胀。
- 错误写法：Go 里把
htmlParser.GetUrls(u)写在mu.Lock()和mu.Unlock()之间 → 所有协程排队等同一把锁，并发度退化到 1，墙钟时间和单线程版本一样甚至更慢。
- 错误写法：Go 里把
wg.Add(1)写在子协程内部（go func(){ wg.Add(1); ... }()）→ 主协程的wg.Wait()可能在子协程还没执行Add时就看到计数为 0 并返回，走查中可能只返回起点一个 URL。
- 错误写法：忘记
defer wg.Done()或在提前return的分支里漏掉Done→ 计数永远不归零，wg.Wait()永久阻塞，程序超时。
- 错误写法：用固定 worker 池 + 有界 channel，且 worker 在处理任务时直接往同一个 channel 写新任务 → 走查图放大到超过缓冲区容量时，所有 worker 都阻塞在写入上、无人消费，直接死锁。
- 错误写法：先
visited.add(next)再判断主机名 →http://b.com/z被写进结果集合，返回的列表里混入外域 URL。
- 错误写法：起始 URL 不预先放进
visited→ 走查里http://a.com/x链回自己，起点被第二次抢占成功并派生任务，环上任务无限增殖。
- 错误写法：
getHost从下标 0 开始找/→ 命中协议里的斜杠，所有主机名都变成空串，过滤失效，会把整个网络爬下来。
- 错误写法：
getHost不处理「7 之后没有/」的情况 →http://a.com这种无路径 URL 上取到 -1 下标，Java 抛StringIndexOutOfBoundsException，Go 切片越界 panic。
- 错误写法：Java 里派生子任务后不调用
invokeAll（或只fork不join）→ 根任务的invoke提前返回，visited还在被后台任务写入时就被拷贝成列表，结果随机缺失。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1236. 网络爬虫 | 中等 | 同一遍历的单线程版，可用来对照并发改造改了哪三处 |
| 1114. 按序打印 | 简单 | 只需线性顺序约束，用信号量或 CountDownLatch 串行化 |
| 1226. 哲学家进餐 | 中等 | 多把锁的获取顺序问题，重点是避免循环等待造成的死锁 |
| 841. 钥匙和房间 | 中等 | 同样是可达性遍历，但邻接表已知且单线程，可对比骨架部分 |