黑马程序员技术交流社区

标题: java中BitSet完美实现bitmap算法 [打印本页]

---

作者: 小江哥    时间: 2019-4-19 11:52
标题: java中BitSet完美实现bitmap算法
bitmap顾名思义就是位映射, 先看一个场景
有一个int数组{1,2,5,7},初步估计占用内存4*4=16字节，但是假如有10亿个这样的数呢，10亿*4/(102410241024)=3.72G左右。
如果这样的一个大的数据做查找和排序，那估计内存也崩溃了，有人说，这些数据可以不用一次性加载，那就是要存盘了，存盘必然消耗IO。
如果用bitmap算法去处理就会简单高效的很多,解决如下
一个byte是占8个bit，如果每一个bit的值就是有或者没有，也就是二进制的0或者1，
如果用bit的位置代表数组值有还是没有，那么0代表该数值没有出现过，1代表该数组值出现过。不也能描述数据了吗？
代码如下

[Java] 纯文本查看 复制代码

 public void add(int num){

 // num/8得到byte[]的index

 int arrayIndex = num >> 3;



 // num%8得到在byte[index]的位置

 int position = num & 0x07;



 //将1左移position后，那个位置自然就是1，然后和以前的数据做|，这样，那个位置就替换成1了。

 bits[arrayIndex] |= 1 << position;

 }

全是位运算操作, 是不是很头疼, 我们强大的jdk已经提供了BitSet类替我们封装了这么难懂的位操作
话不多说上代码

[Java] 纯文本查看 复制代码

public class BitMapTest {

        public static void main(String[] args) {

                int[] array = {3, 8, 5, 7, 1};

                BitSet bitSet = new BitSet(5);



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

                        bitSet.set(array, true);

                }



                bitSet.stream().forEach(e -> System.out.println(e));



        }

}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2