- 正确答案：当两个大文件存储了海量的IP地址，且无法一次性加载到内存中时，可以通过外部排序 + 分块归并、哈希分片（分治）、或使用布隆过滤器结合磁盘文件处理的方法来求交集。最常用且可靠的方法是哈希分片（Hash Partitioning）或外部归并排序后逐行比对。 - 解答思路： 1. 首先明确问题规模：IP地址通常是字符串形式如“192.168.1.1”，每个IP约占用15字节，若文件为1GB，则大约包含7000万条记录，远超单机内存处理能力。 2. 不能将整个文件读入内存进行哈希表查找，因此需要采用分治策略。 3. 常见解决方案是将两个大文件分别按照某种规则（如IP的哈希值）分割成多个小文件，使得每个小文件可以被加载进内存处理。 4. 对每个对应的小文件对，使用哈希集合求交集，最后合并所有结果。 - 深度知识讲解：考点包括： 1. 外部数据处理能力（External Memory Algorithms） 2. 分治思想（Divide and Conquer） 3. 哈希函数的设计与冲突控制 4. 内存与磁盘I/O的权衡 5. 数据去重与集合操作原理核心难点在于：如何在内存受限的情况下完成大规模数据的集合交集运算。方法一：哈希分片法（推荐）步骤如下： 1. 定义k个临时小文件（例如k=1000），用于分片存储。 2. 对第一个文件file1中的每个IP，计算hash(IP) % k，将其写入对应的子文件1_i。 3. 同样地，对file2中的每个IP，也按hash(IP) % k写入子文件2_i。 4. 由于相同IP的哈希值模k结果相同，因此两个文件中相同的IP只会出现在同一对子文件（1_i 和 2_i）中。 5. 对每一对子文件（1_i, 2_i），将其读入内存，将其中一个存入HashSet，遍历另一个判断是否存在，若存在则加入交集结果。优点：避免了全量数据同时在内存中；利用哈希均匀分布特性实现负载均衡。注意事项： - 哈希函数应尽量均匀，避免某些桶过大。 - 可使用String.hashCode()或MD5等，但注意不要用Java中对象的hashCode()，因为字符串内容相等则hashCode相等，可用。 - 分片数量k应根据内存大小设定，确保每个分片能装入内存。方法二：外部归并排序 + 双指针扫描步骤： 1. 分别对两个大文件进行外部排序（External Sort）： - 将大文件切分为若干块，每块读入内存排序后写回磁盘。 - 使用k路归并（k-way merge）将有序块合并为整体有序文件。 2. 得到两个有序的大文件后，使用双指针法逐行扫描： - 若file1当前IP < file2当前IP，file1指针前进； - 若file1 > file2，file2指针前进； - 若相等，则为交集元素，同时前进两个指针。优点：结果自然有序，适合后续处理。缺点：排序过程复杂，I/O开销大。方法三：布隆过滤器（Bloom Filter）近似解法步骤： 1. 构造一个足够大的布隆过滤器，能容纳file1中所有IP。 2. 将file1中所有IP插入布隆过滤器。 3. 遍历file2中每个IP，在布隆过滤器中查询： - 若不存在，则一定不在交集中； - 若存在，则可能在交集中（存在误判）。 4. 将可能的候选IP记录下来，再通过二次验证（如写入临时文件并去重）得到最终结果。优点：空间效率高，适合流式处理。缺点：有误判率，不能保证精确结果；需额外验证。所以，若要求精确交集，不推荐布隆过滤器单独使用，可作为预筛选。 - 扩展知识： 1. IP地址的表示优化：可将字符串IP转换为32位整数（int），节省空间并加快比较。例如：192.168.1.1 → (192<<24)|(168<<16)|(1<<8)|1，类型为int（Java中需用long避免符号扩展）。这样每个IP仅占4字节，提升处理效率。 2. 外部排序实现细节： - 使用多路归并，借助最小堆管理k个文件的当前最小值。 - 每次从k个有序段中取出最小值写入输出流。 3. 实际系统中可使用数据库（如SQLite）、MapReduce、Spark等框架处理此类问题，但面试中考察的是底层思路。 - 伪代码（哈希分片法）： ``` // 参数设置 int numPartitions = 1000; // 分片数量 List writers1 = new ArrayList<>(numPartitions); List writers2 = new ArrayList<>(numPartitions); // Step 1: 分割 file1 BufferedReader br1 = new BufferedReader(new FileReader("file1.txt")); String ip; while ((ip = br1.readLine()) != null) { int partition = hash(ip) % numPartitions; writers1.get(partition).println(ip); } br1.close(); // Step 2: 分割 file2 BufferedReader br2 = new BufferedReader(new FileReader("file2.txt")); while ((ip = br2.readLine()) != null) { int partition = hash(ip) % numPartitions; writers2.get(partition).println(ip); } br2.close(); // 关闭所有写入流 for (int i = 0; i < numPartitions; i++) { writers1.get(i).close(); writers2.get(i).close(); } // Step 3: 对每个分片求交集 Set intersection = new HashSet<>(); for (int i = 0; i < numPartitions; i++) { Set set = new HashSet<>(); BufferedReader br = new BufferedReader(new FileReader("file1_part_" + i)); String line; while ((line = br.readLine()) != null) { set.add(line); } br.close(); br = new BufferedReader(new FileReader("file2_part_" + i)); while ((line = br.readLine()) != null) { if (set.contains(line)) { intersection.add(line); // 或直接输出避免内存过大 } } br.close(); } // 输出交集 for (String ip : intersection) { System.out.println(ip); } // 辅助函数 int hash(String ip) { return ip.hashCode(); // 或更稳定的哈希函数 } ``` 注意：上述伪代码中，为简化未处理文件路径和异常，实际需注意资源释放。若交集结果也很大，可将intersection改为写入文件，避免内存溢出。总结：大文件求交集的本质是“分而治之”，核心是通过哈希或排序将问题分解为内存可处理的子问题。哈希分片法是最直观高效的精确解法，适合面试回答。

kook一面【技术面】2025.5.16（已挂）

全站热榜

创作者周榜