专栏首页我是攻城师理解BitMap算法的原理

理解BitMap算法的原理

前言

位图:一种常用的数据结构,代表了有限域中的稠集(dense set),每一个元素至少出现一次,没有其他的数据和元素相关联。在索引,数据压缩,海量数据处理等方面有广泛应用。

BitMap 的思想的和原理是很多算法的基础,比如 Bloom Filter、Counting Bloom Filter。

BitMap的原理

BitMap 的基本原理就是用一个 bit 位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

举个例子在Java里面一个int类型占4个字节,也就是4*8=32bit,大多数时候我们一个int类型仅仅表示一个整数,但其实如果映射成位存储的话,一个int类型 是可以存储32个bit状态的。

也就是说使用1G的内存,换算成bit=1024 * 1024 * 1024 * 8约等于86亿个bit,注意换算的方式GB=>MB=>KB=>Byte=>Bit。如果存储int类型,能存储多少个?我们 算下1024 * 1024 * 1024 / 4 约等于2亿6千万个int类型。

从上面的计算的结果来看,在面对海量数据的时候,如果能够采用bit存储,那么在存储空间方面可以大大节省。

在Java里面,其实已经有对应实现的数据结构类java.util.BitSet了,BitSet的底层使用的是long类型的数组来存储元素。

也就是说,假设我想排序或者查找的总数N=10000,那么,我申请的数组大小如下:

如果是int类型:int temp[]=new int[1+N/32],也就是312+1=313

如果是long类型:long temp[]=new long[1+N/64],也就是156+1=157

这里注意Java里面的整数除法是向下取整的,所以数组长度还需要加上1.

这里以int为例,生成的bitmap表如下:

a[0]--------->0-31 ->bit表示[0000000000000000000000000000000000000]
a[1]--------->32-63 ->bit表示[0000000000000000000000000000000000000]
a[2]--------->64-95 ->bit表示[0000000000000000000000000000000000000]

其实申请一个int一维数组,那么可以当作为列为32位的二维数组。先通过对32进行相除,得到数组下标,然后将十进制转成二进制之后,进行移位计算,用来代表状态。

下面,我们来看一个排序场景,定义一个元素不重复的数组{2,3,14,7,0}。

BitSet map=new BitSet();

        System.out.println(map.size());

        int a[]={2,3,14,7,0};

        //赋值
        for(int num:a){
            map.set(num,true);
        }
        //排序

        for (int i = 0; i < map.size(); i++) {
            if(map.get(i)){
                System.out.print(i+" ");
            }
        }

输出:

64
0 2 3 7 14

第一行的64,是代表当前的bit数,因为是long类型,而数组里面的最大值没有超过63,所以其实只用一个long类型就能处理上面的排序。

看到这里,如果熟悉排序算法里面计数排序,那么我们就能发现原理非常类似,不同的是使用bitmap排序占用的存储空间更小,但缺点是不支持重复数字。

来看一下关于BitMap算法一些处理大数据问题的场景:

(1)给定40亿个不重复的 int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中。

解法:遍历40亿数字,映射到BitMap中,然后对于给出的数,直接判断指定的位上存在不存在即可。

(2)使用位图法判断整形数组是否存在重复

解法:遍历一遍,存在之后设置成1,每次放之前先判断是否存在,如果存在,就代表该元素重复。

(3)使用位图法进行元素不重复的整形数组排序

解法:遍历一遍,设置状态1,然后再次遍历,对状态等于1的进行输出,参考计数排序的原理。

(4)在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数

解法1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)。

解法2:采用两个BitMap,即第一个Bitmap存储的是整数是否出现,接着,在之后的遍历先判断第一个BitMap里面是否出现过,如果出现就设置第二个BitMap对应的位置也为1,最后遍历BitMap,仅仅在一个BitMap中出现过的元素,就是不重复的整数。

解法3:分治+Hash取模,拆分成多个小文件,然后一个个文件读取,直到内存装的下,然后采用Hash+Count的方式判断即可。

该类问题的变形问题,如已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。 8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==12MBytes,这样,就用了小小的12M左右的内存表示了所有的8位数的电话)

BitMap的一些缺点:

(1)数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题,那就可以考虑用 Bloom Filter 来解决,Bloom Filter 使用多个 Hash 函数来减少冲突的概率。

(2)数据稀疏。又比如要存入(10,8887983,93452134)这三个数据,我们需要建立一个 99999999 长度的 BitMap ,但是实际上只存了3个数据,这时候就有很大的空间浪费,碰到这种问题的话,可以通过引入 Roaring BitMap 来解决。

总结

本文主要介绍了BitMap算法的基本原理和应用案例,其本质上是采用了bit位来表示元素状态,从而在特定场景下能够极大的节省存储空间,非常适合对海量数据的查找,判重,删除等问题的处理。

本文分享自微信公众号 - 我是攻城师(woshigcs)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-10-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 360开源的Qconf配置同步工具使用记录

    我是攻城师
  • 深入理解Java8并发工具类StampedLock

    StampedLock类是JDK8里面新增的一个并发工具类,这个类比较特殊,在此之前我们先简单的了解一下关于数据库或者存储系统的锁策略和机制。

    我是攻城师
  • 在ReadWriteLock类中读锁为什么不能升级为写锁?

    关于读写锁里面有一个锁升级和降级的问题,也就是写锁可以降级为读锁,但是读锁却不能升级为写锁。那么为什么是这样?

    我是攻城师
  • Python_查看sqlite3表结构,

    查看表结构:cursor.execute('PRAGMA table_info(表名)')

    py3study
  • 长短时记忆网络LSTM(基本理论)

    参考: Understanding LSTM Networks The Unreasonable Effectiveness of Recurrent Neu...

    用户1332428
  • Apache httpd 目录列表禁用配置(options indexes)

    Apache httpd服务器在缺省的情况下,开启了基于目录列表的访问,这是一个存在安全隐患的问题,因此可以关闭这个功能。在Apache 2.4的版本中,不在支...

    Leshami
  • python-MySQLdb的二三事

    追寻 介绍 mysqldb是python操作mysql数据库的一个库.mysql的几乎所有的操作都可以实现,另外,mysqldb的一些比较的option让数据...

    若与
  • 解决Ajax发送DELETE请求时后台无法接收到参数的问题(Restful风格)

    TrueDei
  • 【业界】帮化学家偷个懒,利用量子计算来模拟化学反应

    AiTechYun 编辑:xiaoshan.xiang 第一个已知的经典“计算机”是Antikythera mechanism,这是一种模拟机器,用于模拟天体在...

    AiTechYun
  • Saltstack 快速入门教程

    1.介绍 Saltstack 比 Puppet 出来晚几年,是基于Python 开发的,也是基于 C/S 架构,服务端 master 和客户端 minions ...

    程裕强

扫码关注云+社区

领取腾讯云代金券