【数据结构】布隆过滤器

1.布隆过滤器的引入：
我们知道，在海量整形数中查找一个数字是采用位图来完成的；如果要在海量的字符串中查找一个字符串是否在其中，位图就是无法解决的，所以引入了布隆过滤器。

2.布隆过滤器的概述：
布隆过滤器是由布隆这个人提出的，它是由一系列的二进制向量和一些映射函数来实现的，它主要用于检索一个字符串是否在一个集合中，并且空间效率和查询时间都是远远超过一般的算法，还可以表示全集，其他数据结构并不能~但是他也是有一定的缺点：有一定的误判性。
为什么会存在误判性？
当两个字符串通过某一个映射函数投影到同一个位置时，我们就会将对应位置为1，查询的时候，这一位为1，并不能保证两个串都存在~只能保证至少有一个存在~当这一位为0时，这个字符串一定是不存在的，所以~~**不存在是准确的，存在是不准确的**~
为了降低误判，我们采取一种措施：根绝不同的哈希函数将一个字符串映射到不同的几个位，只有当这几个位同时为1时，才能保证这个字符串存在（当投影的位数越多，误判率越低）
根据布隆过滤器的 “存在是不准确的，不存在是准确的”这一特性，布隆过滤器一般用于
在用户进行某些网站或者应用软件登录时，系统先会在布隆过滤器中查找，如果不存在这个信息，提示错误退出~否则检查用户输入的用户名是否在数据库（存储用户信息）中，如果存在，才允许登录。
布隆过滤器一般不允许删除操作，因为某个位有可能是多个字符投影来的~我们不能随随便便将该位置为0。要想进行删除操作，就必须引入引用计数~引用计数不能使用一个位或者一个字节来存储（一个字节最多表示0~255，256个数字），必须采用一个整形数，这样空间的使用，就一下子多了起来~

3.布隆过滤器的实现代码

#pragma once
#include"BitMap.hpp"
#include<string>

template <typename K>
struct __HashFunc1
{
    size_t BKDRHash(const char* str)
    {
        register size_t hash = 0;
        size_t ch = 0;
        while(ch = (size_t)*str++)
        {
            hash = hash * 131 + ch;
        }
        return hash;
    }
    size_t operator()(const  string& key)
    {
        return BKDRHash(key.c_str());
    }
};
template<typename K>
struct __HashFunc2
{
    size_t SDBMHash(const char* str)
    {
        register size_t hash = 0;
        size_t ch = 0;
        while(ch = (size_t)*str++)
        {
            hash = hash * 65599 + ch;
        }
        return hash;
    }
    size_t operator()(const  string& key)
    {
        return SDBMHash(key.c_str());
    }
};
template<typename K>
struct __HashFunc3
{
    size_t RSHash(const char* str)
    {
        register size_t hash = 0;
        size_t magic = 63689;
        size_t ch = 0;
        while(ch = (size_t)*str++)
        {
            hash = hash * magic + ch;
            magic *= 378551;
        }
        return hash;
    }
    size_t operator()(const  string& key)
    {
        return RSHash(key.c_str());
    }
};
template<typename K>
struct __HashFunc4
{
    size_t RSHash(const char* str)
    {
        register size_t hash = 0;
        size_t magic = 63689;
        size_t ch = 0;
        for(long i = 0; ch = (size_t)*str ++; ++i)
        {
            if((i & 1) == 0)
                hash ^= ((hash << 7) ^ ch ^(hash >> 3));
            else
                hash ^= ((hash << 11) ^ ch ^(hash >> 5));
        }
        return hash;
    }
    size_t operator()(const  string& key)
    {
        return RSHash(key.c_str());
    }
};
template<typename K>
struct __HashFunc5
{
    size_t RSHash(const char* str)
    {
        if(!*str)
            return 0;
        register size_t hash = 1315423911;
        size_t magic = 63689;
        size_t ch = 0;
        while(ch = (size_t)*str++)
        {
            hash ^= ((hash << 5) + ch + (hash >> 2));
        }
        return hash;
    }
    size_t operator()(const  string& key)
    {
        return RSHash(key.c_str());
    }
};
template<typename K = string,typename HashFunc1 = __HashFunc1<K>,typename HashFunc2 = __HashFunc2<K>,typename HashFunc3 = __HashFunc3<K>,typename HashFunc4 = __HashFunc4<K>,typename HashFunc5 = __HashFunc5<K> >
class BloomFilter
{
public:
    BloomFilter(size_t num)
        :_bitMap(num * 5),_range(num * 5)
    {}

    void Set(const K& key)
    {
        size_t hash1 = HashFunc1()(key) % _range;
        size_t hash2 = HashFunc2()(key) % _range;
        size_t hash3 = HashFunc3()(key) % _range;
        size_t hash4 = HashFunc4()(key) % _range;
        size_t hash5 = HashFunc5()(key) % _range;

        _bitMap.Set(hash1);
        cout << hash1 <<endl;
        _bitMap.Set(hash2);
        cout << hash2 <<endl;
        _bitMap.Set(hash3);
        cout << hash3 <<endl;
        _bitMap.Set(hash4);
        cout << hash4 <<endl;
        _bitMap.Set(hash5);
        cout << hash5 <<endl;
    }

    bool Test(const K& key)
    {
        size_t hash1 = HashFunc1()(key) % _range;
        if(_bitMap.Test(hash1) == 0)
            return false;
        size_t hash2 = HashFunc2()(key) % _range;
        if(_bitMap.Test(hash2) == 0)
            return false;
        size_t hash3 = HashFunc3()(key) % _range;
        if(_bitMap.Test(hash3) == 0)
            return false;
        size_t hash4 = HashFunc4()(key) % _range;
        if(_bitMap.Test(hash4) == 0)
            return false;
        size_t hash5 = HashFunc5()(key) % _range;
        if(_bitMap.Test(hash5) == 0)
            return false;

        return true;
    }
private:
    BitMap _bitMap;
    size_t _range;
};

void TestBloomFilter()
{
    BloomFilter<> bf(5);
    bf.Set("_bitMap.Test(hash2) == 0");
    cout << endl;
    bf.Set("_bitMap.Test(hash3) == 0");
    cout << endl;
    bf.Set("_bitMap.Test(hash4) == 0");
    cout << endl;
    cout<<bf.Test("_bitMap.Test(hash2) == 0")<<endl;
    cout<<bf.Test("??????")<<endl;
    cout<<bf.Test("_bitMap.Test(hash4) == 0")<<endl;
}

4.带删除操作的布隆过滤器：

template <typename K>
struct __HashFunc1
{
    size_t BKDRHash(const char* str)
    {
        register size_t hash = 0;
        size_t ch = 0;
        while(ch = (size_t)*str++)
        {
            hash = hash * 131 + ch;
        }
        return hash;
    }
    size_t operator()(const  string& key)
    {
        return BKDRHash(key.c_str());
    }
};
template<typename K>
struct __HashFunc2
{
    size_t SDBMHash(const char* str)
    {
        register size_t hash = 0;
        size_t ch = 0;
        while(ch = (size_t)*str++)
        {
            hash = hash * 65599 + ch;
        }
        return hash;
    }
    size_t operator()(const  string& key)
    {
        return SDBMHash(key.c_str());
    }
};
template<typename K>
struct __HashFunc3
{
    size_t RSHash(const char* str)
    {
        register size_t hash = 0;
        size_t magic = 63689;
        size_t ch = 0;
        while(ch = (size_t)*str++)
        {
            hash = hash * magic + ch;
            magic *= 378551;
        }
        return hash;
    }
    size_t operator()(const  string& key)
    {
        return RSHash(key.c_str());
    }
};
template<typename K>
struct __HashFunc4
{
    size_t RSHash(const char* str)
    {
        register size_t hash = 0;
        size_t magic = 63689;
        size_t ch = 0;
        for(long i = 0; ch = (size_t)*str ++; ++i)
        {
            if((i & 1) == 0)
                hash ^= ((hash << 7) ^ ch ^(hash >> 3));
            else
                hash ^= ((hash << 11) ^ ch ^(hash >> 5));
        }
        return hash;
    }
    size_t operator()(const  string& key)
    {
        return RSHash(key.c_str());
    }
};
template<typename K>
struct __HashFunc5
{
    size_t RSHash(const char* str)
    {
        if(!*str)
            return 0;
        register size_t hash = 1315423911;
        size_t magic = 63689;
        size_t ch = 0;
        while(ch = (size_t)*str++)
        {
            hash ^= ((hash << 5) + ch + (hash >> 2));
        }
        return hash;
    }
    size_t operator()(const  string& key)
    {
        return RSHash(key.c_str());
    }
};
template<typename K = string,typename HashFunc5 = __HashFunc5<K> >
class BloomFilter
{
public:
    BloomFilter(size_t num)
    {
        _refBitMap.resize(num * 5);
        _range = num * 5;
    }

    void Set(const K& key)
    {
        size_t hash1 = HashFunc1()(key) % _range;
        size_t hash2 = HashFunc2()(key) % _range;
        size_t hash3 = HashFunc3()(key) % _range;
        size_t hash4 = HashFunc4()(key) % _range;
        size_t hash5 = HashFunc5()(key) % _range;

        //_bitMap.Set(hash1);
        _refBitMap[hash1]++;
        cout << hash1 <<endl;
        _refBitMap[hash2]++;
        cout << hash2 <<endl;
        _refBitMap[hash3]++;        
        cout << hash3 <<endl;
        _refBitMap[hash4]++;
        cout << hash4 <<endl;
        _refBitMap[hash5]++;
        cout << hash5 <<endl;
    }

    bool Test(const K& key)
    {
        size_t hash1 = HashFunc1()(key) % _range;
        if(_refBitMap[hash1] == 0)
            return false;
        size_t hash2 = HashFunc2()(key) % _range;
        if(_refBitMap[hash2] == 0)
            return false;
        size_t hash3 = HashFunc3()(key) % _range;
        if(_refBitMap[hash3] == 0)
            return false;
        size_t hash4 = HashFunc4()(key) % _range;
        if(_refBitMap[hash4] == 0)
            return false;
        size_t hash5 = HashFunc5()(key) % _range;
        if(_refBitMap[hash5] == 0)
            return false;

        return true;
    }
    bool ReSet(const string& key)
    {
        size_t hash1 = HashFunc1()(key) % _range;
        size_t hash2 = HashFunc2()(key) % _range;
        size_t hash3 = HashFunc3()(key) % _range;
        size_t hash4 = HashFunc4()(key) % _range;
        size_t hash5 = HashFunc5()(key) % _range;

        if (_refBitMap[hash1] == 0
            || _refBitMap[hash2] == 0
            || _refBitMap[hash3] == 0
            || _refBitMap[hash4] == 0
            || _refBitMap[hash5] == 0)
        {
            return false;
        }

        _refBitMap[hash1]--;
        _refBitMap[hash2]--;
        _refBitMap[hash3]--;
        _refBitMap[hash4]--;
        _refBitMap[hash5]--;


    }
private:
    vector<size_t> _refBitMap;
    size_t _range;
};

void TestRefBloomFilter()
{
    BloomFilter<> bf(5);
    bf.Set("_bitMap.Test(hash2) == 0");
    cout << endl;
    bf.Set("_bitMap.Test(hash3) == 0");
    cout << endl;
    bf.Set("_bitMap.Test(hash4) == 0");
    cout << endl;

    bf.ReSet("_bitMap.Test(hash4) == 0");

    cout<<bf.Test("_bitMap.Test(hash2) == 0")<<endl;
    cout<<bf.Test("杨同学")<<endl;
    cout<<bf.Test("_bitMap.Test(hash4) == 0")<<endl;
}