#牛客AI配图神器#

一、场景题：一个存储IP地址的100G 的文件, 找出现次数最多的 IP ？

和大文件中存id，然后要求排序问题一样的处理思路

使用MapReduce的思想解决，加上哈希分割，先将大文件中的IP地址按照哈希函数进行分割，存到多个文件上，接着每个分片单独处理，用Hashmap统计IP出现频次，记录当前分片最大值。最后归并处理，找出所有候选IP中的最大出现次数的IP。

1.哈希分割（预处理阶段）

① 使用高效哈希函数计算每个IP的哈希值② 按哈希值取模分片：hash(ip) % N → 生成N个分片文件

分片数计算：假设可用内存1G，每个分片限制为50MB → N=2000分片

2.分块统计（Map阶段）

每个分片处理时：

• 将小文件加载到内存中
• ① 使用HashMap<String, Long>统计IP出现频率 ② 同步维护当前分片的最大值：maxIP和maxCount

3.全局归并（Reduce阶段）

• 读取所有中间结果文件中的最高频IP
• 在这些候选IP中找出全局出现次数最多的IP

4.关键问题

1.哈希函数设计

file_index = hash(IP地址) % 256

这个哈希函数确保了同一个IP地址一定会被映射到同一个文件索引

2.某个分割的文件仍然过大，怎么解决？

若某分片的IP种类过多导致HashMap溢出，解决方案：

• 对该分片进行二次哈希分片

5.面试回答模板

“我会采用分布式计算中常用的分治策略：

1. 哈希分片：将IP按哈希值分散到256个分片中，确保相同IP在同一分片；
2. 分块统计：对每个分片使用HashMap统计频率，同时记录分片内的最大值；
3. 全局归并：比较所有分片的最大值得到最终结果。

二、场景题：100G的文件里有很多id，用1G内存的机器排序，怎么做？

海量数据排序思路

核心方案：外排序（分治+多路归并）MapReduce

外排序是指数据量太大，无法全部加载到内存中，需要将数据分成多个小块进行排序，然后将排序后的小块合并成一个大的有序块

1.分块排序（Map阶段）

• 分块策略 按1G内存容量限制，将100G文件拆分为 200个500MB分块（保留内存用于排序计算和系统开销）
• 内存排序 每个分块加载至内存后： ① 使用快速排序（时间复杂度O(n log n)） ② 去重优化：若存在重复ID，排序时合并相同项（节省存储空间），根据要求是否去重
• 临时文件写入 排序后分块写入磁盘，命名规则：chunk_0001.sorted ~ chunk_0200.sorted

2. 多路归并（Reduce阶段）

使用K路归并算法合并这些排序好的小文件

具体实现方法：

• 从每个小文件中读取一小部分数据到内存（例如每个文件读取几MB）
• 建立最小堆（优先队列）来追踪当前每个文件的最小值
• 每次从堆中取出最小值，写入输出文件
• 从该最小值所在的文件再读入一个ID到堆中
• 重复上述过程直到所有文件都处理完

具体示例：

• ① 分批归并：每轮合并50个分块（50路归并），共需4轮（200/50）
• ② 堆排序优化：使用 最小堆（PriorityQueue） 管理各分块当前读取值

内存管理：

3.核心代码（Java实现）

阶段1：分割大文件，并排序小文件，输出多个小文件排序后的结果

private static List<File> splitAndSort(String inputFile) throws IOException {
        List<File> chunks = new ArrayList<>();
        try (BufferedReader reader = new BufferedReader(new FileReader(inputFile))) {
            List<Long> buffer = new ArrayList<>(MAX_CHUNK_SIZE / 8);
            String line;
            
            while ((line = reader.readLine()) != null) {
                buffer.add(Long.parseLong(line));
                // 内存达到阈值时执行排序和写入
                if (buffer.size() >= MAX_CHUNK_SIZE / 8) {
                    chunks.add(sortAndWrite(buffer));
                    buffer.clear();
                }
            }
            // 处理剩余数据
            if (!buffer.isEmpty()) {
                chunks.add(sortAndWrite(buffer));
            }
        }
        return chunks;
    }

阶段2：多路归并，使用最小堆优化

 private static void mergeFiles(List<File> files, String output) throws IOException {
        PriorityQueue<FileEntry> minHeap = new PriorityQueue<>(
            files.size(), 
            Comparator.comparingLong(FileEntry::current)
        );

        // 初始化堆（每个文件读取一个元素）
        for (File file : files) {
            BufferedReader reader = new BufferedReader(new FileReader(file));
            String line = reader.readLine();
            if (line != null) {
                minHeap.offer(new FileEntry(Long.parseLong(line), reader));
            }
        }

        try (BufferedWriter writer = new BufferedWriter(new FileWriter(output))) {
            while (!minHeap.isEmpty()) {
                FileEntry entry = minHeap.poll();
                writer.write(entry.current.toString());
                writer.newLine();
                
                // 从当前文件读取下一个元素
                String line = entry.reader.readLine();
                if (line != null) {
                    entry.current = Long.parseLong(line);
                    minHeap.offer(entry);
                } else {
                    entry.reader.close(); // 关闭已读完的文件
                }
            }
        }
    }