[置顶] 大数据处理算法二：Bloom Filter算法
来源：程序员人生 发布时间：2015-05-29 08:25:30 阅读次数：3741次
百度面试题：给定a、b两个文件，各寄存50亿个url，每一个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
Bloom Filter是由Bloom在1970年提出的1种多哈希函数映照的快速查找算法。通常利用在1些需要快速判断某个元素是不是属于集合，但是其实不严格要求100%正确的场合。
1. 实例
为了说明Bloom Filter存在的重要意义，举1个实例：
（实例1）,假定要你写1个网络蜘蛛（web crawler）。由于网络间的链接扑朔迷离，蜘蛛在网络间爬行极可能会构成“环”。为了不构成“环”，就需要知道蜘蛛已访问过那些URL。给1个URL，怎样知道蜘蛛是不是已访问过呢？略微想一想，
（实例2）给定a、b两个文件，各寄存50亿个url，每一个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
就会有以下几种方案：
1. 将访问过的URL保存到数据库。
2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就能够查到1个URL是不是被访问过了。
3. URL经过MD5或SHA⑴等单向哈希后再保存到HashSet或数据库。
4. Bit-Map方法。建立1个BitSet，将每一个URL经过1个哈希函数映照到某1位。
方法1~3都是将访问过的URL完全保存，方法4则只标记URL的1个映照位。
以上方法在数据量较小的情况下都能完善解决问题，但是当数据量变得非常庞大时问题就来了。
方法1的缺点：数据量变得非常庞大后关系型数据库查询的效力会变得很低。而且每来1个URL就启动1次数据库查询是否是太小题大做了？
方法2的缺点：太消耗内存。随着URL的增多，占用的内存会愈来愈多。就算只有1亿个URL，每一个URL只算50个字符，就需要5GB内存。
方法3：由于字符串经过MD5处理后的信息摘要长度只有128Bit，SHA⑴处理后也只有160Bit，因此方法3比方法2节省了好几倍的内存。
方法4消耗内存是相对较少的，但缺点是单1哈希函数产生冲突的几率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么？若要下降冲突产生的几率到1%，就要将BitSet的长度设置为URL个数的100倍。
实质上上面的算法都疏忽了1个重要的隐含条件：允许小几率的出错，不1定要100%准确！也就是说少许url实际上没有没网络蜘蛛访问，而将它们错判为已访问的代价是很小的――大不了少抓几个网页呗。
例如有 1组字符 arr：”哈哈“，”呵呵“........
字符串：“哈哈”
哈希算法1处理后：8
哈希算法2处理后：1
哈希算法1处理后：3
插入BitArray后
再处理字符串：“呵呵”
哈希算法1处理后：2
哈希算法2处理后：1
哈希算法1处理后：9
继续插入BitArray后，如果继续游字符串，继续以这类方式插入
判断”在这些字符串是不是包括”嘻嘻“
哈希算法1处理后：0
哈希算法2处理后：1
哈希算法1处理后：7
只要判断 下标分别为 0,1,7位置的值是不是都为1，以下图 由于位置0跟位置7的值不为1
所以”嘻嘻“不包括在arr中，反之如果都为1怎包括
java代码实现以下
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
/**
* BloomFilter算法
*
* @author JYC506
*
*/
public class BloomFilter {
/*哈希函数*/
private List<IHashFunction> hashFuctionList;
/*构造方法*/
public BloomFilter() {
this.hashFuctionList = new ArrayList<IHashFunction>();
}
/*添加哈希函数类*/
public void addHashFunction(IHashFunction hashFunction) {
this.hashFuctionList.add(hashFunction);
}
/*删除hash函数*/
public void removeHashFunction(IHashFunction hashFunction) {
this.hashFuctionList.remove(hashFunction);
}
/*判断是不是被包括*/
public boolean contain(BitSet bitSet, String str) {
for (IHashFunction hash : hashFuctionList) {
int hashCode = hash.toHashCode(str);
if(hashCode<0){
hashCode=-hashCode;
}
if (bitSet.get(hashCode) == false) {
return false;
}
}
return true;
}
/*添加到bitSet*/
public void toBitSet(BitSet bitSet, String str) {
for (IHashFunction hash : hashFuctionList) {
int hashCode = hash.toHashCode(str);
if(hashCode<0){
hashCode=-hashCode;
}
bitSet.set(hashCode, true);
}
}
public static void main(String[] args) {
BloomFilter bloomFilter=new BloomFilter();
/*添加3个哈希函数*/
bloomFilter.addHashFunction(new JavaHash());
bloomFilter.addHashFunction(new RSHash());
bloomFilter.addHashFunction(new SDBMHash());
/*长度为2的24次方*/
BitSet bitSet=new BitSet(1<<25);
/*判断test1很test2重复的字符串*/
String[] test1=new String[]{"哈哈","我","大家","逗比","有钱人性","小米","Iphone","helloWorld"};
for (String str1 : test1) {
bloomFilter.toBitSet(bitSet, str1);
}
String[] test2=new String[]{"哈哈","我的","大家","逗比","有钱的人性","小米","Iphone6s","helloWorld"};
for (String str2 : test2) {
if(bloomFilter.contain(bitSet, str2)){
System.out.println("'"+str2+"'是重复的");
}
}
}
}
/*哈希函数接口*/
interface IHashFunction {
int toHashCode(String str);
}
class JavaHash implements IHashFunction {
@Override
public int toHashCode(String str) {
return str.hashCode();
}
}
class RSHash implements IHashFunction {
@Override
public int toHashCode(String str) {
int b = 378551;
int a = 63689;
int hash = 0;
for (int i = 0; i < str.length(); i++) {
hash = hash * a + str.charAt(i);
a = a * b;
}
return hash;
}
}
class SDBMHash implements IHashFunction {
@Override
public int toHashCode(String str) {
int hash = 0;
for (int i = 0; i < str.length(); i++)
hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
return hash;
}
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
