부 릉 필터 의 작업 원리 와 실례 를 실례 를 통 해 해석 하 다

부 릉 필터
부 릉 필 터 는 데이터 구조 로 비교적 교묘 한 확률 형 데이터 구조(probabilistic data structure)로 효율 적 인 삽입 과 조회 가 특징 이 며'반드시 존재 하지 않 거나 존재 할 수 있다'는 것 을 알려 줄 수 있다.
전통 적 인 List,Set,Map 등 데이터 구조 에 비해 효율 적 이 고 공간 을 차지 하 는 것 이 적 지만 정확 한 것 이 아니 라 확률 적 인 것 이 단점 이다.
부 릉 필터 의 작업 원리
길이 가 m 인 bit 형식의 배열 을 가정 합 니 다.즉,배열 의 모든 위 치 는 하나의 bit 만 차지 하고 모든 bit 는 두 가지 상태 만 있 습 니 다.0,1,모든 bit 의 초기 상 태 는 0 입 니 다.
그 다음 에 모두 k 개의 해시 함수 가 있다 고 가정 하면 이런 함수 의 출력 영역 은 m 보다 크 거나 같 을 수 있 습 니 다.그리고 이런 해시 함수 들 은 서로 독립 되 고 모든 해시 함수 가 계산 한 결 과 는 독립 적 입 니 다.같 을 수도 있 고 다 를 수도 있 습 니 다.모든 계산 한 결 과 는 m 에 나머지(%m)를 취한 다음 에 배열 의 아래 표 시 된 위 치 를 1 로 설정 합 니 다.
여기 서 m 가 13 이 고 k 가 3 인 부 릉 필 터 를 가정 하여 부 릉 필터 의 작업 원 리 를 살 펴 보 겠 습 니 다.

우리 가 부 릉 필터 에 값 을 매 핑 하려 고 할 때,먼저 세 개의 해시 함수 의 값 을 계산 한 다음 13 에 나머지 를 취하 여 대응 하 는 위치 에 매 핑 하고,그림 에 2,6,10 을 매 핑 하면 우 리 는 하나의 값 의 매 핑 을 완성 할 수 있다.

그러면 하나의 값 이 존재 하 는 지 여 부 를 어떻게 판단 합 니까?하나의 값 을 입력 할 때 세 개의 해시 함 수 를 통 해 나머지 를 취하 면 우 리 는 대응 하 는 세 개의 위 치 를 얻 을 수 있 습 니 다.우 리 는 이 세 개의 위치 가 모두 1 인지 판단 해 야 합 니 다.만약 에 모두 1 이 라면 이 값 은 저장 되 고 그렇지 않 으 면 존재 하지 않 습 니 다.
그러나 한 가지 특수 한 상황 이 있 습 니 다.앞에서 말 했 듯 이 서로 다른 해시 함수 의 계산 이 같 을 수도 있 고 다 를 수도 있 습 니 다.그리고 서로 다른 해시 함수 가 서로 다른 값 에 대해 계산 한 값 이 같 을 수도 있 습 니 다.이것 은 하나의 결 과 를 초래 합 니 다.하 쉬 와 나머지 를 통 해 얻 은 위 치 는 다른 값 에 의 해 1 이 되 었 습 니 다.우리 가 저장 한 값 이 너무 많 고 이 bit 배열 이 너무 작 습 니 다.이러한 상황 이 더 많이 발생 할 수 있 습 니 다.하나의 값 은 존재 하지 않 고 모든 위 치 는 다른 값 에 의 해 1 로 설정 되 어 오심 을 초래 했 습 니 다.여기 서 부 릉 필터 에 대해 하나의 지 표를 제 시 했 습 니 다.실수 율 p.
같은 데이터 규모 에서 서로 다른 크기 의 bit 배열 과 서로 다른 수량의 k 의 해시 함수 가 오심 율 에 대한 결과:

가장 적합 한 m(bit 배열 의 크기)와 k(해시 함수 의 수량)를 어떻게 선택 하 는 지 알 고 있 는 n(매 핑 할 가치 가 있 는 수량)과 실수 율 p 의 경우:
m 의 선택:

k 의 선택:

예 를 들 어 n=100 억,p=0.01%를 가정 합 니 다.
공식 을 통 해 m=19.19n 을 계산 하고 위로 20n,즉 2000 억 개의 bit,즉 25gb 를 추출한다.
공식 을 통 해 k=14 를 계산 해 내다.
실제 실수 율 계산:

공식 에 따라 계 산 된 실제 실수 율 은 0.006%이다.
c 언어 구현

#include <stdio.h>

#define Size 100
#define BitSIZE Size * 4 * 8
//c           4    
int bit[Size]={0};

  
int SDBMHash(char *str)
{
  unsigned int hash = 0;
  while (*str)
  {
    // equivalent to: hash = 65599*hash + (*str++);
    hash = (*str++) + (hash << 6) + (hash << 16) - hash;
  }
  return (hash & 0x7FFFFFFF);
}

int RSHash(char *str)
{
  unsigned int b = 378551;
  unsigned int a = 63689;
  unsigned int hash = 0;
 
  while (*str)
  {
    hash = hash * a + (*str++);
    a *= b;
  }
 
  return (hash & 0x7FFFFFFF);
}

int JSHash(char *str)
{
  unsigned int hash = 1315423911;
 
  while (*str)
  {
    hash ^= ((hash << 5) + (*str++) + (hash >> 2));
  }
 
  return (hash & 0x7FFFFFFF);
}


void Insert(int hash){
  
  //int value = hash%BitSIZE; ([0-3200]    )
  //int listindex = value / 32; (listindex     )
  //int bitindex = value % 32; (  )
  
  int value = hash%BitSIZE;
  int listindex = value / 32;
  int bitindex = value % 32;
  int temp = bit[listindex];
  bit[listindex] = bit[listindex] & (1 << bitindex);
  bit[listindex] = bit[listindex] | temp;
}

int Serach(int hash){
  int value = hash%BitSIZE;
  int listindex = value / 32;
  int bitindex = value % 32;
  if (bit[listindex] | (1 << bitindex)){
    return 1;
  }
  return 0;
}



int main () {
  
  char str1[] = "abc123";
  
  //           
  Insert(SDBMHash(str1));
  Insert(RSHash(str1));
  Insert(JSHash(str1));
  
  //               
  int i = 0;
  i = i+Serach(SDBMHash(str1));
  i = i+Serach(RSHash(str1));
  i = i+Serach(JSHash(str1));
  if(i == 3){
    printf("   ：%s  
",str1);
  }

  return 0;
}

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.