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");  

            }  

        }  

    }  

}