假如有10亿QQ号如何去重？

前言

最近在网上看到一个问题：10亿QQ号如何去重？

我觉得挺有意思的。

今天这篇文章跟大家一起分享一下常见的解决方案，希望对你会有所帮助。

更多项目实战在我的技术网站：http://www.susan.net.cn/project

一、技术难点

1.1 数据规模分析

原始数据：10亿×8字节 = 8GB
HashSet去重：至少16GB内存（Java对象开销）
理想方案：<1GB内存

1.2 核心挑战

二、单机解决方案：位图法

2.1 算法原理

利用位数组表示数字存在性：

public class BitMap {  
    private final byte[] bits;  
    
    public BitMap(int maxNum) {  
        this.bits = new byte[(maxNum >> 3) + 1]; // 每byte存储8个数字  
    }  
    
    public void add(int num) {  
        int arrayIndex = num >> 3;  // num/8  
        int position = num & 0x07;  // num%8  
        bits[arrayIndex] |= 1 << position;  
    }  
    
    public boolean contains(int num) {  
        int arrayIndex = num >> 3;  
        int position = num & 0x07;  
        return (bits[arrayIndex] & (1 << position)) != 0;  
    }  
}

2.2 QQ号范围优化

QQ号范围：10000（5位） - 9999999999（10位）
位图内存计算：

(10^10 - 10^4) / 8 / 1024/1024 ≈ 1.16GB

优化方案：

// 偏移量优化：存储(qq - 10000)  
public void add(long qq) {  
    long num = qq - 10000;  
    int arrayIndex = (int)(num >> 3);  
    int position = (int)(num & 7);  
    bits[arrayIndex] |= 1 << position;  
}

三、进阶方案：布隆过滤器

3.1 应对内存限制

3.2 参数设计与实现

public class BloomFilter {  
    private final BitSet bitset;  
    private final int size;  
    private final int[] seeds;  
    
    public BloomFilter(int size, int hashCount) {  
        this.bitset = new BitSet(size);  
        this.size = size;  
        this.seeds = new int[hashCount];  
        for (int i = 0; i < hashCount; i++) {  
            seeds[i] = i * 31;  
        }  
    }  
    
    public void add(String qq) {  
        for (int seed : seeds) {  
            int hash = hash(qq, seed);  
            bitset.set(Math.abs(hash % size), true);  
        }  
    }  
    
    public boolean contains(String qq) {  
        for (int seed : seeds) {  
            int hash = hash(qq, seed);  
            if (!bitset.get(Math.abs(hash % size))) {  
                return false;  
            }  
        }  
        return true;  
    }  
    
    private int hash(String value, int seed) {  
        // MurmurHash 实现  
        int result = 0;  
        for (char c : value.toCharArray()) {  
            result = seed * result + c;  
        }  
        return result;  
    }  
}

3.3 内存优化效果

方案	内存消耗	误差率
原始存储	8 GB	0%
位图法	1.16 GB	0%
布隆过滤器(0.1%)	171 MB	0.001

四、磁盘方案：外部排序与多路归并

4.1 处理流程

4.2 关键代码实现

// 外部排序  
public void externalSort(String input, String output) throws IOException {  
    List<File> chunks = splitAndSort(input, 100_000_000); // 每个文件1千万  
    mergeFiles(chunks, output);  
}  

// 多路归并  
void mergeFiles(List<File> files, String output) {  
    PriorityQueue<MergeEntry> queue = new PriorityQueue<>();  
    List<BufferedReader> readers = new ArrayList<>();  

    // 初始化堆  
    for (File file : files) {  
        BufferedReader reader = new BufferedReader(new FileReader(file));  
        readers.add(reader);  
        String line = reader.readLine();  
        if (line != null) {  
            queue.add(new MergeEntry(line, reader));  
        }  
    }  

    try (BufferedWriter writer = new BufferedWriter(new FileWriter(output))) {  
        long last = -1;  
        while (!queue.isEmpty()) {  
            MergeEntry entry = queue.poll();  
            long qq = Long.parseLong(entry.value);  

            // 去重：只写入不重复的QQ号  
            if (qq != last) {  
                writer.write(entry.value);  
                writer.newLine();  
                last = qq;  
            }  

            // 读取下一行  
            String next = entry.reader.readLine();  
            if (next != null) {  
                queue.add(new MergeEntry(next, entry.reader));  
            }  
        }  
    } finally {  
        readers.forEach(r -> { try { r.close(); } catch (IOException e) {}});  
    }  
}  

class MergeEntry implements Comparable<MergeEntry> {  
    String value;  
    BufferedReader reader;  

    public MergeEntry(String value, BufferedReader reader) {  
        this.value = value;  
        this.reader = reader;  
    }  

    @Override  
    public int compareTo(MergeEntry o) {  
        return this.value.compareTo(o.value);  
    }  
}

五、分布式解决方案

5.1 分片策略设计

5.2 Spark实现方案

val qqRDD = spark.read.textFile("hdfs://qq_data/*.txt")  
  .map(_.toLong)  
  .repartition(1000)  // 分为1000个分区  

// 每个分区内部去重  
val distinctRDD = qqRDD.mapPartitions { iter =>  
  val bitmap = new RoaringBitmap()  
  iter.foreach(qq => bitmap.add(qq.toInt))  
  bitmap.iterator.asScala.map(_.toLong)  
}  

// 全局去重（可选）  
val globalDistinct = distinctRDD.distinct()  

globalDistinct.saveAsTextFile("hdfs://result/")

5.3 内存优化：RoaringBitmap

存储优势对比：

普通位图：10^10 / 8 / 1024/1024 ≈ 1.16 GB  
RoaringBitmap：稀疏数据下可压缩至100-300 MB

六、生产级架构：Lambda架构

6.1 系统架构图

6.2 各层技术选型

架构层	技术栈	处理目标
批处理层	Spark + HDFS	全量数据去重
速度层	Flink + Redis	实时增量去重
服务层	Spring Boot + HBase	统一查询接口

6.3 实时去重实现

public class QQDeduplication {  
    private static final String REDIS_KEY = "qq_set";  

    public boolean isDuplicate(String qq) {  
        try (Jedis jedis = jedisPool.getResource()) {  
            // 使用HyperLogLog进行基数估计  
            if (jedis.pfcount(REDIS_KEY) > 1_000_000_000L) {  
                return true; // 已超过10亿，直接返回重复  
            }  
            return jedis.sadd(REDIS_KEY, qq) == 0;  
        }  
    }  
}

七、终极方案：分层位图索引

7.1 架构设计

7.2 存储计算

QQ号范围：10000 - 9999999999（约100亿）
分层设计：

第一层分片：100个区间（每区间1亿）
第二层分片：100个子区间（每区间100万）
第三层存储：RoaringBitmap（每分区1.2MB）

总内存需求：

100 × 100 × 1.2MB = 12GB（分布式存储可行）

7.3 Java实现

public class LayeredBitmap {  
    private final RoaringBitmap[][][] bitmaps;  
    private static final int L1 = 100; // 一级分片  
    private static final int L2 = 100; // 二级分片  

    public LayeredBitmap() {  
        bitmaps = new RoaringBitmap[L1][L2][];  
    }  

    public void add(long qq) {  
        int l1Index = (int)((qq - 10000) / 100_000_000);  
        long remainder = (qq - 10000) % 100_000_000;  
        int l2Index = (int)(remainder / 1_000_000);  
        int value = (int)(remainder % 1_000_000);  

        if (bitmaps[l1Index][l2Index] == null) {  
            bitmaps[l1Index][l2Index] = new RoaringBitmap();  
        }  
        bitmaps[l1Index][l2Index].add(value);  
    }  

    public boolean contains(long qq) {  
        // 类似add的分片计算  
        RoaringBitmap bitmap = bitmaps[l1Index][l2Index];  
        return bitmap != null && bitmap.contains(value);  
    }  
}

八、方案对比与选型建议

方案	适用场景	内存/存储	时间复杂度	精度
单机位图	<1亿数据	O(n)	O(1)	100%
布隆过滤器	百亿级容忍误差	O(1)	O(k)	<99.9%
外部排序	单机磁盘处理	磁盘空间	O(n log n)	100%
Spark分布式	海量数据批量处理	集群存储	O(n)	100%
Redis实时去重	增量数据实时处理	O(n)	O(1)	100%
分层位图索引	超大规模精准去重	O(n)压缩存储	O(1)	100%

九、实战经验与避坑指南

9.1 数据倾斜解决方案

问题场景：部分QQ号段过于集中（如100000-199999）
解决策略：

// 动态分片函数  
int getShardId(long qq, int shardCount) {  
    String str = String.valueOf(qq);  
    // 取后6位作为分片依据  
    int suffix = Integer.parseInt(str.substring(Math.max(0, str.length() - 6)));  
    return suffix % shardCount;  
}

9.2 去重精度保障

9.3 成本优化建议

冷热分离：热数据用内存位图，冷数据存磁盘
压缩存储：使用RoaringBitmap替代普通位图
分级存储：
- 最近3个月数据：内存存储
- 历史数据：HBase+压缩

总结

分治思想：10亿问题拆解为1000个100万问题
空间换时间：位图法用存储空间换取O(1)时间复杂度
概率智慧：布隆过滤器用可控误差换取千倍空间压缩
分层设计：亿级→百万级→万级分层处理
动静分离：批处理处理历史数据，实时处理增量数据

10亿QQ号去重的本质，是将问题拆解到每个计算单元都能高效处理的粒度。

最后说一句(求关注，别白嫖我)

如果这篇文章对您有所帮助，或者有所启发的话，帮忙关注一下我的同名公众号：苏三说技术，您的支持是我坚持写作最大的动力。

求一键三连：点赞、转发、在看。

关注公众号：【苏三说技术】，在公众号中回复：进大厂，可以免费获取我最近整理的10万字的面试宝典，好多小伙伴靠这个宝典拿到了多家大厂的offer。