10亿QQ号如何去重？

苏三说技术

发布于 2025-07-17 16:12:20

16900

代码可运行

文章被收录于专栏：苏三说技术苏三说技术

运行总次数：0

代码可运行

前言

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

我觉得挺有意思的。

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

一、技术难点

1.1 数据规模分析

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

1.2 核心挑战

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

2.1 算法原理

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

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

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 - ;  
    int arrayIndex = (int)(num >> );  
    int position = (int)(num & );  
    bits[arrayIndex] |=  << position;  
}

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

3.1 应对内存限制

3.2 参数设计与实现

public class BloomFilter {  
    privatefinal BitSet bitset;  
    privatefinalint size;  
    privatefinalint[] seeds;  
    
    public BloomFilter(int size, int hashCount) {  
        this.bitset = new BitSet(size);  
        this.size = size;  
        this.seeds = newint[hashCount];  
        for (int i = ; i < hashCount; i++) {  
            seeds[i] = i * ;  
        }  
    }  
    
    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))) {  
                returnfalse;  
            }  
        }  
        returntrue;  
    }  
    
    private int hash(String value, int seed) {  
        // MurmurHash 实现  
        int result = ;  
        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 = -;  
        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) {  
        returnthis.value.compareTo(o.value);  
    }  
}

五、分布式解决方案

5.1 分片策略设计

5.2 Spark实现方案

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

// 每个分区内部去重  
val distinctRDD = qqRDD.mapPartitions { iter =>  
val bitmap = newRoaringBitmap()  
  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 {  
    privatestaticfinal 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) {  
                returntrue; // 已超过10亿，直接返回重复  
            }  
            return jedis.sadd(REDIS_KEY, qq) == ;  
        }  
    }  
}

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

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 {  
    privatefinal RoaringBitmap[][][] bitmaps;  
    privatestaticfinalint L1 = ; // 一级分片  
    privatestaticfinalint L2 = ; // 二级分片  

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

    public void add(long qq) {  
        int l1Index = (int)((qq - ) / 100_000_000);  
        long remainder = (qq - ) % 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(, str.length() - )));  
    return suffix % shardCount;  
}