GUAVA 의 부 릉 필터

부 릉 필터
블 룸 필터 (Bloom Filter) 는 Burton Howard Bloom 이 1970 년 에 제기 한 것 으로 space efficient 의 확률 형 데이터 구조 로 하나의 요소 가 집합 에 있 는 지 여 부 를 판단 하 는 데 사용 된다.스 팸 메 일 을 걸 러 내 는 흑백 명단 방법, 파충류 (Crawler) 의 주소 판정 모듈 등에 자주 사용 된다.해시 표 는 요소 가 집합 에 있 는 지 여 부 를 판단 하 는 데 도 사용 되 지만, 부 릉 필 터 는 해시 표 의 1 / 8 또는 1 / 4 의 공간 복잡 도 만 있 으 면 같은 문 제 를 완성 할 수 있다.부 릉 필 터 는 요 소 를 삽입 할 수 있 지만 기 존 요 소 를 삭제 할 수 없습니다.그 중의 요소 가 많 을 수록 false positive rate (오보 율) 가 크 지만 false negative (누 보) 는 불가능 합 니 다.
알고리즘 설명
empty Bloom filter 는 m bits 가 있 는 bit array 로 모든 bit 비트 가 0 으로 초기 화 됩 니 다.또한 k 개의 서로 다른 hash function 을 정의 합 니 다. 각각 uniform random distribution 으로 요소 hash 를 m 개의 서로 다른 위치 에 있 는 하나 로 정의 합 니 다.아래 소개 에서 n 은 요소 수 이 고 m 는 부 릉 필터 나 해시 표 의 slot 수 이 며 k 는 부 릉 필터 의 재 hash function 수 입 니 다.
하나의 요 소 를 추가 하기 위해 서 는 k 개의 hash function 으로 hash 를 Bloom filter 의 k bit 위 치 를 얻 고 이 k 개의 bit 위 치 를 1 로 가 져 옵 니 다.
query 하나의 요 소 를 위해 집합 여 부 를 판단 하기 위해 k 개의 hash function 으로 hash 를 k 비트 비트 비트 로 얻 습 니 다.이 k bits 가 모두 1 이면 이 요 소 는 집합 중 입 니 다.그 중 한 명 이 1 이 아니라면 이 요 소 는 집합 에 있 지 않 습 니 다 (있 으 면 add 에 대응 하 는 k 개의 bits 위 치 를 1 로 하기 때 문 입 니 다).
reove 요 소 를 허용 하지 않 습 니 다. 그러면 해당 하 는 k 개의 bits 위 치 를 0 으로 하고 그 중에서 다른 요소 가 대응 하 는 위치 가 있 을 수 있 기 때 문 입 니 다.따라서 reove 는 false negative 를 도입 하 는데 이것 은 절대 허용 되 지 않 는 다.
k 가 크 면 k 개의 독립 된 hash function 을 설계 하 는 것 은 비 현실 적 이 고 어렵다.출력 범위 가 매우 큰 hash function (예 를 들 어 MD5 에서 발생 하 는 128 bits 수) 에 대해 서로 다른 bit 비트 의 상관 성 이 매우 작 으 면 이 출력 을 k 부 로 나 눌 수 있 습 니 다.또는 k 개의 서로 다른 초기 값 (예 를 들 어 0, 1, 2,..., k - 1) 을 요소 와 결합 하여 feed 를 hash function 에 주어 k 개의 다른 수 를 만 들 수 있 습 니 다.
add 의 요소 가 너무 많 을 때 n / m 가 너무 클 때 (n 은 요소 수, m 는 Bloom filter 의 bits 수) false positive 가 너무 높 을 수 있 습 니 다. 이때 filter 를 다시 구성 해 야 하지만 이런 경 우 는 상대 적 으로 드 물 습 니 다.
간단 한 부 릉 필터 구현

public   class  SimpleBloomFilter {  

     private   static   final   int    DEFAULT_SIZE  =   2   <<   24 ;  
     private   static   final   int [] seeds         =   new   int [] {  7 ,  11 ,  13 ,  31 ,  37 ,  61 , };  
     private  BitSet             bits          =   new  BitSet(DEFAULT_SIZE);  
     private  SimpleHash[]       func          =   new  SimpleHash[seeds.length];  
     public   static   void  main(String[] args) {  
        String value  =   " [email protected] " ;  
        SimpleBloomFilter filter  =   new  SimpleBloomFilter();  
        System.out.println(filter.contains(value));  
        filter.add(value);  
        System.out.println(filter.contains(value));  
    }  
     public  SimpleBloomFilter() {  
         for  ( int  i  =   0 ; i  <  seeds.length; i ++ ) {  
            func[i]  =   new  SimpleHash(DEFAULT_SIZE, seeds[i]);  
        }  
    }  
     public   void  add(String value) {  
         for  (SimpleHash f : func) {  
            bits.set(f.hash(value),  true );  
        }  
    }  
     public   boolean  contains(String value) {  
         if  (value  ==   null ) {  
             return   false ;  
        }  
         boolean  ret  =   true ;  
         for  (SimpleHash f : func) {  
            ret  =  ret  &&  bits.get(f.hash(value));  
        }  
         return  ret;  
    }  
     public   static   class  SimpleHash {  
         private   int  cap;  
         private   int  seed;  
         public  SimpleHash( int  cap,  int  seed) {  
             this .cap  =  cap;  
             this .seed  =  seed;  
        }  
         public   int  hash(String value) {  
             int  result  =   0 ;  
             int  len  =  value.length();  
             for  ( int  i  =   0 ; i  <  len; i ++ ) {  
                result  =  seed  *  result  +  value.charAt(i);  
            }  
             return  (cap  -   1 )  &  result;  
        }  
    }  
}  

GUAVA 의 부 릉 필터

import java.nio.charset.Charset;

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnel;
import com.google.common.hash.PrimitiveSink;

public class BloomTest {
    //       
    private long size = 1024 * 1024;

    private BloomFilter bloom = BloomFilter.create(new Funnel() {
        @Override
        public void funnel(String from, PrimitiveSink into) {
            //                 
            into.putString((CharSequence) from, Charset.forName("UTF-8"));
        }
    }, size);

    public void fun() {
        //          
        bloom.put("     ");
        //   
        boolean mightContain = bloom.mightContain("     ");
        System.out.println(mightContain);
    }

    public static void main(String[] args) {
        BloomTest blBoolmTest = new BloomTest();
        blBoolmTest.fun();
    }
}