从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(中)

简介: 从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割

从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(上):https://developer.aliyun.com/article/1522341

1.3 位图解决海量数据面试题

下面是一些海量数据面试题:


1. 给定100亿个整数,如何设计算法找到只出现一次的整数?

2. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?

3. 位图应用变形:1个文件有100亿个int,1G内存,如何找到出现次数不超过两次的所有整数?


这三道题我们一题一题来看:


问题一:给定100亿个整数,如何设计算法找到只出现一次的整数?

       首先这100亿个数据在内存中肯定是放不下的,所以之前学习的存放数据本身的数据结构都用不了,只能用位图。位图的一个比特位只有两种状态来表示数据的有无,这里是要统计次数,所以就要让位图不仅仅只有两种状态。这里可以用KV模型,但是想想还有没有更好的方法?

位图在STL库里有,虽然只是K模型的,但是我们用两个位图就能很好的解决这个问题:

创建两个2^32比特位的位图结构,如上图所示。

  • 两个位图相同下标的两个比特位来表示一个数据的状态。
  • 00表示0次,01表示1次,10表示一次1以上。

完整BitSet.h和two_bitset:

#pragma once
 
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
 
namespace rtx
{
  template<size_t N>
  class bitset
  {
  public:
    bitset() //构造函数开空间,只需开N / 8 + 1
    {
      //_bits.resize(N / 8 + 1, 0); 
      _bits.resize((N >> 3) + 1, 0); // 即上面注释的,效率快一点点
    }
 
    void set(size_t x)
    {
      size_t i = x >> 3; // 将x映射在位图中的位置计算出来。
      size_t j = x % 8; // //映射到char中第几个比特位
 
      _bits[i] |= (1 << j); //将映射的比特位置1。
    }
 
    void reset(size_t x)
    {
      size_t i = x >> 3; // 将x映射在位图中的位置计算出来。
      size_t j = x % 8; // //映射到char中第几个比特位
 
      _bits[i] &= ~(1 << j); //将映射的比特位置0,这里~是按位取反,不要用到!逻辑取反
    }
 
    bool test(size_t x)
    {
      size_t i = x >> 3; // 将x映射在位图中的位置计算出来。
      size_t j = x % 8; // //映射到char中第几个比特位
 
      return _bits[i] & (1 << j); //与上除了对应比特位是1,其它位都是0的数,得到对应比特位bool值
    }
 
  protected:
    vector<char> _bits;
  };
 
  template<size_t N>
  class two_bitset
  {
  public:
    void set(size_t x)
    {
      bool inset1 = _bs1.test(x); // 测试当前状态
      bool inset2 = _bs2.test(x);
 
      if (inset1 == false && inset2 == false)
      {
        _bs2.set(x); // 00 -> 01
      }
      else if (inset1 == false && inset2 == true)
      {
        _bs1.set(x); // 01 -> 10
        _bs2.reset(x);
      }                // 10 是出现两次或两次以上,不用变
    }
 
    void print_once_num()
    {
      for (size_t i = 0; i < N; ++i)
      {
        if (_bs1.test(i) == false && _bs2.test(i) == true)
        {
          cout << i << endl; // 打印只出现一次的整数
        }
      }
    }
 
  protected:
    bitset<N> _bs1;
    bitset<N> _bs2;
    //std::bitset<N> _bs1;
    //std::bitset<N> _bs2;
  };
}

Test.cpp:

#include "BitSet.h"
 
void test_bitset()
{
  rtx::bitset<100> bs; //上面面试题开范围可以这样开:bitset<-1> bs1;
  bs.set(8);
  bs.set(9);
  bs.set(20);
 
  cout << bs.test(8) << endl;
  cout << bs.test(9) << endl;
  cout << bs.test(20) << endl;
  cout << bs.test(30) << endl << endl;
 
  bs.reset(8);
  bs.reset(20);
 
  cout << bs.test(8) << endl;
  cout << bs.test(9) << endl;
  cout << bs.test(20) << endl;
}
 
void test_two_bitset()
{
  int arr[] = { 3, 4, 5, 2, 3, 4, 4, 4, 4, 12, 77, 65, 44, 4, 44, 99, 33, 33, 33, 6, 5, 34, 12 };
 
  rtx::two_bitset<100> bs;
  for (const auto& e : arr)
  {
    bs.set(e);
  }
 
  bs.print_once_num();
}
 
int main()
{
  //test_bitset();
  test_two_bitset();
 
  return 0;
}


  • 问题二:给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
  • 两个文件都有100亿个整数,必然放不进内存中,所以同样采用位图结构。
  • 每个文件使用一个2^32个比特位的位图,两个文件就是两个位图,占用的内存也就是1GB,符合要求。
  • 两个文件都放进位图,这样就可以去重了,然后将两个位图进行按位与运算,得到的结果中,比特位是1的就是交集。

这里具体的实现就不再写了,要注意体会位图的应用,也就是哈希应用的思想。

  • 问题三:一个文件有100亿个int,1G内存,如何找到出现次数不超过两次的所有整数?
  • 采用的方法是两个位图结构,和问题1一样。
  • 只是这里还需要两个位是11的情况,用来表示3次及以上。

只需要在前面代码增加一种情况的处理即可:


1.4 位图的优缺点

上面就是一些位图的应用,有下面这些要求时应该想到位图:

  • 1. 快速查找某个数据是否在一个集合中
  • 2. 排序 + 去重
  • 3. 求两个集合的交集、并集等
  • 4. 操作系统中磁盘块标记

但是位图有优点也是有缺点的:

优点:节省空间,效率高。(直接定制法,直接开到整形的最大范围就不存在冲突)

缺点:一般要求数据相对集中,否则会导致空间消耗上升。还有一个致命缺点:只能针对整形。

2. 布隆过滤器

       如果我就要使用位图来存放字符串呢?当然也是可以的,只是需要和哈希表一样,将字符串转换成整数。


       如上图所示,将不同的字符串通过hashfunc函数转换成不同的整数,然后将这些整数映射到位图中,从而表示字符串的存在情况。


       但是无论是哪种方式,字符串转换成整数,都有可能让两个不同的字符串转换的整数相同。这就会产生误判的情况,那是判断存在有误判,还是判断不存在有误判,还是都有误判呢?:


位图中存在:不一定真正存在。

如上图中“find”和“insert”转换成的整数都是1234,所以位图中第1234个比特位是1,就可以说“find”和“insert”都存在,但实际上是“insert”存在,而“find”不存在,于是就产生了误判。


位图不存在:必然不存在。

还使用上面的例子,如果位图的第1234个比特位是0,说明“find”和“insert”都不存在。


所以根据位图判断出的结构,不存在是准确的,存在是不准确的。


       有没有办法能提高一下判断的准确率呢?答案是有的,布隆过滤器就可以降低误判率,提高准确率。

2.1 布隆过滤器的概念

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


布隆过滤器:用多个哈希函数,将一个数据映射到位图结构中。

使用两个哈希函数,将同一个字符串转换成两个整数,并且都映射在位图中,如上图所示。

       只有一个字符串在位图中的两个比特位同时为1才能说明该字符串存在。"find"经过哈希函数处理后的两个整数,只有一个是被“insert”映射的,另一个是0,说明“find”不存在。而“insert”经过哈希函数处理后的两个整数,在位图中都有映射,可以说明“insert”存在。


此时降低了误判率:


位图存在:字符串存在的准确率提高,但是仍有不存在的可能。

       字符串“find”经过两个哈希函数处理后得到两个整数,与字符串“insert”得到的两个整数相同的概率,比之前各自有一个整数相同的概率低的多。但是仍然有可能“find”的两个整数和“insert”的两个整数相同,此时就会又出现误判。


位图不存在:必然不存在。


布隆过滤器对于不存在的判断是准确的,并且可以降低存在时的误判率。

布隆过滤器的应用场景:不需要一定准确的场景,比如注册昵称时的存在判断。

       如上图中,一个昵称的数据库是放在服务器中的,这个数据库中昵称的存在情况都放在了布隆过滤器中,当从客户端注册新的昵称时,可以通过布隆过滤器快速判断新昵称是否存在。


这里对存在的准确率要去就没有太高,布隆过滤器显示存在(不准确),就换一个昵称,显示不存在(准确),就注册这个昵称,并放入数据库中。

通过布隆过滤器查找可以提高效率,如果之前去数据库中查找的话,效率就会大大降低。

哈希函数个数和布隆过滤器长度的关系:


       现在知道布隆过滤器是什么了,但是我们到底该创建多少个比特位的位图(布隆过滤器长度),又应该使用多少个哈希函数来映射同一个字符串呢?


布隆过滤器长度长度开得短了误判率就高,开得长了就存在空间浪费的情况,优点就不明显了。


如何选择哈希函数个数和布隆过滤器长度一文中,对这个问题做了详细的研究和论证:

  • 哈希函数个数和布隆过滤器长度以及误判率三者之间的关系曲线。

最后得出一个公式:

  • m:表示布隆过滤器长度。k:表示哈希函数个数。n:表示插入的元素个数。n2约等于0.69。

2.2 布隆过滤器的实现

       首先需要写几个哈希函数来将字符串转换成整形,各种字符串Hash函数一文中,介绍了多种字符串转换成整数的哈希函数,并且根据冲突概率进行了性能比较,有兴趣的可以自行研究一下。这里选择分数较高的3个哈希函数:

1.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;
  }
};
 
template<size_t N, class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class BloomFilter // N表示准备要映射N个值
{
public:
 
protected:
  const static size_t _ratio = 5; // 根公式算出来,此时哈希函数是3个,所以m = 3n/ln2 约等于4.2 取5
  std::bitset<_ratio* N>* _bits = new std::bitset<_ratio * N>;
  // 库里的bit是放在栈上的,容易栈溢出,所以自己放到堆上(很挫)用自己写的就是放在堆上的
};

size_t N:最多存储的数据个数。

class K:布隆过滤器处理的数据类型,默认情况下是string,也可以是其他类型。

哈希函数:将字符串或者其他类型转换成整形进行映射,缺省值是将字符串转换成整形的仿函数。

set(): 将数据经过3个哈希函数的处理得到3个整数,

然后将这3个整数都映射到位图中来表示这个数据存在。

  void Set(const K& key)
  {
    size_t hash1 = Hash1()(key) % (_ratio * N); // 注意优先级问题,在最后加括号
    size_t hash2 = Hash2()(key) % (_ratio * N);
    size_t hash3 = Hash3()(key) % (_ratio * N);
 
    _bits->set(hash1);
    _bits->set(hash2);
    _bits->set(hash3);
 
  }

test(): 对每一个哈希函数得到的整数所映射的位置进行判断,如果某个位置不存在直接返回false,说明这个字符串不存在,当所有整数所映射的位置都存在,说明这个字符串存在。

  • 判断每个比特位时,判断它不存在,不要判断它存在,因为不存在是准确的,存在是不准确的。
  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; // 可能存在误判
  }


在这思考:布隆过滤器要不要支不支持删除?

  • 布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素。

       “baidu”和“tencent”映射的比特位都有第4个比特位。删除上图中"tencent"元素,如果直接将该元素所对应的二进制比特位置0,“baidu”元素也被删除了,因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。


面试题: 如何扩展BloomFilter使得它支持删除元素的操作。


       一种支持删除的方法:将布隆过滤器中的每个比特位扩展成一个小的计数器(引用计数),插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一,删除元素时,给k个计数器减一,通过多占用几倍存储空间的代价来增加删除操作。


但是也存在缺陷,无法确认元素是否真正在布隆过滤器中,甚至会有计数回绕。

总的来说,布隆过滤器最好不要支持删除操作。

从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(下):https://developer.aliyun.com/article/1522353?spm=a2c6h.13148508.setting.17.50c04f0egKUJB6

目录
相关文章
|
14天前
|
C++
C++中的封装、继承与多态:深入理解与应用
C++中的封装、继承与多态:深入理解与应用
24 1
|
19小时前
|
C语言 C++
【C++语言】冲突-C语言:命名空间
【C++语言】冲突-C语言:命名空间
|
22小时前
|
JSON Android开发 C++
Android c++ core guideline checker 应用
Android c++ core guideline checker 应用
|
2天前
|
存储 安全 C++
C++中的引用和指针:区别与应用
引用和指针在C++中都有其独特的优势和应用场景。引用更适合简洁、安全的代码,而指针提供了更大的灵活性和动态内存管理的能力。在实际编程中,根据需求选择适当的类型,能够编写出高效、可维护的代码。理解并正确使用这两种类型,是掌握C++编程的关键一步。
10 1
|
7天前
|
算法 C++
C++中的结构应用:Josephus问题
C++中的结构应用:Josephus问题
8 1
|
7天前
|
存储 C++ 容器
c++实现哈希桶
这篇文章回顾了闭散列的概念,指出在数据冲突时,闭散列会自动寻找后续未占用的位置插入数据。然而,这种方法可能导致某些元素状态变为删除,从而在查找时产生问题。为了解决这个问题,文章介绍了拉链法(哈希桶)作为改进策略。拉链法在每个哈希表位置上维护一个链表,冲突的数据挂载在相应位置的链表上。文章详细描述了拉链法的插入、查找和删除操作,并提供了相关代码示例。在插入过程中,当负载因子达到1时,哈希表会进行扩容,同时避免了频繁创建和销毁节点,提高了效率。最后,文章通过测试代码展示了拉链法的正确性。
9 0
|
8天前
|
程序员 C语言 C++
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
9 0
|
12天前
|
C++ 存储 Java
C++ 引用和指针:内存地址、创建方法及应用解析
'markdown'C++ 中的引用是现有变量的别名,用 `&` 创建。例如:`string &meal = food;`。指针通过 `&` 获取变量内存地址,用 `*` 创建。指针变量存储地址,如 `string *ptr = &food;`。引用不可为空且不可变,指针可为空且可变,适用于动态内存和复杂数据结构。两者在函数参数传递和效率提升方面各有优势。 ```
|
14天前
|
设计模式 开发框架 算法
C++中的设计模式:基本概念与应用
C++中的设计模式:基本概念与应用
23 2
|
16天前
|
安全 Linux 编译器
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(下)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
22 0