Hadoop之BloomFilter

BloomFilter概述：

目的是检索元素是否在某个集合中，基于hash，速度比较快，不需要存储所有的元素，只需要按照某种方式存储hash值即可，因此比较节约内存，因此可以常驻内存加快查找速度。同时利用多个hash来解决hash冲突问题

我们假定集合元素为一个列表，我们可以用一个bit列表来存储此元素是否存在，如下所示：

 存在为1不存在为0，不过由于hash很容易冲突，那么可以基于多hash函数进行冲突的避免，每次设置对于的hash值为1，如下所示：

 也就是说x1经过三次hash那么设置对应的下标为1，x2同理，当查找判断的时候我们只需要同样获取三次hash值进行定位，当都为1的时候证明存在，反之则不存在，如下所示：

也就是说y1为不存在，因为有0，而y2，原则上存在，为什么是原则上呢？因为多次对位集合进行设置为1，而不清楚为0，那么很容易形成一个覆盖，也就是说不存在的判断是准确的，而存在的判断是不准确的。

转发请注明出处：http://snv.iteye.com/

总之：

1. BloomFilter能很快的判断某元素是否存在

2.BloomFilter能准确判断不存在的，概率性判断存在的

3.常驻内存对大数据操作很快

Hadoop中的实现：

BloomFilter
CountingBloomFilter
DynamicBloomFilter
RetouchedBloomFilter

使用场景：

1.操作的文件很多，那么当一个请求过来之后首先在内存做判断，如果有那么操作，如果没有那么直接返回，如nosql系列等

2.大数据处理时，如爬虫采集时对url做判断，如果没有采集过那么采集等

3.对否要求高，对是要求低的操作