目录

🌈前言🌈

📁 位图

 📂 概念

📂 模拟实现

📂 C++中位图

 📂 位图的优缺点

📁 布隆过滤器

 📂 概念

 📂 模拟实现

 📂 应用场景

📁 海量数据处理

📁 总结

🌈前言🌈

        本期【C++杂货铺】，将介绍关于哈希表的扩展内容，即位图和布隆过滤器，以及如何通过位图和布隆过滤器解决海量数据处理问题。

        哈希表作为一种数据结构，可以达到O(1)的时间复杂度内找到数据，但是C++中哈希表作为一种数据结构，是在内存中处理数据，如何解决上亿数据的查找问题呢？因此就引入了位图和布隆过滤器。

        本期内容需要你了解一定哈希表的内容，可以阅览下面这篇文章：

【C++杂货铺】unordered系列容器_unordered c++-CSDN博客

📁 位图

 📂 概念

        我们使用哈希表就是为了来查找数据，那我们转换一下思想，哈希表不在用来存储数据，而是通过一个标记位，来标识该数据是否存在。

        我们可以使用一个二进制比特位来表示是否存在数据。设计一个用位置表示数据是否存在的数据结构，这个结构就是位图。

        位图本质就是一个直接定址法的哈希表，每一个整形映射一个bit位，位图提供了bit位的操作接口。

        一个int类型4字节，32位bit，就可以表示32个数据的有无。C/C++没有提供位的类型，我们就可以通过对整形进行位运算来控制对应的位。

        例如一个数据X，通过 X / 32确定存储在哪一个整形，X % 32 确定在整型的那一个位，这样就将X值映射成vector的第i个整形数据的第j位。

        我们只需要开除2^32大小（计算机内整形的最大取值范围）的位图就可以表示出上百亿数据的有无。

📂 模拟实现

<code> template<size_t N = -1>

class BitSet

{

public:

BitSet()

{

_bitset.resize(N / 32 + 1,0);

}

void Set(size_t n)

{

int i = n / 32;

int j = n % 32;

_bitset[i] |= (1 << j);

}

void Reset(size_t n)

{

int i = n / 32;

int j = n % 32;

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

}

bool Test(size_t n)

{

int i = n / 32;

int j = n % 32;

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

}

size_t Size()

{

return _bitset.size();

}

private:

std::vector<size_t> _bitset;

};

📂 C++中位图

bitset - C++ Reference

 📂 位图的优缺点

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

        缺点：只能适用于整形数据。

📁 布隆过滤器

 📂 概念

        如果不是整形数据，我们就要使用布隆过滤器了。

        布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 ⼀种紧凑型的、比较巧妙的概率型数据结构，特点是高效的插入和查询，可以用来告诉你 “某样东西⼀定不存在或者可能存在”，它是用多个哈希函数，将⼀个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

        布隆过滤器复用了位图，首先将数据通过多个哈希函数映射成不同的值，将对应的值映射到特定的位上，只要映射的位全部为1，就可以确定该数据是存在的。

        我们可以看到通过哈希函数可能产生哈希冲突，但是布隆过滤器并不用来存储数据，而是用来判断数据是否存在的，因此不需要解决冲突，而是想办法降低冲突。

        布隆过滤器降低冲突的目的就是最大程度上确定该数据是否存在，判断数据是否存在就是看是否有0的存在，如果映射值1中有一个为0，就说明该数据不存在。

        但是最坏情况下，可能存在不存在的数据，通过哈希函数，得到的映射值在整型所在位上的值为1，这就可能导致误判，即不存在的数据在映射值的位上没有找到0。

误判推导：

        这里不再过多介绍公式推导流程，我们只需要知道结论即可。即

布隆过滤器（Bloom Filter）- 原理、实现和推导_布隆过滤器原理-CSDN博客

布隆过滤器（Bloom Filter）- 原理、实现和推导_布隆过滤器原理-CSDN博客

删除问题：

        布隆过滤器默认是不支持删除的，因为比如"猪八戒“和”孙悟空“都映射在布隆过滤器中，他们映射的位有⼀个位是共同映射的(冲突的)，如果我们把孙悟空删掉，那么再去查找“猪⼋戒”会查找不到，因为那么“猪八戒”间接被删掉了。

        解决方案：可以考虑计数标记的方式，⼀个位置用多个位标记，记录映射这个位的计数值，删除时，仅仅减减计数，那么就可以某种程度支持删除。但是这个方案也有缺陷，如果⼀个值不在布隆过滤器中，我们去删除，减减了映射位的计数，那么会影响已存在的值，也就是说，⼀个确定存在的值，可能会变成不存在，这里就很坑。当然也有人提出，我们可以考虑计数方式支持删除，但是定期重建⼀下布隆过滤器，这样也是⼀种思路。

 📂 模拟实现

<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 Hashfunc1 = HashFuncBKDR,

class Hashfunc2 = HashFuncAP,

class Hashfunc3 = HashFuncDJB>

class BloomFilter

{

public:

void Set(const K& key)

{

size_t bit1 = Hashfunc1()(key) % M;

size_t bit2 = Hashfunc2()(key) % M;

size_t bit3 = Hashfunc3()(key) % M;

_bits.Set(bit1);

_bits.Set(bit2);

_bits.Set(bit3);

}

bool Test(const K& key)

{

size_t bit1 = Hashfunc1()(key) % M;

if (!_bits.Test(bit1))

return false;

size_t bit2 = Hashfunc2()(key) % M;

if (!_bits.Test(bit2))

return false;

size_t bit3 = Hashfunc3()(key) % M;

if (!_bits.Test(bit3))

return false;

return true;

}

private:

static const size_t M = N * X;

BitSet<M> _bits;

};

void TestBloomFilter1()

{

std::string strs[] = { "百度","字节","腾讯" };

BloomFilter<10> bf;

for (auto& s : strs)

{

bf.Set(s);

}

for (auto& s : strs)

{

std::cout << bf.Test(s) << std::endl;

}

for (auto& s : strs)

{

std::cout << bf.Test(s + 'a') << std::endl;

}

std::cout << bf.Test("摆渡") << std::endl;

std::cout << bf.Test("百度") << std::endl;

}

}

 📂 应用场景

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

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

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

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

📁 海量数据处理

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

        我们可以确定的就是排除暴力查找的方案，也可以排除排序+二分查找的方案，因为大部分内存都不支持开辟这么大存储空间。

        这里我们就可以使用位图。只需要开辟2^32个位，即500M左右的空间大小就可以查找数据是否存在，并且时间复杂度为O(1)。

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

 （1）可以使用布隆过滤器来解决，一个文件的query放入布隆过滤器中，另一个文件一次查找，在的就是交集。但是问题就是可能产生误判，但一定能找到交集。 

 （2）哈希切分，因为对内存的访问肯定大于对硬盘的访问，因此我们将大文件切分成多个小文件，将小文件放入内存处理。

        但是这里不是平均切分，而是进行哈希切分，通过哈希函数，将得到映射值相同的query放入一个小文件中。这样我们只需要在内存中将Ai和Bi找交集即可。

        但是每个小文件可能不是均匀的，例如情况一出现多个相同的query或者情况二有多个映射值相同的query，导致小文件过大。针对情况一我们可以将配合数据结构set去重；针对情况二我们对小文件进行二次哈希切分。

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

📁 总结

        以上就是本期【C++杂货铺】的主要内容了，讲解了实际情况下，如何处理海量数据的问题，以及我们可以通过哈希切分的方案将大文件切分成小文件放入内存处理，提高了处理效率。

        如果感觉本期内容对你有帮助，欢迎点赞，关注，收藏Thanks♪(･ω･)ﾉ