下面是用BloomFilter的常见场合
[python]
1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话）
2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上，在遍历这些数的时候，如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。
3)问题实例：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？
解决方案：
将数据文件分割为20个文件，然后将每个文件内的url进行hashcode计算，然后存入长度为该hashcode结果值最大值得长度的BitSet中，例如hashcode最大值为99999999，那么bitset的大小就应该是9千多万位，实际上bitset大小最多可容纳2的32次方位，即4294967296,40多亿，如果存在此Hashcode则为1，否则为0，最后将所有位为1的数据取出来就去重了。
此为单bitset想法，而布隆算法其实就是多个bitset，多个hash，防止冲突而已
4）假设要你写一个网络易做图（web crawler）。由于网络间的链接错综复杂，易做图在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道易做图已经访问过那些URL。给一个URL，怎样知道易做图是否已经访问过呢？
简单的来说就是大数据量文件的查找或者去重类似这样的场景
直接贴代码:
[java]
import java.util.*;
class SimpleHash{
private int cap;
private int seed;
public SimpleHash(int c, int s){
this.cap = c;
this.seed = s;
}
public int hash(String value){
int ret = 0;
int len = value.length();
for(int i=0; i<len; i++){
ret += this.seed*ret + (int)(value.charAt(i));
}
return (cap -1) & ret;
}
}
public class BloomFilter {
private final int BIT_SIZE = 1 << 25;
private final int []seeds = new int[] {5, 7, 11, 13, 31, 37, 61};
private BitSet bitset = new BitSet(this.BIT_SIZE);
private SimpleHash []hashFunc = new SimpleHash[this.seeds.length];
public BloomFilter(){
for(int i=0; i<this.seeds.length; i++){
hashFunc[i] = new SimpleHash(this.BIT_SIZE, this.seeds[i]);
}
}
public void insert(String value){
for(SimpleHash f : this.hashFunc){
bitset.set(f.hash(value), true);
}
}
public boolean isContains(String value){
if(value == null){
return false;
}
boolean ret = true;
for(SimpleHash f : this.hashFunc){
ret = ret & bitset.get(f.hash(value));
}
return ret;
}
public static void main(String []args){
BloomFilter bloomfilter = new BloomFilter();
@SuppressWarnings("resource")
Scanner scanner = new Scanner(System.in);
String value = null;
while(scanner.hasNext()){
value = scanner.next();
if( !bloomfilter.isContains(value)){
bloomfilter.insert(value);
}
else
{
System.out.println("String : " + value + " has exist");
}
}
}
}
