LeetCode 1242. 多线程网络爬虫
题目描述
题意分析
从起始 URL 沿页面链接向外抓取，返回所有能到达且主机名与起点相同的 URL，包含起点本身。不同页面可能重复指向同一个地址，页面之间也可能形成环，同一 URL 只能安排一次抓取。
本题还要求并发执行抓取，不能让一个页面的等待阻塞所有其他页面。返回前必须确认全部已派生任务结束，而不是只看暂时没有待取的 URL。代码按
http://且主机部分不含端口的输入约定提取主机名，比较的是完整主机名，不是 URL 字符串前缀。
解法：并发可达性遍历
核心思路
[!blue]
将页面看成图节点、链接看成有向边。任务负责抓取自己的 URL，并从返回链接中筛出同主机候选；候选若从未发现，就派生新任务。关键是让多个任务共享同一个已访问集合，而各自的慢速接口调用可以并行执行。
“查到没有访问”和“登记已经访问”必须成为一个原子动作，否则两个线程可能同时看到不存在，并重复抓取同一页面。Java 使用并发集合
add的返回值取得唯一处理权；Go 在同一把锁内查重、写入集合并登记任务数量。调用getUrls不持有这把锁，避免网络等待把全部工作串行化。Java 把新发现的 URL 建成子任务，由
invokeAll等待本任务的全部孩子。每个孩子又等待自己的后代，因此根任务完成就代表整棵任务树完成。重复链接只归属于第一个成功登记它的任务，不会因为原网页图有环而产生相互等待的任务环。Go 用
WaitGroup记录已经登记但尚未完成的任务。起点先Add(1)再启动；任务发现新 URL 时也先Add(1)再启动协程，结束时由defer Done()注销。父任务在派生期间仍计数在内，因此新任务尚未真正运行时，计数也不会提前降到零。等待结束后，不再有任务能发现或写入新 URL，此时才遍历访问集合生成答案。Java 的专用线程池在
finally中关闭；结果顺序取决于并发调度与集合遍历，不需要是发现顺序。
解题步骤
- 提取起点主机，将起点先登记到共享访问集合。
- 启动起点任务，任务在锁外获取该页面链接并过滤不同主机。
- 对候选 URL 原子地完成查重与登记；只有首次登记成功者创建处理任务。
- Java 等待各级子任务并最终等待根任务；Go 在启动前计数、结束时减数，由主协程等待计数归零。
- 确认全部任务结束后生成 URL 列表返回，并关闭 Java 专用线程池。
代码实现
class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
String host = getHost(startUrl);
Set<String> visited = java.util.concurrent.ConcurrentHashMap.newKeySet();
visited.add(startUrl);
java.util.concurrent.ForkJoinPool pool = new java.util.concurrent.ForkJoinPool();
try {
// 等待起点任务树全部完成后，才读取结果集合。
pool.invoke(new CrawlTask(startUrl, host, htmlParser, visited));
} finally {
pool.shutdown();
}
return new ArrayList<>(visited);
}
private static class CrawlTask extends java.util.concurrent.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);
}
}
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)
// 计数归零后不再有并发写入，才可遍历结果 map。
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:]
}
复杂度分析
- 时间复杂度：设实际抓取同主机页面数为
V，这些页面返回的链接总数为E，URL 长度上界为L，本地总工作量期望为 $O((V+E)L)$，同时需要执行V次抓取调用。并发会改变实际经过的时间，但不能把总工作量直接除以线程数，接口延迟和调度同样影响耗时。- 空间复杂度：设同时仍被任务保留的接口返回链接数最多为
B，访问集合、任务状态和这些链接列表合计为 $O((V+B)L)$。Go 每个新页面会启动一个任务，不能将活跃任务空间视为固定常数。
关键点总结
[!green]
- URL 的唯一登记决定抓取任务的唯一所有者，同时防止重复链接与环造成重复工作。
- 锁只保护共享状态，慢速抓取在锁外执行。
- 完成条件覆盖正在运行和已经登记的全部任务，不是某个队列暂时为空。
- 子任务登记发生在父任务完成之前，等待计数不会遗漏尚未启动的工作。
- 等待完成再读取结果，Go 普通 map 此时才不存在并发写入。
易错点总结
[!yellow]
- 使用普通集合无同步并发写入，或者把查重与登记分开，导致数据竞争或重复任务。
- 先启动协程再增加等待计数，主协程可能先看到零而返回。
- 抓取接口也放在全局锁内，不同任务必须轮流等待网络，失去并发意义。
- Java 根任务没有等待后代，或 Go 漏掉
Done()，分别会导致返回不完整或无法结束。- 把“暂时没有排队任务”当成完成，忽略仍在抓取中的页面之后可能发现新链接。
- 仅用字符串前缀判断同主机，可能把主机名开头相似但实际不同的 URL 也纳入。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1236. 网络爬虫 | 中等 | 单线程图遍历提供功能基础，本题增加并发后还需保护访问集合与任务完成计数。 |
| 1188. 设计有限阻塞队列 | 中等 | 生产者消费者队列可用于分发待爬URL，但爬虫还需判断队列空且所有工作者都已结束任务。 |