位图法高效统计海量电话号码原理与实现

1. 位图法统计电话号码数量的原理剖析

电话号码统计看似简单，但当数据量达到千万甚至上亿级别时，传统方法就会暴露出严重的性能问题。位图法（Bitmap）作为一种高效的数据结构，能在内存消耗和计算效率之间取得完美平衡。

1.1 为什么需要位图法？

假设我们需要统计10亿个电话号码的去重计数。如果用传统HashSet存储，每个电话号码占用约15字节（11位数字+对象开销），总内存消耗将达15GB。而位图法通过比特位标记存在性，理论上只需约119MB内存（10亿位≈119MB）。

关键区别：HashSet存储实际数据，位图只记录存在状态

1.2 位图实现的核心机制

位图本质上是将电话号码映射到比特数组的特定位置。以11位手机号为例：

1. 数值转换：将电话号码转为整数（如13800138000 → 13800138000）
2. 索引计算：用该整数除以8得到字节位置，模8得到位位置
3. 位操作：通过位运算设置或检查对应比特位

python复制def set_bit(bitmap, number):
    byte_pos = number // 8
    bit_pos = number % 8
    bitmap[byte_pos] |= 1 << bit_pos

2. 工程实现中的关键细节

2.1 电话号码的标准化处理

实际场景中电话号码格式复杂：

• 国际号码：+86 13800138000
• 带分隔符：138-0013-8000
• 区号省略：010-12345678 → 12345678

处理方案：

python复制import re

def normalize_phone(phone):
    # 移除非数字字符
    cleaned = re.sub(r'[^\d]', '', phone)
    # 处理国际区号
    if cleaned.startswith('86') and len(cleaned) > 11:
        cleaned = cleaned[2:]
    return cleaned[-11:]  # 取最后11位作为标准手机号

2.2 内存优化策略

当号码范围过大时（如固话号码），