搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库

BitSet

巫师学堂 2018-05-13
举报

简介


BitSet 按位存储,每一位的值为0或1,用来表示某个整数是否出现过,整数的大小通过bit所在位置决定BitSet这种设计天生具有数据去重的特性,数据的存储也非常紧凑。例如,1G的空间,有 1024*1024*1024*8=8.59*10^9bit,也就是可以表示85亿个不同的数。

原理


BitSet 内部维护一个long数组,每个long共64bit,每1bit表示一个整数,共可以表示64个连续整数。随着存储的元素越来越多,long数组会自动扩容。假设long数组大小为n,则BitSet大小为64n,此时可存储64n个不同整数。

例如:247L用二进制表示为11110111,此时BitSet内long[0]=247L则表示同时存储了0,1,2,4,5,6,7共七个数字。

1 1 1 0 1 1 1 1
0 1 2
4 5 6 7

API


void and(BitSet set)
对此目标位 set 和参数位 set 执行逻辑与操作。
void andNot(BitSet set)
清除此 BitSet 中所有的位,其相应的位在指定的 BitSet 中已设置。
void clear( )
将此 BitSet 中的所有位设置为 false。
void clear(int index)
将索引指定处的位设置为 false。
void clear(int startIndex, int endIndex)
将指定范围内的位设置为 false。
void flip(int index)
将指定索引处的位反转。
void flip(int startIndex, int endIndex)
将指定范围内的每个位反转。
boolean get(int index)
返回指定索引处的位值。
BitSet get(int startIndex, int endIndex)
返回一个新的 BitSet,它由此 BitSet 中指定范围内的位组成。
boolean intersects(BitSet bitSet)
如果指定的 BitSet 中有设置为 true 的位,并且在此 BitSet 中也将其设置为 true,则返回 ture。
int length( )
返回此 BitSet 的"逻辑大小":BitSet 中最高设置位的索引加 1。
void or(BitSet bitSet)
对此位 set 和位 set 参数执行逻辑或操作。
void set(int index)
将指定索引处的位设置为 true。
void set(int index, boolean v)
 将指定索引处的位设置为指定的值
void set(int startIndex, int endIndex)
将指定范围内的位设置为 true。
void set(int startIndex, int endIndex, boolean v)
将指定范围内的位设置为指定的值。
int size( )
返回此 BitSet 表示位值时实际使用空间的位数。
void xor(BitSet bitSet)
对此位 set 和位 set 参数执行逻辑异或操作。

应用


  • 数据去重和排序

例如,有10亿个随机整数,剔除其中重复的数据,并按从小到大排序。

方法:将10亿条数存入BitSet,然后遍历BitSet按顺序取出数据。

BitSet s = new BitSet();

s.set(随机整数);//10亿次

//按顺序从小到大打印出不重复的数据

for(int i=0;i<s.length();i++){

    if(s.get(i)){

         System.out.println(i);   

    }  

}

  • 数据统计

例如,某社交APP有1千万绿钻用户,1.5千万黄钻用户,计算同时是绿钻和黄钻的用户。

方法:创建2个BitSet分别存放绿钻和黄钻的用户ID(ID为整数),对2个BitSet进行与操作即可得出同时是绿钻和黄钻的用户。

BitSet sg = new BitSet();

sg.set(绿钻用户ID);//1千万次

BitSet sy = new BitSet();

sy.set(黄钻用户ID);//1.5千万次

sg.and(sy);//sg此时记录同时为绿钻和黄钻的用户ID


源码分析


下面为JDK1.8源码

  • BitSet 属性

private final static int ADDRESS_BITS_PER_WORD = 6;

//64实际就是每个long64bit

private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;

private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;

//BitSet的数据存储在words数组中

private long[] words;

  • BitSet初始化

public BitSet() {

    //默认大小为64bit

   initWords(BITS_PER_WORD);

    sizeIsSticky = false;

}

//初始化words数组

private void initWords(int nbits) {

    //数组大小由指定bit大小决定

    words = new long[wordIndex(nbits-1) + 1];

}

//根据bit大小计算所需的long数组大小或者所在words中的位置

private static int wordIndex(int bitIndex) {

    return bitIndex >> ADDRESS_BITS_PER_WORD;

}

  • 清空BitSet

//全部清空

public void clear() {

    //实际将long设置为0

    while (wordsInUse > 0)

        words[--wordsInUse] = 0;

}

//清空指定位

public void clear(int bitIndex) {

    if (bitIndex < 0)

        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    //找出该bit位于哪一个long

    int wordIndex = wordIndex(bitIndex);

    if (wordIndex >= wordsInUse)

        return;

    //通过移位反转得到指定位为0,其余位为1的二进制数据,然后与对应的long进行&运算

    words[wordIndex] &= ~(1L << bitIndex);

    //计算当前long数组实际使用大小

    recalculateWordsInUse();

    //

    checkInvariants();

}

  • 设置某一指定位为1

//指定位设为1

public void set(int bitIndex) {

    if (bitIndex < 0)

        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    int wordIndex = wordIndex(bitIndex);

    expandTo(wordIndex);

    //指定位与1进行或运算

    words[wordIndex] |= (1L << bitIndex); // Restores invariants

    checkInvariants();

}

  • 反转某一指定位

public void flip(int bitIndex) {

    if (bitIndex < 0)

        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    int wordIndex = wordIndex(bitIndex);

    expandTo(wordIndex);

    //指定位与1进行异或运算

    words[wordIndex] ^= (1L << bitIndex);

    recalculateWordsInUse();

    checkInvariants();

}

  • 获取某一指定位状态

public boolean get(int bitIndex) {

    if (bitIndex < 0)

        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    checkInvariants();

    int wordIndex = wordIndex(bitIndex);

    //指定位存在且为1返回true,不存在或为0返回false

    return (wordIndex < wordsInUse)

        && ((words[wordIndex] & (1L << bitIndex)) != 0);

}


  • BitSet扩容

private void ensureCapacity(int wordsRequired) {    

   if (words.length < wordsRequired) {    

       // Allocate larger of doubled size or required size 

       //扩容为当前数组大小2倍及以上

       int request = Math.max(2 * words.length, wordsRequired);

       words = Arrays.copyOf(words, request);    

       sizeIsSticky = false;    

   }    

}


结束



欢迎关注

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《BitSet》的版权归原作者「巫师学堂」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注巫师学堂微信公众号

巫师学堂微信公众号:gh_43bc23a06865

巫师学堂

手机扫描上方二维码即可关注巫师学堂微信公众号

巫师学堂最新文章

精品公众号随机推荐

举报