BitSet在阿里面试和RocketMQ中的应用

小半 • 2024年3月2日下午11:32 • 微信精选 • 阅读 202

什么是BitSet

简单理解就是位图，类似BitMap。用来存储二进制位的类

BitSet特性

位存储：BitSet 以位为单位存储数据，每个位只能是 0 或 1。
空间效率：BitSet 比使用 boolean 数组存储二进制数据更节省空间。
快速操作：BitSet 提供快速位操作方法，例如设置、清除、翻转和测试位。

使用场景

布隆过滤器: 布隆过滤器是一种用于判断元素是否存在集合中的概率数据结构。
位图索引: 位图索引可以用于快速查找和过滤数据。
稀疏矩阵: 稀疏矩阵是指大多数元素为 0 的矩阵，可以使用 BitSet 来有效地存储稀疏矩阵。
内存优化: 在需要节省内存的情况下，可以使用 BitSet 来存储二进制数据。

面试题

阿里面试题有这么一题:

有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来

这种就是类似使用布隆过滤器。我们最简单就可以使用BitSet

代码实现

        int range = 10000000;
        Random random = new Random();
        List<Integer> list = new ArrayList<>(range);
        for (int i = 0; i < range; i++) {
            list.add(random.nextInt(range));
        }

        BitSet bitSet = new BitSet(range);
        for (Integer i : list) {
            bitSet.set(i);
        }
        for (int i = 0; i < 100000000; i++) {
            if (!bitSet.get(i)) {
                System.out.println(i);
            }
        }

RocketMQ中BitSet应用

在pop消费中为了解决批量ack的问题引入了BitSet

issues:https://github.com/apache/rocketmq/issues/6841
pr:https://github.com/apache/rocketmq/pull/6842

通过org.apache.rocketmq.client.impl.MQClientAPIImpl#batchAckMessageAsync(java.lang.String, long, org.apache.rocketmq.client.consumer.AckCallback, java.lang.String, java.lang.String, java.util.List<java.lang.String>)方法批量设置消费位点在BitSet中

然后在broker org.apache.rocketmq.broker.processor.AckMessageProcessor#appendAck中进行批量ack

这里简单解释下nextSetBit这个api。

BitSet.nextSetBit() 方法用于查找 BitSet 中从指定索引开始的第一个设置为 1 的位。如果找不到这样的位，则返回 -1

demo说明

BitSet bitSet = new BitSet();
bitSet.set(2);
bitSet.set(5);
bitSet.set(9);

int index = bitSet.nextSetBit(0); // index = 2
index = bitSet.nextSetBit(3); // index = 5
index = bitSet.nextSetBit(6); // index = 9
index = bitSet.nextSetBit(10); // index = -1