|
百度口试题：给定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代码实现如下
[java]?
view plain
?copy
- 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>();??
- ????}??
- /*添加哈希函数类*/??
- void?addHashFunction(IHashFunction?hashFunction)?{??
- this.hashFuctionList.add(hashFunction);??
- /*删除hash函数*/??
- void?removeHashFunction(IHashFunction?hashFunction)?{??
- this.hashFuctionList.remove(hashFunction);??
- /*判定是否被包括*/??
- 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;??
- ????????????}??
- ????????}??
- ????????true;??
- ????}??
- ????/*添加到bitSet*/??
- ????void?toBitSet(BitSet?bitSet,?String?str)?{??
- for?(IHashFunction?hash?:?hashFuctionList)?{??
- int?hashCode?=?hash.toHashCode(str);??
- 0){??
- ????????????????hashCode=-hashCode;??
- ????????????bitSet.set(hashCode,?true);??
- ????????}??
- ??????
- static?void?main(String[]?args)?{??
- ????????BloomFilter?bloomFilter=new?BloomFilter();??
- ????????/*添加3个哈希函数*/??
- ????????bloomFilter.addHashFunction(new?JavaHash());??
- ????????bloomFilter.addHashFunction(new?RSHash());??
- 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="我的","有钱的人道","Iphone6s",153); background-color:inherit; font-weight:bold">for?(String?str2?:?test2)?{??
- if(bloomFilter.contain(bitSet,?str2)){??
- ????????????????System.out.println("'"+str2+"'是一再的");??
- ??????????
- }??
- /*哈希函数接口*/??
- interface?IHashFunction?{??
- int?toHashCode(String?str);??
- class?JavaHash?implements?IHashFunction?{??
- ????@Override??
- int?toHashCode(String?str)?{??
- return?str.hashCode();??
- ??
- }??
- class?RSHash?implements?IHashFunction?{??
- ????@Override??
- 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?0;?i?<?str.length();?i++)??
- ????????????hash?=?str.charAt(i)?+?(hash?<<?6)?+?(hash?<<?16)?-?hash;??
- }??
运行功效
（编辑：湖南网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
