大数据处理算法二:Bloom Filter算法
百度面试题:给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url? Bloom?Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。 一.?实例? 为了说明Bloom?Filter存在的重要意义,举一个实例: ?(实例一),假设要你写一个网络蜘蛛(web?crawler)。由于网络间的链接错综复杂,蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”,就需要知道蜘蛛已经访问过那些URL。给一个URL,怎样知道蜘蛛是否已经访问过呢?稍微想想, ?????????(实例二)给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url? 就会有如下几种方案: 1.?将访问过的URL保存到数据库。 2.?用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。 3.?URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。 4.?Bit-Map方法。建立一个BitSet,将每个URL经过一个哈希函数映射到某一位。 方法1~3都是将访问过的URL完整保存,方法4则只标记URL的一个映射位。 ???????以上方法在数据量较小的情况下都能完美解决问题,但是当数据量变得非常庞大时问题就来了。 方法1的缺点:数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了? 方法2的缺点:太消耗内存。随着URL的增多,占用的内存会越来越多。就算只有1亿个URL,每个URL只算50个字符,就需要5GB内存。 方法3:由于字符串经过MD5处理后的信息摘要长度只有128Bit,SHA-1处理后也只有160Bit,因此方法3比方法2节省了好几倍的内存。 方法4消耗内存是相对较少的,但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么?若要降低冲突发生的概率到1%,就要将BitSet的长度设置为URL个数的100倍。 实质上上面的算法都忽略了一个重要的隐含条件:允许小概率的出错,不一定要100%准确!也就是说少量url实际上没有没网络蜘蛛访问,而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。? 例如有?一组字符?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; } }运行结果 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |