BitMap 的基本原理和实现

前言

文章是自己写了后先发到了公众号里,再转到了内部的KM。算是一个系列的学习笔记,一篇篇来。

本篇是大数据算法系列 第一篇《BitMap的原理和实现》,BitMap 的思想的和原理是很多算法的基础,因此我们以BitMap开篇。

既然是说大数据算法,我们先尝试给大数据算法一个定义,或者说是限定一下这个系列的范围。

大数据算法:在给定的资源约束下,以大数据为输入,在给定时间约束内可以计算出给定问题加过的算法。

大数据算法会有传统的算法有不一样的地方:

  1. 资源有约束
  2. 时间有约束
  3. 大数据作为输入
  4. 不一定是精确算法

前三点可以看作是对算法的要求,第四点可以看作是在大数据场景下算法可以做出的让步。比如说在10亿的数据中求 count distinct 操作,完全精确的算法会十分占用空间资源,而且也很难在快速计算出结果。如果这时候允许一定的误差,就可以在极短的时间使用少量的内容算出结果,比如基数估计算法中的Hyperloglog。

本系列会包括 BitMap、Roaring BitMap、Bloom Filter、Counting Bloom Filter、Linear Counting、Loglog Counting、HyperLogLog Counting 等算法。我会把这些算法一个个过一遍,看论文、写代码、整理学习笔记。

对于技术人员来讲,文章应该做到 图文码并茂,因此我会尽量做到每篇文章都有原理说明和示例代码的实现,原理说明会通过配图的方式来理解,代码的话会有一个比较简单的demo。

一、原理

基本原理

BitMap 的基本原理就是用一个 bit 来标记某个元素对应的 Value,而 Key 即是该元素。由于采用一 个bit 来存储一个数据,因此可以大大的节省空间。

我们通过一个具体的例子来说明 BitMap 的原理,假设我们要对 0-31 内的 3 个元素 (10, 17,28) 排序,那么我们就可以采用 BitMap 方法(假设这些元素没有重复)。

如下图,要表示 32 个数,我们就只需要 32 个 bit(4Bytes),首先我们开辟 4Byte 的空间,将这些空间的所有 bit 位都置为 0。

然后,我们要添加(10, 17,28) 这三个数到 BitMap 中,需要的操作就是在相应的位置上将0置为1即可。如下图,比如现在要插入 10 这个元素,只需要将蓝色的那一位变为1即可。

将这些数据插入后,假设我们想对数据进行排序或者检索数据是否存在,就可以依次遍历这个数据结构,碰到位为 1 的情况,就当这个数据存在。

字符串映射

BitMap 也可以用来表述字符串类型的数据,但是需要有一层Hash映射,如下图,通过一层映射关系,可以表述字符串是否存在。

当然这种方式会有数据碰撞的问题,但可以通过 Bloom Filter 做一些优化。

二、实现

懂原理之后,还是要写代码来加深一下理解,这里用 Python 实现一个最基本的版本。

代码用到了 bitarry 库来直接操作 bit 数组;用 hashlib 来将字符串映射到数字,以便插入 BitMap。

代码很简单,看懂上面的原理的话,很容易就看懂了代码。

三、使用

BitMap 的使用场景很广泛,比如说 Oracle、Redis 中都有用到 BitMap。当然更多的系统会有比 BitMap 稍微复杂一些的算法,比如 Bloom Filter、Counting Bloom Filter,这些会在后面逐一展开。

下面举一个在算法中用到 BitMap 来解决问题的例子。

已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

在这里就不再做和其它算法的对比,直接说一下 BitMap 的思路。

8 位的整数,相当于是范围在(0,99999999),也就是说 99999999 个 bit,也就是 12M 左右的内存,比起用类似 HashMap 的方式的话能节省很大的空间。 可以理解为从0 到 99999999 的数字,每个数字对应一个 Bit位,所以只需要 12M 左右的内存表示了所有的 8 位数的电话。

查询的时候就很简单了,直接统计有多少位是 1 就可以了。

四、总结

BitMap 的思想在面试的时候还是可以用来解决不少问题的,然后在很多系统中也都会用到,算是一种不错的解决问题的思路。

但是 BitMap 也有一些局限,因此会有其它一些基于 BitMap 的算法出现来解决这些问题。

  • 数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题,那就可以考虑用 Bloom Filter 来解决,Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
  • 数据稀疏。又比如要存入(10,8887983,93452134)这三个数据,我们需要建立一个 99999999 长度的 BitMap ,但是实际上只存了3个数据,这时候就有很大的空间浪费,碰到这种问题的话,可以通过引入 Roaring BitMap 来解决。

算法比较成熟,因此参考的东西也挺多,就不再列参考了。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员叨叨叨

8.3 入口函数

通常高级语言程序中只有一个入口函数,不过由于着色程序分为顶点程序和片断程序,两者对应着图形流水线上的不同阶段,所以这两个程序都各有一个入口函数。

1534
来自专栏数据小魔方

sparklines迷你图系列15——Composition(BoxPlot)

今天要跟大家分享的是sparklines迷你图系列14——BoxPlot。 箱线图是用于呈现数据分布形态(功能类似直方图)的一种图表,对于连续型数据,箱线图可以...

2834
来自专栏算法修养

矩阵快速幂小结

      矩阵快速幂大概是用来解决这样一类问题,当你知道了一个递推式比如a[n]=a[n-1]+a[n-2] 题目要求你求出a[n]。如果n大于1亿怎么办? ...

3005
来自专栏冰霜之地

Google S2 是如何解决空间覆盖最优解问题的?

这篇不出意外就是 Google S2 整个系列的最终篇了。这篇里面会把 regionCoverer 算法都讲解清楚。至于 Google S2 库里面还有很多其他...

2133
来自专栏用户2442861的专栏

2014美团网笔试题目(总结)

http://blog.csdn.net/wzy_1988/article/details/12438143

1131
来自专栏简书专栏

Matplotlib进阶

892
来自专栏WindCoder

最大流量和线性分配问题

这里有一个问题:你的业务分配给承包商来履行合同。您可以浏览您的名单,并决定哪些承包商可以参与一个月的合同,你可以查看你的合同,看看哪些合同是一个月的任务。鉴于你...

1542
来自专栏用户画像

3.3 差错控制

概括地说,传输中的差错都是由于噪声引起的。噪声有两大类:一类是信道中所固定的、持续存在的随机热噪声;另一类是由于外界特定个的短暂原因所造成的冲击噪声。前者可以通...

771
来自专栏GIS讲堂

dojo chart详解

Dojo提供了一套很完善的统计图(Chart)接口,在dojox/charting下面,可以支持很多种类型的。

1122
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之最大子向量和(连续子数组的最大和)(九度OJ1372)

题目描述: HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天JOBDU测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和...

19010

扫码关注云+社区