Java数据结构之BitSet

BitSet是一个基于二进制位并按需增长的向量；每一个二进制位表示一个布尔值，默认为false；每一个二进制位都可以独立的修改；BitSet支持逻辑与，逻辑或及逻辑异或操作。

BitSet是通过“字数组”来实现的，目前一个“字”由8个字节组成，共64位，即2^6；目前“字”是通过long型整数来表示的。

对于给点的二进制位下标，BitSet是如何设置它的布尔值的呢？下面用一个例子来简单说明。假设我们的下标范围在【0-1023】这个区间，由上面的说明我们可以得知我们至少需要｛1024/2^6｝= 16“字”（这里通过移位运算来实现除法，即1024>>6）。换句话说就是我们BitSet是由words = new long[16] 这样的数组组成。对于任意合法下标值比如1000，先通过｛1000>>6｝=15得知我们需要修改的位所影响的值在words[15]这个“字”上。然后通过或运算｛words[15] |= (1L<<1000)｝将下标1000所在位的值更新为1并将或运算的值保存在words[15]这个“字”上。当我们取出下标1000所在位的值时，只需要通过与运算｛words[15] & (1L<<1000)｝取其值即可。因应先前我们设置过下标1000的值，所以我们取下标1000的值与运算时，它是1。如果我们没有设置相应下标的值，那么与运算的结果就是0了。需要说明的是在Java中BitSet的实际实现会更繁杂一点，如果有兴趣，可以参考原代码做更多的分析和理解。

那现在讨论一下BitSet可以用来解决什么问题呢？常见的用法是通过它来实现一定范围无序整数的排序算法。下面是一个具体例子。

import java.util.BitSet;

public class BitSetAlgorithm {
	public static void main(String[] args) {
		// unordered int array
		int arrays[] = new int[]{100,58,78,44,22,33,73,81,43,64};
		// the bit set size should great than the max value 100, and should be multiples of 64.
		BitSet set = new BitSet(128);
		for (int index : arrays) {
			// bit set will update the index's value to true
			set.set(index);
		}
		// Iterate the bit set size 
		for (int i = 0 ; i < set.size() ; i++) {
			if ( set.get(i)) {
				System.out.println(i + ",");
			}
		}
	}
}

 

看文章送话费