开发者社区> woooow> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Java中Bitmap的实现

简介: 说bitmap之前,我们要明白数字在内存中的表示,如果说byte用8个二进制位表示,即可以表示个数,每个byte占8位,即每个byte占8行,在内存中这样形象的表示: 而bitmap结构,充分利用了每一行所有的位数,它将每个位置作为一个数,那么一行就可以模拟表示出8个数。
+关注继续查看

说bitmap之前,我们要明白数字在内存中的表示,如果说byte用8个二进制位表示,即可以表示2^8 = 256个数,每个byte占8位,即每个byte占8行,在内存中这样形象的表示:

img_2fea11af47d0518edd22e3bfe248436d.png

而bitmap结构,充分利用了每一行所有的位数,它将每个位置作为一个数,那么一行就可以模拟表示出8个数。

Bitmap介绍

bitmap是很有用的结构。所谓的bitmap就是用一个bit位来标记某个元素,而数组下标是该元素。

bitmap优势

bitmap经常用在大数据的题中,比如10亿个int类型的数,如果用int数组存储的话,那么需要大约4G内存,浪费内存。如果用bitmap解决,就比较方便。bitmap可以用int来模拟,也可以用byte来模拟,它只是逻辑上的概念,在java语言中写不出来,我们采用byte。一个byte占8个bit,如果每一个bit的值是有或者没有,即1或0,则如下图所示:


img_07fc038ff8486acc79d36ad96888fdcb.png

bitmap代码实现

第一步:构建特定长度的byte数组(new byte[capacity/8 + 1]),其中capacity为整数数组长度(如:10亿个数字等)

byte[] bits = new byte[getIndex(n) + 1];

第二步:计算数字num在byte[]中的位置(num/8和num >> 3一样),也就是说num在byte[k],算这个k是几

    /**
     * num/8得到byte[]的index
     * @param num
     * @return
     */
    public int getIndex(int num){
        return num >> 3;
    }

第三步:计算数字num在byte[index]中的位置,就是在byte[index]的第几位,每个byte有8位(num % 8)

    /**
     * num%8得到在byte[index]的位置
     * @param num
     * @return
     */
    public int getPosition(int num){
        return num & 0x07;
    }

第四步:将所在位置从0变成1,其它位置不变

    /**
     * 标记指定数字(num)在bitmap中的值,标记其已经出现过
     * 将1左移position后,那个位置自然就是1,然后和以前的数据做|,这样,那个位置就替换成1了
     * @param bits
     * @param num
     */
    public void add(byte[] bits, int num){
        bits[getIndex(num)] |= 1 << getPosition(num);
    }

解释如下图:


img_7950db6317e99661c8bd170fc8b336c7.png

第五步:判断指定数字num是否存在

    /**
     * 判断指定数字num是否存在<br/>
     * 将1左移position后,那个位置自然就是1,然后和以前的数据做&,判断是否为0即可
     * @param bits
     * @param num
     * @return
     */
    public boolean contains(byte[] bits, int num){
        return (bits[getIndex(num)] & 1 << getPosition(num)) != 0;
    }
img_929a364c96713e0536e76a2152e39585.png

第六步:重置某一数字对应在bitmap中的值

    /**
     * 重置某一数字对应在bitmap中的值<br/>
     * 对1进行左移,然后取反,最后与byte[index]作与操作。
     * @param bits
     * @param num
     */
    public void clear(byte[] bits, int num){
        bits[getIndex(num)] &= ~(1 << getPosition(num));
    }
img_1b64eaf9c5cd176dc915d37dbfc3242f.png

全部代码如下:

public class Test {

    /**
     * 创建bitmap数组
     */
    public byte[] create(int n){
        byte[] bits = new byte[getIndex(n) + 1];
        
        for(int i = 0; i < n; i++){
            add(bits, i);
        }
        
        System.out.println(contains(bits, 11));
        
        int index = 1;
        for(byte bit : bits){
            System.out.println("-------" + index++ + "-------");
            showByte(bit);

        }
        
        return bits;
    }
    
    /**
     * 标记指定数字(num)在bitmap中的值,标记其已经出现过<br/>
     * 将1左移position后,那个位置自然就是1,然后和以前的数据做|,这样,那个位置就替换成1了
     * @param bits
     * @param num
     */
    public void add(byte[] bits, int num){
        bits[getIndex(num)] |= 1 << getPosition(num);
    }
    
    /**
     * 判断指定数字num是否存在<br/>
     * 将1左移position后,那个位置自然就是1,然后和以前的数据做&,判断是否为0即可
     * @param bits
     * @param num
     * @return
     */
    public boolean contains(byte[] bits, int num){
        return (bits[getIndex(num)] & 1 << getPosition(num)) != 0;
    }
    
    /**
     * num/8得到byte[]的index
     * @param num
     * @return
     */
    public int getIndex(int num){
        return num >> 3;
    }
    
    /**
     * num%8得到在byte[index]的位置
     * @param num
     * @return
     */
    public int getPosition(int num){
        return num & 0x07;
    }
    
    /**
     * 重置某一数字对应在bitmap中的值<br/>
     * 对1进行左移,然后取反,最后与byte[index]作与操作。
     * @param bits
     * @param num
     */
    public void clear(byte[] bits, int num){
        bits[getIndex(num)] &= ~(1 << getPosition(num));
    }
    
    /**
     * 打印byte类型的变量<br/>
     * 将byte转换为一个长度为8的byte数组,数组每个值代表bit
     */
    
    public void showByte(byte b){
        byte[] array = new byte[8];
        for(int i = 7; i >= 0; i--){
            array[i] = (byte)(b & 1);
            b = (byte)(b >> 1);
        }
        
        for (byte b1 : array) {
            System.out.print(b1);
            System.out.print(" ");
        }
        
        System.out.println();
    }
    
    public static void main(String[] args) {
        int n = 100;
        new Test().create(n);
    }
}

结果如图,一共100个数:


img_3f2bed971f3915d9ada6bfe2540be53b.png

杂谈

下面是我搜集的一些关于bitmap的,有时间再看。。。
https://blog.csdn.net/a3192048/article/details/80261699

这是关于java中原生的bitmap的实现,BitSet
https://blog.csdn.net/lushuaiyin/article/details/7546144

https://blog.csdn.net/y999666/article/details/51220833

https://blog.csdn.net/xia744510124/article/details/51509285/

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
极致优化:使用二进制分段实现压缩存储|Java 刷题打卡
极致优化:使用二进制分段实现压缩存储|Java 刷题打卡
0 0
详解如何使用「动态规划」实现「通配符匹配」|Java 刷题打卡
详解如何使用「动态规划」实现「通配符匹配」|Java 刷题打卡
0 0
巧妙利用异或性质实现最优解|Java 刷题打卡
巧妙利用异或性质实现最优解|Java 刷题打卡
0 0
Java方法05——简单计算器的实现(练习巩固)
Java方法05——简单计算器的实现(练习巩固)
0 0
java实现下载器(以及创建一个URL对象)
java实现下载器(以及创建一个URL对象)
0 0
java自定义线程池实现
java自定义线程池实现
0 0
【Java数据结构及算法实战】系列010:Java队列04——链表实现的阻塞队列LinkedBlockingQueue
【Java数据结构及算法实战】系列010:Java队列04——链表实现的阻塞队列LinkedBlockingQueue
0 0
两种方式实现一个「扁平化嵌套列表迭代器」|Java 刷题打卡
两种方式实现一个「扁平化嵌套列表迭代器」|Java 刷题打卡
0 0
RSA加密解密及数字签名Java实现
RSA算法是一种非对称密码算法,所谓非对称,就是指该算法需要一对密钥,使用其中一个加密,则需要用另一个才能解密。
0 0
时间轮-Java实现篇
在前面的文章《[时间轮-理论篇](https://developer.aliyun.com/article/910513)》讲了时间轮的一些理论知识,然后根据理论知识。我们自己来实现一个简单的时间轮。
0 0
+关注
woooow
我不生产bug,我只是bug的搬运工
文章
问答
文章排行榜
最热
最新
相关电子书
更多
Java开发手册1.3.0
立即下载
Java开发手册1.1.0
立即下载
Java开发手册1.0.0版
立即下载