跳至主要內容

BitSet位图：100亿数据去重只需1.2GB内存的秘密

老张2026/4/30大约 10 分钟

BitSet位图：100亿数据去重只需1.2GB内存的秘密

适读人群：有数据处理经验的后端开发者 | 阅读时长：约15分钟 | 文章类型：数据结构原理+工程实战

开篇故事

2021年底，我们做一个用户行为分析系统，需要对100亿条用户点击日志去重，统计UV（独立访客数）。数据是从Hadoop导出来的，直接在Java里处理。

最直接的方案：HashSet<Long>。100亿个userId，每个Long对象约24字节（对象头16字节+long值8字节），100亿个对象需要约240GB内存。加上HashSet的桶数组和负载因子，实际内存可能要300GB以上。我们整个集群才200GB RAM。

当时的运维组长老孙听到这个数字，直接说：不行，你想什么呢。

我说：用BitSet，内存可以压到1.2GB。

他：你没睡醒？100亿数据1.2GB？

我说：BitSet每个bit存一个标志位。如果userId是0到999亿之间的整数，100亿个不重复userId，最多需要100亿/8字节 = 1.25GB。

他拿笔算了一下，然后沉默了几秒：我去，这是真的。

今天把这个"魔法"说清楚，顺带把Java BitSet的源码过一遍，看看它是怎么用long数组实现高效位操作的。

一、BitSet的核心原理

1.1 位图的基本思想

传统存储：每个元素占多个字节（Long=8字节，HashSet.Long=24字节）

位图存储：用1个bit表示"某个数字是否存在"，1存在，0不存在

数字集合 {0, 2, 5, 7}  用byte存储：
Bit位置:  7 6 5 4 3 2 1 0
          ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
二进制:    1 0 1 0 0 1 0 1 = 0xA5

存储效率：4个数字只用1字节（vs HashSet的4*24=96字节）
节省比：96倍！

1.2 内存占用对比

方案100亿个整数内存
HashSet<Long>每个约24字节~240GB
long[]数组每个8字节~80GB
BitSet（值域0~1000亿）每个0.001字节~12GB
BitSet（值域0~100亿）每个0.001字节~1.2GB

二、Java BitSet源码深度解析

2.1 核心操作源码分析

package com.laozhang.bitmap;

/**
 * BitSet核心操作源码解析（基于JDK11）
 * 重点：理解long[]数组如何映射到bit位置
 *
 * 关键设计：
 * 1. 底层用long[]，每个long=64bit，能存64个标志位
 * 2. 对n操作时：wordIndex = n >> 6（找到第几个long），bitIndex = n & 63（该long的第几位）
 * 3. 所有位操作用位运算，速度极快
 */
public class BitSetSourceAnalysis {

    /**
     * JDK11 BitSet.set(int bitIndex) 源码
     * 时间复杂度：O(1)
     */
    /*
    public void set(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        int wordIndex = wordIndex(bitIndex); // = bitIndex >> ADDRESS_BITS_PER_WORD (即 bitIndex / 64)
        expandTo(wordIndex); // 如果wordIndex超出当前数组范围，扩容

        words[wordIndex] |= (1L << bitIndex); // 置对应bit为1
        // 1L << bitIndex：bitIndex的低6位决定偏移量（自动mod 64）
        // 比如bitIndex=70：70 & 63 = 6，等价于 1L << 6 = 0b1000000

        checkInvariants();
    }
    */

    /**
     * JDK11 BitSet.get(int bitIndex) 源码
     * 时间复杂度：O(1)
     */
    /*
    public boolean get(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        checkInvariants();

        int wordIndex = wordIndex(bitIndex);
        return (wordIndex < wordsInUse)
            && ((words[wordIndex] & (1L << bitIndex)) != 0);
        // (1L << bitIndex) 只看低6位，即 bitIndex % 64 那一位
    }
    */

    /**
     * JDK11 BitSet.cardinality() 源码
     * 统计所有bit中1的数量（即集合元素个数）
     * 使用Long.bitCount()（映射到POPCNT指令，极快）
     */
    /*
    public int cardinality() {
        int sum = 0;
        for (int i = 0; i < wordsInUse; i++)
            sum += Long.bitCount(words[i]); // POPCNT硬件指令，O(1)
        return sum;
    }
    */

    /**
     * 手动演示BitSet的位操作逻辑
     */
    public static void demonstrateBitOperations() {
        // 模拟set(0), set(2), set(5), set(7)
        long word = 0L;

        // set(0)：第0位置1
        word |= (1L << 0);  // word = 0b00000001 = 1
        // set(2)：第2位置1
        word |= (1L << 2);  // word = 0b00000101 = 5
        // set(5)：第5位置1
        word |= (1L << 5);  // word = 0b00100101 = 37
        // set(7)：第7位置1
        word |= (1L << 7);  // word = 0b10100101 = 165

        System.out.println("word值: " + word); // 165
        System.out.println("二进制: " + Long.toBinaryString(word)); // 10100101

        // get(2)：检查第2位
        System.out.println("get(2): " + ((word & (1L << 2)) != 0)); // true
        // get(3)：检查第3位
        System.out.println("get(3): " + ((word & (1L << 3)) != 0)); // false

        // cardinality：统计1的数量
        System.out.println("1的数量: " + Long.bitCount(word)); // 4

        // 多long的情况：bit=70在第几个long的第几位？
        int bit = 70;
        int wordIndex = bit >> 6;    // = 70 / 64 = 1（第1个long，下标从0开始）
        int bitInWord = bit & 63;    // = 70 % 64 = 6（该long的第6位）
        System.out.println("bit=70: wordIndex=" + wordIndex + ", bitInWord=" + bitInWord);
    }
}

2.2 完整的BitSet应用实现

package com.laozhang.bitmap;

import java.util.BitSet;
import java.util.Random;

/**
 * BitSet实战：大数据去重统计
 * 覆盖三个真实场景：UV统计、整数去重、布隆过滤器前置思想
 */
public class BitSetPracticalUsage {

    /**
     * 场景1：100亿用户ID去重统计UV
     *
     * 前提：userId是0到MAX_USER_ID之间的整数
     * 实际系统中userId通常是自增主键，满足这个条件
     */
    public static class UVCounter {
        // userId范围：0到10_000_000_000L
        // 对应BitSet大小：10亿/64 ≈ 1.56亿个long，约1.25GB
        // 注意：BitSet内部用int下标，最大支持Integer.MAX_VALUE个bit（约21亿）
        // 超大userId范围需要分片处理
        private static final int MAX_USER_ID_MILLIONS = 1000; // 10亿userId

        private final BitSet bitSet;

        public UVCounter() {
            // 分配10亿bit的BitSet，约125MB（注意：不是100亿，这是简化演示）
            this.bitSet = new BitSet(MAX_USER_ID_MILLIONS * 1_000_000);
        }

        /**
         * 记录一次用户访问
         * 时间复杂度：O(1)
         */
        public void visit(int userId) {
            bitSet.set(userId);
        }

        /**
         * 获取UV（独立访客数）
         * 时间复杂度：O(n/64)，n是总bit数
         * Long.bitCount是POPCNT指令，极快
         */
        public int getUV() {
            return bitSet.cardinality();
        }

        /**
         * 是否访问过
         */
        public boolean hasVisited(int userId) {
            return bitSet.get(userId);
        }

        /**
         * 两天UV的合并（并集）
         * 场景：统计两天内的独立访客数（不重复计数）
         */
        public static int mergeDailyUV(BitSet day1, BitSet day2) {
            BitSet merged = (BitSet) day1.clone();
            merged.or(day2); // 位或：两天中任一天访问过的用户
            return merged.cardinality();
        }

        /**
         * 两天都访问过的用户数（交集）
         */
        public static int retainedUsers(BitSet day1, BitSet day2) {
            BitSet retained = (BitSet) day1.clone();
            retained.and(day2); // 位与：两天都访问过的用户
            return retained.cardinality();
        }
    }

    /**
     * 场景2：整数数组去重
     * 数组里有重复整数，用BitSet O(n)去重，比HashSet更省内存
     */
    public static int[] deduplicate(int[] arr, int maxValue) {
        BitSet bs = new BitSet(maxValue + 1);
        for (int n : arr) bs.set(n);

        int[] result = new int[bs.cardinality()];
        int idx = 0;
        for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
            result[idx++] = i;
            // nextSetBit：找到下一个为1的bit位置，比逐个get效率高很多
        }
        return result;
    }

    /**
     * 性能和内存对比实验
     */
    public static void compareWithHashSet() {
        int dataSize = 10_000_000; // 1000万
        Random rnd = new Random(42);
        int[] data = new int[dataSize];
        for (int i = 0; i < dataSize; i++) data[i] = rnd.nextInt(100_000_000); // 0~1亿

        // BitSet方案
        long beforeBS = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        long startBS = System.currentTimeMillis();
        BitSet bitSet = new BitSet(100_000_000);
        for (int d : data) bitSet.set(d);
        int uvBS = bitSet.cardinality();
        long timeBS = System.currentTimeMillis() - startBS;
        long afterBS = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();

        System.out.printf("BitSet方案: UV=%d, 耗时=%dms, 内存增量约%dMB%n",
            uvBS, timeBS, (afterBS - beforeBS) / 1024 / 1024);
        // 据我测试：UV≈9999706, 耗时约45ms, 内存增量约12MB

        // HashSet方案
        long beforeHS = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        long startHS = System.currentTimeMillis();
        java.util.HashSet<Integer> hashSet = new java.util.HashSet<>(dataSize * 2);
        for (int d : data) hashSet.add(d);
        int uvHS = hashSet.size();
        long timeHS = System.currentTimeMillis() - startHS;
        long afterHS = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();

        System.out.printf("HashSet方案: UV=%d, 耗时=%dms, 内存增量约%dMB%n",
            uvHS, timeHS, (afterHS - beforeHS) / 1024 / 1024);
        // 据我测试：UV相同, 耗时约380ms, 内存增量约480MB
    }

    public static void main(String[] args) {
        demonstrateBitOperations();
        compareWithHashSet();

        // UV统计演示
        UVCounter counter = new UVCounter();
        Random rnd = new Random(42);
        for (int i = 0; i < 1_000_000; i++) {
            counter.visit(rnd.nextInt(500_000)); // 50万用户中随机访问
        }
        System.out.println("UV（独立访客）: " + counter.getUV()); // 约480000+（有重复）
    }

    // 引用内部方法
    static void demonstrateBitOperations() {
        BitSetSourceAnalysis.demonstrateBitOperations();
    }
}

四、踩坑实录

坑1：BitSet的userId范围必须是整数，且不能太稀疏

报错现象：线上系统userId用的是UUID格式（如user_a1b2c3d4），想用BitSet节省内存，结果不知道怎么映射。

根本原因：BitSet只支持整数下标（非负整数）。UUID或字符串型ID无法直接用BitSet，需要先建立UUID -> 整数的映射，相当于又引入了HashMap，失去了内存优势。

具体解法：

// BitSet适用条件：
// 1. ID是非负整数类型
// 2. ID的最大值不能太大（否则BitSet本身就占很多内存）
// 3. ID分布相对密集（比如0~1亿，命中率>1%）

// 如果ID是UUID：考虑布隆过滤器（下一篇会讲）
// 如果ID很稀疏（比如0~10^18但只有100万个）：考虑HashSet
// 判断标准：BitSet内存 = maxId/8字节，HashSet内存 = count*24字节
// 当 maxId/8 < count*24 时，即 count > maxId/192 时，BitSet更省

// 临界点：密度 > 0.52%时用BitSet更省
// 比如：maxId=1亿，count>52万时BitSet更合适

坑2：BitSet.size()和BitSet.length()容易搞混

报错现象：用BitSet.size()想知道有多少个bit被置为1，实际上拿到的是BitSet的总容量（long数组的bit数），不是已置位的数量。

根本原因：BitSet有三个容易混淆的方法：

  • size()：内部long[]的总bit数（是64的倍数，可能比实际需要的多）
  • length()：最高位置1的bit的下标+1（逻辑长度）
  • cardinality()：被置1的bit总数（这才是"集合大小"）

具体解法：

BitSet bs = new BitSet();
bs.set(10);
bs.set(100);
bs.set(1000);

System.out.println("size():       " + bs.size());        // 1024（分配的总bit数）
System.out.println("length():     " + bs.length());      // 1001（最高位1000+1）
System.out.println("cardinality(): " + bs.cardinality()); // 3（被置1的数量）

// 结论：
// 想知道"集合有多少元素" -> cardinality()
// 想知道"最大元素是什么" -> nextSetBit(0)反向遍历或length()-1
// size()几乎没有业务意义

坑3：超大ID范围导致BitSet本身占用过多内存

报错现象：userId的范围是0到100亿（10^10），直接new BitSet(10_000_000_000L)报OutOfMemoryError。而且Java的BitSet内部用int下标，最大只能存约21亿个bit（Integer.MAX_VALUE）。

根本原因：

  1. Java BitSet内部用int[]（JDK早期）或long[]作为索引，内部某些方法用int，实际有效范围约21亿bit。
  2. 100亿的userId范围需要约12.5GB内存，单机可能放不下。

具体解法：

// 解法1：对userId分桶，每桶处理10亿范围
// userId 0~9亿 -> BitSet1
// userId 10~19亿 -> BitSet2（offset=10亿）
// ...

public class SplitBitSetUVCounter {
    private static final long BUCKET_SIZE = 1_000_000_000L; // 10亿一桶
    private final java.util.Map<Long, BitSet> buckets = new java.util.HashMap<>();

    public void visit(long userId) {
        long bucketId = userId / BUCKET_SIZE;
        int offset = (int)(userId % BUCKET_SIZE);
        buckets.computeIfAbsent(bucketId, k -> new BitSet((int)BUCKET_SIZE)).set(offset);
    }

    public long getUV() {
        return buckets.values().stream().mapToLong(BitSet::cardinality).sum();
    }
}

// 解法2：对userId做哈希取模，映射到合理范围
// 注意：这会引入哈希碰撞，有一定误判率（类似布隆过滤器）
int mappedId = (int)(userId % 1_000_000_000L);
bitSet.set(mappedId);
// 这实际上变成了有误判率的概率型数据结构，不适合精确去重

五、总结与延伸

  1. BitSet的核心优势是内存效率：每个整数只用1个bit标记存在性，是HashSet的1/192。 适合场景：ID是整数、范围可控（不超过21亿）、密度>0.52%。100亿UV统计用BitSet是工程上的正确选择。

  2. BitSet的位运算（and/or/xor/andNot）批量操作极其高效。 合并两天的UV统计用or()操作，底层是对long数组逐个做位或，JIT会优化为SIMD向量指令。合并1亿bit只需约几毫秒。这是为什么Redis的HyperLogLog和BitMap指令集成广受欢迎的原因。

  3. 当ID不是整数或分布极度稀疏时，考虑布隆过滤器（Bloom Filter）而不是BitSet。 布隆过滤器用多个hash函数把任意类型的ID映射到bit数组，允许一定误判率，但内存效率同样极高——这是下一篇的主题。

编辑此页
最近更新:
贡献者: xiaozhangge