一、问题分析与技术选型

1.1 问题核心与挑战

面对1亿条URL（假设平均长度为100字节），我们首先估算一下数据量：

总数据量 ≈ 1亿 * 100 Byte ≈ 10 GB

这个规模的数据无法一次性装入单台机器的内存中进行传统的去重操作（例如使用 HashSet<String>）。假设每个URL的Java String对象开销约为40-60字节（基于Java 8及之前的String实现，包含char[]、hash等字段），仅存储1亿个String引用就可能需要 4GB ~ 6GB 的内存，这已经接近或超过了许多JVM实例的堆内存上限，更不用说存储字符串本身的数据了。因此，挑战主要在于：

内存限制 (Memory Constraint)：无法将所有数据载入内存。
计算效率 (Computational Efficiency)：需要在合理的时间内完成去重。
分布式考量 (Distributed Consideration)：是否需要以及如何利用多机分布式处理。
准确性 (Accuracy)：是否可以接受极低概率的误判（False Positive）。

1.2 可行方案对比

针对海量数据去重，常见的方案有：

外部排序 + 逐行比较：
思路：将大文件分割成小块，每块在内存中排序，然后使用归并排序的思想合并这些有序小块，在合并过程中跳过重复的行。
优点：准确，无需额外数据结构。
缺点：磁盘I/O密集型，速度相对较慢。
哈希分片 + 单机去重：
思路：使用一个哈希函数（如MD5, SHA-1）对每条URL进行计算，根据哈希值将URL分散到多个小文件中。由于相同的URL其哈希值必然相同，所以它们一定会被分到同一个文件中。然后，对每个小文件单独加载到内存中用 HashSet 去重，最后合并结果。
优点：准确，将大问题分解为小问题，充分利用多核CPU。
缺点：需要多次磁盘读写（一写多读）。
布隆过滤器 (Bloom Filter)：
思路：使用一个位数组和多个哈希函数。添加元素时，用多个哈希函数计算出多个位的位置并将其置1。检查元素时，只有当所有对应的位都是1时，才认为元素“可能存在”；如果有任何一个位是0，则元素“肯定不存在”。
优点：极高的空间效率和查询效率。
缺点：存在误判率（False Positive），即不存在的元素可能被误判为存在；但存在的元素绝不会被误判为不存在（False Negative）。无法删除元素。
分布式处理框架 (如Spark, Flink)：
思路：利用集群的分布式计算和存储能力，直接使用框架提供的 distinct() 算子。
优点：处理能力极强，可水平扩展。
缺点：需要搭建和维护分布式集群，对于“仅1亿条URL”这个量级的问题来说有点“杀鸡用牛刀”，但如果是面试，提出此方案能展现知识广度。

1.3 最终方案选择：分阶段组合策略

为了兼顾效率和准确性，我们采用一个组合策略：

第一阶段 (快速过滤)：使用布隆过滤器进行初步、低内存消耗的去重。它能以极高的概率快速判断出一个URL是否已经“见过”。对于那些被布隆过滤器判定为“肯定不存在”的URL，我们可以直接输出为不重复项。对于那些被判定为“可能存在”的URL，我们将其放入一个“疑似重复”的集合中。由于布隆过滤器极高的空间效率，1亿条数据所需的位数组大小可以控制在100MB ~ 1GB 左右，完全可以放入内存。
第二阶段 (精确判断)：对“疑似重复”的URL集合，使用传统的基于HashSet的精确去重。因为这个集合的大小通常远小于原始数据集（只包含所有可能重复的URL），所以可以轻松放入内存进行处理。

这个组合策略完美发挥了两种技术的优势：布隆过滤器处理了绝大部分的非重复判断，而HashSet则解决了布隆过滤器那部分小小的不确定性，保证了结果的100%准确。

二、核心技术精讲：布隆过滤器

2.1 原理深入

布隆过滤器（Bloom Filter）是由Burton Howard Bloom在1970年提出的一种概率型数据结构。

核心组件：
一个长度为 m 的位数组 (Bit Array)：初始所有位都为0。
k 个不同的哈希函数：每个函数都能将输入元素映射到位数组的某个位置上。
操作流程：

添加元素：
将元素 e 分别输入 k 个哈希函数，得到 k 个哈希值 h1(e), h2(e), ..., hk(e)。
对每个哈希值对 m 取模，得到在位数组上的 k 个位置 p1, p2, ..., pk。
将位数组的这些位置 p1, p2, ..., pk 都设置为1。
查询元素：
同样，计算元素 e 对应的 k 个位置 p1, p2, ..., pk。
检查这些位置上的值：

如果所有位置的值都是1，则返回 “可能存在”。
如果任何一个位置的值是0，则返回 “肯定不存在”。

误判率分析：
误判发生在不同的元素被哈希到完全相同的 k 个位置上。位数组越密集（m 小，n 大），哈希函数越多（k 大），发生冲突的概率就越高。误判率 p 的近似计算公式为：
$p ≈ (1 - e^{-kn/m})^k$
我们可以根据预期的元素数量 n 和可接受的误判率 p 来计算出所需的位数组大小 m 和哈希函数个数 k：
$m = -\frac{n \ln p}{(\ln 2)^2}$
$k = \frac{m}{n} \ln 2$
例如，对于 n = 1亿， p = 0.01 (1%)：
$m = -\frac{10^8 \times \ln(0.01)}{(\ln 2)^2} ≈ -\frac{10^8 \times (-4.605)}{0.480} ≈ 958,505,000 \text{ bits} ≈ 114 \text{ MB}$
$k = \frac{114 \text{ MB} \times 8 \times 1024 \times 1024}{10^8} \times 0.693 ≈ 6.6$，取整为 7 个哈希函数。
可以看到，仅用约114MB内存即可处理1亿条数据，并将误判率控制在1%。

2.2 Java实现方案

在Java中，我们有多种选择：

手动实现：使用 BitSet 作为位数组，组合多个哈希函数（如MD5、SHA系列的不同部分，或使用MurmurHash等高效哈希函数的不同种子）。
使用知名库：如Google Guava库提供的 BloomFilter 类，成熟稳定，性能优异。
使用Redis等外部缓存：Redis提供了布隆过滤器模块（redisbloom），可以分布式共享，避免JVM内存限制。

在本解决方案中，我们将首先展示如何使用 Google Guava 库，因为它最简单、最实用。然后，我们会简要讲解一个简化版的手动实现原理。

三、代码实现：两阶段去重系统

我们将构建一个完整的、基于Java的两阶段URL去重程序。

3.1 环境准备

首先，在Maven项目的 pom.xml 中添加Guava依赖：

xml

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version> <!-- 请使用最新版本 -->
</dependency>

3.2 核心代码实现

我们假设URL列表存储在一个巨大的文本文件 urls.txt 中，每行一个URL。程序将读取该文件，去重后，将结果输出到 unique_urls.txt。

主类：TwoPhaseURLDeduplicator

java

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.io.*;
import java.nio.charset.StandardCharsets;
import java.util.HashSet;
import java.util.Set;

/**
 * 两阶段URL去重器
 * 第一阶段：使用布隆过滤器进行快速过滤
 * 第二阶段：对疑似重复的URL使用HashSet进行精确去重
 */
public class TwoPhaseURLDeduplicator {

    // 预期要插入的元素数量
    private static final long EXPECTED_INSERTIONS = 100_000_000L;
    // 可接受的误判率
    private static final double FPP = 0.01; // 1%

    // 布隆过滤器 (使用Guava)
    private BloomFilter<String> bloomFilter;
    // 用于存储被布隆过滤器标记为“可能重复”的URL，并进行精确判断
    private Set<String> suspectedDuplicates;

    public TwoPhaseURLDeduplicator() {
        // 初始化布隆过滤器
        this.bloomFilter = BloomFilter.create(
                Funnels.stringFunnel(StandardCharsets.UTF_8),
                EXPECTED_INSERTIONS,
                FPP
        );
        // 初始化疑似重复集合
        this.suspectedDuplicates = new HashSet<>();
    }

    /**
     * 处理单个URL
     * @param url 待处理的URL
     * @return true - 是唯一URL（首次出现）； false - 是重复URL
     */
    public boolean processURL(String url) {
        // 查询布隆过滤器
        boolean mightContain = bloomFilter.mightContain(url);

        if (!mightContain) {
            // 布隆过滤器说“肯定不存在”，那一定是新URL
            bloomFilter.put(url); // 将其加入布隆过滤器
            return true;
        } else {
            // 布隆过滤器说“可能存在”，需要进一步检查疑似重复集合
            synchronized (suspectedDuplicates) {
                if (suspectedDuplicates.contains(url)) {
                    // 在疑似集合中存在，是重复URL
                    return false;
                } else {
                    // 在疑似集合中不存在，是首次出现的“疑似重复”URL
                    suspectedDuplicates.add(url);
                    // 注意：这里不需要再put到BloomFilter中，因为它已经在里面了
                    return true;
                }
            }
        }
    }

    /**
     * 从输入文件读取，处理，并写入输出文件
     * @param inputFile  输入文件路径
     * @param outputFile 输出文件路径
     */
    public void processFile(String inputFile, String outputFile) throws IOException {
        long startTime = System.currentTimeMillis();
        long totalLines = 0;
        long uniqueLines = 0;

        try (BufferedReader reader = new BufferedReader(new FileReader(inputFile));
             BufferedWriter writer = new BufferedWriter(new FileWriter(outputFile))) {

            String line;
            while ((line = reader.readLine()) != null) {
                totalLines++;
                if (processURL(line)) {
                    uniqueLines++;
                    writer.write(line);
                    writer.newLine();
                }

                // 打印进度（每100万行打印一次）
                if (totalLines % 1_000_000 == 0) {
                    System.out.printf("已处理 %d0万行数据...%n", totalLines / 1_000_000);
                }
            }
        }

        long endTime = System.currentTimeMillis();
        System.out.println("去重完成！");
        System.out.println("总行数: " + totalLines);
        System.out.println("唯一行数: " + uniqueLines);
        System.out.println("耗时: " + (endTime - startTime) / 1000.0 + " 秒");
        System.out.println("布隆过滤器疑似重复集合大小: " + suspectedDuplicates.size());
    }

    public static void main(String[] args) {
        TwoPhaseURLDeduplicator deduplicator = new TwoPhaseURLDeduplicator();
        String input = "urls.txt";
        String output = "unique_urls.txt";

        try {
            deduplicator.processFile(input, output);
        } catch (IOException e) {
            System.err.println("处理文件时发生错误: " + e.getMessage());
            e.printStackTrace();
        }
    }
}

3.3 代码精讲

初始化 (Constructor):
使用 BloomFilter.create() 创建布隆过滤器。我们传入了：
Funnels.stringFunnel(StandardCharsets.UTF_8)：指定了如何将String对象“倒入”过滤器中，即序列化的方式。
EXPECTED_INSERTIONS：预期插入数量1亿。Guava根据这个值和FPP自动计算最优的 m 和 k。
FPP：误判率0.01。
初始化 suspectedDuplicates 为一个 HashSet，用于存放所有被布隆过滤器标记为“可能重复”的URL。
核心逻辑 (processURL方法):
boolean mightContain = bloomFilter.mightContain(url): 查询布隆过滤器。
if (!mightContain)：这是最理想、也是最常见的情况。布隆过滤器断定此URL是新的，我们直接将其加入布隆过滤器 (bloomFilter.put(url))，并返回 true（是唯一URL）。
else：进入“疑似”流程。由于 HashSet 不是线程安全的，我们使用 synchronized 块进行保护（如果程序是单线程的，可以去掉，但保留以保证扩展性）。
检查 suspectedDuplicates 是否已经包含此URL。如果包含，说明是重复的，返回 false。
如果不包含，说明这是此URL第一次被布隆过滤器误判（或者说，是它第一次进入“疑似”区域）。我们将其加入 suspectedDuplicates，并返回 true（是唯一URL）。注意：此时不需要再将其 put 到布隆过滤器中，因为在它第一次被加入时，布隆过滤器相应的位就已经被设置了。
文件处理 (processFile方法):
使用 BufferedReader 和 BufferedWriter 高效地逐行读写文件。
统计总行数和唯一行数，并打印进度。
最后输出性能统计信息，包括 suspectedDuplicates 的大小。这个大小理论上约等于总插入数 * FPP，即约100万。一个100万大小的 HashSet 在内存中只占几十MB，毫无压力。

3.4 手动实现简化版布隆过滤器（原理演示）

虽然Guava的实现非常优秀，但理解其原理至关重要。下面是一个极简版的手动实现：

java

import java.util.BitSet;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.nio.charset.StandardCharsets;

public class SimpleBloomFilter {
    private BitSet bitSet;
    private int bitSetSize;
    private int numHashFunctions;
    private MessageDigest md5Digest; // 使用MD5作为基础哈希函数来模拟多个哈希函数

    public SimpleBloomFilter(int expectedInsertions, double fpp) {
        this.bitSetSize = (int) (-expectedInsertions * Math.log(fpp) / (Math.log(2) * Math.log(2)));
        this.numHashFunctions = (int) (bitSetSize / expectedInsertions * Math.log(2));
        this.bitSet = new BitSet(bitSetSize);
        try {
            this.md5Digest = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("MD5 algorithm not found", e);
        }
        System.out.printf("BitSet Size: %d bits, Num Hash Functions: %d%n", bitSetSize, numHashFunctions);
    }

    private int[] getHashes(String value) {
        int[] result = new int[numHashFunctions];
        byte[] bytes = md5Digest.digest(value.getBytes(StandardCharsets.UTF_8));
        // MD5产生128位（16字节）的哈希值，我们可以将其切分成多个int值来模拟多个哈希函数
        for (int i = 0; i < numHashFunctions; i++) {
            int hash = 0;
            // 简单地从MD5结果的不同部分取数据来构造哈希值
            for (int j = 0; j < 4; j++) {
                hash <<= 8;
                hash |= bytes[(i * 4 + j) % bytes.length] & 0xFF;
            }
            result[i] = Math.abs(hash % bitSetSize);
        }
        return result;
    }

    public void put(String value) {
        int[] hashes = getHashes(value);
        for (int hash : hashes) {
            bitSet.set(hash);
        }
    }

    public boolean mightContain(String value) {
        int[] hashes = getHashes(value);
        for (int hash : hashes) {
            if (!bitSet.get(hash)) {
                return false;
            }
        }
        return true;
    }
}
// ... 在主程序中使用 SimpleBloomFilter 替换 Guava BloomFilter ...

精讲:

getHashes 方法：使用MD5生成一个128位的摘要，然后通过切分和组合这个摘要，来模拟产生 numHashFunctions 个不同的哈希值。这是一种常见的技巧，避免了计算多个独立哈希的高开销。
put 和 mightContain 方法：逻辑与原理描述一致。
注意：这是一个演示版本，其哈希函数的独立性和分布性不如Guava中经过精心设计和测试的实现（Guava使用了MurmurHash128等），因此实际误判率可能略高于理论值。生产环境强烈推荐使用Guava或Redis的实现。

四、优化与扩展

4.1 性能优化

多线程处理：
上述代码是单线程的，I/O是瓶颈。可以改用生产者-消费者模型。
思路：启动一个线程专门负责读取文件（生产者），将读取到的URL放入一个 BlockingQueue。启动多个工作线程（消费者）从队列中获取URL，调用 processURL 方法进行处理，并将唯一的URL放入另一个结果队列。再由一个写入线程负责将结果写入文件。
挑战：processURL 方法中的 synchronized 块会成为并发瓶颈。可以考虑使用 ConcurrentHashMap 来代替 HashSet，或者使用分片的锁（减小锁粒度）。
I/O优化：
使用 java.nio 包中的 FileChannel 和 MappedByteBuffer 进行内存映射文件读写，可以大幅提升大文件的读取速度。

4.2 扩展性讨论

分布式布隆过滤器：
如果数据量巨大（千亿级以上），单机布隆过滤器的位数组也会很大。此时可以使用Redis的布隆过滤器模块 (BF.RESERVE, BF.ADD, BF.EXISTS 命令)，将布隆过滤器存储在Redis中，所有处理节点共享同一个过滤器状态。
完全分布式方案（Spark示例）：
如果是在面试中，可以简要提及如何使用Spark来处理，这体现了你的技术视野。
scala
// 这是一个Spark的代码示例 val spark = SparkSession.builder().appName("URLDeduplication").getOrCreate() val inputRdd = spark.read.textFile("hdfs://path/to/urls.txt").rdd val uniqueUrlRdd = inputRdd.distinct() // Spark的distinct算子会自动进行分布式的shuffle和去重 uniqueUrlRdd.saveAsTextFile("hdfs://path/to/unique_urls") spark.stop()
原理：distinct() 算子内部会对RDD进行重分区（通常使用哈希分区），使得相同的URL一定会被分到同一个分区（Task）中，然后在每个分区内部进行去重。这本质上和我们之前说的“哈希分片+单机去重”原理相同，但是由Spark框架自动、分布式地完成。

五、总结

面对“1亿条URL如何去重”这个问题，我们交出了一份从理论到实践的完整答卷：

问题分析：认识到核心挑战是内存限制。
技术选型：没有单一银弹，我们选择了布隆过滤器 (Bloom Filter) + HashSet 的组合策略，兼顾了空间效率和100%的准确性。
原理精讲：深入剖析了布隆过滤器的工作原理、误判率公式及其数学推导。
代码实现：使用 Google Guava 库提供了生产级别的代码，并附有详细注释和讲解。同时，提供了一个简化版的手动实现以助理解原理。
优化扩展：讨论了多线程、I/O优化以及走向分布式的方案（如Redis、Spark），展现了解决超大规模问题的潜力。

这个解决方案不仅回答了面试题，更展示了一种处理海量数据的通用方法论：结合多种数据结构的优势，分阶段处理，并始终在时间、空间和准确性之间做出合理的权衡。希望这篇超过5000字的详细讲解能对你有所帮助。

七桃资源网

1亿条URL如何去重?针对海量数据处理的技术面试解决方案分享