如何利用 BigInt 构建高性能的位向量 (Bitset) 用于海量数据标记-js教程-PHP中文网

BigInt位向量通过分块（每块64位）+Map存储非空块，突破Number精度限制，支持百亿级稀疏整数标记，内存仅按需分配。

如何利用 bigint 构建高性能的位向量 (bitset) 用于海量数据标记

用 BigInt 实现位向量（Bitset），核心在于绕过 JavaScript 原生 Number 的 53 位安全整数限制，支持超大索引（比如百亿级整数标记），同时保持单比特操作的常数时间复杂度。它特别适合标记海量、稀疏、无重复的整数存在性，比如判断某 ID 是否在 40 亿用户集合中。

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

普通数组（如 boolean[]）每个元素至少占 1 字节，标记 40 亿个数需 4 GB 内存；Uint32Array 虽紧凑，但最大长度受限于 2^32−1（约 42.9 亿），且索引仍是 Number 类型，无法安全表示大于 2^53−1 的位偏移。而 BigInt 支持任意精度整数索引，配合位运算可构建逻辑上无限长的位向量，内存仅按需分配——实际只存“被置 1”的块，稀疏时极省空间。

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

不把整个位向量拉成一长串 BigInt（不可行），而是采用分块策略，每块用一个 BigInt 表示 64 位（或 32/128 位，64 是常见平衡点）：

给定整数 x，计算所在块号：const blockIdx = x / 64n（BigInt 除法）
计算块内偏移：const bitPos = x % 64n
用 1n 构造掩码，再用 <code>|、&、& ~ 完成 set / test / reset
用 Map<bigint bigint></bigint> 存储非空块（key=blockIdx，value=该块的位图值），避免为全零块分配内存

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

以下为精简可运行逻辑（不含边界校验）：

class BigIntBitset {
  private blocks = new Map<bigint bigint>();

  set(x: bigint): void {
    const blockIdx = x / 64n;
    const bitPos = x % 64n;
    const mask = 1n <h3>适用场景与注意事项</h3>
<ul>
<li>适用于标记范围极大（如 <code>0</code> 到 <code>10^12</code>）、但实际数据稀疏（仅百万/千万级活跃 ID）的场景</li>
  <li>不适用于频繁全量遍历——因为块是稀疏存储的，要遍历所有置 1 位需扫描全部非空块并检查每个 bit</li>
  <li>注意 V8 引擎对 BigInt 位运算的性能：现代 Chrome/Firefox 中 <code>、<code>&</code> 已高度优化，但远超 64 位的大整数运算仍慢于原生整数，所以坚持“每块 ≤ 64 位”很关键</code>
</li>
  <li>若需持久化，可序列化为 <code>{ "blocks": [[blockIdx1, value1], [blockIdx2, value2]] }</code>，用 <code>BigInt.toString(16)</code> 存十六进制字符串节省体积</li>
</ul></bigint>