一、位图

1.1 位图概念

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

1.2 位图的实现

位图的底层结构依然是连续的线性空间，这里我们使用vector容器作为其底层结构。

#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;
namespace bjy {
  template<size_t N>
  class bitset {
  public:
    bitset() {
      if (N % 8 == 0) _bits.resize(N / 8, 0);
      else _bits.resize(N / 8 + 1, 0);
    }
    void set(size_t which){//将某个位设置为1
      size_t i = which / 8, j = which % 8;
      _bits[i] |= (1 << j);
    }
    void reset(size_t which) {//将某个位设置为0
      size_t i = which / 8, j = which % 8;
      _bits[i] &= ~(1 << j);
    }
    bool test(size_t which)const {
      size_t i = which / 8, j = which % 8;
      return _bits[i] & (1 << j);
    }
  private:
    vector<char> _bits;
  };

1.3 位图的特点

1. 速度快且节省时间。

2. 采用直接定址法，不存在哈希冲突。

3. 相对局限，只能处理整型数据。

4. STL中实现的bitset容器存在一定不足，其底层使用静态数组实现。其开辟在栈区会导致在处理海量数据时极易发生StackOverflow。(使用时应特别注意)

二、布隆过滤器

2.1 布隆过滤器的提出

当使用新闻客户端看新闻时，其会不停地推荐新的内容，每次推荐时要去重。但新闻客户端推荐系统如何实现推送去重的？用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。如何实现的呢？

方案一: 使用哈希表存储用户记录，但空间消耗过大。

方案二: 使用位图记录用户信息，明显不可取(位图只能处理整型数据)

方案三: 将位图与哈希进行结合，即布隆过滤器

2.2 概念

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

Bloom Filters (jasondavies.com)

https://www.jasondavies.com/bloomfilter/

2.3 实现原理

布隆过滤器是一个 bit 向量或者说 bit 数组

若要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置进行set操作。例如针对key "百度" 用三个不同的哈希函数分别生成了哈希值 0、3、6，则上图转变为：

再存一个值 "腾讯"，若哈希函数返回 2、3、7 的话，图继续变为：

3 这个bit位由于两个key的哈希函数都返回了3，因此它被覆盖了。

现在若想查询 "b站" 这个key是否存在，哈希函数返回了 0、4、7三个值，结果我们发现 4 这个 bit 位上的值为 0，说明没有任何一个key映射到这个 bit 位上，因此我们可以很确定地说 "b站"这个key不存在。而当我们需要查询 "百度" 这个值是否存在的话，那么哈希函数必然会返回 0、3、6，然后我们检查发现这三个 bit 位上的值均为 1，那么说明"baidu"可能存在。

为什么不是一定存在呢？因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个key即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他key置为了 1 ，那么程序还是会判断这个key存在。

2.4 哈希函数个数和布隆过滤器长度的选择

在使用布隆过滤器时，哈希函数的个数和布隆过滤长度的设定都是我们需要考虑的问题。

1. 哈希函数个数越多则布隆过滤器bit位被置为1的速度越快，且会效率下降。但是若哈希函数过少则会导致误报率较高。

2. 布隆过滤器的长度会直接影响误报率，布隆过滤器长度越长则误报率越低。但若是过长了则失去布隆过滤器原有的优势(占用空间小)，反而还不如选择哈希表。

直接根据下图中的公式选择即可

2.5 布隆过滤器的删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计

数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储

空间的代价来增加删除操作。

缺陷：

1. 无法确认元素是否真正在布隆过滤器中

2. 存在计数回绕

2.6 特点

2.6.1 优点

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

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

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

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

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

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

2.6.2 缺点

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再

建立一个白名单，存储可能会误判的数据)

2. 不能获取元素本身

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

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

2.7 完整代码实现

#include <iostream>
#include <vector>
#include <string>
#include <bitset>
using namespace std;
namespace bjy {
  struct HashBKDR {
    size_t operator()(const string& key) {
      size_t sum = 0;
      for (auto& e : key) {
        sum = sum * 131 + e;
      }
      return sum;
    }
  };
  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 Bloon_filter
  {
  public:
    void set(const K& key) {
      size_t pos1 = Hash1()(key) % (_ratio * N);
      size_t pos2 = Hash2()(key) % (_ratio * N);
      size_t pos3 = Hash3()(key) % (_ratio * N);
      _bits->set(pos1);
      _bits->set(pos2);
      _bits->set(pos3);
    }
    bool test(const K& key) {
      size_t pos1 = Hash1()(key) % (_ratio * N);
      size_t pos2 = Hash2()(key) % (_ratio * N);
      size_t pos3 = Hash3()(key) % (_ratio * N);
      if (_bits->test(pos1) && _bits->test(pos2) && _bits->test(pos3)) return true;
      else return false;
    }
  private:
    const static size_t _ratio = 5;
    bitset<_ratio* N>* _bits = new bitset<_ratio* N>;//库中bitset使用静态数组，开辟在栈上，容易导致栈溢出
  };
}

三、海量数据处理常见面试题

1. 给定100亿个整数，设计算法找到只出现一次的整数

利用两个位图完成该问题的实现。采用KV的统计次数的模型，两个位图中各有一个bit位表示同一个整型。00表示该整型出现次数为0，01表示该整型出现次数为1，10表示该整型出现次数为2次,11表示该整型出现3次及以上。

template<size_t N>
class twobitset
{
public:
  void set(size_t x)
  {
    bool inset1 = _bs1.test(x);
    bool inset2 = _bs2.test(x);
    if (inset1 == false && inset2 == false)//00
        {
      _bs2.set(x);// -> 01
    }
    else if (inset1 == false && inset2 == true)//01
    {
      _bs1.set(x);
      _bs2.reset(x);// ->10
    }
    else if (inset1 == true && inset2 == false)//10
    {
      // ->11
      _bs1.set(x);
      _bs2.set(x);
    }
  }
  void print_once_num(){
    for (size_t i = 0; i < N; ++i){
      if (_bs1.test(i) == false && _bs2.test(i) == true){
        cout << i << endl;
      }
    }
  }
private:
  bitset<N> _bs1;
  bitset<N> _bs2;
};

2. 两个文件分别有100亿个整数，只有1G内存，找到两个文件交集

将文件A中的数据映射到位图A中，将文件B中的数据映射到位图B中，位图A和位图B对应且都为1的位所代表的key的集合即是两个文件的交集。

3. 给两个文件，分别有100亿个query，只有1G内存，找到两个文件交集。分别给出精确算法和近似算法

该问题不可使用bitset解决，其只适用于整型数据。query为字符串，应使用哈希切割思想或者布隆过滤器完成问题。

近似算法:

使用两个布隆过滤器分别处理两个文件，若两个布隆过滤器set(key)都为1，即这个key在两个文件中都可能存在，近似看做交集中的元素。

精确算法:

假设1个query为30Byte,100亿个query则大概需要300G以上的内存空间。我们的电脑肯定没有这么大的空间，所以这里需要使用哈希切割的思想。

若是处理完后某个小文件过大，可以换一个哈希函数对小文件再次进行哈希切割。

4. 给一个超过100G大小的log file, log中存着IP地址。(1)设计算法找到出现次数最多的IP地址。(2)找到top-K的IP。

问题一:

使用哈希切割，将一个大的log file分成500个小log file,相同的IP一定进入同一个小log file。再用map<string,int> 或者unordered_map<string,int>对每个小log file进行次数统计,找出出现次数最多的IP地址。

问题二:

建立一个K个<IP,count>元素的小堆(优先级队列)

海量数据处理