【C++练级之路】【Lv.20】位图和布隆过滤器（揭开大数据背后的秘密面纱） ...

    快乐的流畅：个人主页  


    个人专栏：《算法神殿》《数据结构天下》《进击的C++》  
    远方有一堆篝火，在为久候之人燃烧！  

---

  
引言

哈希映射的头脑，在实际中有许多运用，之前介绍的哈希表是一种经典的应用场景，而本日我们将相识其他的哈希数据结构——位图和布隆过滤器，它们在面对海量数据的场景时，有着得天独厚的优势。
一、位图

1.1 位图的概念

位图（bitset），主要用于存储和管理数据的状态。它通过使用位（bit）来表现数据的存在与否，每个位只能存储0或1，分别代表数据不存在和存在。

位图原理：哈希直接定址法
1.2 位图的优势

先来看一道面试题：
   给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】
  分析：

• 起首分析数据量巨细，40亿整数 == 160亿byte，而1G约为10亿byte，以是巨细约为16G
  
• 快速查找，我们想到哈希表，但是数据量太大，动态内存（最约莫为4G）放不下
  

---

这时，就表现出位图的用处了！
如果将每个整数以比特位的形式存储表现，那么只必要40亿bit，约为0.5G。
以是，位图的主要优势为：

• 查找速度快
  
• 节流存储空间
  

1.3 位图的模拟实现

1.3.1 成员变量与默认成员函数

1. template<size_t N>
2. class bitset
3. {
4. public:
5.         bitset()
6.         {
7.                 _bits.resize(N / 8 + 1);
8.         }
9. protected:
10.         vector<char> _bits;
11.         size_t _n = 0;//有效数据个数
12. };

复制代码

细节：

• 非类型模板参数N，表现数据量（方便开辟足够空间）
  
• vector数据类型为char，方便进行位操作
  
• 构造函数提前开辟足够的空间（+1防止整除偏差）
  

1.3.2 test

检测指定值是否存在

1. bool test(size_t x)
2. {
3.         size_t i = x / 8, j = x % 8;
4.         return _bits[i] & (1 << j);
5. }

复制代码

细节：

• i 代表第几个char，j 代表char中的第几个bit
  
• <<代表从低位向高位移动
  

1.3.3 set

存入指定值，将对应的bit设置为1

1. void set(size_t x)
2. {
3.         size_t i = x / 8, j = x % 8;
4.         if (!test(x))
5.         {
6.                 _bits[i] |= (1 << j);
7.                 ++_n;
8.         }
9. }

复制代码

细节：

• 如果检测该值不存在，则存入
  

1.3.4 reset

删除指定值，将对应的bit设置为0

1. void reset(size_t x)
2. {
3.         size_t i = x / 8, j = x % 8;
4.         if (test(x))
5.         {
6.                 _bits[i] &= ~(1 << j);
7.                 --_n;
8.         }
9. }

复制代码

细节：

• 如果检测该值存在，则删除
  

1.4 位图的缺陷

位图的最大缺陷，就是只能映射整型数据！
同时，面对数据量小且特殊的情况时，位图所斲丧的空间可能比哈希表大。
1.5 位图的应用场景

位图的一些典范应用场景包括：

• 快速查找：查抄某个数据是否在一个集合中。
  
• 排序：在某些排序算法中，位图可以用来加速排序过程。
  
• 求集合的交集、并集等：位图可以用来求解集合运算。
  
• 操作系统中磁盘块的标记：在操作系统中，位图可以用来标记磁盘块的使用状态。
  

二、布隆过滤器

2.1 布隆过滤器的概念

布隆过滤器（Bloom Filter），是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较奇妙的概率型数据结构。其特点为查找元素时，只能为判断肯定不存在大概可能存在。

布隆过滤器原理：哈希除留余数法
简单明确：布隆过滤器 = 位图 + 一系列哈希化函数
2.2 布隆过滤器的优势

前面讲到，位图只能映射整型，而布隆过滤器可以映射差别类型，此中运用最多的是string类。为什么可以映射差别类型呢？正是因为运用了哈希化函数，将差别类型转换为整型，映射在位图上。
当然，布隆过滤器最焦点的头脑，是通过增加哈希化函数，低落哈希辩论的概率。它不再是一 一映射的关系，而是将一个值映射到多个地址，从而低落了值与值之间辩论的概率。
以是，布隆过滤器比位图空间使用率更高，尤其在数据密度较低时。数据量很大时，布隆过滤器可以表现全集，其他数据结构不能。
2.3 布隆过滤器的模拟实现

2.3.1 成员变量

1. template<size_t N,
2.         size_t X = 5,//关联系数
3.         class K = string,
4.         class Hash1 = BKDRHash,
5.         class Hash2 = APHash,
6.         class Hash3 = DJBHash>
7. class BloomFilter
8. {
9. public:
10. protected:
11.         bitset<N * X> _bs;
12. };

复制代码

细节：

• 插入的数据量N和布隆过滤器长度之间，存在一个最佳系数X（根据公式盘算，哈希化函数数量为3时，最佳系数为5）
  
• 布隆过滤器大部分场景处置惩罚string，以是这里默认给出string和相关哈希化函数
  
• 底层使用bitset，进行复用
  

想知道公式来源和推导，请移步这篇文章~
2.3.2 test

1. bool test(const K& key)
2. {
3.         size_t len = N * X;
4.         size_t i1 = Hash1()(key) % len;
5.         size_t i2 = Hash2()(key) % len;
6.         size_t i3 = Hash3()(key) % len;
8.         return _bs.test(i1) && _bs.test(i2) && _bs.test(i3);
9. }

复制代码

细节：

• 如果有一个位置为false，则为false
  
• 全为true，才返回true（可能有误判）
  

2.3.3 set

1. void set(const K& key)
2. {
3.         size_t len = N * X;
4.         size_t i1 = Hash1()(key) % len;
5.         size_t i2 = Hash2()(key) % len;
6.         size_t i3 = Hash3()(key) % len;
8.         _bs.set(i1);
9.         _bs.set(i2);
10.         _bs.set(i3);
11. }

复制代码

细节：插入元素时，分别将对应的多个映射位置都进行更改
2.3.4 哈希化

1. struct BKDRHash
2. {
3.         size_t operator()(const string& s)
4.         {
5.                 size_t hash = 0;
6.                 for (auto& ch : s)
7.                 {
8.                         hash = hash * 31 + ch;
9.                 }
10.                 return hash;
11.         }
12. };
14. struct APHash
15. {
16.         size_t operator()(const string& s)
17.         {
18.                 size_t hash = 0;
19.                 for (long i = 0; i < s.size(); ++i)
20.                 {
21.                         if ((i & 1) == 0)
22.                         {
23.                                 hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
24.                         }
25.                         else
26.                         {
27.                                 hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
28.                         }
29.                 }
30.                 return hash;
31.         }
32. };
34. struct DJBHash
35. {
36.         size_t operator()(const string& s)
37.         {
38.                 size_t hash = 5381;
39.                 for (auto& ch : s)
40.                 {
41.                         hash += (hash << 5) + ch;
42.                 }
43.                 return hash;
44.         }
45. };

复制代码

细节：这里选取了评分前三的string哈希化函数，欲知详情，请移步这篇文章~
2.4 布隆过滤器的缺陷

由于其本身特性（一个值拥有多个映射位置），肯定会导致存在误判！这种特性实在说两面一体的，既能带来优势（精准快速判断肯定不存在），也会带来缺陷（存在会误判）。
还有一个性子，就是不存储元素本身。这也可以说既是优点也是缺点，关键是看怎么使用。这在某些对保密要求比较严酷的场合有很大优势。
最后，一样平常布隆过滤器不支持删除操作。因为一个映射位置可能对应不止一个值，删除可能导致数据庞杂。
2.5 布隆过滤器的应用场景

布隆过滤器的一些典范应用场景包括：

• 防止垃圾邮件：在电子邮件系统中，布隆过滤器可以用来过滤已知的垃圾邮件发送者。
  
• 搜索引擎：在搜索引擎中，布隆过滤器可以用来快速判断某个URL是否已经被爬虫访问过，从而制止重复爬取。
  
• 数据库缓存：在数据库缓存中，布隆过滤器可以用来判断某个数据是否已经在缓存中，从而制止对数据库的频仍查询。
  
• 数据安全：在数据安全范畴，布隆过滤器可以用来判断某个数据是否属于黑名单，从而提供额外的安全保障。
  

三、哈希表、位图和布隆过滤器的对比

3.1 表格对比

数据结构时间复杂度空间使用率准确性映射类型哈希表O(1)低准确任意位图O(1)高准确整型布隆过滤器O(k)极高不准确任意 此中k为哈希化函数的个数，通常这个值很小（本文取k = 3）
3.2 分析对比

• 哈希表和位图在查询时间复杂度上都是 O(1)，但它们的应用场景和数据结构有所差别。哈希表适用于一样平常的键值对存储和查询，而位图适用于处置惩罚大量连续整数的集合。
  
• 布隆过滤器在查询时间复杂度上稍逊于哈希表和位图，但由于其空间效率高且适用于快速判断元素是否存在的场景，因此在某些特定应用中仍然非常有效。必要注意的是，布隆过滤器存在误报率，且通常不支持删除操作。
  

    真诚点赞，手有余香   

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。