1. 问题背景与核心挑战
在电信运营商、电商平台或用户数据分析场景中,我们经常需要处理海量电话号码的去重统计。假设现在有一个包含10亿条电话号码记录的文本文件,每条记录都是11位数字(如13812345678),如何高效计算出其中不重复的电话号码数量?
传统方法如HashSet或数据库DISTINCT查询在面对这种量级数据时,会暴露出明显缺陷:
- 内存消耗:存储10亿个11位数字符串需要约100GB内存(每个号码按20字节估算)
- 计算效率:哈希冲突处理和数据持久化带来的性能损耗
- 硬件成本:分布式计算集群的搭建和维护开销
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 位图法原理剖析
2.1 位图数据结构本质
位图(Bitmap)通过比特位的0/1状态表示元素存在性。对于电话号码统计场景:
- 将每个电话号码转换为唯一整数
- 用该整数作为位图索引位置
- 将对应比特位设为1表示该号码存在
2.2 电话号码编码方案
11位电话号码的数值范围是[10000000000, 19999999999],实际可用号码约100亿个。我们需要设计紧凑的编码方式:
python复制def phone_to_index(phone):
return int(phone) - 10000000000 # 转换为0开始的连续索引
2.3 内存占用计算
原始方案需要约100亿比特位:
- 10000000000 bits ≈ 1.16GB
- 相比原始数据压缩了约100倍
3. 工程实现方案
3.1 基础位图实现(Python示例)
python复制import numpy as np
class PhoneBitmap:
def __init__(self):
self.max_phone = 99999999999
self.min_phone = 10000000000
self.bitmap = np.zeros((self.max_phone - self.min_phone + 1) // 8 + 1, dtype=np.uint8)
def add_phone(self, phone):
index = int(phon
