Bitset是Java中的一种数据结构。Bitset中主要存储的是二进制位,做的也是位运算,每一位只用来存储0,1值,主要用于对数据的标记。
BitSet是位操作的对象,值只有0或1(即true 和 false),内部维护一个long数组,初始化只有一个long segement,所以BitSet最小的size是64;随着存储的元素越来越多,BitSet内部会自动扩充,一次扩充64位,最终内部是由N个long segement 来存储。
Bitset的基本原理是,用1位来表示一个数据是否出现过,0为没有出现过,1表示出现过。默认情况下,BitSet所有位都是0即false。
JDK选择long数组作为BitSet的内部存储结构是出于性能的考虑,在and和or的时候减少循环次数,提高性能。
应用场景:海量数据去重、排序、压缩存储
优点:按位存储,内存占用空间小
缺点:线程不安全
基本操作:
BitSet bitSet1 = new BitSet(); BitSet bitSet2 = new BitSet(); for(int i=0; i<15; i++){ if(i%3 != 0 && i%5 != 0) bitSet1.set(i); if(i%2 == 0) bitSet2.set(i); } bitSet1.and(bitSet2); //交集 bitSet1.or(bitSet2); //并集 bitSet1.andNot(bitSet2); //返回左BitSet中,不在右BitSet的数据 bitSet1.xor(bitSet2); //返回左右BitSet中,不在左右BitSet的数据 bitSet1.intersects(bitSet2); //两边都有位值为true的数据,则返回true bitSet1.set(100); //标识索引为100的位有数据 System.out.println(bitSet1.get(100)); //获取索引为100的位是否有数据 System.out.println(bitSet1.size()); //集合大小,64的倍数 System.out.println(bitSet1.length()); //数据集的长度 System.out.println(bitSet1.cardinality()); //位值为true的个数 bitSet1.set(100); //返回指定index及其后的第一个位值为true的index,找不到返回-1 System.out.println(bitSet1.nextSetBit(0)); System.out.println(bitSet1.nextSetBit(14)); System.out.println(bitSet1.nextSetBit(15)); //返回指定index及其前的第一个位值为true的index,找不到返回-1 System.out.println(bitSet1.previousSetBit(200)); System.out.println(bitSet1.previousSetBit(14)); System.out.println(bitSet1.previousSetBit(0));
去重排序:
ThreadLocalRandom rnd = ThreadLocalRandom.current(); //数据初始化 int arrayLength = 10; int[] array = new int[arrayLength]; for(int i=0; i<arrayLength; i++){ array[i] = rnd.nextInt(arrayLength * 10); } System.out.println(Arrays.toString(array)); //将数据放入BitSet中,会去重 BitSet bitSet = new BitSet(); for(int i=0; i<array.length; i++){ bitSet.set(array[i]); } //递增排序显示 int i = 0; for(i=bitSet.nextSetBit(0); i>=0; i=bitSet.nextSetBit(i+1)){ System.out.print(i + ", "); } System.out.println(); //递减排序显示 for(i=bitSet.previousSetBit(bitSet.length()); i>=0; i=bitSet.previousSetBit(i-1)){ System.out.print(i + ", "); } System.out.println();
相关推荐
RoaringBitmap, 在Java中,一个更好的压缩 bitset RoaringBitmap Bitsets,也称为位图,通常用作快速数据结构。 不幸的是,他们可以使用太多的内存。 为了补偿,我们经常使用压缩位图。咆哮位图是压缩位图,它比传统...
自己实现的bitset数据结构,在vs2005下编译通过。有测试成素。
bitset - Go包实现 bitsets
Java工具包提供了强大的数据结构。在Java中的数据结构主要包括以下几种接口和类: 枚举(Enumeration) 位集合(BitSet) 向量(Vector) 栈(Stack) 字典(Dictionary) 哈希表(Hashtable) 属性(Properties) ...
java bitset 高级数据结构 源码解析 适合 0-3 年开发人员,进阶、面试必备知识!
Java 原生包 BitSet 源码,0~3年 Java 工程师必看,属于高级数据结构,利于进阶,面试必备!
开源项目-xojoc-bitset.zip,位集数据结构
本例程提供了C++的STL常用数据结构及其算法的使用范例,比如vector、string、list、forward_list、deque、queue、stack、map、set、multimap、multiset、tuple、bitset的使用范例,以及algorithm常….zip
Java 数据结构 Java工具包提供了强大的数据结构。在Java中的数据结构主要包括以下几种接口和类: 枚举(Enumeration) 位集合(BitSet) 向量(Vector) 栈(Stack) 字典(Dictionary) 哈希表(Hashtable) 属性...
数据结构与算法 设计模式 软件设计 等文档 ,可以访问我们的官网查看更多内容 [人在地上跑 牛在天上飞](#人在地上跑 牛在天上飞) Java Java-Coding Java-IO Java-IO-练习 [Read or List All Files in a Folder](Java...
当存储的值是相当小的整数时,BitSet(也称为Bitmap或位向量)是实现一组的理想数据结构。 它可能比通用集实现快几个数量级。 特别是,BitSet具有对设置操作(联合,差,交)的快速支持。 FastBitSet.js实现为速度...
数据结构 队列 非阻塞队列:ConcurrentLinkedQueue(无界线程安全),采用CAS机制(compareAndSwapObject原子操作)。 阻塞队列:ArrayBlockingQueue(有界)、LinkedBlockingQueue(无界)、DelayQueue、...
混合DSItr 该存储库包含基于混合数据结构的基于垂直格式的挖掘算法。 提交了四个版本。... HybridDSItr_Plain 使用纯 Bitset 数据结构而不是混合数据结构。 添加了不同的算法来比较不同特征的性能。
枚举(Enumeration) 位集合(BitSet)向量(Vactor)栈(Stack)字典(Dictionary) 哈希(Hashtable)属性(Properties)
STL本例程提供了C++的STL常用数据结构及其算法的使用范例,为面试笔试编程题提供便利
Ardb是一个新的构建在持久化Key/Value存储实现上的NoSQL DB服务实现,支持list/set/sorted set/bitset/hash/table等复杂的数据结构,以Redis协议对外提供访问接口。 Ardb的基本特性如下: 完全兼容Redis...
它包含一组用Kotlin Common编写的优化数据结构,因此可以在JVM,JS和将来的多平台目标中使用。 这些结构被设计为高效分配且快速的,因此Kds包括针对诸如Int或Double基元的专用版本。支持KDS 如果您喜欢kds,或在...
数据结构 队列 集合 链表、数组 字典、关联数组 栈 树 二叉树 完全二叉树 平衡二叉树 二叉查找树(BST) 红黑树 B,B+,B*树 LSM 树 BitSet 常用算法 计数排序 桶排序 基数排序 二分查找 Java 中的排序工具 布隆过滤...
重新启动std::bitset特许经营权 xstd::bit_set是对std::bitset的现代...设计选择一个bitset数据结构 “A bitset可以被看作是任一比特的阵列或一组整数。[...] 常见用法表明很少需要动态长度位bitsets 。” Chuck All
[数据结构](https://github.com/xingshaocheng/architect-awesome/blob/master/README.md#数据结构) * [队列](https://github.com/xingshaocheng/architect-awesome/blob/master/README.md#队列) * [集合](https: