哈希的应用:布隆过滤器(C++实现)

简介: 哈希的应用:布隆过滤器(C++实现)

1. 布隆过滤器

1.1 背景

位图(bitmap算法)告诉我们,想判断一个元素是否存在于某个集合中,如果数据量少,使用搜索树和哈希表是非常快速的。但是一旦元素个数从亿级起步,所需要的内存空间就不足以让这些数据结构发挥作用。位图用一个比特位的0和1表示元素的状态,极大地提高了空间利用率。

然而,位图最大的缺陷是它只能处理整型值,而实际上常常以字符串为key值存储数据,有的人会说,用大佬写的字符串转整型的哈希算法不就好了?结合以前学过的哈希算法,一个字符(char)有256种情况,就算字符是常用的26个英文字母,那它也比数字字符10种情况多。从原理上看,不论通过如何巧妙的哈希函数,字符串转整型发生哈希冲突是不可避免的。

我们一定经历过“该用户名已被占用”这样的场景,常常是输入的过程或者输完一会(甚至不用按回车)就在旁边提示你“已被占用”,这个功能就用到了布隆过滤器。

除此之外,还可以用过滤垃圾网站来理解布隆过滤器:

在黑名单内的垃圾网站毕竟是少数,如果每次都在黑名单里查找,效率太低了,所以可以在数据库之前加上一个布隆过滤器,如果垃圾网站在过滤器中,才会继续在数据库中搜索,这样不在黑名单中的垃圾网站就被过滤掉了。

1.2 概念

布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询。它是位图的优化版本,哈希冲突既然不能避免,那我们就尽量减少出现冲突带来的误判情况。

什么是“冲突带来的误判情况”?

首先,布隆过滤器为了减少哈希冲突(注意是冲突而不是冲突带来的误判),使用了多个哈希函数,将多个位置的比特位设置为1,每一个key值都能用几个比特位表示它的状态。

如何判断一个元素是否存在?

  • 只要它的所有哈希函数得到的比特位上都已经被设置为1,则说明它有可能已经存在。

至于为什么说有可能,请看下面的分析。

像这样就不算误判,因为即使苹果的2、3和香蕉的1、2共用了同一个位置,但是苹果的1和香蕉的3是不同位置,它们就不会构成误判情况。所以真正标识苹果和香蕉是否存在的哈希函数是1和3。

葡萄的每一个哈希函数得出的位置都已经被占用了,但显然它们是被不同元素占用了,而集合中并没有葡萄这个元素,这就是冲突带来的误判情况。

1.3 控制误判率

从原理上,误判情况出现的次数也是不可避免的,只能降低可能性。它取决于两个方面:

  • 哈希函数的个数:哈希函数越多,标识一个元素的哈希函数组合也就越多,出现误判率的可能性越小;
  • 总比特位的个数:决定了哈希函数发生哈希冲突的概率。

但是,它们之间也必须达到平衡,因为哈希函数的个数越多,多次计算会导致效率降低,而布隆过滤器的长度太长也会影响效率。

有人给出了哈希函数个数和布隆过滤器长度在保证效率的情况下最均衡的关系:

m = − ( n l n p ) / ( l n 2 ) 2 m = - (nlnp)/(ln2)^2m=(nlnp)/(ln2)2

k = ( m / n ) l n 2 k = (m/n)ln2k=(m/n)ln2

其中:

  • k:哈希函数个数;
  • m:布隆过滤器长度;
  • n:插入的元素个数;
  • p:误判率。

当哈希函数个数k=3时,取l n 2 ln2ln2=0.7,可以得出布隆过滤器长度m和插入元素个数n之间的关系:m=4n,即布隆过滤器长度为插入元素个数4倍。

2. 实现布隆过滤器

2.1 布隆过滤器类

  • 首先底层用STL中的bitset容器实现,所以需要模板参数N,用于规定布隆过滤器长度。
  • 由于处理的数据类型不一定每次都是字符串类型,所以用模板参数K表示,而字符串类型又是常客,所以赋予数据类型模板参数K以缺省值为string类型。
  • 其次模板参数中还要添加3个哈希函数,都各自缺省地赋予处理string类型的哈希函数。
template<size_t N,
class K = string, class Hash1 = BKDRHash, class Hash2 = APHash, class Hash3 = DJBHash>
class BloomFilter
{
  // ...
private:
  bitset<N> _bs;
};

由于K的缺省值是string,所以默认的哈希函数也要是处理字符串的。

BKDRHash、APHash和DJBHash是个最有效的哈希函数,它们都使用仿函数实现:

struct BKDRHash
{
  size_t operator()(const string& s)
  {
    size_t value = 0;
    for (auto ch : s)
    {
      value = value * 131 + ch;
    }
    return value;
  }
};
struct APHash
{
  size_t operator()(const string& s)
  {
    size_t value = 0;
    for (size_t i = 0; i < s.size(); i++)
    {
      if ((i & 1) == 0)
      {
        value ^= ((value << 7) ^ s[i] ^ (value >> 3));
      }
      else
      {
        value ^= (~((value << 11) ^ s[i] ^ (value >> 5)));
      }
    }
    return value;
  }
};
struct DJBHash
{
  size_t operator()(const string& s)
  {
    if (s.empty())
      return 0;
    size_t value = 5381;
    for (auto ch : s)
    {
      value += (value << 5) + ch;
    }
    return value;
  }
};

2.2 Set

  • Set:插入元素到布隆过滤器中。

插入元素时,需要通过三个哈希函数分别计算出元素对应的三个比特位的序号,然后复用bitset的set接口将位图中的这三个比特位设置为1即可。

void Set(const K& key)
{
    size_t hash1 = Hash1()(key) % N;
    size_t hash2 = Hash2()(key) % N;
    size_t hash3 = Hash3()(key) % N;
    _bs.set(hash1);
    _bs.set(hash2);
    _bs.set(hash3);
}

2.3 Test

  • Test:查找某个元素是否在某个集合中。

同样地,通过三个哈希函数分别计算出元素对应的三个比特位的序号,然后复用bitset的test接口,判断位图中的这三个比特位是否被设置为1。

  • 只要三个比特位中有一个比特位未被设置为1则说明该元素一定不存在;
  • 如果三个比特位全部被设置,返回true。

注意:

三个比特位全部被设置为1并不代表这个元素一定存在于这个集合中,以最开始的葡萄例子就可以知道,不过经过两层的优化(哈希函数减少冲突,多个哈希函数减少误判),误判率已经很低了。

也就是说:

  • 返回false,不存在就是一定不存在,是准确的;
  • 返回true,并不是100%存在,可能存在误判。
bool Test(const K& key)
{
    size_t hash1 = Hash1()(key) % N;
    if (_bs.test(hash1) == false)
    {
        return false;       // 准确
    }
    size_t hash2 = Hash2()(key) % N;
    if (_bs.test(hash2) == false)
    {
        return false;       // 准确
    }
    size_t hash3 = Hash3()(key) % N;
    if (_bs.test(hash3) == false)
    {
        return false;       // 准确
    }
    return true;          // 可能误判
}

2.4 删除

布隆过滤器一般不支持删除操作:

  1. 首先从原理上删除操作会直接影响哈希函数的结果,那么每一次删除都要重新把这个容器中的所有元素重新再映射一遍,影响了其他元素,降低效率。
  2. 其次布隆过滤器要删除一个元素,首先要保证它是真正存在这个集合中的,但是误判是无法避免的,所以删除有一定的风险。

要让布隆过滤器支持删除,必须要满足:

  1. 为每一个比特位增加一个引用计数,当在一个位置上增加一个元素,引用计数+1,反之-1,这样删除就不会改变布隆过滤器的长度,也就不会影响其他元素。但是这违背了布隆过滤器(位图)本身的应用场景:省空间+快速查询。
  2. 当使用Test接口得知元素可能存在于映射以后的布隆过滤器中,再进一步去原始文件验证这个元素是否存在于集合中。但这就像从内存中突然跳到磁盘文件中查找,文件IO和磁盘IO相对于内存而言是很慢的,所以还是降低了效率。

结合上面两点,再加上布隆过滤器本身的应用就是为了查询,而删除对它而言不痛不痒,因为位图这个容器是直接在内存中操作比特位的,即使有很多剩下的没用的元素,对计算机而言它也只是几个比特位,这是无关痛痒的。

3. 优点

  • 增加和查询元素的时间复杂度为O(K)(K为哈希函数的个数,一般比较小),与数据量大小无关。
  • 哈希函数相互之间没有关系,方便硬件并行运算。
  • 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势。
  • 在能够承受一定的误判时,布隆过滤器比其他数据结构有着很大的空间优势。
  • 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能。
  • 使用同一组哈希函数的布隆过滤器可以进行交、并、差运算。

4. 缺陷

  • 有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再自建一个白名单,存储可能会误判的数据)
  • 不能获取元素本身。
    本身,在某些对保密要求比较严格的场合有很大优势。
  • 在能够承受一定的误判时,布隆过滤器比其他数据结构有着很大的空间优势。
  • 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能。
  • 使用同一组哈希函数的布隆过滤器可以进行交、并、差运算。

4. 缺陷

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