【位图&&布隆过滤器&&海量数据面试题】（二）

注意布隆过滤器的模板参数N表示的是数据个数，因为不管数据有多大我们取模后的数据都是小于len的长度的。

为了测试我们可以写一个测试程序来测试一下误判率：

void test_bloomfilter1()
  {
    srand(time(0));
    const size_t N = 10000;
    bloomfilter<N> bf;
    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(i));
    }
    for (auto& str : v1)
    {
      bf.set(str);
    }
    // v2跟v1是相似字符串集，但是不一样
    std::vector<std::string> v2;
    for (size_t i = 0; i < N; ++i)
    {
      std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
      url += std::to_string(999999 + 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";
      //string url = "https://www.cctalk.com/m/statistics/live/16845432622875";
      url += std::to_string(i + rand());
      v3.push_back(url);
    }
    size_t n3 = 0;
    for (auto& str : v3)
    {
      if (bf.test(str))
      {
        ++n3;
      }
    }
    cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
  }

我们主要测试了一下相似字符和不相似字符的误判率：

我们可以运行下结果：

哈希函数为3个，布隆过滤器的长度为5倍左右的样子大概是上面这个样子，当然，你布隆过滤器的长度越长理论上冲突的概率也会越低，大家可以自行下去测验。

顺便问一下布隆过滤器支持删除操作吗？

如果只是我们上面这种设计思路的话就应该不能够支持删除，因为可能存在误删的情况，有什么方法可以支持删除呢？

我们可以用引用计数的思想方法来处理：我们标识每一个字符串时用多个比特位来标识(具体多少大家可根据数据重复量来选择),当我们要选择删除时就用我们上面的思想：这里我以2个比特位来举例，01->00,10->01,11->10

这样我们就可以避免误删的情况。

那布隆过滤器的应用有哪些呢？

我们举一个栗子，我们玩游戏时，游戏呢称的查重我们希望玩家只要输入名字后立马就能够识别是否该名字已经出现过，所以我们可以用布隆过滤器来处理，并且我们发现名字查重是可以容忍误判的，因为系统判定不在一定是准确的，而就算误判了在，那么玩家是不知道该游戏名字是否存在的，所以以玩家的视角这个是没问题的。但是假如玩家想要注册绑定手机号时如果玩家并没有绑定手机号，但是系统误判了，玩家是能够直接感知到的。但是我们可以提前用布隆过滤器过滤出不在，因为不在一定是准确的，而判定为在时在从数据库中查找是否真正存在，这样就提高了查找的效率。

我们可以来总结下布隆过滤器的优点：

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

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

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

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

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

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

布隆过滤器的缺点：

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

不能获取元素本身;

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

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

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

分析：

有两个文件分别有100亿次query,我们可以认为一次查询就是一次sql语句，假设一次查询30字节，那么老规矩，100亿次查询放在内存肯定行不通的(大概300GB)。我们可以用布隆过滤器作为近似算法：思想还是与前面一样，我们可以将其中一个文件的query放进布隆过滤器中，然后在从另外一个文件读取数据，但是这种方式也要处理去重，由于布隆过滤器是不太方便处理去重的，所以我们可以将文件交集找到了后在进行去重（前提要保证文件交集大小不会超过1GB)。

那么如何精确的找到文件交集呢？

我们可以利用哈希切割的思想，将大文件切分成一个一个小的文件。但是怎样切分是关键。问一下，我们能够平均切分文件吗？这种方式未免也太低效了吧，切分后，其中一个大文件的所有小文件还要与另外一个大文件的所有小文件一 一比较，效率太低下了。所以我们采用哈希切分的思想来进行切割，用某种哈希函数将query转换，这里我们不妨将文件分成600份，怎样处理呢？

我们可以采用下面这种方式：

Hashi=HashFunc(query)%600

这样通过哈希函数以及取模运算，每个query都会有一个对应的映射下标，下标是几，就被分到对应下标的小文件。

那么相同查询一定会被分到同一下标的小文件，所以我们只需要比较相同下标文件的数据即可:

这样做就极大提高了效率，我们可以将相同下标的小文件放到set/unoedered_set中去重找交集，最后将所有的小交集并在一起即可。但是这种方式处理还是可能存在着一些问题，大家想想是什么？

我们理想状态下是将大文件分成了内存可以容纳的下的小文件，但是实际上万一有大量的query进入到了某个小文件从而造成了小文件中大小分布不均衡的问题，可能其中一个小文件的大小只有几MB,而另外一个小文件中的数据大小有几GB,这种情况应该怎么处理？

我们可以分成两种情况来处理：

一种是小文件中有大量重复数据

另外一种是小文件中没有大量重复数据

小文件中如果有大量重复数据时就算我们更换哈希函数也是徒劳的，那我们应该怎样处理呢？

我们可以这样处理，将小文件中的数据一个一个放进内存的set中，如果里面有大量重复数据的话，那么set可以帮助我们去重，去重了后可能就能够将数据全部放进内存，如果我们在将数据放进set中抛了异常，那就说明该文件中大概率是没有大量重复数据的，那么我们重新更换哈希函数将小文件再次划分为更小的文件继续处理即可。如果set没有抛异常那么我们就直接将数据加载到了set中，直接进行两个文件找交集即可。

这样我们就用了精确和近似算法找到了两个文件的交集。

趁热打铁，我们再来看一个相似的面试题：给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？与上题条件相同，如何找到top K的IP？

分析：

基本思路与上面讲解的思路一致，我们仍然采用哈希切割的思想将大文件分成小文件，然后将小文件中的数据加载到内存用map/unoedered_map进行数据次数的统计，最后找到最大出现的次数即可。这里我们的数据要保证切割了后小文件的数据内存放得下，至于topK问题我们可以建立一个小堆，一次取小文件中的数据比较即可。

好了，今天的讲解就到这里了，如果你感觉该文章对你有所收获的话能不能3连支持一下博主。

💘💘💘