【C++】位图 + 布隆过滤器

奶芙c 2024-08-18 14:35:02 阅读 61

目录

1. 位图1.1. 概念1.2. 实现1.3. 应用

2. 布隆过滤器2.1. 背景2.2. 概念2.3. 实现2.4. 优点2.5. 缺点

3. 海量数据面试题3.1. 哈希切割3.2. 位图应用3.3. 布隆过滤器3.4. 总结

1. 位图

1.1. 概念

位图是一种用于高效地存储和操作集合的数据结构。它的基本思想是使用一个二进制位(0或1)来表示一个元素是否存在于集合中,位图中的每一位对应着集合中的某个元素,可以通过直接访问某个位来判断某个元素在不在集合中。若某个元素在集合中,则对应位为1,否则,对应位为0。

位图是使用"哈希(映射)"这种思想实现的,计算集合中的元素在位图中的存储位置,采用哈希的直接定址法。适用于海量数据,数据无重复的场景。一般常用于判断某个数据是否存在。

位图开辟空间时,空间大小为数据类型范围的最大值,不是数据的个数,使用非类型模板参数N。eg : 整数,包括有、无符号整数,最大值为2^32-1,非类型模板参数N=UINT_MAX、0XFFFFFFFF(16进制)、-1(自动转换为size_t),共需要500MB内存空间。

位图优缺点:高效存储,节省空间;快速查询,时间复杂度为O(1);只适用于整型数据(%);快速集合运算等。

image.png

1.2. 实现

<code>#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

#include<vector>

using namespace std;

namespace zzx{ -- --> //位图,采用"哈希"思想来实现的

template<size_t N> //非类型模板参数,位图大小开的是数据类型的范围,不是数据的个数

class bitset{

public:

bitset() //构造函数,提前开辟好空间,防止[]越界访问

{

_bits.resize(N/32 + 1, 0); //多开辟一个int,eg:66,并将位图的每一位初始化为0

}

void set(size_t x) //将x映射的位设置为1

{

int i = x / 32; //x存储在数组的第i个整型数据

int j = x % 32; //x存储在数组的这个整数的第j位

_bits[i] |= (1 << j); //其他位不变,第j位变为1

}

void reset(size_t x) //将x映射的位设置为0

{

int i = x / 32;

int j = x % 32;

_bits[i] &= ~(1 << j); //其他位不变,第j位变为0

}

bool test(size_t x) //测试x映射位的值是否为1(状态)

{

int i = x / 32;

int j = x % 32;

return _bits[i] & (1 << j); //整形转bool,0为假,非0为真

}

private:

vector<int> _bits; //底层为数组

};

}

位图实现.png

1.3. 应用

快速查询某一个数据是否在一个集合中。结果是在或不在,只有两种状态,可以用一个二进制比特位来代表数据是否存在的信息。位图中的每一位对应集合中的某个元素,通过直接定址法直接访问某个元素在位图中的存储位,对应位为1表示在,对应位为0表示不在。

排序 + 去重。集合中的元素在位图中的存储位置,采用哈希的直接定址法,从头到尾打印位图,就可以得到一个有序的集合。位图空间大小为数据类型的范围,大小固定的,重复的元素会映射到同一位,达到去重的目的。

求两个集合的交集或者并集。将两个集合set到两个位图中,test同时为1的就为交集,否则,为并集。

操作系统中磁盘块标记。

屏幕截图 2024-04-09 190614.png

2. 布隆过滤器

2.1. 背景

位图只适用于整形数据,对于字符串,位图就无法处理了。

需要先通过哈希函数将字符串转化为整形,在进行映射存储位置,但会出现哈希冲突,从而导致"误判"(不在:对应位为0, 准确的、在:对应位为1, 可能会有"误判”,因为映射位置的冲突,会将不在误判成在)。

为了降低哈希冲突的概率,就有人提出了通过多个不同的哈希函数对key进行不同位置的映射,只要有一个映射位置的值不同,就不在,误判率降低,但仍会有哈希冲突,无法百分百避免。

2.2. 概念

布隆过滤器是一种数据结构,它实际上是很长的二进制向量和一系列随机映射函数。由一个很长的bit数组和一系列哈希函数组成。

它的特点是高效的插入、查询,可以用来告诉你"某样东西一定不存在或者可能存在",相比于传统的list、set、map等数据结构,它更高效,占用的空间内存更少,缺点是返回的结果具有概率性,不是确定的。它是用多个哈希函数,将一个数据映射到位图结构中。此方式不仅可以提升查询效率,也可以节省内存空间。

2.3. 实现

<code>#pragma once

#define _CRT_SECURE_NO_WARNINGS 1

#include"bitset.h"

struct HashFuncBKDR { -- -->

//BKDR

size_t operator()(const string& s)

{

size_t hash = 0;

for (auto& ch : s)

{

hash *= 131;

hash += ch;

}

return hash;

}

};

struct HashFuncAP

{

// AP

size_t operator()(const string& s)

{

size_t hash = 0;

for (size_t i = 0; i < s.size(); i++)

{

if ((i & 1) == 0) // 偶数位字符

{

hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));

}

else // 奇数位字符

{

hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));

}

}

return hash;

}

};

struct HashFuncDJB

{

// DJB

size_t operator()(const string& s)

{

size_t hash = 5381;

for (auto ch : s)

{

hash = hash * 33 ^ ch;

}

return hash;

}

};

template<size_t N, class K = string, class Hash1 = HashFuncBKDR, class Hash2 = HashFuncAP, class Hash3 = HashFuncDJB>

class BloomFilter { //布隆过滤器

public:

void set(const K& key) //用多个哈希函数,将一个数据映射的位设置为1

{

int hash1 = Hash1()(key) % M;

int hash2 = Hash2()(key) % M;

int hash3 = Hash3()(key) % M;

_bits.set(hash1);

_bits.set(hash2);

_bits.set(hash3);

}

bool test(const K& key) //检验Key是否存在集合中

{ //只要有一个映射位对应的值不同,就不存在,若全部相同,但仍有冲突的可能,导致"误判",无法规避

int hash1 = Hash1()(key) % M;

int hash2 = Hash2()(key) % M;

int hash3 = Hash3()(key) % M;

if (_bits.test(hash1) == false) return false;

if (_bits.test(hash2) == false) return false;

if (_bits.test(hash3) == false) return false;

return true;

}

private:

static const size_t M = 5 * N; //N为插入的元素个数,M为布隆过滤器的长度

zzx::bitset<M> _bits;

};

屏幕截图 2024-04-09 213655.png

2.4. 优点

增加、查询元素的时间复杂度位O(K)(K为哈希函数的个数,一般较小),与数据量的大小无关。

布隆过滤器不需要存储元素本身,对于保密要求比较严格的场合具有较大的优势。

各个哈希函数之间无联系,方便硬件并行运算。

数据量很大的时候,布隆过滤器可以表示全集,其他数据结构不能,如:平衡树,需要存储集合中的每个元素,布隆不需要,节省空间。

对于使用相同哈希函数的布隆过滤器,可以进行交集、并集、差集运算。

2.5. 缺点

有误判率,存在"假阳性”。因为哈希冲突,会把不在的误判成在。

不能获取元素本身。

不能从布隆过滤器中删除元素。

采用引用计数方式删除,会造成计数回绕、空间浪费等问题。

3. 海量数据面试题

3.1. 哈希切割

哈希切割面试题.png

3.2. 位图应用

位图面试题.png

<code>//只出现一次的整数

template<size_t N>

class two_bitset1 { -- -->

public:

void set(size_t x) //插入

{

//0次(00)->1次(01)->2次及以上(10)

if (_bs1.test(x) == 0 && _bs2.test(x) == 0) _bs2.set(x);

else

{

_bs1.set(x);

_bs2.reset(x);

}

}

bool test(size_t x) //找出只出现一次的元素

{

if (_bs1.test(x) == 0 && _bs2.test(x) == 1) return true;

else return false;

}

private:

bitset<N> _bs1; //两个位图

bitset<N> _bs2;

};

two_bitset1<UINT_MAX> tbs;

int a[] = { 1, 3, 8, 4, 1, 6, 3, 7, 4, 10, 2 };

for (auto& e : a)

{

tbs.set(e);

}

for (auto& e : a)

{

if (tbs.test(e))

cout << e << endl;

}

//求交集(需去重)

bitset<20> bs1;

bitset<20> bs2;

int a1[] = { 10, 4, 8, 4, 2, 1, 5, 2 };

int a2[] = { 10, 10, 4, 2, 2, 3 };

for (auto& e : a1)

{

bs1.set(e);

}

for (auto& e : a2)

{

bs2.set(e);

}

for (int i = 0; i < 20; i++) //去重了

{

if (bs1.test(i) && bs2.test(i))

cout << i << endl;

}

cout << endl;

for (auto& e : a2) //未去重

{

if (bs1.test(e) && bs2.test(e))

cout << e << endl;

}

//出现次数不超过2次的整数

template<size_t N>

class two_bitset2 {

public:

void set(size_t x) //插入

{

//0次(00)->1次(01)->2次及以上(10)

if (_bs1.test(x) == 0 && _bs2.test(x) == 0) _bs2.set(x);

else if(_bs1.test(x) == 0 && _bs2.test(x) == 1) //注意,此处不能为if,因为上面if走完,会继续往下走

{

_bs1.set(x);

_bs2.reset(x);

}

else

{

_bs1.set(x);

_bs2.set(x);

}

}

bool test(size_t x) //找出只出现一次的元素

{

if (_bs1.test(x) == 0 && _bs2.test(x) == 0) return true;

else if (_bs1.test(x) == 0 && _bs2.test(x) == 1) return true;

else if (_bs1.test(x) == 1 && _bs2.test(x) == 0) return true;

return false;

}

private:

bitset<N> _bs1; //两个位图

bitset<N> _bs2;

};

3.3. 布隆过滤器

布隆过滤器的面试题.png

3.4. 总结

海量数据的特征:数据量太大,内存存不下。

优先考虑具有特点的数据结构能否解决 -》位图、布隆过滤器、堆等。

其次进行"大事化小",哈希切分,但不能平均切分,切小以后,放到内存中处理。



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。