浅谈Java BitSet使用场景和代码示例

浅谈Java BitSet使用场景和代码示例

一、什么是BitSet？

注：以下内容来自JDK API:

BitSet类实现了一个按需增长的位向量。位Set的每一个组件都有一个boolean值。用非负的整数将BitSet的位编入索引。可以对每个编入索引的位进行测试、设置或者清除。通过逻辑与、逻辑或和逻辑异或操作，可以使用一个 BitSet修改另一个 BitSet的内容。

默认情况下，set 中所有位的初始值都是false。

每个位 set 都有一个当前大小，也就是该位 set 当前所用空间的位数。注意，这个大小与位 set 的实现有关，所以它可能随实现的不同而更改。位 set 的长度与位 set 的逻辑长度有关，并且是与实现无关而定义的。

一个Bitset类创建一种特殊类型的数组来保存位值。BitSet中数组大小会随需要增加。这和位向量（vectorofbits）比较类似。

这是一个传统的类，但它在java2中被完全重新设计。

BitSet定义了两个构造方法。

第一个构造方法创建一个默认的对象：

BitSet()

第二个方法允许用户指定初始大小。所有位初始化为0。

BitSet(intsize)

二、Java BitSet实现原理

在java中，BitSet的实现位于java.util包中：

public class BitSet implements Cloneable, java.io.Serializable

{

private final static int ADDRESS_BITS_PER_WORD = 6;

private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;

private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;

/* Used to shift left or right for a partial word mask */

private static final long WORD_MASK = 0xffffffffffffffffL;

private static final ObjectStreamField[] serialPersistentFields =

{

new ObjectStreamField("bits", long[].class),

}

;

/**

* The internal field corresponding to the serialField "bits".

*/

private long[] words;

.....

}

可以看到，BitSet的底层实现是使用long数组作为内部存储结构的，所以BitSet的大小为lohttp://ng类型大小(64位)的整数倍。

它有两个构造函数：

1、BitSet()：创建一个新的位 set，默认大小是64位。

publbzxsbdrEic BitSet()

{

initWords(BITS_PER_WORD);

sizeIsSticky = false;

}

2、BitSet(int nbits)：创建一个位set，它的初始大小足以显式表示索引范围在 0 到 nbits-1 的位。

public BitSet(int nbits)

{

// nbits can't be negative; size 0 is OK

if (nbits < 0)

throw new NegativeArraySizeException("nbits < 0: " + nbits);

initWords(nbits);

sizeIsSticky = true;

}

注：

1、如果指定了bitset的初始化大小，那么会把他规整到一个大于或者等于这个数字的64的整倍数。比如64位，bitset的大小是1个long，而65位时，bitset大小是2个long，即128位。做这么一个规定，主要是为了内存对齐，同时避免考虑到不要处理特殊情况，简化程序。

2：BitSet的size方法：返回此 BitSet 表示位值时实际使用空间的位数，值是64的整数倍

length方法：返回此 BitSet 的“逻辑大小”：BitSet 中最高设置位的索引加 1

三、使用场景

常见的应用场景是对海量数据进行一些统计工作，比如日志分析、用户数统计等。

之前在阿里的实习面试就被问到一道题：有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来？

代码示例如下：

public class Alibaba

{

public static void main(String[] args)

{

Random rahttp://ndom=new Random();

List list=new ArrayList<>();

for (int i=0;i<10000000;i++)

{

int randomResult=random.nextint(100000000);

list.add(randomResult);

}

System.out.println("产生的随机数有");

for (int i=0;i

{

System.out.println(list.get(i));

}

BitSet bitSet=new BitSet(100000000);

for (int i=0;i<10000000;i++)

{

bitSet.set(list.get(i));

}

System.out.println("0~1亿不在上述随机数中有"+bitSet.size());

for (int i = 0; i < 100000000; i++)

{

if(!bitSet.get(i))

{

System.out.println(i);

}

}

}

}

总结

以上就是本文关于浅谈Java BitSet使用场景和代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

{

System.out.println(list.get(i));

}

BitSet bitSet=new BitSet(100000000);

for (int i=0;i<10000000;i++)

{

bitSet.set(list.get(i));

}

System.out.println("0~1亿不在上述随机数中有"+bitSet.size());

for (int i = 0; i < 100000000; i++)

{

if(!bitSet.get(i))

{

System.out.println(i);

}

}

}

}

总结

以上就是本文关于浅谈Java BitSet使用场景和代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。