Python位图数据结构详解（从零开始实现高效集合操作）

如上图所示，如果第3位是1，说明数字3存在于集合中。

为什么使用位图？

• 内存占用极小：每个元素只需1位存储空间
• 查找、插入、删除操作时间复杂度为 O(1)
• 非常适合处理大规模整数集合（如用户ID、IP地址等）

Python位图数据结构实现步骤

由于 Python 没有内置的位图类型，我们可以利用整数的位运算特性来模拟。每个整数在 Python 中可以看作一个“位桶”，我们通过多个整数组合成一个大的位数组。

1. 确定位图容量

假设我们要支持最大值为 max_num 的整数，那么我们需要的位数就是 max_num + 1（因为包含0）。

2. 计算所需整数个数

Python 中一个整数通常可以存储 32 位或 64 位（取决于系统），但为了可移植性，我们按 32 位处理。因此需要的整数个数为：

num_ints = (max_num + 1 + 31) // 32

3. 实现核心方法

我们需要实现以下方法：

• add(num)：添加一个数字
• remove(num)：移除一个数字
• contains(num)：检查数字是否存在

完整代码实现

下面是一个完整的 Python位图数据结构实现：

class Bitmap:    def __init__(self, max_num):        """        初始化位图        :param max_num: 支持的最大整数值        """        self.max_num = max_num        # 计算需要多少个32位整数        self.size = (max_num + 1 + 31) // 32        # 初始化位数组，全部为0        self.bitmap = [0] * self.size    def _get_index_and_offset(self, num):        """        根据数字计算它在哪个整数中，以及在该整数中的偏移位        :param num: 要操作的数字        :return: (整数索引, 位偏移)        """        if num < 0 or num > self.max_num:            raise ValueError(f"Number {num} out of range [0, {self.max_num}]")        index = num // 32        offset = num % 32        return index, offset    def add(self, num):        """添加数字到集合中"""        index, offset = self._get_index_and_offset(num)        # 使用按位或运算设置对应位为1        self.bitmap[index] |= (1 << offset)    def remove(self, num):        """从集合中移除数字"""        index, offset = self._get_index_and_offset(num)        # 使用按位与和按位非清除对应位        self.bitmap[index] &= ~(1 << offset)    def contains(self, num):        """检查数字是否在集合中"""        index, offset = self._get_index_and_offset(num)        # 检查对应位是否为1        return bool(self.bitmap[index] & (1 << offset))    def __str__(self):        """方便调试，打印当前位图状态"""        result = []        for i in range(self.max_num + 1):            if self.contains(i):                result.append(str(i))        return "Bitmap contains: " + ", ".join(result)

使用示例

让我们测试一下这个位图：

# 创建一个支持0~63的位图bm = Bitmap(63)# 添加一些数字bm.add(5)bm.add(10)bm.add(32)# 检查是否存在print(bm.contains(5))   # Trueprint(bm.contains(7))   # False# 移除一个数字bm.remove(10)print(bm.contains(10))  # False# 打印当前内容print(bm)  # Bitmap contains: 5, 32

应用场景

这种高效集合操作方式非常适合以下场景：

• 用户在线状态管理（用户ID作为位索引）
• 布隆过滤器的底层实现
• 海量数据去重（配合哈希函数）
• 权限系统（每个权限对应一位）

总结

通过本教程，你已经掌握了如何用Python位运算实现一个高效的位图数据结构。它不仅节省内存，而且操作速度极快。希望这篇位图实现教程能帮助你在实际项目中解决性能问题！

关键词回顾：Python位图数据结构、位图实现教程、Python位运算、高效集合操作。