首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >经典算法之bitmap算法

经典算法之bitmap算法

作者头像
用户3467126
发布2019-11-26 14:38:41
1.1K0
发布2019-11-26 14:38:41
举报
文章被收录于专栏:爱编码爱编码
概述

本文将讲述Bit-Map算法的相关原理,Bit-Map算法的一些利用场景,例如BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题.最后说说BitMap的特点已经在各个场景的使用性。

Bit-Map算法

先看看这样的一个场景:

给一台普通PC,2G内存,要求处理一个包含40亿个不重复并且没有排过序的无符号的int整数,给出一个整数,问如果快速地判断这个整数是否在文件40亿个数据当中?

问题思考:40亿个int占(40亿*4)/1024/1024/1024 大概为14.9G左右,很明显内存只有2G,放不下,因此不可能将这40亿数据放到内存中计算。要快速的解决这个问题最好的方案就是将数据搁内存了,所以现在的问题就在如何在2G内存空间以内存储着40亿整数。

一个int整数在java中是占4个字节的即要32bit位,如果能够用一个bit位来标识一个int整数那么存储空间将大大减少,算一下40亿个int需要的内存空间为40亿/8/1024/1024大概为476.83 mb,这样的话我们完全可以将这40亿个int数放到内存中进行处理。

具体思路:

1个int占4字节即4*8=32位,那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些数据,其中N代表要进行查找的总数,tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表: tmp[0]:可表示0~31 tmp[1]:可表示32~63 tmp[2]可表示64~95 ....... 那么接下来就看看十进制数如何转换为对应的bit位:假设这40亿int数据为:6,3,8,32,36,......,那么具体的BitMap表示为:

那么怎么快速定位它的索引呢。如果找到它的索引号,又怎么定位它的位置呢。Index(N)代表N的索引号,Position(N)代表N的所在的位置号。

Index(N) = N/8 = N >> 3;

Position(N) = N%8 = N & 0x07;

add方法:

public void add(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 

        // num%8得到在byte[index]的位置
        int position = num & 0x07; 

        //将1左移position后,那个位置自然就是1,然后和以前的数据做|,这样,那个位置就替换成1了。
        bits[arrayIndex] |= 1 << position; 
    }

代码如下:

public class BitMap {
    //保存数据的
    private byte[] bits;

    //能够存储多少数据
    private int capacity;


    public BitMap(int capacity){
        this.capacity = capacity;

        //1bit能存储8个数据,那么capacity数据需要多少个bit呢,capacity/8+1,右移3位相当于除以8
        bits = new byte[(capacity >>3 )+1];
    }

    public void add(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 

        // num%8得到在byte[index]的位置
        int position = num & 0x07; 

        //将1左移position后,那个位置自然就是1,然后和以前的数据做|,这样,那个位置就替换成1了。
        bits[arrayIndex] |= 1 << position; 
    }

    public boolean contain(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 

        // num%8得到在byte[index]的位置
        int position = num & 0x07; 

        //将1左移position后,那个位置自然就是1,然后和以前的数据做&,判断是否为0即可
        return (bits[arrayIndex] & (1 << position)) !=0; 
    }

    public void clear(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 

        // num%8得到在byte[index]的位置
        int position = num & 0x07; 

        //将1左移position后,那个位置自然就是1,然后对取反,再与当前值做&,即可清除当前的位置了.
        bits[arrayIndex] &= ~(1 << position); 

    }

    public static void main(String[] args) {
        BitMap bitmap = new BitMap(100);
        bitmap.add(7);
        System.out.println("插入7成功");

        boolean isexsit = bitmap.contain(7);
        System.out.println("7是否存在:"+isexsit);

        bitmap.clear(7);
        isexsit = bitmap.contain(7);
        System.out.println("7是否存在:"+isexsit);
    }
}

每个byte存8个数字,相对于int类型来说,节省了32倍的存储空间

存储数据范围,就上面的例子来说,上面bits数组的长度为13,那么总共可以存储(13*8)104个数字,分别是(0~103)

上面的代码并没有扩容方法,超出范围会报错,

使用bit数组来表示某些元素是否存在,比如8位电话号码.

缺点:

如果是比较特殊的数字,比如[1,100000000],那么就会浪费存储空间,比如这个就必须要(100000000>>3)个字节

针对上面的缺点,谷歌所实现的EWAHCompressedBitmap对bitmap存储空间做了一定的优化

相信的讲解:https://blog.csdn.net/yizishou/article/details/78365791

问题实例

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

解法一:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32 * 2 bit=1 GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。

解法二:也可采用与第1题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。”

2、给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?

解法一:可以用位图/Bitmap的方法,申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。

作者:hongda 出处:https://www.cnblogs.com/hongdada/p/8267032.html

参考文档

https://www.jianshu.com/p/6082a2f7df8e

https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/06.07.html

http://blog.51cto.com/zengzhaozheng/1404108

http://blog.csdn.net/h348592532/article/details/45362661

https://www.cnblogs.com/protected/p/6626447.html

http://mp.weixin.qq.com/s?_biz=MzIxMjE5MTE1Nw==&mid=2653191272&idx=1&sn=9bbcd172b611b455ebfc4b7fb9a6a55e&chksm=8c990eb2bbee87a486c55572a36c577a48df395e13e74314846d221cbcfd364d44c280250234&scene=21#wechatredirect

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-11-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 爱编码 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档