C++位图/布隆过滤器/海量数据处理

@TOC

零、前言

本章主要讲解C++中对哈希的应用有关方面的内容，位图，布隆，海量数据处理

一、位图

1、位图概念

位图概念：

位图其实就是哈希的变形，同样通过映射来处理数据，只不过位图本身并不存储数据，而是存储标记

通过一个比特位来标记这个数据是否存在，1代表存在，0代表不存在

位图通常情况下用在数据量庞大，且数据不重复的情景下判断某个数据是否存在

相关面试题描述：

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

注意：

遍历时间复杂度O(N)；排序(O(NlogN))利用二分查找: logN；这两种方式除了效率不够高，还有个问题是内存无法完全同时加载这给40亿个不重复的无符号整数

10亿个整数为40亿字节，而10亿字节为1G，所以40亿个整数需要16G大小空间

位图解决方案：

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态

那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在

示图：小端平台上

2、位图接口的介绍以及实现

bitset中常用的成员函数如下：

使用示例：

#include #include using namespace std; int main() { bitset<8> bs; bs.set(2); //设置第2位 bs.set(4); //设置第4位 cout << bs << endl; //00010100 bs.flip(); //反转所有位 cout << bs << endl; //11101011 cout << bs.count() << endl; //6 cout << bs.test(3) << endl; //1 bs.reset(0); //清空第0位 cout << bs << endl; //11101010 bs.flip(7); //反转第7位 cout << bs << endl; //01101010 bs.reset(); //清空所有位 cout << bs.none() << endl; //1 bs.set(); //设置所有位 cout << bs.all() << endl; //1 return 0; }

注：使用成员函数set、reset、flip时，若指定了某一位则操作该位，若未指定位则操作所有位

位图的简单实现：

对于底层来说一个位代表一个数的映射，那么我们以char类型来开辟对应需要空间，同时用vector进行管理

对于开辟空间，一个char类型有8个位，所以需要个数/8即为需要开辟的大小，但是整数相除为向下取整，所以需要我们多开一个空间出来

实现代码：

template class bitset { public: bitset() { _bits.resize(N / 8 + 1,0);//开辟空间并置为0 //_bits.resize((N >> 3) + 1,0); } bool test(size_t x) { size_t i = x / 8;//处于的该数组的第几个空间 size_t j = x % 8;//处于的该空间的第几个比特位 return _bits[i] & (1 << j); } void set(size_t x) { size_t i = x / 8;//处于的该数组的第几个空间 size_t j = x % 8;//处于的该空间的第几个比特位 _bits[i] |= (1 << j);//该位置置为1 } void reset(size_t x) { size_t i = x / 8;//处于的该数组的第几个空间 size_t j = x % 8;//处于的该空间的第几个比特位 _bits[i] &= (~(1 << j));//该位置置为0 } private: vector _bits; };

3、位图的应用

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

排序

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

操作系统中磁盘块标记

二、布隆过滤器

1、布隆过滤器概念和介绍

布隆过滤器的提出：

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？

用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录

如何快速查找：

用哈希表存储用户记录，缺点：浪费空间

用位图存储用户记录，缺点：不能处理哈希冲突

将哈希与位图结合，即布隆过滤器

布隆过滤器概念：

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构

特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”

它是用多个哈希函数，将一个数据映射到位图结构中的不同位置上，不仅可以提升查询效率，也可以节省大量的内存空间

示图：

位图中的哈希冲突：

当字符串使用哈希时，无可避免的会出现哈希冲突的问题（可能两个不同的内容映射相同的位置），而位图又是一个不能解决哈希冲突的数据结构。于是布隆过滤器则是使用了多个哈希函数，将数据映射到多个位置上面，才能确保数据的准确性，减小误判的概率

2、布隆过滤器的操作及实现

布隆的插入操作：

使用了多个哈希函数，将数据映射到多个位置上面，并将对应位置标记为1

示图：

布隆过滤器的查找：

分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中

布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判（哈希冲突）

布隆过滤器删除：

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

一种支持删除的方法：

将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作

缺陷：

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

存在计数回绕

如何选择哈希函数个数和布隆过滤器长度：

如果一个数据要映射多个位置，如果布隆过滤器较小，则会导致数据马上全部映射满，此时无论进行什么操作，都会存在大量的误报率。也就是说，布隆过滤器的长度与误报率成反比，与空间利用率成反比

哈希函数的个数也值得思考，哈希函数越多，映射的位置也就越多，此时准确性也就越高，但随之带来的问题就是效率的降低。也就是说，哈希函数的个数与效率成反比，准确率成正比

示图：

选择公式：

注意：

k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率

所以根据公式，我这里使用的哈希函数为3个，空间就应该开插入元素个数的五倍左右

实现代码：

struct _BKDRHash { //BKDRHash size_t operator()(const std::string& key) { size_t hash = 0; for (size_t i = 0; i < key.size(); i++) { hash *= 131; hash += key[i]; } return hash; } }; struct _SDBMHash { //SDBMHash size_t operator()(const std::string& key) { size_t hash = 0; for (size_t i = 0; i < key.size(); i++) { hash *= 65599; hash += key[i]; } return hash; } }; struct _RSHash { //RSHash size_t operator()(const std::string& key) { size_t hash = 0; size_t magic = 63689; for (size_t i = 0; i < key.size(); i++) { hash *= magic; hash += key[i]; magic *= 378551; } return hash; } }; template class BloomFilter { public: bool Test(const K& key) { size_t index1 = Hash1()(key) % len; size_t index2 = Hash2()(key) % len; size_t index3 = Hash3()(key) % len; if (!_bs.test(index1) || !_bs.test(index2) || !_bs.test(index3)) return false; return true; } void Set(const K& key) { size_t index1 = Hash1()(key) % len; size_t index2 = Hash2()(key) % len; size_t index3 = Hash3()(key) % len; _bs.set(index1); _bs.set(index2); _bs.set(index3); } private: bitset<6*N> _bs; size_t len = 6 * N; }; }

3、布隆过滤器的分析

布隆过滤器优点：

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

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

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

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

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

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

布隆过滤器缺陷：

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

不能获取元素本身

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

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

三、海量数据处理

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

这里的数据要求40亿个不重复的无符号整数，使用位图用一个位来表示一个整数，将所有的数据映射到位图上，当进行查询时，只要位图的对应位置为1，则说明该数据在这40亿个数据中

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

方法1：使用特定的位图，每个映射的数有对应的两个bit位进行表示映射的状态

方法2：使用两个位图，同样的两个位图对应的映射的数的位置共同表示映射状态

注：没有映射00，一次映射01，一次以上映射10

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

方法1：将文件1的整数全部映射到位图中，接着从文件2中读取数据，并在位图中查询该数据，如果数据存在，则说明该数据是交集之一

方法2：使用两个位图，对两个文件进行分别遍历文件读取数据映射到位图上，然后对位图进行遍历求交集，同一个位置都为1，那么则为交集

1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

方法1：使用特定的位图，每个映射的数有对应的两个bit位进行表示映射的状态

方法2：使用两个位图，同样的两个位图对应的映射的数的位置共同表示映射状态

注：没有映射00，一次映射01，两次映射10，三次以上映射11

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

注：query一般为URL中的查询字符串或者SQL中的查询语句，假设每个query30个字节，那么100亿个query也得300G的内存才能装下

近似算法：使用布隆过滤器来进行处理，对一个文件将数据全部进行哈希映射，再对另一个文件中的数据进行查询，但是可能存在哈希冲突，导致造成误判，所以当一个数据不存在于布隆过滤器中，则它必定不存在，但是如果一个数据存在于布隆过滤器中，它也不一定存在

精确算法：如果要精确的进行查找，那就必须得将数据放入内存中，但是由于数据过大我们可以将数据存入到服务器中，先使用布隆过滤器进行处理，如果对应映射不存在，那么久一定不是交集，如果对应映射存在那么就到服务器中进行二次查询

平均切割： 平均切割不是一个很好的方法，但是它确实是我们很容易就能思考到的方法，我们将两个文件中的数据平均切分为M份(能放入内存)，分别存储到一个set中，然后以此将数据进行比较，这种方法就需要以此对所有的数据进行比对，效率会比较低

哈希切割： 创建多个临时文件，并进行标号，读取文件数据使用字符串哈希算法进行哈希映射，映射到对应的文件并将数据存进去，对两个文件的数据都采用这样的做法进行切分，由于我们使用的是同一种字符串哈希算法，所以相同的字符串必定会被映射到同一个编号下的文件中，所以我们只需要依次对编号相同的Ai和Bi文件中使用set寻找交集即可（如果有些文件切分之后依然过大，可以继续对其进行切分）

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？ 与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

使用哈希切割的方式来解决文件分片的问题，相同的IP地址必定会被映射到同一个文件中，所以我们依次读取文件，使用Map进行次数统计即可之后再进行排序即可

Linux的命令：sort log_file | uniq -c | sort -nr | head -k

说明：首先使用sort log_file来将数据进行一个排序，使得相同的IP地址全部靠在一起。接着使用uniq - c进行去重，并将重复的次数显示在每列的旁边，通过这个次数来使用sort -nr进行降序排序，使得出现次数最的IP地址在前面，然后使用head -k 获取前k个IP地址即可

100w个数中找出最大的100个数

由于100w个数据并不算多，可以存放进内存中，所以可以考虑以下解法

方法1：采用快排中的partition划分思想，即单趟划分后，枢轴s前面的数据都比他大，后面的数据都比他小，此时我们选取其中较大的那一部分，继续划分。当划分后前端的数据刚好等于100后划分结束，对前端数据进行排序即可得到结果。如果前端数据不足100，则从后端数据进行排序后取出不足的那部分补上，再进行排序即可。O(100w*100)

方法2：局部淘汰法，使用插入排序来完成，首先取出前100个数据进行排序，然后依次遍历后面的数据，如果数据大于最小值，则将最小值删除，然后按照插入排序的思路将数据插入进去O(100w*100)

方法3：局部淘汰法，使用一个大小为100的小堆来完成，维护一个小堆，当数据比堆顶也就是最小值大的时候，用新数据替换掉堆顶，然后调整堆的结构。遍历完所有数据后就可以得到前100的数据。O(100w*lg100)

海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10

对于每一个电脑，都构建一个大小为10的堆(选大的构建小堆，选小的构建大堆)，选出当前电脑的TOP10，接着将所有电脑的数据汇总起来，共1000个数据，继续用堆从其中选出TOP10

给上千个文件，每个文件大小为 1K—100M。给 n 个词，设计算法对每个词找到所有包含它的文件，你只有 100K 内存

使用倒排索引来解决，即建立起单词——文件的映射，只需要遍历所有文章，如果文章中出现过查询词，则将文件号追加在对应词的倒排拉链中即可，如果100M的文件放不下内存中，就对数据进行切割后处理即可

C++ 数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。