欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-02-23 10:51:46
一、什么是bitset?   注:以下内容来自jdk api:   bitset类实现了一个按需增长的位向量。位set的每一个组件都有一个boolean值。用非负的整数...

一、什么是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的大小为long类型大小(64位)的整数倍。

  它有两个构造函数:

  1、bitset():创建一个新的位 set,默认大小是64位。

public 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 random=new random();
		list<integer> 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<list.size();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使用场景和代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!