1 Star 0 Fork 1

zzx / 37-40

forked from 崔文俊 / quick 
加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
关于BitSet.md 3.92 KB
一键复制 编辑 原始数据 按行查看 历史
崔文俊 提交于 2021-05-24 09:33 . update 关于BitSet.md.

核心思想是这样的:

一个字节8个bit,每个bit取值1或0用于表示存在或者不存在,这已经是最节约内存的做法。

要判断某个数据是否存在,只要把这个数据映射到字节数组中的某个bit上后,就可以快速定位到这个数据是否存在。这个效率是比较高效和节约内存空间的。

private final static int ADDRESS_BITS_PER_WORD = 6;
private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;    //1左移6位是64,也就是说BITS_PER_WORD=64

一个默认大小的BitSet里面是64个bit也就是说有64个开关量可以用于标记64个数据是否存在


    /**
     * Creates a new bit set. All bits are initially {@code false}.
     */
    public BitSet() {
        initWords(BITS_PER_WORD);    //默认64,这个64不是指字节,而是指64个Bit,就是8个字节,所以一个long正好是8个字节
        sizeIsSticky = false;
    }

BitSet里面是用long数组来维持标记的一个long是8个字节一个长度为1的long[]就可以表示64个bit的开关量

如果默认的64个bit不够,假设你现在要在100万个用户中判断某个用户是否存在,假设用户ID都是数字,那么nbits就可以取更大的值,比如传入100万


    /**
     * Creates a bit set whose initial size is large enough to explicitly
     * represent bits with indices in the range {@code 0} through
     * {@code nbits-1}. All bits are initially {@code false}.
     *
     * @param  nbits the initial size of the bit set
     * @throws NegativeArraySizeException if the specified initial size
     *         is negative
     */
    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;
    }

100万个数据的话,最终计算出来是需要15625个长度的long型数组,也就是new long[15625],实际上就是15625 * 8 * 8 = 输入图片说明

输入图片说明

BitSet会自动扩容

这里可以初始化为100个bit,很明显不够,下面我set的时候传入的是46000,所以BitSet会自动扩容

BitSet bitSet = new BitSet(100);
        System.out.println("bitSet.size = " + bitSet.size() + ", bitSet.length = " + bitSet.length());

        bitSet.set(46000, true);

        System.out.println("bitSet = " + bitSet.get(45999));
        System.out.println("bitSet = " + bitSet.get(46000));
        System.out.println("bitSet = " + bitSet.get(46001));
        System.out.println("bitSet.size = " + bitSet.size() + ", bitSet.length = " + bitSet.length());

看一下输出结果,size已经扩容到超过4万6,否则无法容纳,为啥扩容,因为调用了set(46000, true),原来只有100个bit是无法存放的,必须扩容到超过46000个bit才行

初始:bitSet.size = 128, bitSet.length = 0 bitSet = false bitSet = true bitSet = false 扩容后:bitSet.size = 46016, bitSet.length = 46001

从bitSet.get(45999)和bitSet.get(46001)都可以看得出来,这2个值都是false,证明BitSet内部的long[]数组里面相应的bit位并没有被置为true,所以返回false

正因为BitSet内部用数组中的bit来表示有或者无,再加上调用get(xxxxx)的时候,是把xxxxx这个数字映射到具体的某个bit槽位上的,这个过程CPU运算是非常快的,所以可以使用BitSet来进行海量数据的存在与否判断,非常节约内存,同时运算速度也非常快,在做项目的时候如果遇到特定场景,可以尝试使用它。

另外一个就是布隆过滤器的使用,也是值得使用的,海量数据判存在与否的逻辑,都可以尝试BitSet和布隆过滤器。

马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/zhzx/37-40.git
git@gitee.com:zhzx/37-40.git
zhzx
37-40
37-40
master

搜索帮助

344bd9b3 5694891 D2dac590 5694891