位图Bitmap及其Java实现 - 知乎 - 程序猿·D·安宇雨 DeepMind

位图Bitmap及其Java实现 - 知乎

安宇雨 - 随手采集
2023-10-07 16:17:13
随手采集
0000-未整理-等待研究

举个例子，如下图，如果我们想要存放 0,2,4,5,10,11,12,14,15这几个数字，如果采用普通存储方式，若4位表示一个数字，这9个数字需要4*9=36位，至少36位才能存储这些数据。

如果采用位图的方式，只需要上图的16位就能存储这9个数字。

查找的时候，只需要查找这个位的数是1还是0即可，就可以确定该数存在不存在。

当数量足够大时候，不光大大压缩了存储空间，查找速率也极快，可以说是O(1)。

接下来我们看一下思路：

位图的实现，主要在于实现两个功能，一个是获取该位置的值，一个是设置该位置的值。

获取：

我们使用byte类型的数组来实现位图，byte类型在Java占1个字节也就是8位，可以存放8个数据。

先求是第几个字节：number/8；

再求该字节的第几个（0-7）：i=number%8；

将这个字节数右移(7-i)位（也就是把要查找的位移动到最右侧），然后与 0000 0001相与，得到结果是0或1就可以确定。

public boolean get(int number){
        //获取位置
        int site=number>>>3;//等价于 site=number/8
        //获取该字节
        byte temp=bitmap[site];

        //获取该字节的第几个
        int i=number&7;//等价于 i=number%8
        
        //将这个字节数右移(7-i)位（也就是把要查找的位移动到最右侧），然后与 0000 0001相与
        if(((temp>>>(7-i))&1)==0){
            return false;
        }
        return true;
    }

设置该位置的值：

也要先求是第几个字节：number/8；

再求该字节的第几个（0-7）：i=number%8；

如果要设置为1：

将0000 0001 左移(7-i)，此时’1’对应的位置就是该数对应位置，然后和该字节取“或”。

如果要设置为0：

将0000 0001 左移(7-i)，此时’0’对应的位置就是该数对应位置，取反，然后和该字节相与。

private void set(int number, boolean bool){
        //获取位置
        int site=number>>>3;//等价于 site=number/8
        //获取该字节
        byte temp=bitmap[site];

        //获取该字节的第几个
        int i=number&7;//等价于 i=number%8
        //将0000 0001 左移(7-i)
        byte comp= (byte) (1<<(7-i));

        if(bool){//设置为1
            bitmap[site]= (byte) (comp|temp);//取或(0.. 1 0..)
        }else {//设置为0
            comp= (byte) ~comp;//取反
            bitmap[site]= (byte) (comp&temp);//相与(1.. 0 1..)
        }
    }

当存储相对范围比较小，数量特别大的情况下，使用位图的存储空间比直接存储要少得多，查找效率远比直接存储快得多。

所以特定条件下，使用位图能够大大提高存储效率和查找效率。

以下为全部代码：

/**
 * @Author: GoodbyeLullaby
 * @Date: 2019/12/2
 */

public class Bitmap {
    private byte bitmap[];
    private int length;

    public boolean get(int number){
        //获取位置
        int site=number>>>3;//等价于 site=number/8
        //获取该字节
        byte temp=bitmap[site];

        //获取该字节的第几个
        int i=number&7;//等价于 i=number%8
        byte comp=1;

        //将这个字节数右移(7-i)位（也就是把要查找的位移动到最右侧），然后与 0000 0001相与
        if(((temp>>>(7-i))&1)==0){
            return false;
        }
        return true;
    }
    private void set(int number, boolean bool){
        //获取位置
        int site=number>>>3;//等价于 site=number/8
        //获取该字节
        byte temp=bitmap[site];

        //获取该字节的第几个
        int i=number&7;//等价于 i=number%8
        //将0000 0001 左移(7-i)
        byte comp= (byte) (1<<(7-i));

        if(bool){//设置为1
            bitmap[site]= (byte) (comp|temp);//取或(0.. 1 0..)
        }else {//设置为0
            comp= (byte) ~comp;//取反
            bitmap[site]= (byte) (comp&temp);//相与(1.. 0 1..)
        }
    }
    public void add(int index){
        set(index,true);
    }
    public void delete(int index){
        set(index,false);
    }

    public Bitmap (int length){
        this.length=length;
        bitmap=new byte[length>>>3];
    }

    public int getLength() {
        return length;
    }

    public static void main(String[] args){
        Bitmap bitmap=new Bitmap(100000);
        bitmap.add(100);
        System.out.println(bitmap.get(100));
        bitmap.delete(100);
        System.out.println(bitmap.get(100));
    }

}

原网址: 访问
创建于: 2023-10-07 16:17:13
目录: default
标签: 无

未标明原创文章均为采集，版权归作者所有，转载无需和我联系，请注明原出处，南摩阿彌陀佛，知识，不只知道，要得到