BitSet是Java中基于long数组实现的高效位向量类，每个bit表示一个布尔状态，内存占用仅为boolean[]的约1/8；适用于稀疏/密集布尔集合、布隆过滤器、图算法标记等场景，支持O(1)的set/get及批量位运算。
BitSet 是 Java 提供的专用于高效位操作的类，底层用 long 数组实现，每个 bit 可表示一个布尔状态（true/false），空间利用率远高于 boolean[] 或 Set<Boolean>。它适合处理大规模稀疏或密集的布尔集合、标志位管理、布隆过滤器底层、图算法中的顶点标记等场景。
初始化与基本操作
BitSet 默认构造时容量为 64 位，可指定初始大小（实际按 64 的倍数向上对齐）。常用方法包括 set()、get()、clear()、flip() 和 and/or/xor 等逻辑运算：
- set(int index)：将第 index 位设为 true（自动扩容）
- get(int index)：返回第 index 位的值（超出当前范围则返回 false）
- clear(int index) 或 clear()：清零单个位或全部位
- cardinality()：快速获取 true 位的个数（比遍历快得多）
内存与性能优势
BitSet 每个元素只占 1 bit，100 万个布尔值仅需约 125 KB；而 boolean[] 在 JVM 中通常每个元素占 1 字节（8 倍空间），LinkedHashSet 更是包含对象头、哈希表结构等开销。且 BitSet 的批量操作（如 and()）基于 long 数组的位运算，CPU 友好，吞吐量高。
- 插入/查询时间复杂度均为 O(1)，不随 size 增长而变慢
- and()、or()、xor() 等操作是按 long 批量进行的，比手动循环快一个数量级
- isEmpty()、length()、size() 都是常数时间，无需遍历
典型使用场景示例
比如标记 0~999999 中哪些整数已被占用，用 BitSet 比 HashSet<Integer> 节省 90%+ 内存，且支持快速交集计算：
立即学习“Java免费学习笔记（深入）”；
- 用户权限位：用固定索引表示“读”“写”“删除”，set(0) 表示有读权限
- 去重统计：遍历数据流，对数值做 set(value)，最后用 cardinality() 得唯一数个数
- 配合算法：Dijkstra 中标记已访问顶点；DFS/BFS 中记录 visited 集合
注意事项与替代方案
BitSet 不是线程安全的，多线程写入需外部同步；它不支持泛型，也不兼容 Collection 接口（但可转为 Stream 或数组）。若需并发安全，可用 ConcurrentHashMap<Integer, Boolean> 或封装 synchronized BitSet；若只是小范围（如 0~63），直接用 long 类型位运算更轻量。
- 下标从 0 开始，最大有效索引无硬限制（动态扩容）
- toString() 返回类似 "{0, 2, 5}" 的格式，仅用于调试，不建议解析
- 避免频繁调用 get(i) 遍历——应优先用 stream().forEach() 或自行按 long 块遍历提升效率
