【C++】布隆过滤器和位图_布隆过滤器 bitset

目录

位图的概念

位图的模拟实现

模板定义

成员变量

构造函数

set函数

reset函数

test函数

总结

位图的应用

布隆过滤器的概念

布隆过滤器的模拟实现

哈希函数

BloomFilter

实现代码

注意事项

布隆过滤器的查找

布隆过滤器的删除

布隆过滤器的优缺点

---

位图的概念

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

位图的模拟实现

这是一个简单的BitSet模板类实现，用于表示和操作固定大小的位集合

模板定义

template<size_t N>
class BitSet

这是一个模板类，其中N是一个模板参数，表示BitSet的大小（即它可以包含的位的数量）。

成员变量

private:
    vector<int> _bs;

_bs是一个整数类型的向量，用于存储位集合。每个整数可以存储32个位（在大多数现代系统上，int是32位的），因此这个向量的大小取决于N`。

构造函数

BitSet()
{
    _bs.resize((N / 32) + 1, 0);
}

构造函数初始化_bs向量，使其大小足够存储N个位。由于每个整数可以存储32个位，所以需要(N / 32) + 1个整数来确保有足够的空间。每个整数初始化为0。

set函数

void set(size_t num)
{
    size_t i = num / 32;
    size_t j = num % 32;
    _bs[i] |= (1<<j);
}

set函数用于设置指定位（由num指定）为1。它首先计算位所在的整数索引i和位在该整数中的偏移量j`，然后使用按位或运算和左移操作将该位设置为1。

reset函数

void reset(size_t num)
{
    size_t i = num / 32;
    size_t j = num % 32;
    _bs[i] &= ~(1 << j);
}

reset函数用于将指定位（由num指定）重置为0。它使用与set`函数相同的计算来确定整数索引和偏移量，然后使用按位与运算和按位取反操作将该位重置为0。

test函数

bool test(size_t num)
{
    size_t i = num / 32;
    size_t j = num % 32;
 
    return _bs[i] & (1 << j);
}

test函数用于检查指定位（由num`指定）是否被设置。它返回一个布尔值，指示该位是否为1。计算整数索引和偏移量后，它使用按位与运算来检查该位是否设置。

总结

这个BitSet类提供了一个简单但高效的方式来操作固定大小的位集合。它使用整数向量来存储位，并通过计算索引和偏移量来访问和修改特定位。这种实现方式允许在常数时间内访问和修改任何位，而不需要遍历整个集合。

template<size_t N>
 class BitSet
 {
 public:
  BitSet()
  {
   _bs.resize((N / 32) + 1, 0);
  }
 
  void set(size_t num)
  {
   size_t i = num / 32;
   size_t j = num % 32;
   _bs[i] |= (1<<j);
  }
 
  void reset(size_t num)
  {
   size_t i = num / 32;
   size_t j = num % 32;
   _bs[i] &= ~(1 << j);
  }
 
  bool test(size_t num)
  {
   size_t i = num / 32;
   size_t j = num % 32;
 
   return _bs[i] & (1 << j);
  }
 private:
  vector<int> _bs;
 };

位图的应用

1. 快速查找某个数据是否在一个集合中

2. 排序 + 去重

3. 求两个集合的交集、并集等

4. 操作系统中磁盘块标记

布隆过滤器的概念

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

布隆过滤器的模拟实现

这段代码包含了三个哈希函数（BKDRHash, APHash, DJBHash）和一个布隆过滤器（BloomFilter）的实现。我会逐个解释每个部分的功能和特性。

哈希函数

哈希函数通常用于将任意长度的数据映射到固定长度的哈希值。在布隆过滤器中，哈希函数用于生成键的多个索引位置，以便将这些位置在布隆过滤器中设置为1。

1. BKDRHash： 使用了一个简单的哈希算法，通过乘以31（一个常见的素数）然后加上当前字符的ASCII值来生成哈希值。

2. APHash： 这个哈希函数根据字符在字符串中的位置（偶数或奇数）使用不同的位操作来计算哈希值。这种交替的哈希计算方式有助于增加哈希的分散性。

3. DJBHash： 这是Daniel J. Bernstein提出的哈希算法，它使用了一个初始哈希值（5381）和左移操作以及字符的ASCII值来生成哈希。

BloomFilter

布隆过滤器是一种空间效率极高的概率型数据结构，它用来判断一个元素是否在一个集合中。但是，布隆过滤器有一个特点：它可以误报（即，它可能会错误地报告一个元素在集合中），但不会漏报（即，如果它说一个元素不在集合中，那么这个元素确实不在集合中）。

模板参数：

• N：布隆过滤器中比特集合的大小。

• K：键的类型，默认为string。

• HashFunc1, HashFunc2, HashFunc3：三个不同的哈希函数，用于生成键的三个哈希值。

成员函数：

• Set(const K& key)：将给定的键通过三个哈希函数映射到布隆过滤器的三个位置，并将这些位置设置为1。

• Test(const K& key)：使用三个哈希函数检查给定的键在布隆过滤器中的对应位置是否都被设置为1。如果所有位置都是1，则返回true（表示键可能存在于集合中）；否则返回false（表示键一定不在集合中）。

私有成员：

• _bs：一个大小为N的比特集合，使用bit::bitset实现。注意，这里使用的bit::bitset可能是某个特定库或框架中的实现，不是标准C++库中的std::bitset。

实现代码

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 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);
 
 
  }
 
  bool Test(const K& key)
  {
   // 判断不存在是准确的
   size_t hash1 = HashFunc1()(key) % N;
   if (_bs.test(hash1) == false)
    return false;
 
   size_t hash2 = HashFunc2()(key) % N;
   if (_bs.test(hash2) == false)
    return false;
 
   size_t hash3 = HashFunc3()(key) % N;
   if (_bs.test(hash3) == false)
    return false;
 
   // 存在误判的
   return true;
  }
 
 private:
  bit::bitset<N> _bs;
 };

注意事项

1. 布隆过滤器通过牺牲一定的准确性（即可能存在的误报）来换取空间效率。因此，它不适用于需要精确匹配的场景。

2. 布隆过滤器不支持删除操作。一旦一个位置被设置为1，就不能再将其改回0（除非重新初始化整个过滤器）。

3. 选择合适的哈希函数和布隆过滤器的大小对于减少误报率至关重要。

布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。 注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。 比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

布隆过滤器的删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。 比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也 被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。 一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计 数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储 空间的代价来增加删除操作。

缺陷：1. 无法确认元素是否真正在布隆过滤器中2. 存在计数回绕

布隆过滤器的优缺点

• 优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无 关

2. 哈希函数相互之间没有关系，方便硬件并行运算

3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势

5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

• 缺点

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再 建立一个白名单，存储可能会误判的数据)

2. 不能获取元素本身

3. 一般情况下不能从布隆过滤器中删除元素

4. 如果采用计数方式删除，可能会存在计数回绕问题