「C++」位图和布隆过滤器

💻文章目录

位图
- 概念
- 位图的实现
- 位图的应用
布隆过滤器
- 概念
- 布隆过滤器的哈希函数
- 布隆过滤器的插入
- 布隆过滤器的查找
- 布隆过滤器的删除
📓总结

位图

概念

所谓位图，就是在每一位bit位上存放某种状态，1就代表存在，0就代表不存在，因为一个数据只占用一个bit位，所以其适用于海量数据，数据无重复的场景，通常用于判断某个数据存在与否。

在这里插入图片描述

位图的实现

位图一般用于整形数据的判断，内部使用一个数组来实现，可以根据数据所占bit位来分类数据所在空间(数组的下标位置)，例如 42 是一个所占bit位位32位（4字节），我们使用 $42/32 = 1$ 来获取其所在下标位置，再通过 $42$ 来获取其所在bit位位置。

#include <iostream>
#include <vector>

template <size_t N>		//数据的个数
class bitset 
{
public:
    bitset()
        :_count(N)
    {
        _bit.resize((N >> 5)+1);
    }

    void set(size_t which)	//插入数据
    {
        if(which > _count)
            return;

        size_t index = (which >> 5);    // 获得所在下标位置 which / 32
        size_t pos = which % 32;        // 获取bit位位置
        _bit[index] |= (1 << pos);      // 将所在 bit位改为1
    }
	
    void reset(size_t which)	//重置bit位
    {
        if(which > _count)  
            return;

        size_t index = (which >> 5);
        size_t pos = which % 32;
        _bit[index] &= ~(1 << pos);
    }

    bool test(size_t which)	//查找数据
    {
        if(which > _count)
            return false;

        size_t index = (which >> 5);
        size_t pos = which % 32;
        return _bit[index] & (1 << pos);
    }
private:
    std::vector<int> _bit;	//使用vector方便操作
    size_t _count;
};

位图的应用

快速查找某个数据是否在一个集合中
排序 + 去重
求两个集合的交集、并集等
操作系统中磁盘块标记

布隆过滤器

概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间

在这里插入图片描述

布隆过滤器的哈希函数

布隆过滤器通过使用多个哈希函数来使数据冲突减少的可能性，但不是说哈希函数越多越好，一般根据业务需求来安排哈希函数的个数。

struct BKDRHash
{
	size_t operator()(const string& key)
	{
		// BKDR
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

struct APHash
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			char ch = key[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 string& key)
	{
		size_t hash = 5381;
		for(auto ch : key)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

布隆过滤器的插入

布隆过滤器通过使用多个比特位来记录数据的存在。

template<size_t N, 	//数据个数
	class K = string,		//数据类型
	class HashFunc1 = BKDRHash,	//哈希函数1
	class HashFunc2 = APHash ,	//哈希函数2
	class HashFunc3 = DJBHash>	//哈希函数3
class BloomFilter		//布隆过滤器
{
public:
	void Set(const K& key)		//记录位置
	{
		size_t hash1 = HashFunc1()(key) % N;
		size_t hash2 = HashFunc2()(key) % N;
		size_t hash3 = HashFunc3()(key) % N;

		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
	}
private:
	bit::bitset<N> _bs;	
}

布隆过滤器的查找

布隆过滤器是将一个元素存于多个比特位中，所以得通过判断每个哈希函数所对应的位置是否为零，但也因此，其查找元素是否存在时是存在误判的，如果元素存在，不能一定确定其存在，但元素不存在可以判断其一定不存在。

bool Test(const K& key)
{			//如果一个为0，则证明其不存在。
    size_t hash1 = Hash1()(key) % N;
    if (_bs.test(hash1) == false)
        return false;

    size_t hash2 = Hash2()(key) % N;
    if (_bs.test(hash2) == false)
        return false;

    size_t hash3 = Hash3()(key) % N;
    if (_bs.test(hash3) == false)
        return false;	

    return true; 	//哈希函数对应位置全部为1.
}