- 正确答案：使用外排序 + 哈希计数 + 最小堆（或Top-K堆）的组合策略。具体步骤为：1）将4GB大文件分块读入内存，每块大小控制在可用内存范围内（如512MB），对每块进行URL哈希计数（用HashMap统计频次）；2）将各块的计数结果写入临时文件（按URL排序或直接存为键值对）；3）对所有临时计数文件执行多路归并，边归并边累加相同URL的访问次数（需在归并时合并相同key）；4）在归并过程中维护一个容量为10的最小堆，仅保留当前频次最高的10个URL；或更优做法是：先完成全量URL频次统计（通过外部哈希聚合，如分桶+磁盘哈希表），再用快速选择（QuickSelect）或最小堆一次性求Top 10。但考虑到4GB文件中URL数量极大（可能百亿级去重URL）、内存有限（假设面试场景为典型PC/笔记本，可用内存约1~2GB），推荐工业级可行方案为：**分桶哈希（Hash Partitioning） + 内存内计数 + 归并Top-K**，核心是避免全局加载、利用磁盘作为扩展内存。 - 解答思路：第一步：分析数据规模与约束。4GB文本文件，每行一个URL（常见日志格式如Apache access.log），平均URL长度约80字节，则总行数 ≈ 4×1024³ / 80 ≈ 53.6亿行。去重URL数可能达千万至亿级，无法全量载入内存。因此必须采用外部处理范式：分而治之 + 磁盘暂存 + 流式聚合。第二步：选择分桶策略。对每个URL计算hash(url) % N（如N = 100），将URL按哈希桶分散到100个临时文件（part_00, part_01, ..., part_99）。关键点：相同URL必落入同一桶（确定性哈希），保证后续单桶可独立统计准确频次。第三步：逐桶加载统计。对每个part_i文件，用HashMap在内存中精确计数（因单桶数据量降为约5360万行，URL去重后内存可控）；统计完后，将对按count降序排序，取本桶Top 10，或更优——将全部计数对写入“候选集文件”，最后统一归并。但更高效的是：对每个桶输出其局部Top K（K=10），再合并100个Top 10 → 总共1000条候选，再从中选全局Top 10。但此法有缺陷（局部Top未必含全局Top，如某URL均匀分布于各桶则频次被拆分）。故正确做法是：**桶内必须做全量计数，然后输出该桶全部（或仅输出count > threshold的高频候选），再全局归并统计**。第四步：归并计数。使用多路归并（k-way merge）对100个已按URL字典序排序的计数文件进行归并（可在分桶时就对每个part_i内部按URL排序，或使用外部排序算法预处理），归并过程中合并相同URL的count（因同一URL只在一个桶中，归并时相邻相同URL即为同一URL）。边归并边维护一个大小为10的最小堆（PriorityQueue），若新count > 堆顶count，则弹出堆顶、插入新元素。最终堆中即为全局访问量最高的10个URL。 - 深度知识讲解： 1）底层I/O与内存管理：Java中应使用BufferedReader（带8KB以上缓冲区）逐行读取，避免String.split()造成临时对象爆炸；URL解析若含参数需考虑是否归一化（如去掉utm参数、排序query key），否则相同语义URL会被视为不同（这是实际工程中关键预处理，常被忽略）。 2）哈希冲突与分桶质量：String.hashCode()在Java中为31 * h + char，对URL这种长字符串易发生碰撞，但%N分桶本身不要求哈希完美，只要分布均匀即可。可改用MurmurHash3等非加密哈希提升分布性。 3）外部排序原理：当数据无法全载入内存时，经典方法是“生成-归并”（Generate-Sort-Merge）。生成阶段将数据切分为多个可内存排序的run，分别排序后写磁盘；归并阶段用最小堆实现k路归并，时间复杂度O(N log k)，其中k为run数。本题中“分桶”本质是按key哈希划分run，天然避免了跨桶key比较，比通用外部排序更高效。 4）Top-K算法对比： - 最小堆法：时间复杂度O(N log K)，空间O(K)，适合流式场景，无需存储全部计数； - 快速选择（QuickSelect）：期望O(N)，但需全量计数数组，空间O(M)（M为去重URL数），对亿级M不现实； - 计数排序/桶排序：仅适用于count范围小且已知（如max_count < 1e6），但Web访问频次服从Zipf分布，头部极少数URL占大部分流量，count跨度可达1e9，不适用。 5）MapReduce类比：该解法正是MapReduce的朴素实现——Map阶段：分桶+本地计数；Shuffle阶段：按URL哈希分组（由分桶隐式完成）；Reduce阶段：归并+聚合+TopK。Hadoop中可通过自定义Partitioner和Reducer实现，Spark中用reduceByKey + takeOrdered(10)(Ordering.by(-_._2))一行解决。 6）内存优化细节：URL字符串重复率高（如静态资源路径），可用String.intern()或更安全的LRUStringPool减少内存占用；或改用byte[] + Unsafe操作避免String对象头开销（JDK9+ String为byte[]+coder，已优化）。 - 伪代码（核心流程，Java风格）： ``` // Step 1: 分桶 int NUM_BUCKETS = 100; FileWriter[] bucketWriters = new FileWriter[NUM_BUCKETS]; for (int i = 0; i < NUM_BUCKETS; i++) { bucketWriters[i] = new FileWriter("bucket_" + i); } BufferedReader reader = new BufferedReader(new FileReader("access.log")); String line; while ((line = reader.readLine()) != null) { String url = parseUrl(line); // 提取URL，可选归一化 int bucket = Math.abs(url.hashCode()) % NUM_BUCKETS; bucketWriters[bucket].write(url + "\n"); } for (FileWriter w : bucketWriters) w.close(); // Step 2: 每桶计数并排序（写入sorted_bucket_i） for (int i = 0; i < NUM_BUCKETS; i++) { Map counter = new HashMap<>(); BufferedReader br = new BufferedReader(new FileReader("bucket_" + i)); String url; while ((url = br.readLine()) != null) { counter.put(url, counter.getOrDefault(url, 0L) + 1); } br.close(); // 按URL排序写入（为归并准备） List> entries = new ArrayList<>(counter.entrySet()); entries.sort(Map.Entry.comparingByKey()); PrintWriter pw = new PrintWriter("sorted_bucket_" + i); for (Map.Entry e : entries) { pw.println(e.getKey() + "\t" + e.getValue()); } pw.close(); } // Step 3: 多路归并 + Top10最小堆 PriorityQueue minHeap = new PriorityQueue<>(10, Comparator.comparingLong(e -> e.count)); // 初始化100路归并器：每个桶一个BufferedReader和当前行 BufferedReader[] brs = new BufferedReader[NUM_BUCKETS]; String[] currentLines = new String[NUM_BUCKETS]; for (int i = 0; i < NUM_BUCKETS; i++) { brs[i] = new BufferedReader(new FileReader("sorted_bucket_" + i)); currentLines[i] = brs[i].readLine(); } while (true) { // 找出所有非null行中字典序最小的URL（归并关键） String minUrl = null; long totalCount = 0; for (int i = 0; i < NUM_BUCKETS; i++) { if (currentLines[i] != null) { String[] parts = currentLines[i].split("\t", 2); String url = parts[0]; if (minUrl == null || url.compareTo(minUrl) < 0) { minUrl = url; totalCount = Long.parseLong(parts[1]); } else if (url.equals(minUrl)) { totalCount += Long.parseLong(parts[1]); } } } if (minUrl == null) break; // 更新堆 if (minHeap.size() < 10) { minHeap.offer(new UrlCount(minUrl, totalCount)); } else if (totalCount > minHeap.peek().count) { minHeap.poll(); minHeap.offer(new UrlCount(minUrl, totalCount)); } // 推进所有等于minUrl的桶指针 for (int i = 0; i < NUM_BUCKETS; i++) { if (currentLines[i] != null) { String[] parts = currentLines[i].split("\t", 2); if (parts[0].equals(minUrl)) { currentLines[i] = brs[i].readLine(); } } } } // 输出结果 List result = new ArrayList<>(minHeap); result.sort((a, b) -> Long.compare(b.count, a.count)); for (UrlCount uc : result) { System.out.println(uc.url + " -> " + uc.count); } ``` 补充说明：上述伪代码中的归并逻辑为简化版，实际高效实现应使用“最小堆驱动归并”——即把每个桶的首行放入最小堆（按URL排序），每次pop最小URL，合并所有同URL行，再从对应桶推入下一行。这样时间复杂度为O(N log B)，B为桶数，比O(N*B)的暴力扫描更优。此处为教学清晰暂用直观写法。该问题本质考察：大数据量下的算法工程能力——如何权衡时间/空间/IO/精度；对哈希、堆、外部排序等基础数据结构的融会贯通；以及对真实系统约束（内存、磁盘、CPU缓存）的敏感度。

滴滴平台后端ai开发一面-实习面经

全站热榜

创作者周榜