题目二：给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
题目三：1 个文件有 100 亿个 int，1G内存，设计算法找到出现次数不超过2次的所有整数
注：位图只能处理整形。采用位图标记字符串时，必须先将字符串转化为整形的数字，找到位图中对应的比特 位，但是在字符串转整形的过程中，可能会出现不同字符串转化为同一个整形数字，即冲突，因此一般不会直接用位图处理字符串。
👉布隆过滤器👈
布隆过滤器的提出
我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？
用哈希表存储用户记录，缺点：浪费空间。
用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
将哈希与位图结合，即布隆过滤器。
布隆过滤器概念
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
布隆过滤器的实现
1. 查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为 1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。
布隆过滤器的应用场景
布隆过滤器的公式
#pragma once #include "BitSet.h" namespace Joy { // 哈希函数 struct HashBKDR { // BKDR size_t operator()(const string& key) { size_t val = 0; for (auto ch : key) { val *= 131; val += ch; } return val; } }; struct HashAP { // AP size_t operator()(const string& key) { size_t hash = 0; for (size_t i = 0; i < key.size(); i++) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5))); } } return hash; } }; struct HashDJB { // DJB size_t operator()(const string& key) { size_t hash = 5381; for (auto ch : key) { hash += (hash << 5) + ch; } return hash; } }; // N表示准备要映射N个值,布隆过滤器处理的类型通常是字符串 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); _bits.set(hash1); size_t hash2 = Hash2()(key) % (_ratio * N); _bits.set(hash2); size_t hash3 = Hash3()(key) % (_ratio * N); _bits.set(hash3); } bool test(const K& key) { size_t hash1 = Hash1()(key) % (_ratio * N); if (!_bits.test(hash1)) return false; // 准确的 size_t hash2 = Hash2()(key) % (_ratio * N); if (!_bits.test(hash2)) return false; // 准确的 size_t hash3 = Hash3()(key) % (_ratio * N); if (!_bits.test(hash3)) return false; // 准确的 return true; // 可能存在误判 } // 能否支持删除? ->布隆过滤器一般不支持删除,如果要 // 删除的话,可以加上映射位置的引用计数。 void reset(const K& key); private: const static size_t _ratio = 5; // _ratio为倍率 bitset<_ratio* N> _bits; // 使用自己实现的bitset }; void BloomFilterTest1() { BloomFilter<10> bf; string arr1[] = { "苹果", "西瓜", "阿里", "美团", "苹果", "字节", "西瓜", "苹果", "香蕉", "苹果", "腾讯" }; for (auto& str : arr1) { bf.set(str); } string arr2[] = { "苹果111", "西瓜", "阿里2222", "美团", "苹果dadcaddxadx", "字节", "西瓜sSSSX", "苹果 ", "香蕉", "苹果$", "腾讯" }; for (auto& str : arr2) { cout << str << ":" << bf.test(str) << endl; } } void BloomFilterTest2() { srand(time(0)); const size_t N = 1000000; BloomFilter<N> bf; cout << sizeof(bf) << endl; std::vector<std::string> v1; std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html"; for (size_t i = 0; i < N; ++i) { v1.push_back(url + std::to_string(1234 + i)); } for (auto& str : v1) { bf.set(str); } // 相似 std::vector<std::string> v2; for (size_t i = 0; i < N; ++i) { std::string url = "http://www.cnblogs.com/-clq/archive/2021/05/31/2528153.html"; url += std::to_string(rand() + i); v2.push_back(url); } size_t n2 = 0; for (auto& str : v2) { if (bf.test(str)) { ++n2; } } cout << "相似字符串误判率:" << (double)n2 / (double)N << endl; std::vector<std::string> v3; for (size_t i = 0; i < N; ++i) { string url = "zhihu.com"; url += std::to_string(rand() + i); v3.push_back(url); } size_t n3 = 0; for (auto& str : v3) { if (bf.test(str)) { ++n3; } } cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl; } }
存储空间越大，布隆过滤器的误判率就会越低。注：库里的 bitset 是静态数组，空间太大容易栈溢出，可以在堆上开空间。
2. 删除
布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给 k 个计数器(k 个哈希函数计算出的哈希地址)加一，删除元素时，给 k 个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。
布隆过滤器优点和缺点
优点
- 增加和查询元素的时间复杂度为：O(K), (K 为哈希函数的个数，一般比较小)，与数据量大小无关
- 哈希函数相互之间没有关系，方便硬件并行运算
- 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
- 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
- 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
- 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
缺点
- 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
- 不能获取元素本身
- 一般情况下不能从布隆过滤器中删除元素
- 如果采用计数方式删除，可能会存在计数回绕问题
布隆过滤器的题目
题目一：给两个文件，分别有 100 亿个 query，我们只有 1G 内存，如何找到两个文件交集？分别给出精确算法和近似算法。 query 是查询，常见的查询有：网络请求、SQL 语句等，它们都是字符串。近似算法允许一些误判，那么我们可以先将一个文件的 query 放入布隆过滤器中，再去查另一个文件的 query 在不在布隆过滤器中，就可以找到两个文件的交集了（还需要去重）。精确算法如下图所示：
题目二：如何扩展BloomFilter使得它支持删除元素的操作？布隆过滤器一般是不支持删除的，支持删除可能会影响其他值的查询。如果想要支持删除，可以添加引用计数。但是支持了删除，空间消耗就更多，优势就变小了。
哈希切分题目：给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？
Linux 系统命令实现
注：哈希切分并不是平均切分，而是相同的哈希值的字符串等进入到相同的位置。
哈希的应用非常地广泛，服务器存储中也使用到了哈希。
👉总结👈
本篇博客主要讲解了常见的哈希函数，什么是位图、位图的实现和应用、什么是布隆过滤器、布隆过滤器的实现和优缺点以及哈希切分等等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
