BitMap

作者: Gyu2233 | 来源:发表于2020-02-26 01:09 被阅读0次

简介

所谓的BitMap,就是用一个bit位,来标记某个元素所对应的value,而key即是该元素,这样做, 不仅可以运用于快速查找,去重,排序,压缩数据,还能节省存储空间。

基本思想

举个例子来介绍其思想
假设我们要对5个元素(4,7,2,5,3)进行排序(这里假设元素没有重复)。我们可以使用BitMap算法达到排序目的。

  • 首先我们开辟一个字节(8byte)的空间,将这些空间的所有的byte位都设置为0
  • 然后便利这5个元素,第一个元素是4,我们把第五个字节的值设置为1(下标从0开始)
  • 然后再处理剩下的四个元素,最终8个字节的状态如下
    | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
  • 现在我们遍历一次bytes区域,把值为1的byte的位置输出(2,3,4,5,7),这样便达到了排序的目的

Map映射

假设需要排序或则查找的数的总数N=100000000,BitMap中1bit代表一个数字,1个int = 4Bytes = 4 * 8bit = 32 bit,那么N个数需要(N/32) int空间。所以我们需要申请内存空间的大小为int a[1 + N/32],其中:a[0]在内存中占32为可以对应十进制数0-31,依次类推:
a[0]----------------------------->0-31
a[1]----------------------------->32-63
a[2]----------------------------->64-95
以此类推。。
那么,十进制的数如何转换为对应的bit位呢?请继续往下看。。

1,求十进制数在对应数组arrays中的下标,比如十进制数0-31,对应为arrays[0],32-63对应为arrays[1],归纳一下就是,对于一个十进制数n,其对应为arrays[n/32]
2, 求十进制数对应在arrays[i]中的下标,比如十进制31在arrays[0]中下标为31,十进制数31在arrays[1]中下标为0,也就是说,在对于arrays[i],都分配了0-31的下标,分别对应32个十进制数的下标。
3, 位移实现,如果是二维数组,那么,
一个十进制数n,对应为arrays[n/32][n%32],
如果是一维呢?
我们可以用移位操作实现置1
arrays[n/32] |= 1 << n % 32
也就是,
arrays[n>>5] |= 1 << (n & 0x1F)

简单代码实现

public class BitMap {

    private static final int N = 10000000;

    private int[] a = new int[N/32 + 1];

    /**
     * 设置所在的bit位为1
     * @param n
     */
    public void addValue(int n){
        
        int row = n >> 5;//row = n / 32 求十进制数在数组a中的下标
        
        a[row] |= 1 << (n & 0x1F);//相当于 n % 32 求十进制数在数组a[i]中的下标
    }

    
    public boolean exits(int n){// 判断所在的bit为是否为1
        int row = n >> 5;
        return (a[row] & ( 1 << (n & 0x1F))) != 1;
    }

    public void display(int row){
        System.out.println("BitMap位图展示");
        for(int i = 0;i < row; i++){
            List<Integer> list = new ArrayList<Integer>();
            int temp = a[i];
            for(int j = 0; j < 32; j++){
                list.add(temp & 1);
                temp >>= 1;
            }
            System.out.println("a["+i+"]" + list);
        }
    }

    public static void main(String[] args){
        int num[] = {1,2,3,4,5,6,7,8,9,10};
        BitMap map = new BitMap();
        for(int i=0;i<num.length;i++){
            map.addValue(num[i]);
        }

        int temp = 120;
        if(map.exits(temp)){
            System.out.println("temp:" + temp + "has already exists");
        }
        map.display(5);
    }
}

相关文章

网友评论

      本文标题:BitMap

      本文链接:https://www.haomeiwen.com/subject/dfhrchtx.html