理解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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JavaEdge

"聊胜于无",浅析Java中的原子操作Java的指针Unsafe类i++不是线程安全的1 原子更新基本类型类2 原子更新数组3 AtomicReference(原子更新引用)4 原子更新字段Atomi

5966
来自专栏web前端教室

重学javascript 红皮高程(4)

继续啊,顺着JS高程的目录往下走,今天是3.4.4 Boolean类型。 这个Boolean一般来说它只有二个值,true和false。但其实它还有第三种值, ...

2249
来自专栏DHUtoBUAA

《剑指Offer》附加题_用两个队列实现一个栈_C++版

  在《剑指Offer》中,在栈和队列习题中,作者留下来一道题目供读者自己实现,即“用两个队列实现一个栈”。   在计算机数据结构中,栈的特点是后进先出,即最后...

2965
来自专栏非著名程序员

解决TextView排版混乱或者自动换行的问题

其实在TextView中遇到排版自动换行而导致混乱不堪的情况是非常常见的,而且导致这种问题产生的原因就是英文和中文混合输入,半角字符和全角字符混合在一起了。一般...

5416
来自专栏电光石火

3X3 九宫格

题目:3X3 的九宫格,每个横竖斜相加都等于15,使用1-9数字。 要求:PHP语言,1-9数字不重复。 解题思路分析: 1:可以知道和为15,所以获...

3907
来自专栏鸿的学习笔记

python的装饰器和闭包

因为在编译时,python会认为b是局部变量,这是python的一个设计选择,为了避免变量的污染,想一想。如果某人在函数内部改动了变量,你没有办法看到这个函数,

921
来自专栏文武兼修ing——机器学习与IC设计

栈与栈的实现栈栈的基本操作栈的实现

栈 栈是一种基础的数据结构,只从一端读写数据。基本特点就”后进先出“,例如顺序入栈1,2,3,4,5,再顺序出栈是5,4,3,2,1 栈的基本操作 栈的基本操作...

3155
来自专栏Java爬坑系列

【Java入门提高篇】Day32 Java容器类详解(十四)ArrayDeque详解

  今天来介绍一个不太常见也不太常用的类——ArrayDeque,这是一个很不错的容器类,如果对它还不了解的话,那么就好好看看这篇文章吧。

942
来自专栏海说

14、Iterator跟ListIterator的区别

14、Iterator与ListIterator的区别       在使用List,Set的时候,为了实现对其数据的遍历,会经常使用到Iterator(跌代器)...

1880
来自专栏禅林阆苑

golang 利用指针导出变量 【原创】

golang 利用指针导出变量 Write By CS逍遥剑仙 我的主页: www.csxiaoyao.com GitHub: github....

48314

扫码关注云+社区

领取腾讯云代金券