当前位置： 首页 > article >正文

【数据结构】从位图到布隆过滤器

article 2025/3/4 4:21:45

位图的引入

         在学习位图之前，我想先和大家谈谈我们之前学习过的搜索元素的方式都有哪些，首先肯定是大家学习完基本语法就学会了的暴力查找，通过遍历整个区间来搜索某个元素；然后呢，大家可能还学习过二分查找，对于排过序的数组，使用二分查找的时间复杂度是O(logN)；再然后，可能还学习过搜索树，二叉树在平衡的前提下查找/插入/删除的时间复杂度是O(logN)，但极端情况下（二叉树严重不平衡），这些操作的时间复杂度会退化到O(N)，而AVL树和红黑树通过旋转保证二叉树的平衡性，将这些操作的时间复杂度稳定在O(logN)；再然后，大家可能接触过哈希表，通过以空间换时间的方式，用元素的关键字和位置建立映射，查找元素只需要通过关键字得到下标就能够直接访问，在不发生哈希冲突时，查找元素的时间复杂度是O(1)。
        前面我们提到的这些方式都能够搜索元素，并且除了暴力查找，都挺优秀的，但是有一个缺点，那就是查找时占用内存空间太大了，请大家思考一个问题：

给定40亿个不重复的无符号整数，在没排过序的情况下，如何能够快速判断一个数是否存在于这些数中？

让我们计算一下，40亿个不重复的无符号整数，需要的空间就是差不多4*1024*1024*1024个int（4字节），也就是4*4*1024*1024*1024字节=16G，这么大的内存空间，使用前面提到的这些方式都不好使了！

        但其实我们可以发现一件事，前面的这些方式都是用4个字节（32个比特位）来存放一个整数，但是我们其实最关心的是这个数存在还是不存在，只需要1和0就行了，一个比特位就能够判断出这个数存不存在。那这个数的大小怎么表示呢？我们就用这个比特位的位置来表示它的大小。

所以说我们一个比特位就能完成先前用32个比特位才能完成的判断，那么判断40亿个不重复的整数就只需要0.5G的内存空间就行了！

        现在我们给出位图的定义：

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用
来判断某个数据存不存在的。

位图的实现

        我们前面说了，位图就是用比特位来表示数的存在状态，那么具体是怎么实现的呢？口说无凭，接下来让我们自己设计一个位图！

        为了用很多个比特位来表示很多个数，我们就可以用int数组来承载比特位，假设一个数是n，那么通过n/32能得出这个比特位在第几个整型中，通过n%32能得出这个比特位在这个整型的第几个比特位中（除以32和取模32是因为int的大小是32位）

        至于操作，根据我们前面的描述，位图最需要提供的是：

  1. 将某个比特位的值置为1
  2. 将某个比特位的值置为0
  3. 判断某个比特位的值是0还是1

        接下来上代码！

#include <iostream>
#include <vector>

template<size_t N>
class bit_set
{
public:
    bit_set()
    {
        _bits.resize(N/32 + 1, 0);
    }
    void set(size_t n) // 将位图的第n个比特位设置为1
    {
        int i = n / 32; // 这个数在第几个整型
        int j = n % 32; // 这个数在该整型的第几个比特位
        _bits[i] |= (1 << j); // 与除了j位置为1其它位置都为0的数按位或
    }
    void reset(size_t n) // 将位图的第n个比特位设置为0
    {
        int i = n / 32; 
        int j = n % 32; 
        _bits[i] &= ~(1 << j); // 与除了j位置为0其它位置都为1的数按位与
    }
    bool test(size_t n) // 判断位图对应位是否为1
    {
        int i = n / 32; 
        int j = n % 32; 
        return _bits[i] & (1 << j); // 与除了j位置为1其它位置都为0的数按位与
    }
private:
    std::vector<int> _bits;
};

在注释中解释了代码的含义，由于篇幅有限，我就不作详细讲解了，大家可以自己找几个数算算就懂啦。

位图的延展应用

1. 给定100亿个整数，找出其中只出现一次的整数？

        要找出只出现一次的整数，也就是说我们现在需要三种状态：没出现过、出现一次、出现两次及以上（00， 01， 10），我们可以设计一个包含两个位图的数据结构，当一个整数不存在时，两个位图的对应比特位都设置为0；当一个整数出现一次时，第一个位图对应位设置为0，另一个位图对应位设置为1；当出现一次以上时，第一个位图对应位设置为1，另一个位图对应位设置为0。

2. 给定两个文件，分别有100亿个整数，只有1G的内存，如何找到文件交集？

    两个文件的整数各自映射到一个位图中，两个位图都为1的位置就是交集的值。

布隆过滤器的引入

        请大家思考这样一个场景，我们设计了一个网络爬虫，每天需要处理10亿条URL的去重，该用什么数据结构解决呢？大家的第一反应可能是哈希表，但通过前面我们的学习，想必大家也认识到了，使用传统哈希表的话，内存压根存不下这么多东西，而去重操作实际上不需要存放数据本身，我们仍然只需要判断是否存在，把存在的数据去除即可，这正好非常适合用位图解决！

        但是位图的位置仍然是使用哈希函数计算的，不可避免地会出现哈希冲突，也就是说，我们的判断可能是不准确的，难道就只能这么放弃了吗！当然不是，一个叫布隆的大佬觉得，既然使用哈希会发生哈希冲突，那么使用多个哈希把一个元素映射到好几个位置，不就降低了冲突的概率了吗，而且我们的位图是用来判断元素是否存在于集合中的，发生哈希冲突意味着当位图认为元素存在时，元素不一定存在（这个位置可能和其它存在的元素的哈希值冲突），但是当位图认为元素不存在时，这个元素一定不存在呀！这不是正好可以用来过滤不存在的数据吗 ！

        这就是Burton Howard Bloom在1970年提出的布隆过滤器的思想，这是一种概率型的数据结构，可以告诉我们某个元素一定不存在和可能存在。

布隆过滤器的实现

        使用初始为0，位数为m的比特位图+和k个独立的哈希函数实现，当需要插入元素时，使用几个不同的哈希函数计算出几个哈希值，相当于将该元素映射到位图的这几个比特位；当进行查找元素时，布隆过滤器判断这个元素不存在时，这个元素肯定不存在于集合中；但是判断这个元素存在时，由于可能出现哈希冲突，这个元素也可能不存在于集合中。

        接下来上代码！

#include "bitset.hpp" // 我们刚刚自己写的位图，当然库中也有（好像有bug）
#include <string>

using namespace std;

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, 
    class HashFunc2 = APHash, 
    class HashFunc3 = DJBHash>
class BloomFilter
{
public:
    void set(const K& key)
    {
        size_t pos1 = HashFunc1()(key) % N + 1;
        size_t pos2 = HashFunc2()(key) % N + 1;
        size_t pos3 = HashFunc3()(key) % N + 1;

        _bs.set(pos1);
        _bs.set(pos2);
        _bs.set(pos3);
    }
    bool test(const K& key)
    {
        size_t pos1 = HashFunc1()(key) % N + 1;
        size_t pos2 = HashFunc2()(key) % N + 1;
        size_t pos3 = HashFunc3()(key) % N + 1;

        if(_bs.test(pos1) == false) return false;
        if(_bs.test(pos2) == false) return false;
        if(_bs.test(pos3) == false) return false;

        return true;
    }
private:
    bit_set<N> _bs;
};

布隆过滤器的注意事项

布隆过滤器的局限性？

  布隆过滤器只能用于判断元素是否存在，而不能获取元素

  传统的布隆过滤器只能插入元素，而不能删除元素（但可以通过引用计数实现）

布隆过滤器的价值？

        布隆过滤器可以快速准确地判断元素不存在的情况，并且占用的空间远小于哈希表，因此可以像过滤器一样筛选掉不存在的元素，而即使过滤器会误判元素存在，由于可以通过调整位图大小和哈希函数的数量以降低误判率，因此只要用户有需求，完全可以过滤掉绝大多数不存在的元素，接下来只需要对剩下的一小部分元素判断是否存在即可，这样判断的开销就大大降低了！

布隆过滤器的应用场景？

        由于布隆过滤器可以快速准确地判断元素不存在的情况，并且占用的空间远小于哈希表，所以可以用于筛选/过滤信息

        缓存穿透防护：快速过滤不存在的数据请求（如Redis缓存未命中时，可以不直接访问数据库，而是再用布隆过滤器过滤一遍）

        网络爬虫：使用少量空间快速准确地取出重复URL，避免重复抓取


http://www.kler.cn/a/567912.html

相关文章：

  • 新时代，科技助力运动旅游开启新潮流
  • Android 数据库查询对比（APN案例）
  • 【Django REF】Django REF 常用知识点汇总
  • Qt 自带颜色属性
  • LVS+Keepalived 高可用集群搭建
  • 智能图像处理平台：图片管理
  • MySQL DBA技能指南
  • 低代码与开发框架的一些整合[3]
  • 从“0”开始入门PCB之（1）--PCB的结构与制作工艺
  • Halcon算子 binary_threshold、auto_threshold、dyn_threshold
  • 理解文件系统
  • Suspense 使用方法
  • 机器学习决策树
  • 【JavaEE进阶】Spring Boot 日志
  • 线程安全问题
  • PyCharm社区版如何运行Django工程？
  • 网络安全内参
  • 数据结构与算法：二叉树
  • C++ Qt OpenGL渲染FFmpeg解码后的视频
  • CMS Made Simple v2.2.15远程命令执行漏洞（CVE-2022-23906）