java bitset(换一种存储思路)源码解析

作者简介

微信公众号（高质量文章推送）：走向全栈工程师
作者：陈博易

前言

算法题：现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。

看到这样的算法题不知道你有没有好的思路呢？

你也许有这样的思路1：
1 创建一个一亿大小的数组，默认值java都是赋值为0
2 然后将产生的随机数按数值大小放入数组a[i]=i
3 遍历一次数组a[i]==0的就是i就是符合要求的

你也许有这样的思路2：
1 产生1千万个大小在1-1亿之间的随机数
2 产生的随机数保存到数组或者集合中
3 遍历循环判断1-1亿的数字并且分别判断是否在保存的数组或者集合中
4 将符合要求的数字单独存储

这样的想法似乎ok。考虑如下：
1 java中int 占用4字节，1千万个int 占用4千万个字节（大概38M）
2 从1-1亿递增循环，循环体中还需要遍历1千万个随机数分别判断是否符合条件（卧槽，这得遍历到何年何月啊，明显这个思路是有问题的）

这样的算法效率何如，我们从时间和控件分析下

算法的时间复杂度
上面提到的嵌套循环，外层一亿次，内层1千万次。通过分析可知算法的时间复杂度为o(n^2),即为平方阶

算法的空间复杂度
这里需要用数组和集合来存储1千万个整数。通过分析可知空间复杂度为o(n),即为线性阶

看到这里的时间复杂度o(n2)我已经害怕了，因为本道算法题的n已经到千万、亿的级别了。说明这个思路的效率是非常低！

---

引入bitset

什么是bitset
BitSet是位操作的对象，一个bit位只有0或1即false和true，内部维护了一个long数组。

为什么要使用bitset

例如有N个需要存储，int resource=[1,2,4]
由于一个int 占用4个字节，那么resource数组占用12个字节。
如果使用bitset来储存long[0]=【0,1,1,0,1,...0】(总共64位,...全部用0填充)，原来一个整数占用内存是4个字节，现在用一个位来存储，比例32:1，简单的说用bitset按位存储可以省32倍的内存空间。
效率优势：1(M)=1X1024X1024x8=8388608(bit)，用1m的空间可以存储839万个整数，1G大约可以存86亿个整数。

用bitset解决算法题

public class TestJava {
    public static void main(String[] args) {
        test();
        for (int i = 0; i < 100000000; i++) {
            for (int j = 0; j < 10000000; j++) {

            }
        }
    }

    private static void test() {
        int maxNum = 10;//模拟1千万个随机数
        int rangeNum = 100;//模拟1亿
        BitSet bitSet = new BitSet();
        Random random = new Random();
        for (int i = 0; i < maxNum; i++) {
            //int randNumber =rand.nextInt(MAX - MIN + 1) + MIN;
            //产生1到一亿之间的随机数
            int num = random.nextInt(rangeNum) + 1;
            //存储到bitset中维护的long数组中
            bitSet.set(num);
            System.out.println("boyi.chen" + "test: 产生的随机数-->" + num);
        }
        //求出1到1亿之间没有在随机数中出现的数
        for (int i = 1; i <= rangeNum; i++) {
            //到bitset中维护的long数组中利用逻辑&运算结果是否为1
            if (bitSet.get(i)) {
                //bitset中存在该整数，结束当前循环
                continue;
            }
            System.out.println("boyi.chen" + "test: 将1到1亿之间没有在随机数-->" + i);
        }

    }
}

上面为了方便测试，所以将数字改小了。上面代码为了求出1到1亿之间没有在随机数中出现的数，没有出现嵌套循环，性能明显是提高了。时间复杂度为o(n)，效率提高了很多

bitset源码解析

BitSet bitSet = new BitSet(); //初始化

  //变量声明
  private long[] words;
  private final static int ADDRESS_BITS_PER_WORD = 6;
  //1<<6==64
  private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
  //内部维护的words数组大小是否由用户指定，默认是false
  private transient boolean sizeIsSticky = false;

    /**
     * Creates a new bit set.初始化bitset
     */
    public BitSet() {
        initWords(BITS_PER_WORD);
        sizeIsSticky = false;
    }

 /**
     * 传入bit位索引,返回long数组中的位置索引.
     */
    private static int wordIndex(int bitIndex) {
        return bitIndex >> ADDRESS_BITS_PER_WORD;
    }

//默认初始化大小为: long[wordIndex(BITS_PER_WORD -1)+1]
//wordIndex(BITS_PER_WORD -1)+1==wordIndex(1<<6-1)+1
//<<是左移运算符，如果看不懂得话，可以去补补计算机原理得基础知识了。
//1<<6==64，这里就是初始化了大小为1的数组long[1]
 private void initWords(int nbits) {
        words = new long[wordIndex(nbits-1) + 1];
    }

总结：上面的代码其实就是当用户不指定大小，默认初始化一个大小位1的long数组

bitSet.set(int bitIndex); //存储过程

  /**
     * Sets the bit at the specified index to {@code true}.
     *
     * @param  bitIndex 一个位索引
     * @throws IndexOutOfBoundsException if the specified index is negative
     * @since  JDK1.0
     */
    public void set(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
        //bitIndex在words数组的位置，例如words[0]
        int wordIndex = wordIndex(bitIndex);
        //如果bitIndex超过1-63扩充words大小到words[1]
        expandTo(wordIndex);
        //通过逻辑或、左移运算将bitIndex存储在words数组中
        words[wordIndex] |= (1L << bitIndex); // Restores invariants

        checkInvariants();
    }

举个例子说明一下
set(7)
int wordIndex = wordIndex(bitIndex);//wordIndex =0，说明存储在words[0]位置

words[wordIndex] |= (1L << bitIndex); // Restores invariants//这个看着会
复杂一点，实际上也就一个类似循环左移（怎么理解类似循环左移呢？一般看到这条语句，会认为bitIndex如果超过64位，高位会溢出并得到返回0，事实上这个1会重新循环到低位，还可以理解成1<<bitIndex%64）和逻辑或运算，1L << bitIndex的结果是128（原码=00000000...（这里省略6*8个0）10000000，正数的补码和原码相等）。这里还有一个|运算，简单说就是将words[0]上的存储的补码和新的set(7)的补码进行逻辑|运算，这样就可以实现按位存储了。举个例子：001|010那就是011（因为|运算的原则就是有1则1，全0为0，重要的事情说三遍，三遍，三遍，这里仅仅是演示逻辑与运算为什么可以存储不同的数）

bitSet.get(int bitIndex); //判断传入的整数是否存在，存在则true 不存在则false

拓展

https://mp.weixin.qq.com/s/xN2DcPLR4vbW338rCVIy9Q 美团技术团队用bitset解决的这样的场景,这篇文章从头到尾可以动看看，认真思考下。

image.png

/*
* 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.
*/
bit有这样的注释说明 The choice of word size is determined purely by performance concerns.bitset内部维护的word数组大小为64的偶数倍完全出于性能考虑。cpu读取内存数据的提高，这里涉及到内存对齐的问题。
请参考文章：
https://www.2cto.com/kf/201407/319682.html

总结

如果上文中有很多生词，请百度计算机原理

1. 请大家多关注关注我。
2. 接下来继续分享一些算法和一些源码解析

个人相关教程

各种大佬推荐的编程视频资源分享
Android 微信 支付宝支付，2行代码实现支付
Android前端 Java后端 集成支付宝支付
postman使用 Android java后端 接口调试工具
Android抓包 Charles http接口调试
消息推送 Android java后端集成小米推送
如何导入简单的java项目-IntelliJ IDEA
Android NDK JNI 开发 环境搭建入门篇
Android NDK JNI 开发之旅 so类库 简单使用篇

请关注我（高质量文章推送）

Android NDK JNI 开发之旅 开源项目

长按二维码“识别”关注或者扫一扫