大数据相关的概念--海量数据处理——Bloom Filter

　　简单来说一下什么是Bloom Filter？

　　所谓的Bloom filter是二进制向量数据结构，它具有很好的空间和时间效率，可以用来检测一个元素是不是集合中的一个成员。如果检测结果为是，则该元素不一定在集合中；但如果检测结果为否，该元素一定不在集合中。因此Bloomfilter具有100%的召回率。这样每个检测请求返回有“在集合内（可能错误）”和“不在集合内（绝对不在集合内）”两种情况。

　　本文从解决这类问题的方法入手，开辟一系列专题来解决海量数据问题，BloomFilter的详细介绍，有不懂的朋友可以看看

　　1.适用的一些范围

　　可以用来实现数据的字典，进行数据的判重，或者集合求交集

　　2.Bloom Filter基本原理及要点：

　　原理上是比较简单的，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，明显在过程并不保证查找的结果是100%正确的。

　　同时也不支持删除一个已经插入的关键字，因为该关键字对应的位是会牵动到其他的关键字。简单的改进就是countingBloomfilter，用一个counter数组代替位数组，也就可以删除了。

　　有一个重要的问题是，如何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。

　　一个简单的例子：我们假设错误率为0.01，则此时m应大概是n的13倍，这样k大概就是8个了。

　　需要注意的是，在这里m与n的单位是不同的，m是bit为单位，而n则是以元素个数为单位，通常单个元素的长度都是有很多bit的，因此使用bloomfilter内存上一般都是节省的。

　　3.实际中的问题实例

　　例如：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，但是内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？

　　根据实际的问题，首先是来计算一下内存的一个占用，4G=2^32大概是40亿*8大概是340亿bit，n=50亿，若按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，差距并不是太多，这样会使出错率上升些。如果这些urlip是一一对应的，就可以转换成ip，就可以简单化了。

　　以上是对Bloom Filter的一个详细的介绍，如果是刚入门大数据，对这个概念理解起来有一点的困难也算是正常，在接下来的大数据的学习中，我们将继续为推出更实用的资讯。