【C++ 学习 ㉖】- 布隆过滤器详解（哈希扩展）

目录

一、布隆过滤器的简介

二、布隆过滤器的实现

2.1 - BloomFilter.h

2.2 - test.cpp

---

---

一、布隆过滤器的简介

布隆过滤器（Bloom Filter）是由 Burton Howard Bloom 在 1970 年提出的一种紧凑型的、比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 "某样东西一定不存在或者可能存在"。

布隆过滤器的原理：当插入一个数据时，通过 K 个哈希函数将这个数据映射到位图结构中的 K 个比特位，并把它们都置为 1。检索时，如果 K 个比特位中的任何一个为 0，则被检索的数据一定不存在；如果都为 1，则被检索的数据可能存在（之所以说 "可能" 是误差的存在）。

---

二、布隆过滤器的实现

2.1 - BloomFilter.h

#pragma once
​
#include "bitset.h"
#include 
​
namespace yzz
{
    struct BKDRHash
    {
        size_t operator()(const std::string& str)
        {
            size_t hash = 0;
            for (const char& ch : str)
            {
                hash = hash * 131 + ch;
            }
            return hash;
        }
    };
​
    struct APHash
    {
        size_t operator()(const std::string& str)
        {
            size_t hash = 0;
            for (size_t i = 0; i < str.size(); ++i)
            {
                size_t ch = str[i];
                if ((i & 1) == 0)
                    hash ^= (hash << 7) ^ ch ^ (hash >> 3);
                else
                    hash ^= (~(hash << 11)) ^ ch ^ (hash >> 5);
            }
            return hash;
        }
    };
​
    struct DJBHash
    {
        size_t operator()(const std::string& str)
        {
            size_t hash = 5381;
            for (const char& ch : str)
            {
                hash = hash * 33 ^ ch;
            }
            return hash;
        }
    };
​
    template<size_t N, class K = std::string, 
        class Hash1 = BKDRHash, class Hash2 = APHash, class Hash3 = DJBHash>
    class BloomFilter
    {
    public:
        void set(const K& key)
        {
            _bs.set(Hash1()(key) % N);
            _bs.set(Hash2()(key) % N);
            _bs.set(Hash3()(key) % N);
        }
​
        bool test(const K& key) const
        {
            if (_bs.test(Hash1()(key) % N) == 0)
                return false;
            if (_bs.test(Hash2()(key) % N) == 0)
                return false;
            if (_bs.test(Hash3()(key) % N) == 0)
                return false;
            return true;
        }
    private:
        bitset _bs;
    };
}

各种字符串Hash函数 - clq - 博客园 (cnblogs.com)。

注意：传统的布隆过滤器不支持删除操作，因为删除一个数据，可能同时删除了其它数据，例如：

删除 "dantezhao" 的同时，也删除了 "yyj"。

Counting Bloom Filter 的出现，解决了上述问题，它将 Bloom Filter 的位数组的每一位扩展为一个小的计数器（Counter）。插入数据时，给对应的 K（K 为哈希函数的个数）个 Counter 的值分别加 1；删除数据时，给对应的 K 个 Counter 的值分别减 1。Counting Bloom Filter 通过多占用几倍的存储空间的代价，给 Bloom Filter 增加了删除操作。

2.2 - test.cpp

#include "BloomFilter.h"
#include 
using namespace std;
​
int main()
{
    yzz::BloomFilter<100> bf;
    bf.set("唐三藏");
    bf.set("白龙马");
    bf.set("孙悟空");
    bf.set("猪八戒");
    
    cout << bf.test("唐三藏") << endl;  // 1
    cout << bf.test("白龙马") << endl;  // 1
    cout << bf.test("孙悟空") << endl;  // 1
    cout << bf.test("猪八戒") << endl;  // 1
    cout << bf.test("沙悟净") << endl;  // 0
    return 0;
}