位图

位图的概念

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

直接来看问题：

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在

这40亿个数中。

思路：解决问题的方法，可以使用位图来解决。把这40亿个数据映射在位图上，将位图上对应的比特位置为1。然后拿着需要判断的数在位图上看看其对应的比特位是否为1，如果是则存在，否则为0。

具体做法：

使用直接定址法，这40亿个数据的值是几，就把第几个比特位标记为1。因为40亿个整数，大概需要16G内存，而使用比特位，我们只需使用char作为存储在vector上的类型，每一个都是1bit大，因此在vector上开辟2^32大小的空间，表示数据大小范围，一共512M。

[L%@O2FPEY64{20H7U20D61.png

开辟好空间后，开始将每一个数据映射到位图上。每一个char对象为8bit，于是让每一个值先确定自己在哪个char对象上，然后确定映射在哪个比特位上。

x映射的值，在第 x/8 个char对象上。

x映射的值，在第 x%8 个比特位上。

所以，我们可以根据上面的理论，用代码简单实现位图

使用非模板参数N，作为数据的个数。

开辟空间：空间开辟的大小为N /8 +1，因为N个数据，每8个为一组，多开辟一组，避免N不是8的整除。然后初始化为0。即位图上的比特位一开始全是0.

//初始化空间，初始值为0
    bitset()
    {
      _bits.resize((N >> 3) + 1, 0);
    }

数据映射位图上的比特位：先计算好数据所在的组别和比特位的位置，然后将其置为1。置为1的操作是让这一个char对象组别的比特位与这个数据的比特位进行或运算。

[{N51IQ00(PF2V4O4$5XAS3.png

void set(size_t x)
    {
      size_t i = x >> 3;//位于哪一个char对象上
      size_t j = x % 8;//位于这个char对象上的哪个比特位上
      _bits[i] |= (1 << j);//通过或运算，将x对应的比特位变为1
    }

将某个数据映射的比特位从1变回0：同样的找到这个位置后，然后这一组别的比特位与这个数据的比特取反后进行与运算。

W01~FI}9XSC0JI4BGFBCMRU.png

void reset(size_t x)
    {
      size_t i = x >> 3;
      size_t j = x % 8;
      _bits[i] & = (~(1 << j));//通过与运算，让x对应的比特位变为0
    }

判断一共数据是是否存在：同样，先计算出这个数据映射的位置。然后返回这一组别跟这个数据的比特，然后进行与运算，注意不是与等，是不能改变原本位图的比特位的。

[$A5R((9$A(GFKAIQRA6ZW4.png

//判断x是否存在，如果存在返回true
    bool test(size_t x)
    {
      size_t i = x >> 3;
      size_t j = x % 8;
      return _bits[i] & (1 << j);
    }

完整代码如下：

namespace my_BitSet
{
  template<size_t N>
  class bitset
  {
  public:
    //初始化空间，初始值为0
    bitset()
    {
      _bits.resize((N >> 3) + 1, 0);
    }
    void set(size_t x)
    {
      size_t i = x >> 3;//位于哪一个char对象上
      size_t j = x % 8;//位于这个char对象上的哪个比特位上
      _bits[i] |= (1 << j);//通过或运算，将x对应的比特位变为1
    }
    void reset(size_t x)
    {
      size_t i = x >> 3;
      size_t j = x % 8;
      _bits[i] & = (~(1 << j));//通过与运算，让x对应的比特位变为0
    }
    //判断x是否存在，如果存在返回true
    bool test(size_t x)
    {
      size_t i = x >> 3;
      size_t j = x % 8;
      return _bits[i] & (1 << j);
    }
  private:
    vector<char> _bits;
  };
}

布隆过滤器

位图对于判断大量数据中是否存在某一个数据的情况固然是好，其优点是节省空间和判断速度块。但其缺点是一般要求范围相对集中，如果范围特别分散，那么空间消耗就大了，而且是只针对整型。因此，布隆过滤器降临！

布隆过滤器的概念

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

一般的位图下，每一个数据只跟位图产生一个映射点，而且只能用于整型。但布隆过滤器是每一个数据可以有N个映射点，N个映射点对应于N个哈希函数，这个是我们自己定义的。用哈希函数将非整型转化成整型。

Q3_]AUGEDAE0J(OE(IQT6F3.png

布隆过滤器的长度的计算方式：

使用公式： 00BU(]DH]MR%7EJV%YRZ}OM.png

K为哈希函数的个数，m为布隆过滤器长度，n为数据的个数。假设K为3，而ln2约等于0.7，因此m==4.2n。

布隆过滤器的功能支持：

布隆过滤器支持set和test方法，最好不要有将1变回0的操作。因为这样会导致其它数据的判断的误差。如果真的要支持，就用计数的方法，但这种方法不推荐。

简单实现代码如下

这里使用3个哈希函数，分别为：BKDRHash、APHash和DJBHash。使用string为类型。

set方法：

void set(const K& key)
    {
      //通过不同的哈希函数，让同一个数据可以计算出三个不同的位置
      size_t hash1 = HashFunc1()(key) % (N * X);
      size_t hash2 = HashFunc2()(key) % (N * X);
      size_t hash3 = HashFunc3()(key) % (N * X);
      //计算出位置后，使用位图的set方法将位图上对应的比特位进行0变1
      _bs.set(hash1);
      _bs.set(hash2);
      _bs.set(hash3);
    }

test方法：

bool test(cost K& key)
    {
      //先逐个位置判断，如果它是0，直接返回false
      size_t hash1 = HashFunc1()(key) % (N * X);
      if (!_bs.test(hash1))
      {
        return false;
      }
      size_t hash2 = HashFunc2()(key) % (N * X);
      if (!_bs.test(hash2))
      {
        return false;
      }
      size_t hash3 = HashFunc3()(key) % (N * X);
      if (!_bs.test(hash3))
      {
        return false;
      }
      //直到最后，说明该数据是存在的，返回true
      return true;
    }

整体代码如下：

namespace my_BloomFilter
{
  struct BKDRHash
  {
    size_t operator()(const string& key)
    {
      size_t hash = 0;
      for (auto ch : key)
      {
        hash *= 131;
        hash += ch;
      }
      return hash;
    }
  };
  struct APHash
  {
    size_t operator()(const string& key)
    {
      unsigned int hash = 0;
      int i = 0;
      for (auto ch : key)
      {
        if ((i & 1) == 0)
        {
          hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));
        }
        else
        {
          hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));
        }
        ++i;
      }
      return hash;
    }
  };
  struct DJBHash
  {
    size_t operator()(const string& key)
    {
      unsigned int hash = 5381;
      for (auto ch : key)
      {
        hash += (hash << 5) + ch;
      }
      return hash;
    }
  };
  template<size_t N,
    size_t X = 5,
    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 * X);
      size_t hash2 = HashFunc2()(key) % (N * X);
      size_t hash3 = HashFunc3()(key) % (N * X);
      //计算出位置后，使用位图的set方法将位图上对应的比特位进行0变1
      _bs.set(hash1);
      _bs.set(hash2);
      _bs.set(hash3);
    }
    bool test(cost K& key)
    {
      //先逐个位置判断，如果它是0，直接返回false
      size_t hash1 = HashFunc1()(key) % (N * X);
      if (!_bs.test(hash1))
      {
        return false;
      }
      size_t hash2 = HashFunc2()(key) % (N * X);
      if (!_bs.test(hash2))
      {
        return false;
      }
      size_t hash3 = HashFunc3()(key) % (N * X);
      if (!_bs.test(hash3))
      {
        return false;
      }
      //直到最后，说明该数据是存在的，返回true
      return true;
    }
  private:
    std::bitset<N* X> _bs;
  };
}

海量数据处理问题

哈希切割

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

超过100G大小的文件，肯定不能直接放到内存中，而是通过将它切割，分成很多份。那么如何去切割呢？是平均分成100份，每一份1G这样吗？

如果平均切割，那么会导致的问题是：如果文件中有好几个相同的值，且分布不集中，此时平均切割就很可能使一个IP有很多份在很多小文件中。

因此不能平均切割，需要的是哈希切割。哈希切割就是通过取模，让取模结果相同的数据放到同一份小文件里面。

哈希切割后，通过map来对每一个小文件进行统计。

7IT8F1EYK)W[MY]J4I5CRLG.png

小问题如果超过1G的问题：

①不重复的IP有很多个，map就需要很多节点，因此map是统计不下来的。

②重复的IP有很多个，map可以统计下来，因为节点不多。

解决方法：

先不看什么情况，直接用map统计，如果是第二种情况的话就直接统计下来了。但是第一种情况，会在insert的时候失败，因此可以在失败的时候捕捉异常，接着换哈希函数递归切分再统计即可。

位图的应用

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

只出现一次，那就说明，它在位图中比特位是：01。如果找到该位置发现是00或11或者其它的情况，那就不是。

但一个一般的位图只会出现单个比特，即要么是0，要么是1，不会出现两个比特。这里的方法使用两个位图的结构。即定义两个位图，然后用同一个数据计算出来的同一个位置，分别在这个两个位图上进行0和1的操作。

$ARDK9VD}Q9DP{}5(_]XYJOB.png$

简单的代码实现：

template<size_t N>
  class twobitset
  {
  public:
    void set(size_t x)
    {
      //初次映射：两个位图对应的比特位都为0，即00
      if (!_bs1.test(x) && !_bs2.test(x)//  00
      {
        _bs2.set(x);//  01
      }
      else if (!_bs1.test(x) && _bs2.test(x) //  01
      {
        //第二次遇到这个数字后，此时是01的，要变成10
        _bs1.set(x); //11
        _bs2.reset(x); // 10
      }
      //如果第三次遇到，也不用管了，第二次遇到的时候就已经不是它了
      //10
      //11
    }
    void PrintOnce()
    {
      for (size_t i = 0; i < N; ++i)
      {
        if (!_bs1.test(i) && _bs2.test(i))  // 01 出现一次
        {
          cout << i << endl;
        }
      }
      cout << endl;
    }
  private:
    bitset<N> _bs1;
    bitset<N> _bs2;
  };
}

2.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

这里提供两种思路：

思路1：先将一个文件的数据映射到位图中，然后用另外一个文件的数据去遍历，得到交集，需要注意去重。

思路2：分布将两文件映射到两个位图，然后通过两位图的与运算判断是否有交集。

3.位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。

这道问题跟第一个问题基本一样，就是让“01”和"10"为需要找到的整数。如果出现"11"以上，那么就不行。

布隆过滤器的应用

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

query是一般为一个查询指令，可能是一个网络请求的指令，也可能是一个数据库sql语句。

精确算法找文件交集的思路是：分别给两个文件创建布隆过滤器，然后让它们进行哈希切割，分成一个个小文件。最后通过编号相同的小文件中查找交集。

近似算法的思路是：将一个文件的数据映射到一个布隆过滤器中，然后另外一个文件去查找有没有相同的，有就是交集。这种算法会造成误判。

位图/布隆过滤器/海量数据处理方式

位图