lyp123

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

#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位的序号代表这个数字

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

元素将会被会被不同的哈希函数处理三次，每个哈希函数都返回一个作为位数组索引值的整数，然后我们检测位数组在x、y与z处的值是否为1。如果有一处不为1，那么就说明这个元素没有被添加到这个布隆过滤器中。如果都为1，就说明这个元素在布隆过滤器里面。当然，会有一定误判的概率。 这样的话，权衡一下散列时间和错误率，就可以很高效地完成存储数据以及查找数据了。

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