[데이터 구조] 부 릉 필터 - 비트 맵 확장

이 박문 은 요소 가 존재 하 는 지 를 신속하게 검색 할 수 있 는 데이터 구조 인 부 릉 필 터 를 소개 하 는 데 목적 을 둔다.본 고 는 비트 맵 과 부 릉 필터 의 비교 에서 이 두 가지 데이터 구 조 를 사용 하 는 서로 다른 상황 을 토론 했다.부 릉 필터 의 주요 사용 장면 도 소개 했다.
부 릉 필터 도입
이전에 비트 맵 을 배 웠 기 때문에 하나의 정수 가 하나의 집합 에 존재 하 는 지 신속하게 판단 할 수 있다
그러나 현실 생활 에서 우 리 는 문자열 을 많이 사용 하 는데 비트 맵 만 으로 는 문자열 을 처리 할 수 없어 서 비트 맵 을 가 져 왔 다.
부 릉 필터 의 사상
해시 표를 배 운 후에 우 리 는 문자열 해시 알고리즘 을 알 고 있 습 니 다. 문자열 을 key 값 으로 변환 한 다음 비트 맵 에 저장 할 수 있 습 니 다.
그러나 문자열 해시 알고리즘 을 통 해 해시 충돌 (여러 문자열 이 같은 key 값 으로 매 핑) 을 일 으 킬 수 있 습 니 다. 그러면 오심 율 이 높 습 니 다.
부 릉 필터 의 실현
따라서 부 릉 필 터 는 여러 문자열 의 해시 알고리즘 을 동시에 사용 하여 매 핑 하 는 것 입 니 다.
만약 에 우리 가 5 개의 문자열 해시 알고리즘 으로 매 핑 을 한다 고 가정 하면 하나의 문자열 이 존재 하 는 지 여 부 를 판단 할 때 해당 하 는 5 개의 비트 가 동시에 존재 하 는 지 판단 하면 됩 니 다.
부 릉 필터 코드 구현

#pragma once

#include
using namespace std;

//             
#include"BitMap.h"

//           
template
struct BKDRHash
{
	size_t operator()(const T str)
	{
		register size_t hash = 0;
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash = hash * 131 + str[i];
		}
		return hash;
	}
};

template
struct SDBMHash
{
	size_t operator()(const T str)
	{
		register size_t hash = 0;
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash = 65599 * hash + str[i];
		}
		return hash;
	}
};

template
struct RSHash
{
	size_t operator()(const T str)
	{
		register size_t hash = 0;
		size_t magic = 63689;
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash = hash * magic + str[i];
			magic *= 378551;
		}
		return hash;
	}
};

template
struct APHash
{
	size_t operator()(const T str)
	{
		register size_t hash = 0;
		for (long i = 0; i < str.size(); ++i)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ str[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ str[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

template
struct JSHash
{
	size_t operator()(const T str)
	{
		if (str.empty())
			return 0;
		register size_t hash = 1315423911;
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash ^= ((hash << 5) + str[i] + (hash >> 2));
		}
		return hash;
	}
};

//       ，5 HashFunc             ，           
template,
typename HashFunc2 = SDBMHash,
typename HashFunc3 = RSHash,
typename HashFunc4 = APHash,
typename HashFunc5 = JSHash>
class BoolmFilter
{
public:
	BoolmFilter(size_t num)
		:_bp(num*2*5)
	{}

	size_t HashFunC1(const K& num)
	{
		HashFunc1 hf;
		size_t index = hf(num);
		return index;
	}
	size_t HashFunC2(const K& num)
	{
		HashFunc2 hf;
		return hf(num);
	}
	size_t HashFunC3(const K& num)
	{
		HashFunc3 hf;
		return hf(num);
	}
	size_t HashFunC4(const K& num)
	{
		HashFunc4 hf;
		return hf(num);
	}
	size_t HashFunC5(const K& num)
	{
		HashFunc5 hf;
		return hf(num);
	}
	void Set(const K &num)
	{
		//                     
		size_t hf1 = HashFunC1(num);
		size_t hf2 = HashFunC2(num);
		size_t hf3 = HashFunC3(num);
		size_t hf4 = HashFunC4(num);
		size_t hf5 = HashFunC5(num);

		//       
		//cout << hf1 << " " << hf2 << " " << hf3 << " " << hf4 << " " << hf5 << endl;

		//          
		_bp.Set(hf1);
		_bp.Set(hf2);
		_bp.Set(hf3);
		_bp.Set(hf4);
		_bp.Set(hf5);
	}

	//Reset          
	//void Reset();

	bool Find(K &num)
	{
		//    num              
		//       ，   FALSE，num     
		//    ，   TRUE，          
		int hf1 = HashFunC1(num);
		if(_bp.Find(hf1) == false)
			return false;

		int hf2 = HashFunC2(num);
		if (_bp.Find(hf2) == false)
			return false;

		int hf3 = HashFunC3(num);
		if (_bp.Find(hf3) == false)
			return false;

		int hf4 = HashFunC4(num);
		if (_bp.Find(hf4) == false)
			return false;

		int hf5 = HashFunC5(num);
		if (_bp.Find(hf5) == false)
			return false;

		return true;
	}
protected:
	//     _bp;
	BitMap _bp;
};

부 릉 필터 와 비트 맵 의 대비
비트 맵 의 장점:
하나의 정수 가 집합 에 존재 하 는 지 여 부 를 신속하게 판단 할 수 있다.
비트 맵 의 단점:
그 장점 에서 말 한 것 처럼 정수 만 판단 할 수 있 고 다른 유형의 데 이 터 를 처리 할 수 없다.
부 릉 필터 의 장점:
1. 비트 맵 을 바탕 으로 해시 알고리즘 을 이용 하여 확장 하여 문자열 형식의 데 이 터 를 처리 할 수 있 도록 합 니 다.
2. 시간 복잡 도 O (k), [K 는 문자열 해시 알고리즘 의 개 수 를 나타 낸다] 그 효율 은 다른 알고리즘 보다 훨씬 높다.
부 릉 필터 의 단점:
해시 충돌 로 인해 브 론 필 터 는 어느 정도 오심 성 이 있 습 니 다. 적 당량 의 문자열 해시 알고리즘 을 어떻게 사용 하 는 지 고려 해 야 할 문제 입 니 다.
부 릉 필터 의 오류:
문자열 해시 알고리즘 을 사용 하 는 수량 이 많 을 수록 좋 습 니까?(땡)
문자열 해시 알고리즘 이 너무 많 으 면 하나의 문자열 이 여러 자 리 를 차지 하고 충돌 할 확률 이 커진다 는 것 을 설명 한다.
따라서 적 당량 의 문자열 해시 알고리즘 을 사용 해 야 합 니 다.
부 릉 필터 의 몇 가지 주요 응용 장면:
(1) 스 팸 사이트, 메 일의 여과
(2) 파충류 중에서 웹 페이지 가 올 라 갔 는 지 여 부 를 어떻게 신속하게 판단 하 는 지도 부 릉 필터 의 사용 장소 중 하나 이다.