RoaringBitmap在SpringBoot中的使用以及与BitSet对比

最近在程序化中使用到了位图但是我们的系统使用的是java util下的BitSet我们是把素材还有人员id等先存储到一个Map中然后BitSet中存储对应的下标先获取到对应的下标然后利用BitSet去求交集和并集所以就自己研究了下更高性能的一个位图RoaringBitmap。RoaringBitmap是一个高性能的压缩位图库是 Java 中BitSet的升级版。直接上代码首先需要引入对应的maven库dependency groupIdorg.roaringbitmap/groupId artifactIdRoaringBitmap/artifactId version1.2.3/version /dependencyimport org.roaringbitmap.RoaringBitmap; public class RoaringDemo { public static void main(String[] args) { // 创建空位图 RoaringBitmap rb new RoaringBitmap(); // 添加单个元素0 value 2^32 rb.add(1); rb.add(100); rb.add(100000); // 批量添加 rb.add(1L, 1000L); // 添加 [1, 1000) 区间 rb.add(0, 1, 2, 3, 4); // 变参添加 // 检查存在性 boolean contains rb.contains(100); // true // 删除元素 rb.remove(100); rb.remove(1L, 100L); // 删除区间 // 获取统计信息 System.out.println(rb.getCardinality()); // 元素个数 System.out.println(rb.getSizeInBytes()); // 实际占用字节数 } }布尔集合运算交集/并集RoaringBitmap userA new RoaringBitmap(); userA.add(1, 2, 3, 4, 5); RoaringBitmap userB new RoaringBitmap(); userB.add(4, 5, 6, 7, 8); // 并集 (OR) - A 或 B 喜欢的 RoaringBitmap union RoaringBitmap.or(userA, userB); // 结果: {1,2,3,4,5,6,7,8} // 交集 (AND) - A 和 B 都喜欢的 RoaringBitmap intersection RoaringBitmap.and(userA, userB); // 结果: {4,5} // 差集 (ANDNOT) - A 喜欢但 B 不喜欢的 RoaringBitmap diff RoaringBitmap.andNot(userA, userB); // 结果: {1,2,3} // 异或 (XOR) - 只被一个人喜欢的 RoaringBitmap xor RoaringBitmap.xor(userA, userB); // 结果: {1,2,3,6,7,8} // 原地修改版本更省内存 userA.or(userB); // userA 变为并集 userA.and(userB); // userA 变为交集范围查询与切片RoaringBitmap rb new RoaringBitmap(); rb.add(0L, 1000000L); // 100 万个连续数字 // 获取范围切片不拷贝数据视图操作 RoaringBitmap subset rb.selectRange(100, 200); // [100, 200) // 限制最大返回数量 RoaringBitmap limited rb.limit(100); // 前 100 个元素 // 排名查询 int rank rb.rank(500); // 小于 500 的元素个数 // 选择第 N 个元素 int value rb.select(99); // 第 100 小的元素0-based序列化与反序列化// 序列化到文件紧凑格式 try (DataOutputStream dos new DataOutputStream(new FileOutputStream(bitmap.bin))) { rb.serialize(dos); } // 反序列化 try (DataInputStream dis new DataInputStream(new FileInputStream(bitmap.bin))) { RoaringBitmap rb2 new RoaringBitmap(); rb2.deserialize(dis); } // 获取字节数组网络传输 byte[] bytes new byte[rb.serializedSizeInBytes()]; rb.serialize(ByteBuffer.wrap(bytes));并行批量操作// 并行 OR多核加速 RoaringBitmap[] bitmaps {rb1, rb2, rb3, rb4, rb5}; RoaringBitmap result RoaringBitmap.parOr(bitmaps); // 并行 AND RoaringBitmap result2 RoaringBitmap.parAnd(bitmaps); // 并行聚合统计 long[] cardinalities RoaringBitmap.orCardinality(bitmaps);用户画像标签系统中的使用public class UserTagSystem { // 标签 - 用户集合将拥有该标签的用户统一放在一个RoaringBitmap中 private MapString, RoaringBitmap tagIndex new HashMap(); // 给用户打标签 public void tagUser(String tag, int userId) { tagIndex.computeIfAbsent(tag, k - new RoaringBitmap()).add(userId); } // 查找同时具有多个标签的用户交集 public RoaringBitmap findUsersWithAllTags(String... tags) { if (tags.length 0) return new RoaringBitmap(); RoaringBitmap result tagIndex.getOrDefault(tags[0], new RoaringBitmap()).clone(); for (int i 1; i tags.length; i) { result.and(tagIndex.getOrDefault(tags[i], new RoaringBitmap())); } return result; } // 查找具有任意一个标签的用户并集 public RoaringBitmap findUsersWithAnyTag(String... tags) { RoaringBitmap[] bitmaps Arrays.stream(tags) .map(t - tagIndex.getOrDefault(t, new RoaringBitmap())) .toArray(RoaringBitmap[]::new); return RoaringBitmap.or(bitmaps); } // 获取用户数量 public int getUserCount(String tag) { return tagIndex.getOrDefault(tag, new RoaringBitmap()).getCardinality(); } }RoaringBitmap是处理海量整数集合的高性能压缩位图相比BitSet节省 10-100 倍内存集合运算快数倍是大数据场景的标配工具。与BitSet对比基础操作对比// BitSet BitSet bs new BitSet(); bs.set(100); bs.set(1000000); System.out.println(bs.get(100)); // true System.out.println(bs.cardinality()); // 2 // 遍历低效遍历所有位 for (int i bs.nextSetBit(0); i 0; i bs.nextSetBit(i 1)) { System.out.println(i); } // 集合运算手动实现极慢 BitSet andResult (BitSet) bs1.clone(); andResult.and(bs2); // RoaringBitmap RoaringBitmap rb new RoaringBitmap(); rb.add(100); rb.add(1000000); System.out.println(rb.contains(100)); // true System.out.println(rb.getCardinality()); // 2 // 遍历高效只遍历存在的 for (int value : rb) { System.out.println(value); } // 集合运算原生优化极快 RoaringBitmap andResult RoaringBitmap.and(rb1, rb2); RoaringBitmap orResult RoaringBitmap.or(rb1, rb2);两个特性对比特性BitSetRoaringBitmap定位Java 标准库基础位图高性能压缩位图库设计目标通用、简单海量数据、高性能数据特点适合密集数据适合稀疏数据内存策略固定分配不压缩自适应压缩动态调整存储机制对比数据[5, 6, 7, 1000000]BitSet 内部┌────────────────────────────────────────┐│ long[15625] 数组 ││ 每个 long 64 bit ││ 要存 1000000必须分配 1000001 bit ││ ││ [5]1 [6]1 [7]1 ... [1000000]1 ││ ↓ ↓ ↓ ↓ ││ 大量空间浪费中间都是0 │└────────────────────────────────────────┘内存1000001 bit ≈ 122 KB无论实际有几个1数据[5, 6, 7, 1000000]RoaringBitmap 内部┌─────────────────────────────────────────┐│ 按高 16 位分区Chunk每个 Chunk 65536 │├─────────────────────────────────────────┤│ Chunk 0 (0-65535): ││ ├─ Container 类型: ArrayContainer ││ └─ 内容: [5, 6, 7]有序数组3×2字节 │├─────────────────────────────────────────┤│ Chunk 15 (983040-1048575): ││ ├─ Container 类型: ArrayContainer ││ └─ 内容: [1000000-98304015936] │└─────────────────────────────────────────┘内存约 20 字节稀疏时极省关键差异对比对比项BitSetRoaringBitmap稀疏数据内存❌ 差必须分配最高位✅极优只存实际数据密集数据内存✅ 紧凑✅ 同样紧凑添加元素速度✅ O(1) 极快⚡ O(1) 快略慢于 BitSet遍历速度✅ 快⚡更快缓存友好集合运算❌ 需遍历全部位✅原生优化快数倍范围查询❌ 需遍历✅原生支持序列化大小❌ 大全量✅小压缩格式64位支持❌ 不支持仅 int✅Roaring64Bitmap不可变版本❌ 无✅ImmutableRoaringBitmap线程安全❌ 需外部同步❌ 需外部同步