布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间.
在面对海量整数数据时,使用位图不但效率高还节省空间.但是位图对数据类型有限制,只能映射处理整数类型数据.
可是如果处理含量字符串数据时,该怎么处理呢?
此时布隆过滤器便由此而生.
由于位图采用的是直接定址法,不存在哈希冲突.
而布隆过滤器实质采用的是通过哈希算法转换成整数映射一个位置进行进行标记,此时便难免会产生哈希冲突,并且哈希冲突概率较高.
例如以下图示:
但是我们通过布隆过滤器了解的是:
如果该字符串显示存在,说明是不准确的,存在误判.
如果该字符串显示不存在,说明是准确的,不存在误判.
那么通过哈希算法计算映射位置是不可能完全除去误判,但是可以降低误判率,那么怎么降低布隆过滤器的误判率?
我们可以将么一个字符串多映射几个位(调用不同的哈希算法让同一个字符串映射不同位置),理论而言,一个字符串映射的位越多,则误判效率越低,但是也不能映射太多位置,因为映射的位置数越多,消耗的空间就越大,进而会导致布隆过滤器的优势降低.
所以我们可以给每个字符串设置3个映射位,例如以下图示,假如黄瓜与香蕉和西瓜分别有一个映射位置发生了哈希冲突,但是它还有一个映射位置:
如果这个位置被设置了,说明它确实存在.
如果这个位置没有被设置,说明它确实不在.
所以,只有三个映射位置都跟别的数据发生冲突才可以造成误判,可是误判的的概率相较之前极大降低.
一:黑名单应用
当我们给出大量数据名单来检测是存在于黑名单中时,我们便可以使用布隆过滤器进行筛选:
如果给出名单经过布隆过滤器检测显示存在(此时可能有误判),那么我们需要到黑名单数据库中进一步检测查找.
如果给出名单经过布隆过滤器检测后显示不存在(没有误判),那么我们可以直接返回检测结果,不需要到数据库中查询.
布隆过滤器将名单中不存在于黑名单的过滤,让大量数据只有有限数据能够到数据库中检测,进而提高了查找效率.
二:注册昵称检查
当我们在注册页面中输入注册昵称时,显示昵称是否被占用时:
如果提示被占用,可能存在误判,但是可以允许,因为误判的概率很小,那么我们不可以使用该名称注册.
如果提示没被占用,说明我们可以使用该名称注册.
综合来讲,以上应用场景适合允许误判的情况下,提高了查找效率.
布隆过滤器由一个位图构成,其中N表示要映射N个数据.此外为了准确开辟N个数据所需要合适大小的布隆过滤器,有人通过检测研究得出了以下关系式:
其中,n代表哈希函数个数,m为布隆过滤器长度,n为需要插入的元素个数,p为误报率.
在模拟实现中,我们所需要的哈希函数为3个,所以通过计算得出布隆过滤器中插入一个元素需要4.2个位长度的位图.(为了防止映射位置不够,我们设置为5).
由于布隆过滤器一般用于处理字符串类型的数据,所以将模板参数的K缺省值设为string.
//三个哈希函数
//布隆过滤器框架
template<size_t N, class K = string, class Hash1 = BKDRHash, class Hash2 = APHash, class Hash3 = DJBHash>
class BloomFilter
{
public:
private:
const static size_t _ratio = 5; //const static 可以直接定义;
std::bit_set<_ratio* N> _bits;
};
此外,为了能够将字符串转换成整型,我们采取了经过测试,综合评分最高的HashBKDR,HashAP,HashDJB算法计算元素哈希映射位置,进而极大避免了哈希冲突的概率.
struct HashBKDR
{
size_t operator()(const string& s)
{
size_t value = 0;
for (auto ch : s)
{
value = value * 131 + ch;
}
return value;
}
};
struct HashAP
{
size_t operator()(const string& s)
{
size_t value = 0;
for (size_t i = 0; i < s.size(); i++)
{
if ((i & 1) == 0)
{
value ^= ((value << 7) ^ s[i] ^ (value >> 3));
}
else
{
value ^= (~((value << 11) ^ s[i] ^ (value >> 5)));
}
}
return value;
}
};
struct HashDJB
{
size_t operator()(const string& s)
{
if (s.empty())
return 0;
size_t value = 5381;
for (auto ch : s)
{
value += (value << 5) + ch;
}
return value;
}
};
布隆过滤器的插入实则是在位图中,通过三个哈希函数分别计算出该元素的映射位置,然后再复用位图中的set函数将对应映射位置置为1.
void set( const K& key )
{
size_t hash1 = Hash1()(key) % (_ratio * N);
_bits.set(hash1);
size_t hash2 = Hash2()(key) % (_ratio * N);
_bits.set(hash2);
size_t hash3 = Hash3()(key) % (_ratio * N);
_bits.set(hash3);
}
注意:
只有当该元素映射的三个位置都被设置为1,才能说明该元素存在(也有可能这三个位置都发生哈希冲突,但这概率较低).
布隆过滤器用于探测某个元素是否存在于布隆过滤器中,检测时,我们只要通过该元素分别找到该元素对应的三个比特位,然后再分别判断这三个比特位的状态:
如果这三个比特位全部被设置,说明该元素存在,返回true.(可能存在误判).
如果这三个比特位有一个位没被设置,就说明该元素一定不存在.(三个位置有的其他位被设置可能发生哈希冲突).
bool test(const K& key)
{
size_t hash1 = Hash1()(key) %(_ratio * N)
if ( _bits.test(hash1) == false)
return false; //该元素一定不存在.
size_t hash2 = Hash2()(key) % (_ratio * N);
if ( _bits.test(hash2) == false )
return false;
size_t hash3 = Hash3()(key) % (_ratio * N);
if ( _bits.test(hash3) == false )
return false;
return true; //所以就表明在.(可能存在误判)
}
注意:
1:由于一个比特位存在并不能说明该元素存在过,但是有一个比特位不存在却能说明该元素不存在,所以我们不能判断比特位存在的情况,而是要判断该比特位不存在的情况.
2:为了防止计算哈希映射位置范围超过比特位的范围造成越界,我们%布隆过滤器的长度来控制计算出来的结果在布隆过滤器范围内.
布隆过滤器一般不支持删除,原因如下:
1:因为布隆过滤器判断一个元素存在时会存在误判,因此我们不能保证删除的元素存在于布隆过滤器中,此时通过该元素将计算出的映射为设置为0可能会影响其他数据.
2:当删除的数据确实在布隆过滤器中,但是也有可能该元素的三个映射位中有其它映射位发生了哈希冲突,此时,将这些映射位设置为0,也会影响到其他元素的检测.
例如以下图示:
那么如何让布隆过滤器支持删除呢?
1: 我们必须要保证删除的元素存在于不容过滤器中,例如在昵称应用时,我们要删除一个名称在删除之前我们可以提前设置一个test函数检测筛选出可能存在的名称,如果结果为存在(还不能判断真正存在),那么我们就需要到名称数据库中查找该名称,确定该名称是否真正存在.
2: 我们要保证删除该元素后不会影响到其他元素,所以我们可以在位图的每一个比特位中设置一个计数值,如果铀元素插入到对应的比特位,那么该比特位的计数器就++,在删除时,我们只需要将该元素对应比特位计数器–就行.
例如以下图示:
但是,布隆过滤器还是没有提供删除函数,因为布隆过滤器的优势本来就是调高查找效率和节省空间,如果删除时要确认该元素是否存在还要在数据库中查找,消耗时间. 且还需要在每个比特位中设置一个计数变量,这又要多占用几倍的存储代价.
using namespace std;
struct HashBKDR
{
size_t operator()(const string& s)
{
size_t value = 0;
for (auto ch : s)
{
value = value * 131 + ch;
}
return value;
}
};
struct HashAP
{
size_t operator()(const string& s)
{
size_t value = 0;
for (size_t i = 0; i < s.size(); i++)
{
if ((i & 1) == 0)
{
value ^= ((value << 7) ^ s[i] ^ (value >> 3));
}
else
{
value ^= (~((value << 11) ^ s[i] ^ (value >> 5)));
}
}
return value;
}
};
struct HashDJB
{
size_t operator()(const string& s)
{
if (s.empty())
return 0;
size_t value = 5381;
for (auto ch : s)
{
value += (value << 5) + ch;
}
return value;
}
};
template < size_t N,class K = string,class Hash1 = HashBKDR,class Hash2=HashAP,class Hash3 = HashDJB>
class BloomFilter
{
public:
void set( const K& key )
{
size_t hash1 = Hash1()(key) % (_ratio * N);
// cout << hash1 << endl;
_bits.set(hash1);
size_t hash2 = Hash2()(key) % (_ratio * N);
// cout << hash2 << endl;
_bits.set(hash2);
size_t hash3 = Hash3()(key) % (_ratio * N);
// cout << hash3 << endl;
_bits.set(hash3);
}
bool test(const K& key)
{
size_t hash1 = Hash1()(key) %(_ratio * N);
// cout << hash1 << endl;
if ( _bits.test(hash1) == false)
return false;
size_t hash2 = Hash2()(key) % (_ratio * N);
// cout << hash2 << endl;
if ( _bits.test(hash2) == false )
return false;
size_t hash3 = Hash3()(key) % (_ratio * N);
// cout << hash3 << endl;
if ( _bits.test(hash3) == false )
return false;
//走到这里,说明三个探测为不在.
return true; //所以就表明在.(可能存在误判)
}
private:
const static size_t _ratio = 5; //const static 可以直接定义;
myBit::bit_set<_ratio* N> _bits;
};
void TestBloomFilter()
{
BloomFilter<10> bf;
string arr[] = { "苹果","西瓜22","苹果111","西瓜22","苹果2222","香蕉3333","西瓜3333","美团333","阿里333","字节"};
for (auto& str : arr)
{
bf.set(str);
}
string arr1[] = { "苹果","西瓜","苹果111","西瓜22" };
for (auto& str : arr1)
{
cout << bf.test(str) << endl;
}
}
题目一: 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件的交集？给出近似算法。
题目中要求给出近似算法,意味着可以允许存在一些误判,这时,我们便可以采用使用布隆过滤器:
1: 首先遍历读取到一个文件中的querry,将该文件的querr全部插入到布隆过滤器中.
2: 然后再遍历读取另外一个文件的querry,使用test()函数分别判断每个querry是否存在与布隆过滤器中,如果存在,则说明该querry是交集,如果不存在,说明该querry不是交集.
题目二: 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件的交集？给出精确算法。
如果这道题要求我们给出的是精确算法,那么我们就不能使用布隆过滤器了,此时应该用上哈希切分.
首先,我们先来计算以下内存空间计算题:
假设每个查询30byte,100亿个查询需要多少个空间?
进制转换如下:
综合以上进度转换:
10 亿字节 = 1GB;
3000亿字节 = 300GB = 300000MB;
当我们清楚内存进制转换后,此时我们便可以对更加方便的使用哈希切分思想解题,步骤如下:
1:依次读取文件A中的querry, 使用哈希算法 i = Hash(querry) % 1000,分别计算每个querry对应的映射位置( i 的范围为0-999).这里实则是将文件A中的querry分成了1000个小文件,每个小文件的大小为300MB,然后让每个querry放进对应编号为Ai的小文件中.
2:依次读取文件A中的querry, 使用哈希算法 i = Hash(querry) % 1000,分别计算每个querry对应的映射位置( i 的范围为0-999).这里实则是将文件A中的querry分成了1000个小文件,每个小文件的大小为300MB,然后让每个querry放进对应编号为Ai的小文件中.
3: 我们知道在AB两个文件中,相同的querry一定被放进相同编号i的小文件中,我们可以依次将Ai和Bi(编号相同)的小文件分别放进两个set容器中,set容器会对该小文件中的querry的进行去重,然后依次遍历这两个容器,如果querry相同即为交集.
图示如下:
有没有可能某个小文件由于哈希冲突很多导致文件太大了,加载不到程序中?
我们可以将这个算法思想写成递归,再对这个文件进行哈希切分成一个个小文件,但是我们为了防止该query的映射位置相同,我们要换一个哈希算法来计算该query的映射位置,并且我们要根据该文件的大小合理分配每个小文件的大小.
题目二:给一个超过100G大小的log file，log中存着IP地址，设计算法找到出现次数最多的IP地址？
我们也可以将这100GB大小的log file 分成一个个小文件,这里我们选择分成500个,每个文件200MB,这样就会让相同的ip进入到同一个小文件中.
我们知道,虽然相同的ip一定会进入同一个小文件,但是同一个小文件中有可能会有不同的ip:
1: 有可能ip不同,但是通过哈希函数计算出来的映射位置相同,即哈希冲突.
2: 有可能哈希函数计算出来的结果不相同相同,但是%500之后计算出来的映射位置是相同的.
但是这些问题并不重要不重要,且概率较小,我们能保证大部分的小文件中的ip相同就行.
然后使用map<string,int>对每个小文件的ip统计出现次数,找出每个小文件中出现次数最多的ip,然后依次遍历对比,就可以获取log file文件中次数出现最多的ip了(当然也有可能出现小文件因哈希冲突过多导致内存过大,我们只要对其递归进行哈希切分即可).
针对本题如何找到top K的IP?
如果要找到出现topK的IP地址,我们可以先将一个小文件加载到内存中,选出该次数最多的K个IP地址建一个k值pair<ip,count>类型的小堆,然后依次将剩下的小文件加载内存,如果该小文件中IP统计次数大于堆顶IP统计次数,则将堆顶IP与该文件中的IP进行交换,然后再进行向下调整,使其认为小堆,此时,小堆的K个IP即为这两个小文件中的统计次数最多的K个IP,如果对比完所有小文件中的ip后,此时的小堆中K个IP即为log file 文件中统计次数最多的K个的IP.