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

前言

最近在网上看到一个问题：10亿QQ号如何去重？
我觉得挺有意思的。
今天这篇文章跟大家一起分享一下常见的解决方案，希望对你会有所帮助。
更多项目实战在我的技术网站：http://www.susan.net.cn/project
一、技术难点

1.1 数据规模分析

<ul>原始数据：10亿×8字节 = 8GB
HashSet去重：至少16GB内存（Java对象开销）
理想方案：> 3) + 1]; // 每byte存储8个数字      }          public void add(int num) {          int arrayIndex = num >> 3;  // num/8          int position = num & 0x07;  // num%8          bits[arrayIndex] |= 1 > 3;          int position = num & 0x07;          return (bits[arrayIndex] & (1 > 3);      int position = (int)(num & 7);      bits[arrayIndex] |= 1  { try { r.close(); } catch (IOException e) {}});      }  }  class MergeEntry implements Comparable {      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);      }  }  [/code]五、分布式解决方案

5.1 分片策略设计

5.2 Spark实现方案

1. public class BitMap {  
2.     private final byte[] bits;  
3.    
4.     public BitMap(int maxNum) {  
5.         this.bits = new byte[(maxNum >> 3) + 1]; // 每byte存储8个数字  
6.     }  
7.    
8.     public void add(int num) {  
9.         int arrayIndex = num >> 3;  // num/8  
10.         int position = num & 0x07;  // num%8  
11.         bits[arrayIndex] |= 1 << position;  
12.     }  
13.    
14.     public boolean contains(int num) {  
15.         int arrayIndex = num >> 3;  
16.         int position = num & 0x07;  
17.         return (bits[arrayIndex] & (1 << position)) != 0;  
18.     }  
19. }  

复制代码

5.3 内存优化：RoaringBitmap

存储优势对比：

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

复制代码

六、生产级架构：Lambda架构

6.1 系统架构图

6.2 各层技术选型

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

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

复制代码

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

7.1 架构设计

7.2 存储计算

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

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

总内存需求：

1. public class BloomFilter {  
2.     private final BitSet bitset;  
3.     private final int size;  
4.     private final int[] seeds;  
5.    
6.     public BloomFilter(int size, int hashCount) {  
7.         this.bitset = new BitSet(size);  
8.         this.size = size;  
9.         this.seeds = new int[hashCount];  
10.         for (int i = 0; i < hashCount; i++) {  
11.             seeds[i] = i * 31;  
12.         }  
13.     }  
14.    
15.     public void add(String qq) {  
16.         for (int seed : seeds) {  
17.             int hash = hash(qq, seed);  
18.             bitset.set(Math.abs(hash % size), true);  
19.         }  
20.     }  
21.    
22.     public boolean contains(String qq) {  
23.         for (int seed : seeds) {  
24.             int hash = hash(qq, seed);  
25.             if (!bitset.get(Math.abs(hash % size))) {  
26.                 return false;  
27.             }  
28.         }  
29.         return true;  
30.     }  
31.    
32.     private int hash(String value, int seed) {  
33.         // MurmurHash 实现  
34.         int result = 0;  
35.         for (char c : value.toCharArray()) {  
36.             result = seed * result + c;  
37.         }  
38.         return result;  
39.     }  
40. }  

复制代码

7.3 Java实现

1. // 外部排序  
2. public void externalSort(String input, String output) throws IOException {  
3.     List<File> chunks = splitAndSort(input, 100_000_000); // 每个文件1千万  
4.     mergeFiles(chunks, output);  
5. }  
7. // 多路归并  
8. void mergeFiles(List<File> files, String output) {  
9.     PriorityQueue<MergeEntry> queue = new PriorityQueue<>();  
10.     List<BufferedReader> readers = new ArrayList<>();  
12.     // 初始化堆  
13.     for (File file : files) {  
14.         BufferedReader reader = new BufferedReader(new FileReader(file));  
15.         readers.add(reader);  
16.         String line = reader.readLine();  
17.         if (line != null) {  
18.             queue.add(new MergeEntry(line, reader));  
19.         }  
20.     }  
22.     try (BufferedWriter writer = new BufferedWriter(new FileWriter(output))) {  
23.         long last = -1;  
24.         while (!queue.isEmpty()) {  
25.             MergeEntry entry = queue.poll();  
26.             long qq = Long.parseLong(entry.value);  
28.             // 去重：只写入不重复的QQ号  
29.             if (qq != last) {  
30.                 writer.write(entry.value);  
31.                 writer.newLine();  
32.                 last = qq;  
33.             }  
35.             // 读取下一行  
36.             String next = entry.reader.readLine();  
37.             if (next != null) {  
38.                 queue.add(new MergeEntry(next, entry.reader));  
39.             }  
40.         }  
41.     } finally {  
42.         readers.forEach(r -> { try { r.close(); } catch (IOException e) {}});  
43.     }  
44. }  
46. class MergeEntry implements Comparable<MergeEntry> {  
47.     String value;  
48.     BufferedReader reader;  
50.     public MergeEntry(String value, BufferedReader reader) {  
51.         this.value = value;  
52.         this.reader = reader;  
53.     }  
55.     @Override  
56.     public int compareTo(MergeEntry o) {  
57.         return this.value.compareTo(o.value);  
58.     }  
59. }  

复制代码

八、方案对比与选型建议

[table][tr]方案适用场景内存/存储时间复杂度精度[/tr][tr][td]单机位图[/td][td]