哈希扩展：位图、布隆过滤器以及海量数据处理问题
哈希扩展：位图、布隆过滤器以及海量数据处理问题
1. 位图
1.1 位图相关面试题
给40亿个不重复的⽆符号整数，没排过序。给⼀个⽆符号整数，如何快速判断⼀个数是否在这40亿个数中。（本题为腾讯/百度等公司出过的⼀个⾯试题）
解题思路1：暴⼒遍历，时间复杂度O(N)，太慢
解题思路2：排序 + ⼆分查找。时间复杂度消耗O(N*logN)+O(logN)
深⼊分析：解题思路2是否可⾏，我们先算算40亿个数据⼤概需要多少内存。
1G=1024MB=1024 * 1024KB=1024 * 1024 * 1024Byte约等于10亿多Byte
那么40亿个整数约等于16G，说明40亿个数是⽆法直接放到内存中的，只能放到硬盘⽂件中。⽽⼆分查找只能对内存数组中的有序数据进⾏查找。
解题思路3：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使⽤⼀个⼆进制⽐特位来代表数据是否存在的信息，如果⼆进制⽐特位为1，代表存在，为0代表不存在。那么我们设计⼀个⽤位表示数据是否存在的数据结构，这个数据结构就叫位图。
1.2 位图的设计及实现
位图本质是⼀个直接定址法的哈希表，每个整型值映射⼀个bit位，位图提供控制这个bit的相关接⼝。
实现中需要注意的是，C/C++没有对应位的类型，只能看int/char这样整形类型，我们再通过位运算去控制对应的⽐特位。⽐如我们数据存到vector< int >中，相当于每个int值映射对应的32个值，⽐如第⼀个整形映射0-31对应的位，第⼆个整形映射32-63对应的位，后⾯的以此类推，那么来了⼀个整形值 x ，i = x / 32；j = x % 32；计算出x映射的值在vector的第i个整形数据的第j位。
解决给40亿个不重复的⽆符号整数，查找⼀个数据的问题，我们要给位图开2 ^ 32个位，注意不能开40亿个位，因为映射是按⼤⼩映射的，我们要按数据⼤⼩范围开空间，范围是是0 ~ 2 ^ 32 - 1，所以需要开2 ^ 32个位。然后从⽂件中依次读取每个set（set就是存到位图中）到位图中，然后就可以快速判断⼀个值是否在这40亿个数中了。
#pragma once
#include <vector>
namespace bs
{
template<size_t N> // N是需要多少比特位
class bitset
{
public:
bitset()
{
_bs.resize(N / 32 + 1, 0);
//_bs.resize((N >> 5) + 1, 0);
}
// 把 x 映射的位标记成1
void set(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_bs[i] |= (1 << j);
}
// 把 x 映射的位标记成0
void reset(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_bs[i] &= (~(1 << j));
}
// x 映射的位是 1 返回true
// x 映射的位是 0 返回false
bool test(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
return _bs[i] & (1 << j);
}
private:
std::vector<size_t> _bs;
};
}
#include <iostream>
using namespace std;
#include "BitSet.h"
int main()
{
bs::bitset<100> bs;
bs.set(32);
bs.set(33);
bs.reset(33);
bs.set(34);
cout << bs.test(31) << endl;
cout << bs.test(32) << endl;
cout << bs.test(33) << endl;
cout << bs.test(34) << endl;
cout << bs.test(35) << endl;
// 开 2^32个位的位图
bs::bitset<-1> bs1;
bs::bitset<0xffffffff> bs2;
bs::bitset<UINT_MAX> bs3;
return 0;
}
1.3 C++库中的位图bitset
可以看到核⼼接⼝还是set / reset 和 test，当然后⾯还实现了⼀些其他接⼝，如to_string将位图按位转成01字符串，再包括operator[]等⽀持像数组⼀样控制⼀个位的实现
VS的C++库中写的bitset和我们写的bitset的不同之处
#include <iostream>
#include <bitset>
using namespace std;
#include "BitSet.h"
int main()
{
// 在堆上开空间
bs::bitset<100> bs1;
cout << sizeof(bs1) << endl; // 12
bs::bitset<10000> bs2;
cout << sizeof(bs2) << endl; // 12
// 为什么是12？因为我们用的vector，它的底层就是3个指针维护的
// 静态数组 - 在栈上开空间
std::bitset<100> bs3;
cout << sizeof(bs3) << endl;
std::bitset<10000> bs4;
cout << sizeof(bs4) << endl;
//std::bitset<-1> bs5; // 给-1就会崩溃
// 把它转到在堆上开空间
std::bitset<-1>* ptr = new std::bitset<-1>();
return 0;
}
1.4 位图的优缺点
优点：增删查改快，节省空间
缺点：只适⽤于整形
1.5 位图相关考察题目
1. 给定100亿个整数，设计算法找到只出现⼀次的整数
虽然是100亿个数，但是还是按范围开空间，所以还是开2 ^ 32个位，跟前⾯的题⽬是⼀样的
2. ⼀个⽂件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数
之前我们是标记在不在，只需要⼀个位即可，这⾥要统计出现次数不超过2次的，可以每个值⽤两个位标记即可，00代表出现0次，01代表出现1次，10代表出现2次，11代表出现2次以上。最后统计出所有
01和10标记的值即可，该题跟第一题是一样的。
#pragma once
#include <vector>
namespace bs
{
template<size_t N> // N是需要多少比特位
class bitset
{
public:
bitset()
{
_bs.resize(N / 32 + 1, 0);
}
// 把 x 映射的位标记成1
void set(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_bs[i] |= (1 << j);
}
// 把 x 映射的位标记成0
void reset(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_bs[i] &= (~(1 << j));
}
// x 映射的位是 1 返回true
// x 映射的位是 0 返回false
bool test(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
return _bs[i] & (1 << j);
}
private:
std::vector<size_t> _bs;
};
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
bool bit1 = _bs1.test(x);
bool bit2 = _bs2.test(x);
if (!bit1 && !bit2) // 00->01
{
_bs2.set(x);
}
else if (!bit1 && bit2) // 01->10
{
_bs1.set(x);
_bs2.reset(x);
}
else if (bit1 && !bit2) // 10->11
{
_bs2.set(x);
}
}
// 返回0 出现0次
// 返回1 出现1次
// 返回2 出现2次
// 返回3 出现3次及以上
int get_count(size_t x)
{
bool bit1 = _bs1.test(x);
bool bit2 = _bs2.test(x);
if (!bit1 && !bit2)
{
return 0;
}
else if (!bit1 && bit2)
{
return 1;
}
else if (bit1 && !bit2)
{
return 2;
}
else
{
return 3;
}
}
private:
bitset<N> _bs1;
bitset<N> _bs2;
};
}
void test_twobitset()
{
bs::twobitset<100> tbs;
int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };
for (auto e : a)
{
tbs.set(e);
}
for (size_t i = 0; i < 100; ++i)
{
//cout << i << "->" << tbs.get_count(i) << endl;
if (tbs.get_count(i) == 1 || tbs.get_count(i) == 2)
{
cout << i << endl;
}
}
}
#include <iostream>
using namespace std;
#include "BitSet.h"
int main()
{
test_twobitset();
return 0;
}
3. 给两个⽂件，分别有100亿个整数，我们只有1G内存，如何找到两个⽂件交集？
把数据读出来，分别放到两个位图，依次遍历，同时在两个位图的值就是交集
// 模拟位图找交集
void test_bitset1()
{
int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };
int a2[] = { 5,3,5,99,6,99,33,66 };
bs::bitset<100> bs1;
bs::bitset<100> bs2;
for (auto e : a1)
{
bs1.set(e);
}
for (auto e : a2)
{
bs2.set(e);
}
for (size_t i = 0; i < 100; i++)
{
if (bs1.test(i) && bs2.test(i))
{
cout << i << endl;
}
}
}
2. 布隆过滤器
2.1 什么是布隆过滤器
有⼀些场景下⾯，有⼤量数据需要判断是否存在，⽽这些数据不是整形，那么位图就不能使⽤了，使⽤红⿊树 / 哈希表等内存空间可能不够。这些场景就需要布隆过滤器来解决。
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的⼀种紧凑型的、⽐较巧妙的概率型数据结构，特点是⾼效地插⼊和查询，可以⽤来告诉你“某样东西⼀定不存在或者可能存在”，它是⽤多个哈希函数，将⼀个数据映射到位图结构中。此种⽅式不仅可以提升查询效率，也可以节省⼤量的内存空间。
布隆过滤器的思路就是把key先映射转成哈希整型值，再映射⼀个位，如果只映射⼀个位的话，冲突率会⽐较高，所以可以通过多个哈希函数映射多个位，降低冲突率。
布隆过滤器这⾥跟哈希表不⼀样，它⽆法解决哈希冲突，因为他压根就不存储这个值，只标记映射的位。它的思路是尽可能降低哈希冲突。判断⼀个值key在是不准确的，判断⼀个值key不在是准确
的。
2.2 布隆过滤器误判率推导
这个推导过程比较复杂，涉及概率论、极限、对数运算，求导函数等知识，有兴趣且数学功底⽐较好的可以看一下下面的博客。
布隆过滤器（Bloom Filter）- 原理、实现和推导布隆过滤器（Bloom Filter）- 原理、实现和推导
2.3 布隆过滤器代码实现
#pragma once
#include <string>
#include "BitSet.h"
struct HashFuncBKDR
{
// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The CProgramming Language》
// 一书被展示而得 名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法累乘因子为31。
size_t operator()(const std::string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash *= 31;
hash += ch;
}
return hash;
}
};
struct HashFuncAP
{
// 由Arash Partow发明的一种hash算法。
size_t operator()(const std::string& s)
{
size_t hash = 0;
for (size_t i = 0; i < s.size(); i++)
{
if ((i & 1) == 0) // 偶数位字符
{
hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
}
else // 奇数位字符
{
hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
}
}
return hash;
}
};
struct HashFuncDJB
{
// 由Daniel J. Bernstein教授发明的一种hash算法。
size_t operator()(const std::string& s)
{
size_t hash = 5381;
for (auto ch : s)
{
hash = hash * 33 ^ ch;
}
return hash;
}
};
template<size_t N, // 插⼊过滤器的元素个数
size_t X = 5, // 这里的 X 是 布隆过滤器的bit⻓度 与 插⼊过滤器的元素个数的比值
class K = std::string,
class Hash1 = HashFuncBKDR,
class Hash2 = HashFuncAP,
class Hash3 = HashFuncDJB>
class BloomFilter
{
public:
void Set(const K& key)
{
size_t hash1 = Hash1()(key) % M;
size_t hash2 = Hash2()(key) % M;
size_t hash3 = Hash3()(key) % M;
//cout << hash1 << " " << hash2 << " " << hash3 << endl;
_bs.set(hash1);
_bs.set(hash2);
_bs.set(hash3);
}
bool Test(const K& key)
{
size_t hash1 = Hash1()(key) % M;
size_t hash2 = Hash2()(key) % M;
size_t hash3 = Hash3()(key) % M;
if (_bs.test(hash1) && _bs.test(hash2) && _bs.test(hash3))
{
return true; // 可能存在误判
}
return false;
}
// 获取公式计算出的误判率
double getFalseProbability()
{
double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);
return p;
}
private:
static const size_t M = N * X;
// 我们实现位图是用vector，也就是在堆上开的空间
bs::bitset<M> _bs;
//std::bitset<M> _bs;
// vs下std的位图是开的静态数组，M太大会存在崩的问题
// 解决方案就是bitset对象整体new一下，空间就开到堆上了
//std::bitset<M>* _bs = new std::bitset<M>();
};
测试布隆过滤器的代码是否正确
void TestBloomFilter1()
{
BloomFilter<10> bf;
bf.Set("孙悟空");
bf.Set("猪八戒");
bf.Set("唐僧");
cout << bf.Test("孙悟空") << endl;
cout << bf.Test("悟空孙") << endl;
cout << bf.Test("猪八戒") << endl;
cout << bf.Test("八戒猪") << endl;
cout << bf.Test("唐僧") << endl;
cout << bf.Test("唐僧1") << endl;
}
布隆过滤器误判率测试
void TestBloomFilter2()
{
srand(time(0));
const size_t N = 1000000;
BloomFilter<N> bf;
//BloomFilter<N, 3> bf;
//BloomFilter<N, 10> bf;
std::vector<std::string> v1;
//std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
//std::string url = "https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=ln2&fenlei=256&rsv_pq=0x8d9962630072789f&rsv_t=ceda1rulSdBxDLjBdX4484KaopD%2BzBFgV1uZn4271RV0PonRFJm0i5xAJ%2FDo&rqlang=en&rsv_enter=1&rsv_dl=ib&rsv_sug3=3&rsv_sug1=2&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&inputT=330&rsv_sug4=2535";
std::string url = "猪八戒";
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是相似字符串集（前缀一样），但是后缀不一样
v1.clear();
for (size_t i = 0; i < N; ++i)
{
std::string urlstr = url;
urlstr += std::to_string(9999999 + i);
v1.push_back(urlstr);
}
size_t n2 = 0;
for (auto& str : v1)
{
if (bf.Test(str)) // 误判
{
++n2;
}
}
cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
// 不相似字符串集 前缀后缀都不一样
v1.clear();
for (size_t i = 0; i < N; ++i)
{
//string url = "zhihu.com";
string url = "孙悟空";
url += std::to_string(i + rand());
v1.push_back(url);
}
size_t n3 = 0;
for (auto& str : v1)
{
if (bf.Test(str))
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
cout << "公式计算出的误判率:" << bf.getFalseProbability() << endl;
}
布隆过滤器的bit⻓度 与 插⼊过滤器的元素个数的比值 X 为 5
布隆过滤器的bit⻓度 与 插⼊过滤器的元素个数的比值 X 为 3
布隆过滤器的bit⻓度 与 插⼊过滤器的元素个数的比值 X 为 10
2.4 布隆过滤器删除问题
布隆过滤器默认是不⽀持删除的，因为⽐如"猪⼋戒“和”孙悟空“都映射在布隆过滤器中，他们映射的位有⼀个位是共同映射的(冲突的)，如果我们把孙悟空删掉，那么再去查找“猪⼋戒”会查找不到，那么“猪⼋戒”间接被删掉了。
2.5 布隆过滤器的应用
⾸先我们分析⼀下布隆过滤器的优缺点：
优点：效率⾼，节省空间，相⽐位图，可以适⽤于各种类型的标记过滤
缺点：存在误判(在是不准确的，不在是准确的)，不好⽀持删除
布隆过滤器在实际中的⼀些应⽤：
爬⾍系统中URL去重：
在爬⾍系统中，为了避免重复爬取相同的URL，可以使⽤布隆过滤器来进⾏URL去重。爬取到的URL可以通过布隆过滤器进⾏判断，已经存在的URL则可以直接忽略，避免重复的⽹络请求和数据处理。
垃圾邮件过滤：
在垃圾邮件过滤系统中，布隆过滤器可以⽤来判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件的特征信息存储在布隆过滤器中，当新的邮件到达时，可以通过布隆过滤器快速判断是否为垃圾邮件，从⽽提⾼过滤的效率。
预防缓存穿透
在分布式缓存系统中，布隆过滤器可以⽤来解决缓存穿透的问题。缓存穿透是指恶意用户请求⼀个不存在的数据，导致请求直接访问数据库，造成数据库压⼒过⼤。布隆过滤器可以先判断请求的数据是否存在于布隆过滤器中，如果不存在，直接返回不存在，避免对数据库的⽆效查询。
对数据库查询提效
在数据库中，布隆过滤器可以⽤来加速查询操作。例如：⼀个app要快速判断⼀个电话号码是否注册过，可以使⽤布隆过滤器来判断⼀个用户电话号码是否存在于表中，如果不存在，可以直接返回不存在，避免对数据库进⾏⽆⽤的查询操作。如果在，再去数据库查询进⾏⼆次确认。
3. 海量数据处理问题
3.1 10亿个整数里面求最大的前100个
经典topk问题，⽤堆解决。
3.2 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？
分析： 假设平均每个query字符串50byte，100亿个query就是5000亿byte，约等于500G(1G约等于10亿多Byte)
哈希表 / 红⿊树等数据结构肯定是⽆能为⼒的。
解决⽅案1： 这个⾸先可以⽤布隆过滤器解决，⼀个⽂件中的query放进布隆过滤器，另⼀个⽂件依次查找，在的就是交集，问题就是找到交集不够准确，因为在的值可能是误判的，但是交集⼀定被找到了。
解决⽅案2：
哈希切分，⾸先内存的访问速度远⼤于硬盘，⼤⽂件放到内存搞不定，那么我们可以考虑切分为⼩⽂件，再放进内存处理。
但是不要平均切分，因为平均切分以后，每个⼩⽂件都需要依次暴⼒处理，效率还是太低了。
可以利⽤哈希切分，依次读取⽂件中query，i = HashFunc(query) % N，N为准备切分多少份⼩⽂件，N取决于切成多少份，内存能放下，query放进第i号⼩⽂件，这样A和B中相同的query算出的hash值i是⼀样的，相同的query就进⼊的编号相同的⼩⽂件就可以编号相同的⽂件直接找交集，不⽤交叉找，效率就提升了。
本质是相同的query在哈希切分过程中，⼀定进⼊的同⼀个⼩⽂件Ai和Bi，不可能出现A中的的query进⼊Ai，但是B中的相同query进⼊了和Bj的情况，所以对Ai和Bi进⾏求交集即可，不需要Ai和Bj求交集。（本段表述中i和j是不同的整数）
哈希切分的问题就是每个⼩⽂件不是均匀切分的，可能会导致某个⼩⽂件很⼤内存放不下。我们细细分析⼀下某个⼩⽂件很⼤有两种情况：1.这个⼩⽂件中⼤部分是同⼀个query。2.这个⼩⽂件是有很多的不同query构成，本质是这些query冲突了。针对情况1，其实放到内存的set中是可以放下的，因为set是去重的。针对情况2，需要换个哈希函数继续⼆次哈希切分。所以我们遇到⼤于1G⼩⽂件，可以继续读到set中找交集，若set insert时抛出了异常(set插⼊数据抛异常只可能是申请内存失败了，不会有其他情况)，那么就说明内存放不下是情况2，换个哈希函数进⾏⼆次哈希切分后再对应找交集。
3.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。本质是相同的ip在哈希切分过程中，⼀定进⼊的同⼀个⼩⽂件Ai，不可能出现同⼀个ip进⼊Ai和Aj的情况，所以对Ai进⾏统计次数就是准确的ip次数。
4. 位图相关例题
现有容量为10GB的磁盘分区，磁盘空间以簇（cluster）为单位进行分配，簇的大小为4KB，若采用位图法管理该分区的空闲空间，即用一位（bit）标识一个簇是否被分配，则存放该位图所需簇的个数为 （）
A.80
B.320
C.80K
D.320K
答案
10GB = 10 * 1024 * 1024K ，一个簇大小为4K，那10GB总共有 10 * 1024 * 1024 / 4 = 10 * 1024 * 256个簇用位图来进行存储时：一个簇占用一个比特位，总共需要10 * 1024 * 256个比特位，10 * 1024 * 256 bit = 10 * 1024 * 256 / 8 Byte = 320K，一个簇大小为4K，故总共需要320K / 4K=80个簇进行存储。因此：选择A
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
32
0- 0
已为社区贡献1条内容
所有评论(0)