这两天又开了一门创新实验课 icon_cry.png ,说是创新实验课,就是大家坐到一起讨论一下别人创新的东西哈哈哈 icon_lol.png 还是比较水的,不过第一次课还是学到了一点东西,这里就简单总结分享一下。

1.bitmap

首先切入正题,bitmap是个啥,有啥用,啥玩意啊,我一开始的时候也是一脸懵逼,但是老师举了一个很有趣的例子:

在一个数组里面存几百个个int数,最多也就是耗费上千个字节,这不难实现,毕竟现在电脑内存8g都是标配,但是给40亿个不重复的unsigned int的整数,没有排过序,然后再给一个数,如果快速判断这个数是否在那40亿个数当中?
分析: 如果将数据全部存入内存,再遍历判断,需要大约15G内存才能实现(unsigned int为4字节)。

或许这里有人会说,难道我不可以使用外部排序吗?答案是肯定的,但是不值得。

下面就来正式介绍我们的bitmap:
位图算法: 利用2进制位表示是否存在。0表示不存在,1表示存在。
例如: 有{3,5,7,8,2},可以利用一个8位的二进制来表示该集合 11010110
因此,通过申请40亿位长的空间(不到512M)就可以表示这40亿的整数了。
注:这里我一开始没有理解的是不同位数的怎么办,后面才想通这里的bitmap指的是从1开始到终点有四十亿位,就是说这个里面不允许有重复的数字,每个bit位的序号代表这个数字 icon_idea.png

2.bloom_filter

理解了上面的bitmap下这个布隆过滤器就很好理解了,布隆过滤器就是基于bitmap实现的,这个过滤器顾名思义就是能查找里面的数据,同样的方式,我们把数据存入bitmap,这里注意,我们这布隆过滤器里面存入的数据不一定是数字,也可以是字符串等等各种类型,那么这些内容是怎么存入bitmap的呢?
不难想到:哈希函数,哈希函数可以将所有的数据变成整型,然后再存入布隆过滤器,但是用到哈希函数就不得不提到这个错误率的问题,在布隆过滤器里面,使用了不止一个哈希函数来减少错误率,举个例子

元素将会被会被不同的哈希函数处理三次,每个哈希函数都返回一个作为位数组索引值的整数,然后我们检测位数组在x、y与z处的值是否为1。如果有一处不为1,那么就说明这个元素没有被添加到这个布隆过滤器中。如果都为1,就说明这个元素在布隆过滤器里面。当然,会有一定误判的概率。

这样的话,权衡一下散列时间和错误率,就可以很高效地完成存储数据以及查找数据了。

3.应用举例

在实验里面,老师让我们做了在两个巨大的字符文本中找到相同的字符串,在我看来,这个算法运行速度相当之高,也算是收获满满。关于bitmap的应用就是上面那个例子啦这里就不赘述了。