如何基于BigInt实现海量数据标记的高效位向量Bitset方案

作者：袖梨 2026-05-20

BigInt位向量巧妙利用分块存储和稀疏处理，突破JavaScript数值精度限制，实现百亿级整数的高效标记。

借助BigInt的特性构建位向量，能够突破53位安全整数的限制，实现超大规模数据的快速标记。这种方案尤其适合处理海量、稀疏且无重复的整数集合，比如判断某个ID是否存在于数十亿用户库中。

为什么 BigInt 比普通数组或 Uint32Array 更适合海量位标记

传统数组每个元素至少占用1字节空间，标记40亿数据需要消耗4GB内存。Uint32Array虽然更紧凑，但其长度和索引仍受Number类型限制。BigInt位向量则支持任意精度的整数索引，通过只存储有效数据块的方式，在稀疏场景下可大幅节省内存。

关键设计：分块 + BigInt 位操作

采用分块策略管理位向量，每块使用一个BigInt表示64位数据：

通过const blockIdx = x / 64n计算目标数据所在块号
使用const bitPos = x % 64n确定块内偏移位置
通过位运算实现置位、检测和复位操作
利用Map结构仅存储非空块，避免内存浪费

基础操作实现示例（TypeScript 风格）

以下是核心功能代码实现：

class BigIntBitset {
  private blocks = new Map();
  set(x: bigint): void {
    const blockIdx = x / 64n;
    const bitPos = x % 64n;
    const mask = 1n << bitPos;
    const current = this.blocks.get(blockIdx) ?? 0n;
    this.blocks.set(blockIdx, current | mask);
  }
  test(x: bigint): boolean {
    const blockIdx = x / 64n;
    const bitPos = x % 64n;
    const current = this.blocks.get(blockIdx);
    if (current === undefined) return false;
    return (current & (1n << bitPos)) !== 0n;
  }
  reset(x: bigint): void {
    const blockIdx = x / 64n;
    const bitPos = x % 64n;
    const mask = ~(1n << bitPos);
    const current = this.blocks.get(blockIdx);
    if (current !== undefined) {
      this.blocks.set(blockIdx, current & mask);
      if (current & mask === 0n) this.blocks.delete(blockIdx);
    }
  }
}