亲宝软件园·资讯

展开

算法---BitMap

白露非霜 人气:4

问题:

假设有3亿个整数(范围0-2亿),如何判断某一个树是否存在。局限条件一台机器,内存500m。

 

常规的思路:我们可以将数据存到一个集合中,然后判断某个数是否存在;或者用一个等长的数组来表示,每个数对应的索引位置,存在就标记为1,不存在0。当然如果设备条件允许,上面的这方案是可行的。

但是现在我们内存只有500m。Int类型4个字节。

单单是这3亿个数都已经:300000000*4/1024/1024 差不多1144m了。显然已经远超过内存限制了。

显然在这种条件下面,我们想要将这些书完整的存储下来已经是不现实的。只有另寻他经。

上面的第二种方案中提供一个很好思路,用标记来标注。我们只有寻求内存占用更小的数据类型来标记了,1int=4byte,1byte = 8bit

如果我们用bit来打标记。就不可以很好的缩小内存占用了嘛。1int=4byte,如果用bit那么内存占用就会缩小32倍,1144/32大概36m就可以了。

也就是说其实我们的一个int位置,可以表示32个数据存在与否。

Int 1的二进制完整表示:0000 0000 0000 0000 0000 0000 0000 0001,它是有32位,只不过平时前面的0都是没有显示的

我们声明一个int类型的标记数组:flag[2亿/32 +1],数组长度2亿/32 +1,就可以了,为什么是2亿/32,不是3亿呢,因为这3亿个数的范围就是0-2亿,所以我们的标记数组最大只需要对应2亿即可。有的数,就将其标记为1。就是说数组的没一个元素其实包含了32个数存在与否。

Flag[0] --->0-31

Flag[1] --->32-63

Flag[2] --->64-95

Flag[3] --->96-127

.......

我们怎么来操作这个int类型里面的32位呢,这就要用到我们的位运算:

<<:左移

>>:右移

&:同位上的两个数都是1则位1,否则为0

|:同为上的两个数只要有一个为1 则为1,否则为0

 

我们怎么找到某个数的标记在数组的索引及其值的多少位呢?

假设3这个数

Index = 3 / 32 = 0

Location = 3 % 32 = 3

3的标记应该在flag[0] 的第三个位置,将其置为1:

flag[0]  |=  1 << Location (位或是不会影响其他位置1的标记)

原本的flag[0]  0000 0000 0000 0000 0000 0000 0000 0011    原本已经有了0和1

     |    0000 0000 0000 0000 0000 0000 0000 1000    1 << Location 之后的

得到:           0000 0000 0000 0000 0000 0000 0000 1011    现在有0,1,3了

这样就可以所有的数据标记给保存下来了。

那么判断的时候怎么判断呢。

同理先找到某个数精确位置

还是3

Index = 3 / 32 = 0

Location = 3 % 32 = 3

现在我们的flag[0] -> 0000 0000 0000 0000 0000 0000 0000 1011

Exist = flag[0] & (1 << Location) != 0  &:相同位上的两个数都是1则位1,否则为0

  0000 0000 0000 0000 0000 0000 0000 1011

&  0000 0000 0000 0000 0000 0000 0000 1000

    0000 0000 0000 0000 0000 0000 0000 1000

&运算之后结果不为0说明该数存在。

 

大致的思路就是这个样子,下面用代码实现上述逻辑

 

package com.nijunyang.algorithm.math;

/**
 * Description:
 * Created by nijunyang on 2020/5/5 22:33
 */
public class BitMap {
    /**
     * 范围中最大的那个数
     */
    private int max;

    private int[] flag;

    public BitMap(int max) {
        this.max = max;
        flag = new int[max >> 5 + 1]; //除以32也可以表示为>>5
    }

    /**
     * 添加数据标记
     * @param val
     */
    public void put(int val) {        //往bitmap里面添加数字

        int index = val / 32;        // 计算数组索引位置
        int location = val % 32;    // 计算在32位int中的位置
        flag[index] |= 1 << location;   //标记位改成1
    }

    /**
     * 判断是否存在
     * @param val
     * @return
     */
    public boolean exist(int val) {
        int index = val / 32;
        int location = val % 32;

        int result = flag[index] & (1 << location);
        return result != 0;
    }

    /**
     * 移除标记
     * @param val
     * @return
     */
    public void remove(int val) {
        int index = val / 32;
        int location = val % 32;

        System.out.println(Integer.toBinaryString(flag[index]));
        flag[index] = flag[index] &~ (1 << location); //~取反1变0 0变1
        System.out.println(Integer.toBinaryString(flag[index]));
    }

    public static void main(String[] args) {
        BitMap bitMap = new BitMap(200_000_000);
        bitMap.put(128);
        bitMap.put(129);
        System.out.println(bitMap.exist(127));
        System.out.println(bitMap.exist(128));
        bitMap.remove(128);
        System.out.println(bitMap.exist(128));

    }
}

 

 

虽然说用bitMap的这种思想可以解决上面的这个问题,但是它还是有缺点的,我们上面用的数字,如果是其他类型可能就需要hash之后得到hashcode再进行这个操作,对于hash冲突是无法解决的。因为标记只有0和1。数据量少的时候相对于普通的hash集合操作并没有优势。它对于那种数据量很大,且数据相对密集的,因为数组的长度是和最大的数据值有关,而不是和集合容量有关。

布隆过滤器就使用bitMap的思想。不过它同时会使用集中hash算法来计算hashcode,来尽量解决hash冲突。Redis缓存设计与性能优化 中有简单的介绍。

JDK中也有一个BitSet类。

 

加载全部内容

相关教程
猜你喜欢
用户评论