【C++高阶】哈希—— 位图 | 布隆过滤器 | 哈希切分

island1314 2024-08-20 14:35:02 阅读 70

✨                                          人生如梦,朝露夕花,宛若泡影     🌏

📃个人主页:island1314

🔥个人专栏:C++学习

⛺️ 欢迎关注:👍点赞 👂🏽留言 😍收藏  💞 💞 💞

  


🚀引言

 之前我们已经在这篇文章中 【C++高阶】哈希函数底层原理全面探索和深度解析-CSDN博客 

了解到了哈希的一些相关知识,现在我们来对哈希进行一些扩展了解

1.  位图

🥃问题:

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

根据我们现有的知识,该如何处理上诉问题呢?

方法一:排序 + 二分查找

因为二分查找的效率还是比较高的,logN的时间复杂度,但是磁盘上面无法进行排序,排序要支持下标的随机访问,这40亿个整数又无法加载到内存里面,你怎么进行排序呢?所以这样的方式也是不可行的。

方法二:红黑树 或者 哈希表

红黑树查找的效率是logN,哈希表可以直接映射,查找的效率接近常数次,虽然他们查找的效率确实很快,但是40亿个整数,那就是160亿字节,10亿字节是1GB,16GB字节红黑树和哈希表怎么能存的下呢?这还没有算红黑树的三叉链结构,每个结点有三个指针,而且哈希表每个结点会有一个next指针,算上这些的话需要的内存会更大,所以用红黑树或哈希表也是无法解决问题的。

但是这些方式都行不通,先来看一下40亿的无符号整数占用多大的内存空间:

10亿个字节 ≈ 1GB。40亿个字节 ≈ 4GB。40亿个无符号整数 ≈ 16GB。

而一般的内存根本放不下这么多的数据,无论是上面的哪种方法,都需要存放数据本身,即使是用数组来存放都需要16GB,如果用红黑树(有三叉链,颜色)需要大的内存,哈希表虽然少一点,但是仍然有next指针,还是存放不下.

问题中只要求判断一个数是否在这40亿个数据中,所以可以不存放数据本。

因此我们可以采用 位图 的方式来处理这个问题。

1.1 位图概念

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

🍉对于40亿个数据,至少需要40亿个比特位才能标识它们的状态,对于这种情况一般选择

2^{32}

个比特位:因为 

2^{31}

 < 40亿 < 

2^{32}

232 = 42亿9千多万,40亿个数据完全可以表示的下,此时相当于一个数组,有232个元素,每个元素是一个比特位。

使用位图方式占用的内存就小多了:

 

2^{32}

 个比特位 =

2^{29}

个字节 =

2^{19}

KB =

2^{9}

MB = 512MB = 0.5GB从最开始需要16GB内存空间直接下降到了需要0.5GB的空间。

但是在语言层面上并没有比特位的数组。

  

2^{32}

个比特位可以用

2^{27}

个int类型的数组来表示。 也可以用

2^{29}

个char类型的数组来表示。

🌰🌰随便例举一些数字,如下图所示,这里采用char类型为数组的基本单位。

数据范围是1到22,所以需要3个char类型的变量。下标为1的比特位表示数字1的存在情况,下标为18的比特位表示数字18是否存在这3个char类型的变量是用一个数组实现的,即char [3]。这3个char类型变量的地址从左到右依次升高,但是每个char类型中比特位却是:低的比特位在右,高的比特位在左。

确定数据的映射位置:

如何确定一个数据映射在位图的哪个比特位呢?以整数18为例说明:

 18映射在位图下标为2的八个比特位中,即第三个char类型变量。(18 / 8 ) 具体映射在下标为2的char类型变量中下标为2的比特位上,也就是在这个char类型中第三个比特位上。(18 % 2)

💢💢注:如果数据相对集中,而且从比较大的数字开始的,可以采用相对值,比如最小的数据是1000,最大的数据是2000,可以开辟1000个比特位的位图,下标为0的比特位表示数字1000是否存在,依此类推。

不适用int类型数组的原因:

💢我们知道,数据在内存中的存储是有大小端的,如果使用int类型的数组,上图就变成:

只需要一个int类型的数据就够了,并且还多出8个比特位。

💢假设上图中是小端存储方式,并且是处理完的位图,此时将这份代码换到了大端存储方式的机器上:

此时位图结构就变成了上图中所示,原本表示数字0~7的8个比特位放在了高地址处,变成了表示24 ~31的8个比特位。

 原本在小端机上的程序在大端机上极有可能出现BUG。而采用char类型数组就不用考虑大小端的问题,因为一个char类型就是一个字节,每个char都是从低地址到高地址排列。

上面是在内存中存储的真实样子,但是我们在使用的时候无需知道位图在内存中样子。

这种方式其实就是一种哈希思想,将数据直接映射到位图上。

1.2 位图实现

<code>namespace qian

{

// 非类型模板参数

template <size_t N>

class bitset

{

public:

bitset() 构造函数

{

//_bits.resize(N / 8 + 1, 0);

//可能开的比特位恰好满足数字的个数,也可能最多浪费7个比特位

//_bits.resize(N >> 3 + 1, 0);//位运算符优先级过低,这里先进行+运算,则结果和我们预想的不一致,发生错误。

_bits.resize((N >> 3) + 1, 0);

}

void set(size_t x) // x 映射的位标记为 1

{

size_t i = x >> 3; //映射到第几个char中

size_t j = x % 8; //映射到char中第几个比特位

//将映射到位图中的比特位置一

_bits[i] |= 1 << j;

}

void reset(size_t x) // x 映射的位标记为 0

{

size_t i = x >> 3;

size_t j = x % 8;

_bits[i] &= ~(1 << j);

}

bool test(size_t x) // x 映射位为1返回真,0返回假

{

size_t i = x / 8;

size_t j = x % 8;

return _bits[i] & (1 << j);//这里不是&=,因为test不改变位图,只是判断一下而已

//有些编译器bool值是四个字节,返回时会发生整型提升,高位补符号位,但这些都不重要,只要是非0就行,判断为真

//我的编译器bool值是一个字节

}

private:

vector<char> _bits;

};

}

基本构造剖析

 使用非类型模板参数,该参数用来指定位图比特位的个数。 底层使用的是vector,vector中是char类型变量。

在构造函数中需要指定vector的大小,否则vector的大小是0,一个比特位也没有。

非类型模板参数N指定是比特位的个数,而构造函数开辟的是char类型变量的个数,所以需要N / 8。由于N / 8的结果不是整数时会取整而抛弃小数部分,所以需要在N /8 后再加1,也就是再增加 8 个比特位来确保位图够用。

CPU在计算除法的时候,其实是很复杂的,而进行移位运算就很简单,效率也非常高。

N / 8相当于N右移3位。

因此我们使用移位运算来代替除法来提高效率

需要注意的是:加法的优先级比移位运算高,所以必须给(N>>3)加括号

函数剖析:

🍅set()

该接口的作用是将x映射在位图中的比特位置1,表示该数据存在。

 首先将x映射在位图中的位置计算出来。 然后将映射的比特位置一。

💢如上图所示,要将一个char类型中的8个比特位的某一个位置一而不影响其他位,就需要或等一个只有那个位是1其他位都是0的char类型,这样一个char类型可以通过1左移固定位数得到。

🍍reset():

<code>void reset(size_t x) // x 映射的位标记为 0

{

size_t i = x >> 3;

size_t j = x % 8;

_bits[i] &= ~(1 << j);

}

该接口的作用是将x映射在位图中的比特位清0,表示数据x不存在。

 同样先计算处x所在位图中的位置。 然后再进行清0。

💢如上图所示,将char类型中的某个比特位清0而不影响其他位,需要与等一个只有那个位是0其他位都是1的char类型变量,这样一个char类型可以通过1左移固定位数,然后取反得到。

🍌test()

该接口的作用是在位图中查找数据x是否存在。

 首先计算出x映射在位图中的位置。 然后看该比特位是0还是1。

判断某个比特位是1还是0,需要一个只有这个位是1其他位都是0的char类型变量,如果这个bit是0,那么与以后的结果就是0,对应的bool值flase,如果这个bit是1,那么与以后的结果就不是0,对应的bool值是true。

bool值本质上是4个字节的整形,所以这里涉及到了整形提升,但是并没有影响。如果与以后的结果是0,整形提升后的结果仍然是0,bool值就是false。如果与以后的结果非0,即使符号位是1,整形提升和的结果仍然非0,bool的值就是true。

位图的测试

创建

2^{32}

个比特位的位图方式:

第一种方式:指定大小位-1,因为非类型模板参数是size_t类型的,所以-1强转位size_t以后,32个比特位都是1,所以就是232。

第二种方式:使用十六进制的方式,指定非类型模板参数的size_t类型的32个比特位都是1,此时也是

2^{32}

比较差的方式:使用

2^{32}

的十进制,也就4294967296,这个数字容易记错。

根据上面程序运行结果,可以看到,置一,清零,判断都符合我们的预期。

从任务管理器中查看我们的程序所占的内存,当32个比特位的位图没有创建的时候,所占内存大小7.9MB,位图创建以后,所占内存变成了519.8MB,增加了512MB,也就是0.5GB,这和我们之前分析的一样。

任何一个数据集,使用32个比特位的位图都可以统计的下,也就是最多占用0.5GB的空间。因为整数的最大值就是232,也就是4294967296,32个比特位的位图足够放的下。即使数据集的数据个数是10个亿,但是这里有很多的重复的数据,而最大值也不会超过232。

注意:位图只能判断整数存不存在,并不存放数据本身。


1.3 位图应用

首先我们分析⼀下哈希位图的优缺点:

优点:增删查改快,节省空间

缺点:一般要求数据相对集中,否则会导致空间消耗上升。并且只适⽤于整形

布隆过滤器在实际中的⼀些应用:

🍈应用一

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

分析:

首先这100亿个数据在内存中肯定是放不下的,所以之前学习的存放数据本身的数据结构都用不了,只能用位图。位图的一个比特位只有两种状态来表示数据的有无,这里是要统计次数,所以就要让位图不仅仅只有两种状态。

解决办法:

💢之前是判断整数是否出现,现在是判断只出现一次的整数,那就说明有的整数出现了多次,其实解决起来也很简单,我们

只需要开两个位图即可,用两个比特位去标识即可,两个位图相同下标的两个比特位来表示一个数据的状态。00表示0次,01表示1次,10及11表示一次1以上。

💢有人可能会觉得100亿个整数太多了,担心位图存不下,别说100亿,就是1000亿,1w亿都能存的下,因为位图存的是一个范围内有多少种数,与数据的个数完全无关,仅仅和数据的范围有关系,所以根本不用担心存不下这样的事情,因为整数最多就42亿多个。

代码如下:

<code>template <size_t N>

class twobitset

{

public:

twobitset()//初始化列表会初始化

{}

void set(size_t x)

{

if (!_bs1.test(x) && !_bs2.test(x))

{

//出现0次,则搞成01

_bs2.set(x);

}

else if (!_bs1.test(x) && _bs2.test(x))

{

//出现1次,则搞成10

_bs1.set(x);

_bs2.reset(x);

}

//10出现1次以上,不需要变他

}

void PrintOnce()

{

for (size_t i = 0; i < N; i++)

{

if (!_bs1.test(i) && _bs2.test(i))

{

//如果是01,说明出现一次,可以打印出来

cout << i << " ";

}

}

}

private:

bitset<N> _bs1;

bitset<N> _bs2;

};

测试结果如下:

🍅应用二

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

解决办法:

两个文件都有100一个整数,必然放不进内存中,所以同样采用位图结构。每个文件使用一个232个比特位的位图,两个文件就是两个位图,占用的内存也就是1GB,符合要求。

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

测试代码如下:

<code>// 模拟位图找交集

void test_interbitset()

{

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 };

bitset<100> bs1;

bitset<100> bs2;

for (auto e : a1)

{

bs1.set(e);

}

for (auto e : a2)

{

bs2.set(e);

}

cout << "交集为:" << endl;

for (size_t i = 0; i < 100; i++)

{

if (bs1.test(i) && bs2.test(i))

{

cout << i << " " << endl;

}

}

}

🍍应用三

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

解决办法:

💢之前我们是标记在不在,只需要⼀个位即可,这⾥要统计出现次数不超过2次的,可以每个值⽤两个位 标记即可,00代表出现0次,01代表出现1次,10代表出现2次,11代表出现2次以上。最后统计出所有 01和10标记的值即可。

1.4 其他写法

比如我们数据存到vector中,相当于每个int值映射对应的32个值,比如第⼀个整形映射0-31对应的位,第⼆个整形映射32-63对应的位,后面的以此类推,那么来了⼀个整形值 x,i=x/32;j=x%32;计算出x映射的值在vector的第i个整形数据的第j位。

<code>namespace island

{

template<size_t N> // N是需要多少⽐特位

class bitset

{

public:

bitset()

{

_bs.resize(N / 32 + 1);

}

// x 映射的位标记为 1

void set(size_t x)

{ //在第 i 个值的 第 j 位

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)); // 让1左移j 位

}

// x 映射位为1返回真,0返回假

bool test(size_t x)

{

size_t i = x / 32;

size_t j = x % 32;

return _bs[i] & (1 << j);

}

private:

std::vector<int>_bs;

};

//模拟位图找交集

void test_bitset()

{

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 };

bitset<100> bs1;

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次的所有整数

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

{

_bs1.set(x);

_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()

{

bit::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;

}

}

}

}

2. 布隆过滤器

2.1 布隆过滤器的概念

有⼀些场景下面,有大量数据需要判断是否存在,而这些数据不是整形,那么位图就不能使用了,使用红黑树/哈希表等内存空间可能不够。这些场景就需要布隆过滤器来解决。

 布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的⼀种紧凑型的、比较巧妙的概率型 数据结构特点是高效地插⼊和查询,可以⽤来告诉你 “某样东西⼀定不存在或者可能存在”,它是 ⽤多个哈希函数,将⼀个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。 布隆过滤器的思路就是把key先映射转成哈希整型值,再映射一个位,如果只映射一个位的话,冲突率会比较多,所以可以通过多个哈希函数映射多个位,降低冲突率。 布隆过滤器这里跟哈希表不一样,它无法解决哈希冲突的,因为他压根就不存储这个值,只标记映射 的位。它的思路是尽可能降低哈希冲突判断一个值key在是不准确的,判断一个值key不在是准确 的。

2.2 布隆过滤器器误判率推导

如果大家还想更深了解可以参考下面这篇文章

如何选择哈希函数个数和布隆过滤器长度一文中,对这个问题做了详细的研究和论证。

 

2.3 布隆过滤器的实现

哈希函数

首先需要写几个哈希函数来将字符串转换成整形,各种字符串Hash函数一文中,介绍了多种字符串转换成整数的哈希函数,并且根据冲突概率进行了性能比较,有兴趣的朋友可以自行研究一下。

<code>//下面三个字符串转换成整形的仿函数

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,

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;

if (!_bs.test(hash1))

{

return false;

}

size_t hash2 = Hash2()(key) % M;

if (!_bs.test(hash2))

{

return false;

}

size_t hash3 = Hash3()(key) % M;

if (!_bs.test(hash3))

{

return false;

}

return true; // 可能存在误判

}

// 获取公式计算出的误判率

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;

island::bitset<M> _bs;

};

基本框架分析:

该模板有多个参数,但是大部分都是使用的缺省值,不用必须去传参,底层使用的上面1.4中实现的bitset。

size_t N:最多存储的数据个数。size_t X = 5, //平均存储一个值,需开辟X个位,该值根据前面公式得来,此时哈希函数是3个,故m=3n/ln2=4.3n,向上取整后X为5,先给个缺省值是5。class K:布隆过滤器处理的数据类型,默认情况下是string,也可以是其他类型。哈希函数:将字符串或者其他类型转换成整形进行映射,给的缺省值是将字符串转换成整形的仿函数。

函数剖析:

set():

将数据经过三个哈希函数的处理得到三个整数,然后将这三个整数都映射到位图中来表示这个数据存在。

Test():

对每一个哈希函数得到的整数所映射的位置进行判断,如果某个位置不存在直接返回false,说明这个字符串不存在,当四个整数所映射的位置都存在,说明这个字符串存在。

getFalseProbability():

获取公式的误判率

布隆过滤器的测试

测试1:

测试2:

<code>void TestBloomFilter2()

{

srand(time(0));

const size_t N = 10000;

BloomFilter<N> bf;

//BloomFilter<N, 3> bf;

//BloomFilter<N, 10> bf;

std::vector<std::string> v1;

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 = "孙悟空";

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;

}

可以看到,X值越大,也就是一个字符串所需要的映射比特位越多,布隆过滤器的误判率越小。但是空间消耗也增加了。

哈希函数的个数越多,误判率也会越小,但是对于的空间消耗也会增加。

综上我们可知布隆过滤器只能提高存在判断的准确率,并不能让它完全准确。

2.4 布隆过滤器的删除

布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素。

“猪八戒” 和 “孙悟空”  映射的比特位都有第4个比特位。删除上图中 “猪八戒” 元素,如果直接将该元素所对应的二进制比特位置0,“孙悟空” 的元素也被删除了,因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

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

缺陷:

无法确认元素是否真正在布隆过滤器中如果采用计数方式删除,存在计数回绕

2.5 布隆过滤器的应用

首先我们分析⼀下布隆过滤器的优缺点:

优点:效率高,增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关。数据量很大时,布隆过滤器可以表示全集,其他数据结构不能

6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算。哈希函数相互之间没有关系,方便硬件并行运算。相比位图,可以适用于各种类型的标记过滤

缺点:存在误判(在是不准确的,不在是准确的),不好支持删除,不能获取元素本身。

布隆过滤器在实际中的⼀些应用:

爬虫系统URL去重

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

垃圾邮件过滤

在垃圾邮件过滤系统中,布隆过滤器可以用来判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件 的特征信息存储在布隆过滤器中,当新的邮件到达时,可以通过布隆过滤器快速判断是否为垃圾邮件,从而提高过滤的效率。

预防缓存穿透

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

对数据库查询提效

在数据库中,布隆过滤器可以用来加速查询操作。例如:⼀个app要快速判断⼀个电话号码是否注册过,可以使⽤布隆过滤器来判断⼀个用户电话号码是否存在于表中,如果不存在,可以直接返回不存 在,避免对数据库进行无用的查询操作。如果在,再去数据库查询进行二次确认

3. 哈希切分

我们可以用哈希切分对海量数据处理问题

3.1 应用一

给两个⽂件,分别有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是不同的整数)哈希切分的问题就是每个小文件不是均匀切分的,可能会导致某个小文件很⼤内存放不下。我们细细分析⼀下某个小文件很大有两种情况:

这个小文件中大部分是同⼀个query。这个小文件是 有很多的不同query构成,本质是这些query冲突了。

针对情况1,其实放到内存的set中是可以放 下的,因为set是去重的。针对情况2,需要换个哈希函数继续⼆次哈希切分。所以本体我们遇到大于1G小文件,可以继续读到set中找交集,若set insert时抛出了异常(set插⼊数据抛异常只可能是 申请内存失败了,不会有其他情况),那么就说明内存放不下是情况2,换个哈希函数进⾏二次哈希 切分后再对应找交集。

3.2 应用二

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

本题的思路跟上题完全类似,依次读取文件A中query,i=HashFunc(query)%500,query放进Ai号小文件,然后依次⽤map对每个A小文件统计 ip 次数,同时求出现次数最多的 ip或者topk ip。本质是相同的 ip 在哈希切分过程中,⼀定进⼊的同⼀个小文件Ai,不可能出现同⼀个ip进⼊Ai和Aj 的情况,所以对Ai进行统计次数就是准确的ip次数。



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。