Python位图实现：高效处理海量整数存在性判断

本文深入解析了Python中位图（BitMap）的底层实现原理与实用技巧，揭示其本质是一段连续内存，每个bit高效标识一个非负整数的存在状态；通过bytearray或array.array('B')手动构建，并借助位运算（如n>>3和n&7）精准定位字节与比特位置，显著提升海量整数存在性判断的性能与空间效率，同时重点警示越界访问的隐性风险——既硬核又接地气，是优化大数据去重、布隆过滤器底层及内存敏感场景的必读实践指南。

BitMap 本质是啥？别被名字唬住

BitMap 就是一段连续的内存，每个 bit 代表一个整数是否存在。比如第 i 位为 1，表示整数 i 在集合中；为 0 表示不存在。它不是 Python 内置类型，得自己用 bytearray 或 array.array('B') 搭建底层存储，再靠位运算操作。

关键点：索引必须是非负整数，且最大值不能超过 len(bitmap) * 8 - 1。越界访问不会报错，但结果不可预测——这是最常踩的坑。

怎么算 byte 和 bit 的位置？别手算出错

给定整数 n，它在 BitMap 中的位置由两部分决定：n // 8 是字节偏移，n % 8 是该字节内的 bit 偏移（从右往左，0~7）。实际用的时候推荐直接写成 n >> 3 和 n & 7，更快更安全。

• set_bit(n)：bitmap[n >> 3] |= (1
• get_bit(n)：(bitmap[n >> 3] >> (n & 7)) & 1
• clear_bit(n)：bitmap[n >> 3] &= ~(1

注意：Python 的 int 是任意精度，但 1 这种在旧版 CPython 下可能触发警告（尤其用 array.array 时），建议统一用 bytearray。

为什么不用 set？什么时候该上 BitMap？

当你要判断「1 亿以内整数是否存在」，用 set 占约 800MB 内存；同样范围的 BitMap 只要 ~12.5MB。但代价是：只支持非负整数、不支持动态扩容、无法遍历元素（除非全扫描）。

典型适用场景：

• 去重后统计某批日志里的用户 ID（ID 范围已知且集中）
• 布隆过滤器底层存储（配合哈希函数）
• 内存受限服务里做快速存在性校验（如限流白名单）

常见误用：拿 BitMap 存负数或超大稀疏 ID（比如只有 1 和 999999999），这时反而浪费空间、降低 cache 局部性。

Python 实现要注意的三个细节

一是初始化大小别写死。比如要覆盖 [0, N)，需申请 (N + 7) // 8 字节，不是 N // 8；二是 bytearray 默认填 0，省去清零步骤；三是多线程下没加锁，set_bit 不是原子操作——两个线程同时设同一个 bit，可能丢一次写入。

简单可靠写法：

size_bytes = (max_n + 7) // 8
bitmap = bytearray(size_bytes)
def set_bit(n):
if n < 0 or n >= max_n:
return
bitmap[n >> 3] |= (1 << (n & 7))
def has_bit(n):
if n < 0 or n >= max_n:
return False
return bool(bitmap[n >> 3] & (1 << (n & 7)))

边界检查不能省，Python 不会帮你拦住 n = -1 或 n = len(bitmap)*8 这种越界访问——它会静默 wrap around，结果完全不对。

到这里，我们也就讲完了《Python位图实现：高效处理海量整数存在性判断》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！