【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++编程中,调试日志对于定位问题和优化代码至关重要,本文将介绍几种常用的调试日志输出方法,并教你如何在日志中添加时间戳,希望对大家有所帮助... 目录1. 使用 #ifdef _DEBUG 宏2. 加入时间戳：精确到毫秒3.Windows 和 MFC 中的调试日志方法MFC
阅读更多...
深入理解C++ 空类大小

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中，规
阅读更多...
Servlet中配置和使用过滤器的步骤记录

Servlet中配置和使用过滤器的步骤记录

《Servlet中配置和使用过滤器的步骤记录》：本文主要介绍在Servlet中配置和使用过滤器的方法,包括创建过滤器类、配置过滤器以及在Web应用中使用过滤器等步骤,文中通过代码介绍的非常详细,需... 目录创建过滤器类配置过滤器使用过滤器总结在Servlet中配置和使用过滤器主要包括创建过滤器类、配置过滤
阅读更多...
在 VSCode 中配置 C++ 开发环境的详细教程

在 VSCode 中配置 C++ 开发环境的详细教程

《在VSCode中配置C++开发环境的详细教程》本文详细介绍了如何在VisualStudioCode（VSCode）中配置C++开发环境,包括安装必要的工具、配置编译器、设置调试环境等步骤,通... 目录如何在 VSCode 中配置 C++ 开发环境：详细教程1. 什么是 VSCode？2. 安装 VSCo
阅读更多...
C++11的函数包装器std::function使用示例

C++11的函数包装器std::function使用示例

《C++11的函数包装器std::function使用示例》C++11引入的std::function是最常用的函数包装器,它可以存储任何可调用对象并提供统一的调用接口,以下是关于函数包装器的详细讲解... 目录一、std::function 的基本用法1. 基本语法二、如何使用 std::function
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2