【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#如何调用C++库

《C#如何调用C++库》：本文主要介绍C#如何调用C++库方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录方法一：使用P/Invoke1. 导出C++函数2. 定义P/Invoke签名3. 调用C++函数方法二：使用C++/CLI作为桥接1. 创建C++/CL
阅读更多...
C++如何通过Qt反射机制实现数据类序列化

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类，并对数据类进行存储、打印、调试等操作。由于数据类
阅读更多...
Linux下如何使用C++获取硬件信息

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息：读取"/proc/cpuinfo"文件获取磁盘信息：读取"/proc/diskstats"文
阅读更多...
C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
C++ vector的常见用法超详细讲解

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》：本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve
阅读更多...
如何高效移除C++关联容器中的元素

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...
Python获取C++中返回的char*字段的两种思路

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串，目前我找到两种解决问题的思路，具体实现如下：
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...
Java调用C++动态库超详细步骤讲解(附源码)

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,：本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步：动态库生成（vs2017+qt5.12.10）第二步：Java调用C++
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2