Pursue Wind

在100MB内存下存储一亿个整数（范围1到2亿），并快速判断某个整数是否存在，可通过以下方案实现：

核心思路：位图（Bitmap）

设计原理
位图通过每个二进制位（bit）表示一个整数是否存在。对于范围在1到2亿的整数，只需用2亿个二进制位（约23.84MB）即可覆盖所有可能值，1表示存在，0表示不存在。
内存计算

整数范围：1~200,000,000 → 共2亿个可能值。
位图大小：200,000,000 bits = 25,000,000 bytes ≈ 23.84MB。
剩余内存：100MB - 23.84MB = 76.16MB（足够支持其他操作）。

实现步骤

初始化位图：
创建一个长度为200,000,000的二进制数组，初始所有位为0。
填充数据：
遍历一亿个整数，将对应位置1。例如，数值n对应的位索引为n-1（因范围从1开始）。
查询存在性：
输入数值m，检查位图第m-1位是否为1。

示例代码（Python伪代码）

python

class Bitmap:
    def __init__(self, max_num):
        self.size = max_num
        self.bits = bytearray((max_num // 8) + 1)
    
    def set(self, num):
        index = (num - 1) // 8  # 确定字节位置
        offset = (num - 1) % 8  # 确定字节内的位偏移
        self.bits[index] |= 1 << offset
    
    def exists(self, num):
        index = (num - 1) // 8
        offset = (num - 1) % 8
        return (self.bits[index] & (1 << offset)) != 0

# 初始化位图（覆盖1~2亿）
bitmap = Bitmap(200_000_000)
# 填充数据（假设data为一亿个整数列表）
for num in data:
    bitmap.set(num)
# 查询是否存在
print(bitmap.exists(123456))  # 输出True或False

优化与扩展

内存压缩
若整数范围不连续或稀疏，可结合分段位图或Roaring Bitmap进一步压缩空间。
并行处理
在多核CPU环境下，可将位图分段处理，利用多线程加速数据加载与查询。
持久化存储
将位图序列化到磁盘，重启时快速加载，避免重复计算。

对比其他方案

方案	空间占用	查询速度	误判率	实现复杂度
位图（Bitmap）	23.84MB	O(1)	0%	低
哈希表	≥400MB	O(1)	0%	中
布隆过滤器	约11.4MB*	O(k)	>0%	中

*布隆过滤器按1%误判率计算，需约11.4MB，但存在假阳性问题，不适用强一致性场景。

总结

位图是此场景的最优解，其优势包括：

极低的空间占用（23.84MB << 100MB）。
O(1)时间复杂度的精准查询（无哈希冲突）。
实现简单，无需复杂数据结构或概率模型。
适用于海量整数存在性判断场景（如URL去重、用户ID过滤）。

核心思路：位图（Bitmap） ​

优化与扩展 ​

对比其他方案 ​

总结 ​

核心思路：位图（Bitmap）

优化与扩展

对比其他方案

总结