【C++ ——— 哈希】位图 | 布隆过滤器

2024-05-31 20:44
文章标签 c++ 哈希 过滤器 布隆

本文主要是介绍【C++ ——— 哈希】位图 | 布隆过滤器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 1、位图
      • 1.1位图概念
  • 2.位图实现
  • 位图的应用
      • 1.一百亿个整数，设计算法找到只出现一次的整数?
      • 2.给两个文件，分别有一百亿个整数，我们只有1G内存该如何找到两个文件的交集？
      • 3.位图应用变形：一个文件有100亿个int，1G内存，设计算法找到出现不超过两次的所有整数。
  • 3.布隆过滤器
      • 3.1 布隆过滤器的提出
        • 3.2布隆过滤器概念
  • 海量数据的面试题
      • 1.给两个文件，分别由100亿个query（数据请求），我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法（近似算法就是布隆过滤器算法）：
      • 2.给一个超过100G大小的log file，log 中存放着IP地址，设计算法找到出现次数最多的IP地址？如何找到top K的IP？

1、位图

1.1位图概念

1.面试题
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】
解决方案：

  1. 二分查找。[不能用这种方式：1.要排序，2.40亿个整数需要约16g的内存，内存开不出这么大的空间]
  2. 位图解决：我们只需要标记这个值在不在，没必要存下来，让每个值映射一个比特位，需要2^32个比特位，也就是只需要0.5G。数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。

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

2.位图实现

//N是需要多少比特位
template<size_t N>
class bitset
{
public://构造bitset(){//构造函数提前开空间//_bits.resize(N/32+1, 0);_bits.resize((N >> 5) + 1, 0);//2^5是32 且移位运算优先级要注意。}//映射一个值到位图中void set(size_t x){//要把第j位处理为1，其他位不变。//找一个第j位为1其他位为0的补码//让他们或运算，或是两个位都为0时才为0size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);//左移操作符向高位移动//右移操作符向低位移动//注意左移右移操作符不是方向的问题，是高位和低位的问题。}//将x的对应比特位置为0void reset(size_t x){//把第j位处理位0，其他位不变//同上找第j位为0，其他位为1的补码//按位与运算。 与运算两个位都为1才为1size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}//查看这个x在位图中是否为1，为1就是存在。bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}private:vector<int> _bits;
};

我们看上题说要开40亿个整形我们要怎么开呢？

//直接写为16进制
bitset<oxffffffff> bigbs;
//-1传过去转化为size_t类型直接能转化为最大值。
bitset<-1> bigbs2;

位图的应用

1.一百亿个整数，设计算法找到只出现一次的整数?

这有一百亿个数会不会出现空间不够的情况？
不会。就算是一百亿个整数最多也就42亿九千万个整数会出现很多重复值。
不论是100亿还是1000亿都只开42亿九千万个空间
这里需要三种状态：

  1. 出现0次
  2. 出现1次
  3. 出现两次即以上
    可以用两个位表示这三种状态。
    我们用两个位图表示一个位。
    在这里插入图片描述

位图代码实现：

//用两个位图来表示一个值
class twobitset
{
public:void set(size_t x){//00->01//01->10//10->状态不变出现了两次即以上if (_bs1.test(x) == false && _bs2.test(x) == false){_bs2.set(x);}else if (_bs1.test(x) == false && _bs2.test(x) == true){_bs1.set(x);_bs2.reset(x);}}void PrintfOnce(){for (size_t i = 0; i < N; i++){if (_bs1.test(i) == false && _bs2.test(i) == true){cout << i << endl;}}cout << endl;}private:bitset<N> _bs1;bitset<N> _bs2;
};

2.给两个文件，分别有一百亿个整数，我们只有1G内存该如何找到两个文件的交集？

跟上题思路很像，各自映射到一个位图中。一个值两个位图都存在，就是交集。（先去重复值）

3.位图应用变形：一个文件有100亿个int，1G内存，设计算法找到出现不超过两次的所有整数。

我们可以用上面的一个值映射两个位图解决这个方法，但是我们只有1G内存所以还是要做一些特殊处理的

template<size_t N>
//用两个位图来表示一个值
class twobitset
{
public:void set(size_t x){//00->01//01->10//10->11//11->状态不变if (_bs1.test(x) == false && _bs2.test(x) == false){_bs2.set(x);}else if (_bs1.test(x) == false && _bs2.test(x) == true){_bs1.set(x);_bs2.reset(x);}else if (_bs1.test(x) == true && _bs2.test(x) == false){_bs1.set(x);_bs2.set(x);}}void Printf(){for (size_t i = 0; i < N; i++){if (_bs1.test(i) == false && _bs2.test(i) == true){cout <<"1->"<< i << endl;}else if(_bs1.test(i) == true && _bs2.test(i) == false){cout << "2->" << i << endl;}}cout << endl;}
private:bitset<N> _bs1;bitset<N> _bs2;
};

3.布隆过滤器

搜索

  1. 暴力排查 数据量大了，效率就低
  2. 排序+二分查找 问题a：排序有代价 问题b：不方便
  3. 搜索树-> AVL树+红黑树
  4. 哈希 ->扩容代价很高
    ——————————————
    以上数据结构，都是以空间换时间、空间消耗很高

数量很大的数据
5、[整形]的在不在及其扩展问题 – 位图及其变形 以时间换空间的算法
6、[其他类型]的在不在呢？ --需要用到布隆过滤器

3.1 布隆过滤器的提出

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？

  1. 用哈希表存储用户记录，缺点：浪费空间
  2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
  3. 将哈希与位图结合，即布隆过滤器
3.2布隆过滤器概念

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

用什么方法能让字符串映射到位图中呢？
我们可以考虑把先把字符串转换为一个对应的整形，不过整形的位图一个整形对应一个位，有42亿多的整型值够我们匹配，但是字符串呢？字符串可是无限的，所以肯定会有不同的字符串映射到同一个整形。
不过我们只需要判断这个字符串在不在
以上思路：
判断：在（不准确，可能存在误判不同字符串映射的整形是同一个。本质也就是哈希冲突导致的。）
判断：不在（准确，没有字符串映射肯定就是不在的）

看下图中映射方式：
一个字符串映射三个位置的整形值。会降低误判的概率
布隆过滤器无法完全解决误判，所以布隆过滤器出现的场景就需要接受误判

在这里插入图片描述

布隆过滤器场景：
我们玩游戏创建角色时，需要给角色创建昵称，如果直接拿你输入的昵称和数据库里存的已有昵称进行比较那样效率会很低。
在这里插入图片描述
我们可以在数据库和玩家客户端的中间建立一个布隆过滤器
布隆过滤器只能准确判断不在数据库中的数据。
判断在数据库中的情况时，需要额外去数据库中匹配数据。
在这里插入图片描述
布隆过滤器、代码实现：

struct BKDRHash
{size_t operator()(const string& key){//BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
};template<size_t N ,class K = string,class HashFunc1 = BKDRHash,class HashFunc2 = BKDRHash,class HashFunc3 = BKDRHash>
class BloomFilter
{
public:void Set(const K& key){size_t Hash1 = HashFunc1()(key) % N;size_t Hash2 = HashFunc2()(key) % N;size_t Hash3 = HashFunc3()(key) % N;_bs.set(Hash1);_bs.set(Hash2);_bs.set(Hash3);}//一般不支持删除，删除一个值可能会影响其他值//非要支持删除的话，可以使用引用计数法，不过那样会void Reset(const K& key);bool Test(const K& key){size_t Hash1 = HashFunc1()(key) % N;if (_bs.test(Hash1) == false)return false;size_t Hash2 = HashFunc2()(key) % N;if (_bs.test(Hash2) == false)return false;size_t Hash3 = HashFunc3()(key) % N;if (_bs.test(Hash3) == false)return false;//可能存在误判的风险return true;}
private:bitset<N> _bs;
};

海量数据的面试题

布隆过滤器（哈希切分）

1.给两个文件，分别由100亿个query（数据请求），我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法（近似算法就是布隆过滤器算法）：

假设：平均一个query是50byte，100亿个query就是5000亿个byte。1G约等于10亿byte
那么5000亿byte 约等于 500G
内存存不下，红黑树/哈希表都使用不了。
分析：
1.我们可以先把两个文件的500G文件分成500份，每份1G左右

在这里插入图片描述
2.但是只是单纯的划分了500份空间对我们的查询比对操作效率，没有任何的提高。所以我们在划分空间时需要用到哈希算法，通过哈希函数把映射位置相同或相似的值，集中在一个小块。
我们做了这么多的目的就是为了把这块空间加载到内存中，
下图这种方式就是哈希切分法
在这里插入图片描述
3.之后我们把Ai和Bi的数据分别加载到内存中，对他们两个分别进行位图映射。然后判断他们中是否有交集
在这里插入图片描述
4.但是这种思路还有一个问题–如果单个文件过大呢？
比如这个小文件有10G
这种单个文件过大差不多有两种情况：
一、这个小文件，内大多数都是相同的query
二、这个小文件，有很多种不同的query

解决方法：
Ai和Bi分别插入setA和setB中
不管文件大小直接插入：
情况一：这个小文件大多都是相同query，插入第一个后，后面重复插入就会set失败。
情况二：不断插入set后，内存不足，会抛异常，需要换个哈希函数把这个小文件进行二次切分，再找交集。

2.给一个超过100G大小的log file，log 中存放着IP地址，设计算法找到出现次数最多的IP地址？如何找到top K的IP？

哈希切割：
1.我们先要统计次数，但是文件太大加载不到内存，我们无法统计次数，可以用哈希切分把相似IP地址分到一个区域里（跟上题思路类似）（相同IP一定会进入同一个文件）
2.切分完，直接在对应Ai中的数据使用map或者unordered_map统计次数，记得统计完次数和最大值比对进行更新。
3.top K问题：额外建一个小堆如果次数比堆顶大就进堆。

这篇关于【C++ ——— 哈希】位图 | 布隆过滤器的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1019001。

相关文章

C++右移运算符的一个小坑及解决

C++右移运算符的一个小坑及解决

《C++右移运算符的一个小坑及解决》文章指出右移运算符处理负数时左侧补1导致死循环,与除法行为不同,强调需注意补码机制以正确统计二进制1的个数... 目录我遇到了这么一个www.chinasem.cn函数由此可以看到也很好理解总结我遇到了这么一个函数template<typename T>unsigned
阅读更多...
C++统计函数执行时间的最佳实践

C++统计函数执行时间的最佳实践

《C++统计函数执行时间的最佳实践》在软件开发过程中,性能分析是优化程序的重要环节,了解函数的执行时间分布对于识别性能瓶颈至关重要,本文将分享一个C++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法
阅读更多...
深入解析C++ 中std::map内存管理

深入解析C++ 中std::map内存管理

《深入解析C++中std::map内存管理》文章详解C++std::map内存管理,指出clear()仅删除元素可能不释放底层内存,建议用swap()与空map交换以彻底释放,针对指针类型需手动de... 目录1️、基本清空std::map2️、使用 swap 彻底释放内存3️、map 中存储指针类型的对象
阅读更多...
C++ STL-string类底层实现过程

C++ STL-string类底层实现过程

《C++STL-string类底层实现过程》本文实现了一个简易的string类,涵盖动态数组存储、深拷贝机制、迭代器支持、容量调整、字符串修改、运算符重载等功能,模拟标准string核心特性,重点强... 目录实现框架一、默认成员函数1.默认构造函数2.构造函数3.拷贝构造函数(重点)4.赋值运算符重载函数
阅读更多...
C++ vector越界问题的完整解决方案

C++ vector越界问题的完整解决方案

《C++vector越界问题的完整解决方案》在C++开发中,std::vector作为最常用的动态数组容器,其便捷性与性能优势使其成为处理可变长度数据的首选,然而,数组越界访问始终是威胁程序稳定性的... 目录引言一、vector越界的底层原理与危害1.1 越界访问的本质原因1.2 越界访问的实际危害二、基
阅读更多...
c++日志库log4cplus快速入门小结

c++日志库log4cplus快速入门小结

《c++日志库log4cplus快速入门小结》文章浏览阅读1.1w次，点赞9次，收藏44次。本文介绍Log4cplus，一种适用于C++的线程安全日志记录API，提供灵活的日志管理和配置控制。文章涵盖... 目录简介日志等级配置文件使用关于初始化使用示例总结参考资料简介log4j 用于Java，log4c
阅读更多...
C++归并排序代码实现示例代码

C++归并排序代码实现示例代码

《C++归并排序代码实现示例代码》归并排序将待排序数组分成两个子数组,分别对这两个子数组进行排序,然后将排序好的子数组合并,得到排序后的数组,：本文主要介绍C++归并排序代码实现的相关资料,需要的... 目录1 算法核心思想2 代码实现3 算法时间复杂度1 算法核心思想归并排序是一种高效的排序方式，需要用
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
C++中detach的作用、使用场景及注意事项

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()？它的作用是什么？类比一下：二、join()的作用总结三、join()怎么
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2