先来看几道面试题：
有木有被上面的大大大数据吓到了无从下手啊？今天介绍的BitSet就可以解决这一问题。
简介
一个按需增长的位向量，C++和java都有提供实现。
BitSet是位操作的对象，值只有1和0。用1位来表示一个数据是否出现过，0为没有出现过，1表示出现过。使用用的时候既可根据某一个是否为0表示此数是否出现过。
比较
一般，int占4个字节，long占8个字节。而一个字节是由8个位组成的。
粗略估计，int和BitSet的比例为4*8:1，即32：1。如果是long，差距就更大了。
基本操作
1、重要属性
BitSet在java.util包下，初始大小为64位。
/** BitSets are packed into arrays of "words." Currently a word is* a long, which consists of 64 bits, requiring 6 address bits.* The choice of word size is determined purely by performance concerns.*/
private final static int ADDRESS_BITS_PER_WORD = 6;private long[] words;2、构造函数
//构造函数一public BitSet(int nbits) {// nbits can't be negative; size 0 is OKif (nbits < 0)throw new NegativeArraySizeException("nbits < 0: " + nbits);//new 一个long数组initWords(nbits);sizeIsSticky = true;}private void initWords(int nbits) {words = new long[wordIndex(nbits-1) + 1];}
//构造函数二private BitSet(long[] words) {this.words = words;this.wordsInUse = words.length;checkInvariants();}3、检查函数
BitSet类中提供了两个内部检查的函数。
/*** Sets the field wordsInUse to the logical size in words of the bit set.* WARNING:This method assumes that the number of words actually in use is* less than or equal to the current value of wordsInUse!*/private void recalculateWordsInUse() {// Traverse the bitset until a used word is foundint i;for (i = wordsInUse-1; i >= 0; i--)if (words[i] != 0)break;wordsInUse = i+1; // The new logical size}/*** Every public method must preserve these invariants.*/private void checkInvariants() {//wordsInUse 实际使用的long的个数assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);assert(wordsInUse >= 0 && wordsInUse <= words.length);assert(wordsInUse == words.length || words[wordsInUse] == 0);}
4、扩容
跟其他可以自动扩容类相同，扩容发生在set元素时，如下：
public void set(int bitIndex) {if (bitIndex < 0)throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);int wordIndex = wordIndex(bitIndex);//扩容方法expandTo(wordIndex);words[wordIndex] |= (1L << bitIndex); // Restores invariants//检查checkInvariants();}private void expandTo(int wordIndex) {int wordsRequired = wordIndex+1;if (wordsInUse < wordsRequired) {ensureCapacity(wordsRequired);wordsInUse = wordsRequired;}}//核心扩容方法private void ensureCapacity(int wordsRequired) {if (words.length < wordsRequired) {// Allocate larger of doubled size or required sizeint request = Math.max(2 * words.length, wordsRequired);//拷贝words = Arrays.copyOf(words, request);sizeIsSticky = false;}}应用实例
为了方便演示，就把数字改小了。需求就是生成10个10以内的随机数，并求出20以内哪些数字没在生成的随机数中。
// 先把随机数放入list中Random random = new Random();List<Integer> list = new ArrayList<>();for (int i = 0; i < 10; i++) {int randomResult = random.nextInt(10);list.add(randomResult);}//查看生产的随机数System.out.println("产生的随机数有");for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));}System.out.println("the end");//将随机数放入bitset中BitSet bit = new BitSet();for (int i = 0; i < 10; i++) {bit.set(list.get(i));}//打印没有随机生产的数for (int i = 0; i < 20; i++) {if (!bit.get(i)) {System.out.println(i);}}本文链接：https://my.lmcjl.com/post/3753.html
展开阅读全文
4 评论