从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(下）

从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割（中)：https://developer.aliyun.com/article/1522346

完整 BloomFilter.h 和测试

#pragma once
 
#include <iostream>
#include <vector>
#include <bitset>
#include <string> // to_string
using namespace std;
 
struct HashBKDR
{
  size_t operator()(const string& key)
  {
    size_t val = 0;
    for (auto ch : key)
    {
      val *= 131;
      val += ch;
    }
 
    return val;
  }
};
 
struct HashAP
{
  size_t operator()(const string& key)
  {
    size_t hash = 0;
    for (size_t i = 0; i < key.size(); i++)
    {
      if ((i & 1) == 0)
      {
        hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
      }
      else
      {
        hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
      }
    }
    return hash;
  }
};
 
struct HashDJB
{
  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 Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class BloomFilter // N表示准备要映射N个值
{
public:
  void Set(const K& key)
  {
    size_t hash1 = Hash1()(key) % (_ratio * N); // 注意优先级问题，在最后加括号
    size_t hash2 = Hash2()(key) % (_ratio * N);
    size_t hash3 = Hash3()(key) % (_ratio * N);
 
    _bits->set(hash1);
    _bits->set(hash2);
    _bits->set(hash3);
 
  }
 
  bool Test(const K& key)
  {
    size_t hash1 = Hash1()(key) % (_ratio * N);
    if (!_bits->test(hash1))
    {
      return false; // 准确的
    }
 
    size_t hash2 = Hash2()(key) % (_ratio * N);
    if (!_bits->test(hash2))
    {
      return false; // 准确的
    }
 
    size_t hash3 = Hash3()(key) % (_ratio * N);
    if (!_bits->test(hash3))
    {
      return false;  // 准确的
    }
 
    return true; // 可能存在误判
  }
 
  // 一般不支持删除，因为可能会影响其它值（引用计数可以解决，但空间消耗更多了）
  //void Reset(const K& key);
 
protected:
  const static size_t _ratio = 5; // 根公式算出来，此时哈希函数是3个，所以m = 3n/ln2 约等于4.2 取5
  std::bitset<_ratio* N>* _bits = new std::bitset<_ratio * N>;
  // 库里的bit是放在栈上的，容易栈溢出，所以自己放到堆上（很挫）用自己写的就是放在堆上的
};

Test.cpp：

#include "BloomFilter.h"
 
void TestBloomFilter1()
{
  BloomFilter<10> bf;
  string arr1[] = { "苹果", "西瓜", "阿里", "美团", "苹果", "字节", "西瓜", "苹果", "香蕉", "苹果", "腾讯" };
 
  for (auto& str : arr1)
  {
    bf.Set(str);
  }
 
  for (auto& str : arr1)
  {
    cout << bf.Test(str) << " ";
  }
  cout << endl;
 
  string arr2[] = { "苹果111", "西瓜", "阿里2222", "美团", "苹果dadcaddxadx", "字节", "西瓜sSSSX", "苹果 ", "香蕉", "苹果$", "腾讯" };
 
  for (auto& str : arr2) // 测试相似字符串在不在
  {
    cout << str << ":" << bf.Test(str) << endl;
  }
}
 
void TestBloomFilter2() // 网上找的测试误判率的测试
{
  srand(time(0));
  const size_t N = 100000;
  BloomFilter<N> bf;
  cout << sizeof(bf) << endl;
 
  std::vector<std::string> v1;
  std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
 
  for (size_t i = 0; i < N; ++i)
  {
    v1.push_back(url + std::to_string(1234 + i));
  }
 
  for (auto& str : v1)
  {
    bf.Set(str); // 将十万个不同的字符串映射到位图中
  }
 
  std::vector<std::string> v2;
  for (size_t i = 0; i < N; ++i) // 获取十万个和前面相似的字符串用于下面测试
  {
    std::string url = "http://www.cnblogs.com/-clq/archive/2023/05/31/2528153.html";
    url += std::to_string(rand() + i);
    v2.push_back(url);
  }
 
  size_t n2 = 0;
  for (auto& str : v2)
  {
    if (bf.Test(str))
    {
      ++n2;
    }
  }
  cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
 
  std::vector<std::string> v3; // 获取十万个和前面不相似的字符串用于下面测试
  for (size_t i = 0; i < N; ++i)
  {
    string url = "zhihu.com";
    url += std::to_string(rand() + i);
    v3.push_back(url);
  }
 
  size_t n3 = 0;
  for (auto& str : v3)
  {
    if (bf.Test(str))
    {
      ++n3;
    }
  }
  cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}
 
int main()
{
  TestBloomFilter1();
  TestBloomFilter2();
 
  return 0;
}

可以看到，相似字符串的误判率在百分之十左右。

       可以试试改X值，X值越大，也就是一个字符串所需要的映射比特位越多，布隆过滤器的误判率越小。但是空间消耗也增加了。

• 哈希函数的个数越多，误判率也会越小，但是对于的空间消耗也会增加。

布隆过滤器只能提高存在判断的准确率，并不能让它完全准确。

2.3 布隆过滤器的优缺点和应用

优点：

• 1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关。
• 2. 哈希函数相互之间没有关系，方便硬件并行运算。
• 3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势。
• 4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势。
• 5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能。

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

缺点：

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

• 2. 不能获取数据本身。
• 3. 一般情况下不能从布隆过滤器中删除元素。
• 4. 如果采用计数方式删除，可能会存在计数回绕问题。

海量数据面试题： 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出近似算法和精确算法。

       分析：和位图应用一样，数据量太大，无法放入内存中，由于是字符串，近似算法可以使用布隆过滤器来处理。创建两个布隆过滤器，每个是2^32大小，占用空间0.5GB，两个就是1GB。将两个文件中的字符串各自映射到布隆过滤器中，然后两个布隆过滤器进行按位与操作，最后是1的位置就是交集。具体代码这里就不写了，主要体会布隆过滤器是使用的思想。

精确算法就不能用布隆过滤器处理了，要用到下面的哈希切割：

3. 哈希切割（哈希切分）

先看一道哈希切割的海量数据面试题：给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？设计算法找到top k的IP地址呢？

分析：

• 100GB大小的文件，无法放入内存。
• 找到出现次数最多的IP，需要准确统计，无法使用位图或者布隆过滤器，因为它两的存在是不准确的。

• 统计次数，还是需要用到map或者是unordered_map。
• 将100GB的文件拆分成100个1GB大小的小文件，每个小文件进行统计。

一个个来统计次数，依次读取每个小文件，依次统计次数。

统计完一个，将出现最多次数的IP及次数保存，并且clear掉map，再统计下一个小文件。

如果将这100GB的文件均分为100给1GB的小文件，统计会出现问题。

假设A0中出现次数最多的IP是“IP1”，出现最少次数的IP是“IP2"，那么这个小文件最终得到是”IP1“出现最多。

A1小文件中，出现最多的是”IP2“，出现最少的是”IP1“，那么这个小文件最终得到是”IP2“出现最多。

最终是A0中统计出来”IP1“的次数和A1中统计出来”IP2“的次数在比较。

这样最终比较时的数据具有片面性，因为在统计每个小文件时，会舍弃很多的数据，这些舍弃的数据再最终比较时并没有被考虑到。

如果在分小文件的时候，让相同的IP分到一个小文件中，这样统计出来的次数就不片面了。

此时就需要用到哈希切分的方法。

哈希切分：通过哈希函数，将相同或者相近的数据切分到一组。

       如上图所示，通过哈希函数，将100GB文件中的所有IP都转换成整数，然后模100，得到多少就进入标号为多少的小文件中。

哈希切分时：相同的IP经过哈希函数处理得到的整数必然是相同的，所以也必然会被分到同一个小文件中。

虽然会有哈希碰撞的情况，产生碰撞的IP都会在一个小文件中，而不会被分到其他小文件。

       经过哈希切分后，每个小文件中统计出现次数最多的IP就是这100GB文件中该IP出现的总次数。最后再从每个小文件中出现次数最多的IP中比较出最终出现次数最多的IP。

       但是此时又存在问题，哈希切分并不是均分，也就意味着每个小文件中的IP个数不一样，有的多有的少。如果某个小文件的大小超出1GB怎么办？有两种超出1GB的情况：

这个小文件中冲突的IP很多，都是不同的IP，大多数是不重复的，此时无法使用map来统计：需要换一个哈希函数递归切分这个小文件。

这个小文件中冲突的IP很多，都是相同的IP，大多数是重复的，此时仍然可以用map来统计：直接统计。

       无论是哪种情况，我们先都直接用map去统计，如果是第二种情况，内存就够用，map可以进行统计，而且不会报错。

       如果是第一种情况，map就会因为内存不够而插入失败，相当于new节点失败，就会抛异常，此时我们只需要捕获这个异常，然后换一个哈希函数递归切分这个小文件即可。

再看这道海量数据面试题： 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？给出近似算法和精确算法。（近似算法前面讲了这里就忽略）

这个问题和布隆过滤器应用中的问题一样，只是需要给出精确的算法，所以肯定不能使用布隆过滤器，还是需要map来统计。

1GB的内存，无法存放下100亿个字符串，所以需要哈希切分。

       假设平均每个字符串的大小是50B，那么100亿个字符串就是500GB，所以需要将这500GB哈希切分成1000份，每个小文件才能在内存中进行准确的次数统计。

将文件A和文件B各自进行哈希切分为1000个小文件，每个小文件平均大小是0.5GB。

然后Ai和Bi去找交集，找1000次就找到了两个文件中的所有交集。

如果某个小文件太大，仍然使用上个问题的方法去处理。

       找交集的方法有很多，这里就不再详细讲解了，但是需要注意的是，每个小文件Ai和Bi都需要各自去重以后再找交集。

4. 笔试选择题

1. 下面关于位图说法错误的是（）

A .位图就是用比特比特位表示一个数据的状态信息

B .通过位图可以求两个集合的交集

C .位图实际是哈希变形思想的一种应用

D .位图可以很方便的进行字符串的映射以及查找

2. 现有容量为10GB的磁盘分区，磁盘空间以簇（cluster）为单位进行分配，簇的大小为4KB，若采用位图法管理该分区的空闲空间，即用一位（bit）标识一个簇是否被分配，则存放该位图所需簇的个数为 （）

A .80

B .320

C .80K

D .320K

3. 下面关于布隆过滤器优缺点说法错误的是（）

A .布隆过滤器没有直接存储数据，可以对数据起到保护作用

B .布隆过滤器查找的结果不准确，并不能使用

C .布隆过滤器采用位图的思想表示数据装填，可以节省空间

D .布隆过滤器可能会存在误判，告知数据存在可能是不准确的

4. 下面关于布隆过滤器说法不正确的是（）

A .布隆过滤器是一种高效的用来查找的数据结构

B .布隆过滤器弥补了位图不能存储字符串等类型得缺陷

C .可以使用布隆过滤器可以准确的告知数据是否存在

D .布隆过滤器不存储数据本身，是一种紧促的数据结构

答案及解析

1. D

A：正确，位图概念

B：正确，将两个序列分别映射到两个位图上，对两个位图的每个字节进行按位与操作，结果为1 的比特位对应的数据    的就是两个序列的交集

C：正确，位图就是将数据与数据在位图中对应的比特位进行了一一对应，是哈希的一种变形

D：错误，采用位图标记字符串时，必须先将字符串转化为整形的数字，找到位图中对应的比特 位，但是在字符串转    整形的过程中，可能会出现不同字符串转化为同一个整形数字，即冲 突，因此一般不会直接用位图处理字符串。

2. A

10GB = 10*1024*1024K  一个簇大小为4K，

那10GB总共有 10*1024*1024/4 = 10*1024*256个簇

用位图来进行存储时：一个簇占用一个比特位，总共需要10*1024*256个比特位，

10*1024*256 bit = 10*1024*256/8字节 = 320K

一个簇大小为4K，故总共需要320K/4k=80个簇进行存储

10GB/4KB=2.5M，共有2.5M个可分配的簇， 2.5M/8=320KB，

需要320K的字节来标记可分配的簇， 320KB/4KB=80个，

这320KB同样是按4KB一簇在硬盘上存储，所以需要除4K，得80个簇

 3. B

 A：正确，布隆过滤器底层使用的是位图，没有直接存储数据本身

 B：错误，如果可以接受误差，是可以用的

 C：正确

 D：正确，因为多个元素的比特位上可能有重叠

 4. C

 A：正确，因为其底层使用的是位图，而位图优势哈希的一种变形

 B：正确，布隆过滤器可以映射存储任意类型，只是存在误判的问题

 C：错误，布隆过滤器找到数据不存在，则该数据一定不存在，如果说存在，那可能存在，          不存在 一定是准确的，存在时可能会误判

 D：正确，因为其底层使用位图，用比特位代表数据存在与否的状态信息，

        是一种紧促的数据结构

本篇完。

       位图和布隆过滤器都是针对数据量很大的情况下使用的数据结构，并且它们不能存放数据本身，只能表示数据存在或者不存在，位图只针对整形，并且不存在误判的情况，布隆过滤器主要针对字符串，但是也可以是其他自定义类型，但是存在误判，可以通过增加哈希函数或者映射一个数据所需要的比特位来降低误判率，但是会消耗更多的空间。

本篇博客主要是介绍哈希思想的应用，位图以及布隆过滤器归根到底还是哈希思想的体现。

下一部分就开始进入C++11的系统学习了。