位图算法(BitMap)

问题

假设有2亿个数,范围在0~3亿,给出一个数,判断这2亿个数中是否存在该数?使用内存不得超过500M

解决方式

定义一个3亿长度的整型数组int[],预先将所有数初始化,判断是否存在时只需int[number] != 0 即可判断。

时间复杂度:O(1)

空间复杂度:3亿 * 4 / 1024 / 1024 = 1144.5M

使用内存不符合要求, 那么我们应当如何解决呢?这时,就该用到BitMap了

前置知识

位移

位移分为左移和右移

  • 左移

    1 << 2 = 4; 表示1往左移2位,我们用二进制如下表示

    # 1的二进制
    0000 0001
    # 左移2位
    0000 0100 -> 4
    
  • 右移

    4 >> 2 = 1; 表示4往右移2位,用二进制如下表示

    # 4的二进制
    0000 0100
    # 右移2位
    0000 0001 -> 1
    

逻辑运算

  • 与运算

    5 & 4 = 4;表示两个数的二进制位做与运算,同位皆为1则结果为1,否则为0

    # 5
    0000 0101
    # 4
    0000 0100
    # 与运算
    0000 0100 -> 4
    
  • 或运算

    5 | 4 = 5; 表示两个数的二进制位做或运算,同位有一个为1则结果为1,都为0则为0

    # 5
    0000 0101
    # 4
    0000 0100
    # 或运算
    0000 0101 -> 5
    
  • 异或

    5 ^ 4 = 1; 表示两个数的二进制位做异或运算,同位不同则结果为1,相同则为0

    # 5
    0000 0101
    # 4
    0000 0100
    # 或运算
    0000 0001 -> 1
    

使用BitMap

我们知道,整型所表示的二进制位有32位,假设我们一个数存在则在该数的位置上表示1,不存在则表示0,则1个整型可表示32个数是否存在,如表示3是否存在的二进制为 0000 1000,那么我们的内存将会瞬间缩小32倍!

如假设我们有N个数{3, 10, 36, 66},则我们开出int[MAX/32+1]的int数组,这里的MAX指这些数中的最大的数,所以我们这里是开出3个长度int数组,具体结构表示如下:

data[0]: 0~31
data[1]: 31~63
data[2]: 64~95

假设我们要判断65是否存在,那么我们可以通过以下方式计算:

65 / 32 = 2 -> 定位到在下标为2的数组中:data[2]

65 % 32 = 1 -> 定位到65在data[2]的二进制的下标位置:1

所以我们只需通过一个除法,一个取余,就得到了65所在的位置,这时只需看看这个位置是否为1,就能判断65是否存在了。那这个是怎么看呢?我们画个图表示吧~

因为在给出的数中{3, 10, 36, 66},在data[2]的数只有66,所以我们的data[2]二进制表示形式如下所示:

这里省略了前面24位

而65经过以上的计算方式后的二进制表示形式如下

我们将data[2]&65,最后得出为0,则表示65不存在。

以上就是BitMap的核心思想了

算法实现

算法我们已经明白了,那么代码怎么写呢?

public class BitMap {

    private final int[] data;

    public BitMap(int capacity) {
        this.data = new int[capacity + 1];
    }
    // element = 5
    public void add(int element) {
        // 0
        int dataIndex = element >> 5;
        // 5
        int location = element & 31;
        // 1 << location = 0010 0000
        //   0000 0000
        // | 0010 0000
        //   0010 0000
        data[dataIndex] |= 1 << location;
    }

    public boolean find(int element) {
        int dataIndex = element >> 5;
        int location = element & 31;
        //   0010 0000
        // & 0010 0000
        //   0010 0000
        int exist = data[dataIndex] & (1 << location);
        return exist != 0;
    }

    public static void main(String[] args) {
        BitMap bitMap = new BitMap(100);
        bitMap.add(5);
        bitMap.add(29);
        bitMap.add(66);
        System.out.println(bitMap.find(5));
        System.out.println(bitMap.find(65));
    }
}

以上代码实现了添加和查找,那么删除该怎么做呢?这个小问题就留给大家了~

小结

以上我们从一个小问题开始讲述了如何通过BitMap进行解决,那么我们使用BitMap的时间复杂度和空间复杂度是多少呢?

时间复杂度:O(1)

空间复杂度:对于整型来说,占用空间是整型数组的1/32,对于以上问题所占用的空间为:

​ 3亿 / 32 * 4 / 1024 / 1024 = 35.76M

BitMap如此高效且节约空间,我们能够用它解决哪些问题呢?

  • 数据判重
  • 不重复的数据进行排序

通过这两点,我们可以扩展出很多的场景应用

  • 找不重复的数

  • 过滤,如我们有1亿的商品,黑客使用一个不存在的商品id查询我们商品库,由于这个商品不存在,那么就无法走缓存了,最后请求会直接打到数据库上,黑客使用这种方式疯狂查询一个不存在的商品,如果没有别的措施,就会把我们的数据库打垮。那么我们就可以使用BitMap将这些商品id存到内存中,请求是判断这个BitMap中是否存在就可以啦~(其实这就是我们大名鼎鼎的布隆过滤器)

  • 统计,我们想要统计系统中用户的连续登陆情况,或者在某个时间段呢哪些天是否登陆,传统做法是将用户登陆情况存到数据库中,假设我们日活1亿用户,那么每日都将增加1亿的数据...但是当我们使用BitMap,这个问题将轻松解决,那么应当如何实现呢?

  • 用户标签,根据用户标签推荐用户可能需要的商品

  • .....

说了这么多BitMap的优点,那它的缺点是什么呢?

  • 处理不了重复数据,只知道存不存在(1或者0),不知道存在几个
  • 因为处理不了重复问题,所以处理不了Hash冲突,如果Hash冲突了,那就不知道这个位置上是谁了
  • 因为处理不了Hash冲突,所以不能对String类型进行处理,上面描述时也说明了,开的数组是最大数是什么,就要开多大的数组,假设我们只有10个数(范围0~2亿),这时候我们也得开2亿的空间,但是不如直接使用Map。

如何解决重复问题,且听下回分解~

# bitmap 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×