【C++高阶(六)】哈希的应用--位图&布隆过滤器

简介: 【C++高阶(六)】哈希的应用--位图&布隆过滤器

1. 前言

哈希最常用的应用是unordered

系列的容器,但是当面对海量数据

如100亿个数据中找有没有100这

个数时,使用无序容器的话内存放不下

所以哈希思想还有别的更重要的应用!

本章重点:

本篇文章着重讲解哈希的应用的
两个容器,一个是位图,一个是布隆
过滤器,并且模拟实现它们.最后会
讲解如何使用这两个容器来解决一
些海量数据的面试题问题


2. 位图的概念以及定义

请先看一道海量数据的面试题:

如果要使用unordered_set来解决
40亿个整数,一个整数占4四节,
总共大约占16个G的内存空间
并且set容器中不止有整型数据,还有
其他的数据,所以不能用set!

而一个数在或不在可以用1/0来表示

也就是说其实只需要一个比特位就可

以知道一个数在不在其中.

于是位图横空出世!

位图概念:

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

举例说明:

判断1~22中哪些数据是存在的
只需要用三个整型也就是24个
比特位的空间,同理,40亿个数据
也用不着16G的内存,使用0.5G
内存的位图即可判断一个数在不在!


3. 位图的模拟实现

先来看看库中实现的位图:

模板参数N代表位图的大小

位图有三个主要的接口函数:

  1. set: 将一个数据放入位图中
  2. reset:将一个数据从位图中删掉
  3. test:检测一个数据在不在位图中

位图本身就是一段连续的空间
所以用char类型数组来充当位图的
基本结构是很符合情况的!

先将位图框架写出来:

template<size_t N>//N是所有数中的最大值
class bit_set
{
public:
  bit_set()
  {
    _bit.resize(N / 8 + 1, 0);
  }
  void set(size_t x)//将第x位变成1
  {}
  void reset(size_t x)//将第x位由1变0
  {}
  bool test(size_t x)
  {}
private:
  vector<char> _bit;
};

在写set,reset等函数时,要先清除一点,
那就是char类型的数组一个元素有八个
比特位,所以我们需要确定两个位置:
一是此数据在哪一个数组元素中
二是此数据对应此元素的第几个比特位
下面我们画个图来推导一下公式:

现在已经能准确的找到这个比特位了
那么怎样将这个比特位变成0/1并且
不会影响到其他的比特位呢?下面分享
两个很巧妙的方法,请大家细细品尝:

template<size_t N>//N是所有数中的最大值
class bit_set
{
public:
  bit_set()
  {
    _bit.resize(N / 8 + 1, 0);
  }
  void set(size_t x)//将第x位变成1
  {
    //x/8->在第几个char
    //x%8->在这个char的第几个比特位
    size_t i = x / 8;
    size_t j = x % 8;
    _bit[i] |= (1 << j);//将x对应的比特位变成1
  }
  void reset(size_t x)
  {
    size_t i = x / 8;
    size_t j = x % 8;
    _bit[i] &= ~(1 << j);//将x对应的比特位变成0
  }
  bool test(size_t x)
  {
    size_t i = x / 8;
    size_t j = x % 8;
    return _bit[i] & (1 << j);
  }
private:
  vector<char> _bit;
};

关于代码的解释都在注释中,请耐心观看

必要时可以自己画图做做试验


4. 布隆过滤器的概念以及定义

位图有一个缺陷,那就是只能判断整型是否存在

遇见字符串等类型的数据就很难处理了

布隆过滤器的提出:

布隆过滤器的概念:

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

举例说明:

查找字符"美团"是否存在时,会找到
这三个绿色的位置,看看是否都为1

布隆过滤器的拓展阅读:

布隆过滤器原理


5. 布隆过滤器模拟实现(一)

首先,布隆过滤器的底层也是位图,所以

只需封装一层即可实现一个布隆过滤器!

但实现布隆过滤器的关键有以下几个

  • 一个字符串映射几个位置?
  • 怎样把字符串转换为整数?

一般而言,一个字符串映射的越多,那么
误判率就越低,但是映射过多会导致不同
的字符串映射到相同的位置,所以一般映射
三个位置,并且将字符串转换为整数也就
需要三种不同的方法,我在网上找了一些
字符串转整数的算法,请看下面的代码:

//三个不同的字符串映射成整数的函数
struct HashBKDR
{
  size_t operator()(const string& key)
  {
    size_t val = 0;
    for (auto ch : key)
    {
      val *= 131;
      val += ch;
    }
    return val;
  }
};
struct HashAP
{
  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
{
  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 Bloom_Filter
{
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;//开的空间越大,误判率越小
  std::bitset<_ratio* N>* _bits = new std::bitset<_ratio * N>;//标准库中的位图是在栈上开辟的静态数组,过大会栈溢出
};

6. 布隆过滤器模拟实现(二)

布隆过滤器的查找是一个很玄幻的过程:

分别计算每个哈希值对应的比特位置存储的是否为零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中

因为哈希函数可能存在冲突的原因,如下:

所以我们得出一个结论:

  • 布隆过滤器说一个元素存在,那它可能存在
  • 布隆过滤器说一个元素不在,那它一定不在

布隆过滤器的删除操作:

如果你理解了上面的内容,你一定能
明白布隆过滤器是不支持删除的,因为
删除一个关键字时可能将其他的关键字
的一部分也给删除了,因为一个bit位
只能存储一个二进制信息!


7. 处理海量数据的面试题

海量数据的处理,有对位图的应用

也有对布隆过滤器的应用一步一步解析

位图的应用:

  1. 给100亿个整数,设法找到只出现一次的整数?
  2. 给两个文件,分别有100亿个整数,只有1G内存,如何找到两个文件交集?
  3. 位图应用变形:一个文件有100亿个int,1G内存,设法找到出现次数不超过2次的所有整数

布隆过滤器的应用:

  1. 给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法
  2. 如何扩展BloomFilter使得它支持删除元素的操作

这些问题大家可以下来想一想,有什么问题欢迎私信


8. 总结

讲到这里,哈希的所有内容就已经

讲完了,所以无脑哈希无脑哈希,

但实际上要学好哈希还真得费点脑子

海量数据得处理问题在面试时也是

经常问的,希望同学们好好学扎实!


🔎 下期预告:C++11新改动🔍


目录
打赏
0
2
2
0
18
分享
相关文章
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
117 15
基于 C++ 布隆过滤器算法的局域网上网行为控制:URL 访问过滤的高效实现研究
本文探讨了一种基于布隆过滤器的局域网上网行为控制方法,旨在解决传统黑白名单机制在处理海量URL数据时存储与查询效率低的问题。通过C++实现URL访问过滤功能,实验表明该方法可将内存占用降至传统方案的八分之一,查询速度提升约40%,假阳性率可控。研究为优化企业网络管理提供了新思路,并提出结合机器学习、改进哈希函数及分布式协同等未来优化方向。
34 0
企业员工数据泄露防范策略:基于 C++ 语言的布隆过滤器算法剖析[如何防止员工泄密]
企业运营过程中,防范员工泄密是信息安全领域的核心议题。员工泄密可能致使企业核心数据、商业机密等关键资产的流失,进而给企业造成严重损失。为应对这一挑战,借助恰当的数据结构与算法成为强化信息防护的有效路径。本文专注于 C++ 语言中的布隆过滤器算法,深入探究其在防范员工泄密场景中的应用。
76 8
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
147 12
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
149 5
C++多线程应用
【10月更文挑战第29天】C++ 中的多线程应用广泛,常见场景包括并行计算、网络编程中的并发服务器和图形用户界面(GUI)应用。通过多线程可以显著提升计算速度和响应能力。示例代码展示了如何使用 `pthread` 库创建和管理线程。注意事项包括数据同步与互斥、线程间通信和线程安全的类设计,以确保程序的正确性和稳定性。
150 5
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
164 2
|
10月前
|
【C++核心】函数的应用和提高详解
这篇文章详细讲解了C++函数的定义、调用、值传递、常见样式、声明、分文件编写以及函数提高的内容,包括函数默认参数、占位参数、重载等高级用法。
116 3
|
11月前
|
C++ STL应用宝典:高效处理数据的艺术与实战技巧大揭秘!
【8月更文挑战第22天】C++ STL(标准模板库)是一组高效的数据结构与算法集合,极大提升编程效率与代码可读性。它包括容器、迭代器、算法等组件。例如,统计文本中单词频率可用`std::map`和`std::ifstream`实现;对数据排序及找极值则可通过`std::vector`结合`std::sort`、`std::min/max_element`完成;而快速查找字符串则适合使用`std::set`配合其内置的`find`方法。这些示例展示了STL的强大功能,有助于编写简洁高效的代码。
131 2
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问