해시 확장 부 릉 필터

1. 부 릉 필터 도입
하나의 요소 가 지정 한 집합 에 있 는 지 판단 하 는 문제 가 있다.
우리 의 일반적인 조작 은 이 집합 을 먼저 저장 한 다음 에 지 정 된 요소 와 저 장 된 집합 중의 요 소 를 일일이 비교 하여 존재 하 는 지 여 부 를 판단 하 는 것 이다.그러나 집합 중의 요소 가 증가 함 에 따라 우리 가 필요 로 하 는 저장 공간 이 점점 커지 고 검색 속도 도 점점 느 려 진다. 이때 우 리 는 해시 표 라 는 데이터 구 조 를 생각 했다.해시 표 는 해시 함 수 를 통 해 하나의 요 소 를 비트 배열 (Bit Array) 의 한 점 으로 표시 합 니 다. 그러면 우 리 는 이 요소 에 대응 하 는 점 이 1 인지 확인 하면 이 집합 에 존재 하 는 지 여 부 를 알 수 있 습 니 다.그러나 해시 표 는 해시 충돌 문제 에 직면 하고 있 습 니 다. 우리 의 비트 배열 길이 가 m 점 이 라 고 가정 하면 해시 충돌 을 1% 로 낮 추 려 면 해시 표 에 n 개의 요 소 를 저장 하 는 것 이 만족 해 야 합 니 다. n / m < 1% 이면 이 해시 표 는 m / 100 개의 요 소 를 수용 할 수 있 습 니 다.그러나 이렇게 하면 검색 속 도 를 높 였 을 뿐 메모리 공간 이 유효 하 게 저장 되 지 않 는 다 면 어떻게 해결 해 야 할 까?사실, 우 리 는 여러 개의 Hash 함 수 를 이용 하여 해시 충돌 문 제 를 해결 할 수 있 습 니 다. 만약 에 하나의 Hash 함수 가 지정 한 집합 에 있 지 않 으 면 정말 존재 하지 않 는 것 이 아 닙 니 다.모든 해시 함수 가 지정 한 집합 에서 이 요 소 를 계산 하면 존재 할 가능성 이 높다 는 뜻 으로 해시 충돌 문 제 를 크게 해결 할 수 있 습 니 다.
일반적으로 브 론 필 터 를 사용 하 는 것 은 문자열 이 집합 에 존재 하 는 지 여 부 를 처리 하 는 데 사 용 됩 니 다. 여러 개의 해시 함 수 를 통 해 이 문자열 의 여러 개의 해시 값 을 계산 하여 이 문자열 에 대응 하 는 모든 해시 값 에 대응 하 는 bit 위 치 를 1 로 설정 합 니 다.이러한 방식 으로 문자열 을 찾 을 때 여러 개의 해시 표를 통 해 해시 값 을 계산 하고 해시 값 에 대응 하 는 bit 비트 에서 이 bit 비트 가 1 인지 아 닌 지 를 판단 합 니 다. 모두 1 이면 이 문자열 이 존재 한 다 는 것 을 표시 합 니 다. 해시 함수 에 대응 하 는 비트 가 0 이면 이 문자열 이 존재 하지 않 음 을 표시 합 니 다.그러나 주의해 야 할 것 은 브 론 필 터 는 삭제 작업 을 할 수 없습니다. 이 문자열 에 대응 하 는 bit 비트 는 다른 문자열 에 도 대응 하 는 bit 비트 일 수 있 기 때문에 삭제 작업 을 할 수 없습니다.
2. 부 릉 필터 의 구조 체 정의
위 에서 브 론 필 터 를 분석 한 결과 브 론 필 터 는 비트 맵 과 여러 개의 해시 함 수 를 결합 하여 이 루어 졌 기 때문에 브 론 필터 의 구조 체 유형 을 디자인 할 때 비트 맵 의 구조 체 와 여러 개의 해시 함 수 를 정의 해 야 한 다 는 것 을 알 수 있다.코드 는 다음 과 같 습 니 다:

#include"Bitmap.h"                                                                                                       
//          
typedef BitMapType(*BloomHash)(const char* str);
//                 
#define BloomHashCount 2
typedef struct BloomFilter{
    BitMap bm; 
    BloomHash bloom_hash[BloomHashCount];
}BloomFilter;

3. 부 릉 필터 초기 화 및 폐기
3.1 초기 화
부 릉 필터 의 구조 체 정 의 를 통 해 알 수 있 듯 이 부 릉 필 터 를 초기 화 하 는 것 은 비트 맵 과 여러 개의 해시 함 수 를 초기 화 하 는 것 입 니 다.코드 는 다음 과 같다.

//0.    
BitMapType HashFunc1(const char* str)
{                                                                                                                        
    BitMapType hash=0;
    BitMapType ch=0;
    while(ch=(BitMapType)*str++)
    {   
        hash=65599*hash+ch;
    }   
    return hash;
}
BitMapType HashFunc2(const char* str)
{
    BitMapType hash=0;
    BitMapType ch=0;
    while(ch=(BitMapType)*str++)
    {
        hash=32233*hash+ch;
    }
    return hash;
}
//1.   
void BloomFilterInit(BloomFilter* bf)
{
    //    
    if(bf==NULL)
        return;
    //     
    BitmapInit(&bf->bm,10000);                                                                                           
    //         
    bf->bloom_hash[0]=HashFunc1;
    bf->bloom_hash[1]=HashFunc2;
}

3.2 소각
부 릉 필 터 를 없 애 면 부 릉 필 터 를 원래 상태 로 초기 화 할 것 이 므 로 비트 맵 을 없 애고 해시 함수 포인 터 를 NULL 로 설정 하면 됩 니 다.코드 는 다음 과 같 습 니 다:

//2.  
void BloomFilterDestroy(BloomFilter* bf)
{
    if(bf==NULL)
        return;
    BitmapDestroy(&bf->bm);
    bf->bloom_hash[0]=NULL;
    bf->bloom_hash[1]=NULL;
}

4. 부 릉 필터 삽입 작업
문자열 을 삽입 하 는 단계: (1) 여러 개의 해시 함 수 를 통 해 이 문자열 에 대응 하 는 모든 해시 값 을 계산 합 니 다.(2) 이 해시 값 에 대응 하 는 bit 위 치 를 1 로 설정 하면 됩 니 다.
코드 는 다음 과 같 습 니 다:
부 릉 필터 찾기
지정 한 문자열 을 찾 는 절차: (1) 각 해시 함수 로 지정 한 문자열 의 해시 값 을 계산 합 니 다.(2) 이 해시 값 에 대응 하 는 bit 비트 가 1 인지 0 인지 판단 합 니 다. 어떤 해시 함수 가 대응 하 는 bit 위 치 를 0 으로 계산 하면 이 문자열 이 존재 하지 않 음 을 나타 냅 니 다.모든 해시 함수 가 계산 한 대응 하 는 bit 비트 가 1 이면 이 문자열 이 존재 합 니 다.
코드 는 다음 과 같 습 니 다:

void BloomFilterInsert(BloomFilter* bf,const char* str)
{
    //    
    if(bf==NULL||str==NULL)
        return;
    size_t i=0;
    for(i=0;ibloom_hash[i](str)%(bf->bm.capacity);
        BitmapSet(&bf->bm,hash);
    }
}

문자열 문 제 를 처리 하 는 부 릉 필터 의 기본 동작 입 니 다!