当前位置：首页 > news >正文

【C++】哈希扩展海量数据处理

news 来源：原创 2025/9/7 9:28:21

位图

位图面试题

C++库中的位图bitset

位图优缺点

位图相关题目

布隆过滤器

布隆过滤器的介绍

布隆过滤器的应用

海量数据处理

位图

位图面试题

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

解题思路1：暴力遍历，时间复杂度O(N)，太慢。

解题思路2：排序+二分查找。时间复杂度消耗O(N*logN)+O(logN)。虽然排序消耗大一点，但是只排序1次，后续查找都是O(logN)。

但是，我们再来深入分析一下思路2是否可行，我们先算算40亿个数据大概需要多少内存。1G=1024MB=1024*1024KB=1024*1024*1024Byte约10亿多Byte。那40亿个整数需要160亿字节，160/10=16，所以，需要16G的内存来保存这些数据。这显然是不现实的，只能放到硬盘文件中。

解题思路3：其实我们并不需要记录这些数字，只需要记录这个数字在不在就行。数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，因此，最少可以通过一个bit就可以表示一个数字在不在，如果比特位为1，表示存在，为0表示不存在。因此，就只需要40亿个比特位=5亿个字节=500多M，设计了一个用位表示数据是否存在的数据结构，即位图。

接下来我们可以模拟实现一下，C++中没有位这种类型，只有int、char这样的整形，通过位运算找到对应的比特位。比如我们将数据存到vector<int>中，每一个int映射对应的32个值，比如第一个int映射0-31位，第二个映射32-63对应的位，依次类推。

假设要查x，i=x/32，j=x%32，映射的位是第i个整形数据的第j位。

我们使用vector<int> _bs来当做位图结构，_bs开成N/32+1个大小，

namespace ghs
{template<size_t N>class bit_set{bit_set(){_bs.resize(N / 32 + 1);  //需要N个位，那么N/32+1就是需要多少个int}private:std::vector<int> _bs;};
}

在这个类中，我们需要实现set这个接口，将某一个值x映射的位标记成1，先使用i=x/32计算出在哪个int，然后就j=x%32计算出在哪个bit，然后将_bs[i] |= (1<<j)。

//将x映射的位标记成1
void set(size_t x)
{int i = x / 32;int j = x % 32;_bs[i] |= (1 << j);
}

然后，使用同样的思路，对于reset接口，将一个值x映射的位标记成0，_bs[i] &= ~(1 << j);

//将x映射的位标记成0
void reset(size_t x)
{int i = x / 32;int j = x % 32;_bs[i] &= ~(1 << j);
}

然后，可以使用return _bs[i] & (1 << j);来判断某一个值是不是存在。

//x映射的位是1返回真
//x映射的位是0返回假
void test(size_t x)
{int i = x / 32;int j = x % 32;return _bs[i] & (1 << j);
}

因此，为了保存42亿个数是否存在，只需要将非类型模版参数取为0xffffffff（或-1）。

C++库中的位图bitset

库中的位图核心接口仍然是set、reset、test等接口。

使用库里的bitset时会有一个bug，就是如果开很大，比如N=-1，就会崩溃报错，原因就是这是在栈上开的，栈的空间有限，因此，可以在堆上来开辟，

位图优缺点

优点：增删查改快，节省空间。

缺点：只适用于整形。

位图相关题目

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

虽然是100亿个整数，但是还是按范围开（如果是int，就开42亿个位），使用两个位图结构a、b，那这个数在这两个位图对应的可能是00、01、10，用00表示这个数没有出现过，用01表示这个整数出现了1次，用10表示这个数出现了2次及以上，这样哪个数的位图是01，就代表这个数出现了一次，这样就可以复用位图。

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

同样的，使用两个位图结构a、b，那这个数在这两个位图对应的可能是00、01、10、11，用00表示这个数没有出现过，用01表示这个整数出现了1次，用10表示这个数出现了2次，用11表示这个数出现了3次及以上，所以，求出01和10出现的次数即可。一个位图是是0.5G，两个位图就用了1G。

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

把数据读出来，分别放到两个位图，依次遍历，同时在两个位图的值就是交集。

布隆过滤器

布隆过滤器的介绍

在一些场景下面，有大量数据需要判断是否存在，但是这些数据不是整形，那么就不能使用位图了，这些场景就需要使用布隆过滤器来解决。

布隆过滤器的思路就是，把key先映射转成哈希整形值，再映射一个位置，如果只映射一个位置的话，冲突率会比较多，所以可以通过多个哈希函数映射多个位置，降低冲突率。

然而，布隆过滤器这里和哈希表不一样，它无法解决哈希冲突，因为它根本不存储这个值，只标记映射的位。它的思路是尽可能降低哈希冲突。判断一个值key在是不准确的，判断一个值不在是准确的！布隆过滤器的推导非常复杂，这里我们只需要记住结论：

假设m是布隆过滤器的bit长度，n是插入过滤器的元素个数，k是哈希函数的个数，那么：

1.在k一定的情况下，当n增加时，误判率增加，m增加时，误判率减少。

2.在m和n一定时，当哈希函数个数k=m/n*ln2时误判率最低。

布隆过滤器的应用

优点：效率高，节省空间，相比位图，可以适用于各种类型的标记过滤。

缺点：存在误判（在是不准确的，不在是准确的），不好支持删除。

爬虫系统URL去重

在爬虫系统中，为了避免重复爬取相同的URL，可以使用布隆过滤器来进行URL去重。爬取到的URL可以通过布隆过滤器进行判断，已经存在的URL可以直接忽略，避免重复的网络请求和数据处理。

垃圾邮件过滤

在垃圾邮件过滤系统中，布隆过滤器可以判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件的特征信息存储在布隆过滤器中，当收到新的邮件中，可以通过布隆过滤器快速判断是否为垃圾邮件。

预防缓存穿透

缓存穿透是指恶意用户请求一个不存在的数据，导致请求直接访问数据库，造成数据库压力过大。布隆过滤器可以先判断请求的数据是否存在于布隆过滤器，如果不存在，直接返回不存在，避免对数据库的无效查询。

对数据库查询提效

在数据库中，布隆过滤器可以用来加速查询操作。例如：一个app要快速判断某一个电话号码是否注册过，可以使用布隆过滤器来判断一个用户电话号码是否存在于表中，如果不存在，则可以直接返回不存在，避免对数据块进行无用的查询操作；如果在，再去数据库查询进行二次确认。（数据库的数据在磁盘上，查询效率比较低。）

海量数据处理

1.10亿个整数里面求最大的前100个。

这是经典的topK问题，用堆解决。

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

分析：假设每个query字符串50byte，100亿个query就是5000亿个byte，约500G（1G约10byte）。

解决方案1：可以使用布隆过滤器解决，一个文件的query放进布隆过滤器，另一个文件依次查找，在的就是交集，但是有可能误判，导致找的交集不够准确，但是交集一定被找到了。

解决方案2：

使用哈希切分。首先内存的访问速度远大于硬盘，大文件放到内存中搞不定，那么我们可以考虑切分成小文件，再放进内存处理。但是不要平均切分，因为平均切分以后，每个小文件都需要依次暴力处理，效率还是太低了。
可以使用哈希切分，依次读取文件中query，i=HashFunc(query)%N，N为准备切分多少份小文件，N取决于切成多少份，内存能放下，query放进第i号小文件，这样A和B中相同的query算出的hash值是一样的，相同的query就进入到了编号相同的小文件，就可以直接去编号相同的小文件中找交集，不用交叉找，效率提升了。
本质是相同的query在哈希切分的过程中，一定进入了相同编号的Ai和Bi，不可能出现A中的query进入Ai，但是B中相同的query进入了编号不同的Bi这种情况。因此不需要对Ai和Bj求交集。
哈希切分的问题就是每个小文件不是均匀切分的，可能会导致某个小文件很大内存放不下。细分一下，某一个小文件很大有2中情况：1.这个小文件中大部分是同一个query。2.这个小文件是由很多不同的query构成，本质是这些query冲突了。针对情况，其实放到内存中的set是可以放下的，set可以去重。针对情况2，需要换一个哈希函数继续二次哈希切分。所以我们遇到大于1G小文件，继续读到set中找交集，如果set在insert时抛异常（set在插入时，只有申请内存失败时才会抛异常，不会有其他情况），那么就说明内存放不下，就是情况2，这样我们只需要换一个哈希函数进行二次哈希切分再找对应交集。

3. 给一个超过100G大小的log file，log中存在着IP地址，设计算法找到出现次数最多的IP地址？查找出现次数前10的ip地址。

本题思路和上题很相似。依次读取文件A中的query，i=HashFunc(query)%500，query放进Ai号小文件，然后依次用map<string,int>对每个Ai小文件进行ip计数，同时求出出现次数最多的ip（topK）。本质是相同的ip在哈希切分的过程中，一定进入同一个小文件Ai，不可能同一个ip进入Ai和Aj的情况，所以对Ai进行统计计数就是准确的ip次数。

但是也可能出现某一个小文件过大的问题，出现这个问题的原因只能是不同的ip映射到同一个值的数量过多，所以当map插入异常时捕获异常，然后对这个小文件进行二次切分。

位图

位图面试题

C++库中的位图bitset

位图优缺点

位图相关题目

布隆过滤器

布隆过滤器的介绍

布隆过滤器的应用

海量数据处理

相关文章：