C++ 哈希思想应用:位图,布隆过滤器,哈希切分

C++ 哈希思想应用:位图,布隆过滤器,哈希切分

  • 一.位图
    • 1.位图的概念
      • 1.问题
      • 2.分析
      • 3.位图的概念
      • 4.演示
    • 2.位图的操作
    • 3.位图的实现
      • 1.char类型的数组
      • 2.int类型的数组
      • 3.解决一开始的问题
        • 位图开多大呢?
        • 小小补充
        • 验证
    • 4.位图的应用
      • 1.给定100亿个整数,设计算法找到只出现一次的整数?
        • 1.位图开多大?
        • 2.思路
        • 3.代码
        • 4.验证
      • 2.给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
      • 3.一个文件有100亿个整数,1G内存,设计算法找到出现次数不超过2次的所有整数
      • 4.给定100亿个整数,0.5G内存,设计算法找到只出现一次的整数?
        • 1.思路
        • 2.验证代码实现
  • 二.布隆过滤器
    • 1.布隆过滤器的提出
    • 2.布隆过滤器的概念
    • 3.布隆过滤器的应用场景
      • 1.能够容忍误判的场景
      • 2.无法容忍误判的场景
    • 4.代码实现
      • 1.选择字符串哈希函数
      • 2.推导出布隆过滤器长度
      • 3.大致结构
      • 4.具体实现
      • 5.测试
        • 1.小型测试
        • 2.大型测试
    • 5.标准非STL容器 : bitset
      • 验证
      • 改造
    • 6.布隆过滤器的优缺点
  • 三.哈希切分
    • 1.给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法
      • 1.近似算法
      • 2.精确算法
    • 2.给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?与上题条件相同,如何找到top K的IP?如何直接用Linux系统命令实现?
  • 四. 如何扩展BloomFilter使得它支持删除元素的操作?
    • 1.布隆过滤器删除的局限及其问题
    • 2.代码
    • 3.验证布隆过滤器删除的坑点
    • 4.使用额外的数据结构来进行扩展
      • 1.如何做呢?
      • 2.代码
      • 3.验证

一.位图

1.位图的概念

1.问题

给你40亿个不重复的无符号整数,没排过序.给一个无符号整数,如何快速判断一个数是否在这40亿个数中?

2.分析

1 Byte = 8 bit
1KB = 1024 Byte
1MB = 1024KB = 10241024 大约= 10的6次方Byte
1GB = 1024MB = 1024
10的6次方 大约= 10的9次方Byte = 10亿字节
因此4GB 约等于40亿字节

其实最快的方式就是记住1GB约等于10亿字节,这种题就好算了

我们知道40亿个整数,大概就是16GB
如果用排序+二分,
排序需要开16GB大的数组,就算用外排序(归并排序)排完序了,但是二分也需要数组啊…

如果用AVL树红黑树和哈希表
红黑树:三叉链结构+颜色 AVL树:三叉链结构+平衡因子 哈希表:负载因子每个节点的next指针等问题
内存当中更存不下

因此就需要用到位图了

3.位图的概念

在这里插入图片描述

4.演示

假设我们的位图使用一个char类型的数组实现的话
我们这个arr数组的最大值是22,因此只需要22个比特位即可
因此我们用一个char类型的数组,数组中有3个char即可
存放之前:
在这里插入图片描述
存放方式:
在这里插入图片描述
存放过程:
在这里插入图片描述
存放完毕后:
在这里插入图片描述

2.位图的操作

位图的三个核心操作:
set将x对应的比特位设置为1

将某一个比特位置为1,同时不影响其他比特位:
按位或一个数,这个数对应的那个比特位为1,其余比特位为0

void set(size_t x)
{
	size_t i = x / 8;
	size_t j = x % 8;
	_bits[i] |= (1 << j);
}

reset将x对应的比特位设置为0

将某一个比特位置为0,同时不影响其他比特位:
按位与一个数,这个数对应的那个比特位为0,其余比特位为1

void reset(size_t x)
{
	size_t i = x / 8;
	size_t j = x % 8;
	_bits[i] &= ~(1 << j);
}

test检查x在不在

跟一个数进行按位与
按位与一个数,这个数对应的那个比特位为1,其余比特位为0
如果结果
为0:说明不存在,
不为0说明存在

bool test(size_t x)
{
	size_t i = x / 8;
	size_t j = x % 8;

	return _bits[i] & (1<<j);
}

3.位图的实现

1.char类型的数组

实现了set reset test之后
位图其实就已经实现完毕了

namespace wzs
{
	// N是需要多少比特位
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bits.resize(N/8+1, 0);
		}
	
		void set(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			_bits[i] |= (1 << j);
		}
	
		void reset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			_bits[i] &= ~(1 << j);
		}
	
		bool test(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
	
			return _bits[i] & (1<<j);
		}
	private:
		vector<char> _bits;
	};
}

2.int类型的数组

也可以采用int类型的数组来搞
此时就不是除8模8了
而是除32模32了
因为一个int类型有32个比特位

namespace wzs
{
	// N是需要多少比特位
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			//_bits.resize(N/32+1, 0);
			_bits.resize((N>>5) + 1, 0);
		}

		void set(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			_bits[i] |= (1 << j);
		}

		void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			_bits[i] &= ~(1 << j);
		}

		bool test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			return _bits[i] & (1<<j);
		}
	private:
		vector<int> _bits;
	};
}

3.解决一开始的问题

因此对于一开始的那个问题:
在这里插入图片描述

位图开多大呢?

注意: 使用位图,且没有指定范围时,我们要按照该数据的范围大小来开位图

无符号整数的范围是0~4,294,967,295
因此我们需要开0~4,294,967,295大的范围

0~2的32次方-1的范围
一共有2的32次方个整数,

2的10次方是1024
2的30次方就是1024*1024*1024=1024*1024K=1024M=1G
因此2的32次方就是4G个整数

而我们使用一个比特位表示一个整数的,一个字节有8个比特位
因此我们只需要4G/8=0.5G个字节即可

因此我们的位图大小就是0.5G,正常情况下内存当中完全能存的下
无需担心

小小补充

而这个数字也不好记,其实它还有下面3种写法

  1. (size_t)-1 将-1强转为无符号整形
  2. UINT_MAX (unsigned_intMAX)
  3. 0xffffffff(16进制:8个f)
  4. pow(2,32)-1

一定注意:^在C++/C当中是异或,不是幂
因此(2^32)-1不等于那个数字

pow的返回值类型是double类型
在这里插入图片描述

验证

下面我们来验证一下位图能否完成这一任务
在这里插入图片描述
在这里插入图片描述
成功完成这一任务

4.位图的应用

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

1.位图开多大?

我们先算一下100亿个整数要占多少G的内存?
一个比特位映射一个整数,一个字节有8个比特位
100亿个整数=100亿个比特位=100亿/8个字节=12.5亿字节=1.25G

我们真的要用1.25G的空间吗?
并不是!!!
而是刚才我们算的0.5G就足以

因为我们只存范围
如果要求必须使用位图来做,就算只有2个整数,不给我们范围,还是要用0.5G大小的位图

2.思路

找到只出现一次的整数,因为一个比特位只有0和1这两种状态,因此无法表示出现了1次以上的数字的状态

那么怎么办?
如果用2个比特位来表示一个整数的状态呢?
00就是出现0次
01就是出现1次
10就是出现2次
出现2次以后这个数我们就不再统计次数了

因此我们可以:
1.修改上面的位图,用2个比特位来表示一个整数
此时位图的大小就要乘以2,成为1G
2.用2个位图来做,每个位图依然是0.5G
只不过set,test函数要修改一下即可

下面我们就按照第2种来做吧,这个清晰易懂

3.代码

因为我们没有统计2次以上的次数,因此我们不允许进行reset操作

//利用组合来进行封装
template<size_t N>
class two_bitset
{
public:
	void set(int x)
	{
		//00 -> 01
		if (_bits1.test(x) == false && _bits2.test(x) == false)
		{
			_bits2.set(x);
		}
		//01 -> 10
		else if (_bits1.test(x) == false && _bits2.test(x) == true)
		{
			_bits1.set(x);
			_bits2.reset(x);
		}
		//10,不记录了
	}

	//返回x出现了多少次
	//返回2表示2次及以上
	int test(int x)
	{
		if (_bits1.test(x) == false && _bits2.test(x) == false)
		{
			return 0;
		}
		else if (_bits1.test(x) == false && _bits2.test(x) == true)
		{
			return 1;
		}
		return 2;
	}

private:
	bitset<N> _bits1;
	bitset<N> _bits2;
};
4.验证

在这里插入图片描述
成功

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

经过刚才的那道题
我们已经能够很轻松的解决了

管你100亿还是200亿,统统开0.5G的位图

因为有2个文件,因此开2个位图,正好1个G

每个文件当中的每个整数还是按照一个比特位来映射
只不过取交集的时候要求两个位图当中的test都为true才是交集
因此我们直接用一开始的位图即可,不用再去写位图了
在这里插入图片描述
集合是具有互异性的,而我们的位图是天然去重的,因此无需担心交集当中出现重复值

下面我们来玩一下
在这里插入图片描述

3.一个文件有100亿个整数,1G内存,设计算法找到出现次数不超过2次的所有整数

跟第一个问题的思路一样,只不过找的条件不一样
此时就需要记录超过2次的次数了
可以用11表示出现3次即以上的次数
然后稍稍改一下即可,这里就不赘述了

4.给定100亿个整数,0.5G内存,设计算法找到只出现一次的整数?

1.思路

这不还是第1题吗?
不是的,因为这里只有0.5G,而我们的一个位图是0.5G,需要使用2个位图才可以

因此按照第1题的思路来做的话,内存当中是存不下的
怎么办?

首先我们要知道:我们一定还是需要2个位图的,一个位图搞不定
而一共就只有0.5G内存,分配给2个位图的话
一个位图才只有0.25G啊,存不下0~2的32次方-1这么大的范围,只能存一半

此时我们发现,只能存一半,那么我一次存一半,一共存2次不就行了吗?
第一次位图当中只查找0到2的31次方-1的范围当中只出现1次的整数
第二次位图当中只查找2的31次方到2的32次方-1的范围当中只出现1次的整数不就行了吗?

只不过第二次存的时候,只存大于等于2的31次方的值,而且所有的值要先减去2的31次方再存入,然后取的时候取出来再加上2的31次方

因此我们就可以这样玩

2.验证代码实现

因为第一次存完之后,存第二次之前要先把位图当中的原有数据清空
因此我们要提供一个clear操作,将位图当中的x对应的比特位置为0

void clear(int x)
{
	_bits1.reset(x);
	_bits2.reset(x);
}
void test_bitset4()
{
	//-1 -3 -4 -5都是转为无符号之后大于2的31次方的整数
	int a[] = { 1,1,2,2,2,2,5,6,1,9,7,-1,-3,-4,-5 };
	set_int::two_bitset<(1 << 31) - 1> bs;

	for (auto& e : a)
	{
		if ((size_t)e < (1 << 31))
		{
			bs.set(e);
		}
	}

	for (auto& e : a)
	{
		if ((size_t)e < (1 << 31))
		{
			int ret = bs.test(e);
			if (ret == 1)
			{
				cout << e << endl;
			}
			bs.clear(e);
		}
	}
	cout<<"第一次位图完成,下面开始第二次"<<endl;
	for (auto& e : a)
	{
		if ((size_t)e >= (1 << 31))
		{
			bs.set((size_t)e - (1 << 31));
		}
	}

	for (auto& e : a)
	{
		if ((size_t)e >= (1 << 31))
		{
			int ret = bs.test((size_t)e - (1 << 31));
			if (ret == 1)
			{
				cout << e << endl;
			}
		}
	}
}

在这里插入图片描述

二.布隆过滤器

这是知乎的一位大佬写的关于布隆过滤器的文章的开头的内容
我也觉得这句话写的特别好,分享给大家
在这里插入图片描述
我觉得不仅仅布隆过滤器是这句话的代表,我们后面要讲的哈希切分更是这句话典型的代表
完美的体现了对于数据结构选择的灵活性

1.布隆过滤器的提出

在这里插入图片描述
下面我们来分析一下,这种方法的准确性到底如何?
在这里插入图片描述
也就是说这个方法是走不通的,因为存在误判的可能

2.布隆过滤器的概念

但是布隆这个大佬是这么考虑的:
这个方法的确是行不通,但是这个方法对于不在的判定结果是准确的
那么我能否利用这个方法来进行一层过滤,把不在的完全过滤出去呢
在这里插入图片描述
而这就是我们今天要介绍的布隆过滤器
在这里插入图片描述

3.布隆过滤器的应用场景

1.能够容忍误判的场景

对于一些能够容忍误判的场景(也就是能够接受把不在误判为在),这个方法完全可以
比如说:
在这里插入图片描述
在这里插入图片描述

2.无法容忍误判的场景

在这里插入图片描述
对于一些无法容忍误判的场景,这个方法可以提高我查询的效率
也就是如果判定为不在,那么这个字符串一定不在,直接返回即可
如果判断为在,那么我再去相应的数据库当中进行查找,看看这个字符串到底是不是真的存在

因此布隆过滤器才叫做"过滤器"嘛

4.代码实现

下面我们来一起实现一下布隆过滤器吧

1.选择字符串哈希函数

很多大佬设计的很多字符串哈希算法:字符串哈希函数
我们就选上3个哈希函数吧
在这里插入图片描述

2.推导出布隆过滤器长度

这是知乎上的一位大佬写的关于布隆过滤器的一篇文章,感兴趣的话大家可以看一看
详解布隆过滤器的原理,使用场景和注意事项
在这里插入图片描述

3.大致结构

在这里插入图片描述
下面请大家思考一个问题:布隆过滤器支持删除吗?
在这里插入图片描述
答案是:一般是不支持的
当然也可以支持,此时就不能用一个比特位来进行映射了,而要用一个char/int来进行映射,采用类似于引用计数的方式进行映射

不过那样做的缺陷是,本来一个比特位就能解决问题,现在要用8个甚至32个比特位才能解决问题,对于空间的消耗一下子扩大为8被甚至32倍

4.具体实现

1.set

//插入x
void set(const K& x)
{
	//Hash1()是匿名对象,是仿函数对象,调用operator(),传入x作为参数
	size_t hashi1 = Hash1()(x) % M, hashi2 = Hash2()(x) % M, hashi3 = Hash3()(x) % M;
	//将3个比特位全部置为1即可
	_bits.set(hashi1);
	_bits.set(hashi2);
	_bits.set(hashi3);
}

2.test

//查找x
bool test(const K& x)
{
	//只要有一个比特位为0,就是false
	//3个比特位都为1,返回true(但是存在误判)
	size_t hashi1 = Hash1()(x) % M, hashi2 = Hash2()(x) % M, hashi3 = Hash3()(x) % M;
	if (_bits.test(hashi1) == false) return false;
	if (_bits.test(hashi2) == false) return false;
	if (_bits.test(hashi3) == false) return false;
	return true;
}

5.测试

1.小型测试
void test_bloom_filter()
{
	string strs[] = { "小明","小红" ,"小刚","李明","李华","小强" };
	BloomFilter<6> bf;
	for (auto& e : strs)
	{
		bf.set(e);
	}
	cout << "查看是否能够成功查找" << endl;
	for (auto& e : strs)
	{
		cout << e << " : " << bf.test(e) << endl;
	}
	cout << "查看是否存在误判" << endl;
	for (auto& e : strs)
	{
		cout << e << " : " << bf.test(e + 'a') << endl;
	}
	cout << "查看是否存在误判" << endl;
	string s[] = { "小名","小鸣","小茗","小铭",
"小洪","小虹","小宏","小鸿" };
	for (auto& e : s)
	{
		cout << e << " : " << bf.test(e) << endl;
	}
}

在这里插入图片描述

2.大型测试
void test_bloom_filter2()
{
	srand(time(0));
	const size_t N = 1000000;//N是100万
	BloomFilter<N> bf;

	std::vector<std::string> v1;
	std::string url = "https://zhuanlan.zhihu.com/p/43263751/";

	for (size_t i = 0; i < N; ++i)
	{
		v1.push_back(url + std::to_string(i));
	}

	for (auto& str : v1)
	{
		bf.set(str);
	}

	// v2跟v1是相似字符串集(前缀一样),但是后缀不一样
	std::vector<std::string> v2;
	for (size_t i = 0; i < N; ++i)
	{
		std::string urlstr = url;
		urlstr += std::to_string(9999999 + i);
		v2.push_back(urlstr);
	}

	size_t n2 = 0;
	for (auto& str : v2)
	{
		if (bf.test(str)) // 误判
		{
			++n2;
		}
	}
	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

	// 不相似字符串集  前缀后缀都不一样
	std::vector<std::string> v3;
	for (size_t i = 0; i < N; ++i)
	{
		string url = "布隆过滤器";
		url += std::to_string(i + rand());
		v3.push_back(url);
	}

	size_t n3 = 0;
	for (auto& str : v3)
	{
		if (bf.test(str))
		{
			++n3;
		}
	}
	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}

在这里插入图片描述
误判率大概是百分之9,百分之6左右
我们将M=5N调大一些,也就是把位图开大一些来看看
M=7
N:
在这里插入图片描述
误判率大概是百分之3,百分之4左右
已经很小了
M=9*N
在这里插入图片描述
误判率大概是百分之2,百分之1左右
知乎那位大佬针对于这一点也给出了折线图分析
在这里插入图片描述
感兴趣的话大家可以看一下那篇文章

5.标准非STL容器 : bitset

下面我们来说一下一个非常容易被忽视的点:
标准非STL容器 : bitset
这是一位大佬的博客,里面详细

bitset其实并不满足STL的所有要求

bitset内部是使用静态数组(类似于int arr[N])分配内存的,
也就是说bitset的数组并不是开辟在堆区的,而是开辟在栈区的
所以,使用bitset时要小心栈溢出

验证

下面我们来验证一下:
我们知道,如果bitset的数组是动态数组,也就是开辟在堆区的数组
那么bitset对象当中应该就只有一个指针也就是4/8个字节
如果bitset内部使用的是vector,那么bitset对象的大小就等于vector对象的大小
而我们知道vector的底层就是3个指针
start,finish,endOfStorage
因此大小就是12/24个字节
在这里插入图片描述
在这里插入图片描述
可以看出,随着位图越来越大,两者栈空间的差距也越来越大
在这里插入图片描述
那么怎么办呢?
难不成库里面的bitset就用不成了吗?
当然不是,new一个bitset对象,解引用调用其方法即可
下面我们改造一下布隆过滤器
封装std的bitset

改造

template <size_t N,class K = string,class Hash1 = HashFuncBKDR,class Hash2 = HashFuncAP,class Hash3 = HashFuncDJB>
class BloomFilter
{
public:
	//插入x
	void set(const K& x)
	{
		//Hash1()是匿名对象,是仿函数对象,调用operator(),传入x作为参数
		size_t hashi1 = Hash1()(x) % M, hashi2 = Hash2()(x) % M, hashi3 = Hash3()(x) % M;
		//将3个比特位全部置为1即可
		_pbits->set(hashi1);
		_pbits->set(hashi2);
		_pbits->set(hashi3);
	}
	//查找x
	bool test(const K& x)
	{
		//只要有一个比特位为0,就是false
		//3个比特位都为1,返回true(但是存在误判)
		size_t hashi1 = Hash1()(x) % M;
		if (_pbits->test(hashi1) == false) return false;
		size_t hashi2 = Hash2()(x) % M;
		if (_pbits->test(hashi2) == false) return false;
		size_t  hashi3 = Hash3()(x) % M;
		if (_pbits->test(hashi3) == false) return false;
		return true;
	}
private:
	//这里定义一个M,表示布隆过滤器的长度
	//因为N是布隆过滤器的非类型模板参数,M是位图的非类型模板参数,因此这里要加static和const来修饰M
	static const int M = 5 * N;
	//set_int::bitset<M> _bits;
	//std::bitset<M> _bits;
	std::bitset<M>* _pbits = new bitset<M>;
};

在这里插入图片描述
N=100万验证成功

6.布隆过滤器的优缺点

在这里插入图片描述

三.哈希切分

1.给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法

query:查询,比如SQL语句,网址等等,都是一个查询
这里我们把它当成字符串即可

1.近似算法

利用布隆过滤器+分批次读取
在这里插入图片描述

2.精确算法

利用哈希切分+set求交集
在这里插入图片描述
哈希切分时间复杂度:O(N)
每个query只遍历常数次
在这里插入图片描述
平均切分:时间复杂度O(N^2)
文件B当中的每个query读N次

从这就可以看出哈希切分的强大之处

2.给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?与上题条件相同,如何找到top K的IP?如何直接用Linux系统命令实现?

如何找到次数最多和TOP-K的IP地址?
在这里插入图片描述
如何利用linux系统命令来实现,这是文心一言给的答案
在这里插入图片描述

四. 如何扩展BloomFilter使得它支持删除元素的操作?

1.布隆过滤器删除的局限及其问题

在这里插入图片描述
将布隆过滤器中的每个比特位扩展成一个char/int,插入元素时给k个char/int加一,删除元素时,给k个char/int减一,通过多占用几倍的存储空间的代价来增加删除

但是有几个问题:

  1. 无法确认元素是否真正在布隆过滤器中
  2. 存在计数回绕

2.代码

template <size_t N, class K = string,class Hash1 = HashFuncBKDR, class Hash2 = HashFuncAP, class Hash3 = HashFuncDJB>
class BloomFilterExtendedVersion
{
public:
	BloomFilterExtendedVersion()
	{
		_v.resize(5 * N, 0);
	}
	//插入x
	void set(const K& x)
	{
		size_t hashi1 = Hash1()(x) % _v.size(), hashi2 = Hash2()(x) % _v.size(), hashi3 = Hash3()(x) % _v.size();
		_v[hashi1]++;
		_v[hashi2]++;
		_v[hashi3]++;
	}
	//查找x
	bool test(const K& x)
	{
		size_t hashi1 = Hash1()(x) % _v.size(), hashi2 = Hash2()(x) % _v.size(), hashi3 = Hash3()(x) % _v.size();
		if (_v[hashi1] == 0) return false;
		if (_v[hashi2] == 0) return false;
		if (_v[hashi3] == 0) return false;
		return true;
	}
	//删除x
	bool erase(const K& x)
	{
		if (test(x) == false) return false;
		size_t hashi1 = Hash1()(x) % _v.size(), hashi2 = Hash2()(x) % _v.size(), hashi3 = Hash3()(x) % _v.size();
		_v[hashi1]--;
		_v[hashi2]--;
		_v[hashi3]--;
	}
private:
	vector<int> _v;
};

3.验证布隆过滤器删除的坑点

在这里插入图片描述

4.使用额外的数据结构来进行扩展

1.如何做呢?

因此,仅仅只用计数器来做是不行的,那么怎么办呢?
在这里插入图片描述
其实跟我们上面讲的布隆过滤器在学校B无法容忍误判的场景相似
删除时先进行查找,如果不在布隆过滤器当中,那就返回false即可,
如果在布隆过滤器当中,那么就先到数据库当中查找,如果真的在,那么久把计数器–,并且在数据库当中删除该元素

此时我们用一个unordered_set/set充当数据库,存储实际的元素

下面我们写代码

2.代码

template <size_t N, class K = string,class Hash1 = HashFuncBKDR, class Hash2 = HashFuncAP, class Hash3 = HashFuncDJB>
class BloomFilterExtendedVersion
{
public:
	BloomFilterExtendedVersion()
	{
		_v.resize(5 * N, 0);
	}
	//插入x
	void set(const K& x)
	{
		size_t hashi1 = Hash1()(x) % _v.size(), hashi2 = Hash2()(x) % _v.size(), hashi3 = Hash3()(x) % _v.size();
		_v[hashi1]++;
		_v[hashi2]++;
		_v[hashi3]++;
		_us.insert(x);
	}
	//查找x
	bool test(const K& x)
	{
		size_t hashi1 = Hash1()(x) % _v.size(), hashi2 = Hash2()(x) % _v.size(), hashi3 = Hash3()(x) % _v.size();
		if (_v[hashi1] == 0) return false;
		if (_v[hashi2] == 0) return false;
		if (_v[hashi3] == 0) return false;
		if (_us.count(x) == 0) return false;
		return true;
	}
	//删除x
	bool erase(const K& x)
	{
		if (test(x) == false) return false;
		size_t hashi1 = Hash1()(x) % _v.size(), hashi2 = Hash2()(x) % _v.size(), hashi3 = Hash3()(x) % _v.size();
		_v[hashi1]--;
		_v[hashi2]--;
		_v[hashi3]--;
		_us.erase(x);
	}
private:
	vector<int> _v;
	unordered_set<K> _us;
};

3.验证

在这里插入图片描述
经过上面的一系列分析
我们可以得出
如果该布隆过滤器是应用在能够容忍误判的场景
那么建议不要实现删除操作,否则既浪费空间,又会产生计数回绕和误删的坑点
如果该布隆过滤器是应用在无法容忍误判的场景,
那么可以实现删除操作,唯一的不太好的点就是浪费空间,不过没有计数回绕和误删的问题了

以上就是C++ 哈希思想应用:位图,布隆过滤器,哈希切分的全部内容,希望能对大家有所帮助!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/510947.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

aardio plus滑尺滑块垂直

在滑尺调色工具中&#xff0c;将“控件宽度”调到小于“控件高度”时&#xff0c;就看到滑块滑条变成垂直的了。 一年前下载了aardio&#xff0c;刚接触&#xff0c;看到plus&#xff0c;滑尺配色工具&#xff0c;然后就试了一下&#xff0c;结果一直没找到怎么把plus滑尺调节…

Flash选型确认

3.1 NOR Flash选型 容量&#xff1a;容量大小一般是我们首先要考虑的因素&#xff0c;Flash的大小一般用bit表示&#xff0c;容量范围涵盖512Kb~512Mb。例如型号GD25Q64C容量就为64Mb8MB。 供电电压&#xff1a;Nor Flash的供电电压一般分为四种&#xff1a;2.7V~3.6V&#x…

盘点AI编程效率神器合集,代码助手工具大模型、Agent智能体

关注wx公众号:aigc247 进社群加wx号&#xff1a;aigc365 程序员是最擅长革自己命的职业&#xff0c;让我们借助AI的力量一起摸鱼一起卷&#xff01; 据说好用的AI代码助手工具、大模型、Agent智能体 微软的compoliot&#xff1a;AI神器之微软的编码助手Copilot-CSDN博客 阿…

Stream流,线程

文章目录 Stream流思想作用三类方法获取方法单列集合(Collection[List,Set双列集合Map(不能直接获取)数组同一类型元素(Stream中的静态方法) 常见的中间方法终结方法收集方法 Optional类 线程相关概念多线程概念实现方式继承Thread类实现Runnable接口比较 常用方法线程安全产生…

电机控制器电路板布局布线参考指导(二)

电机控制器电路板布局布线参考指导&#xff08;二&#xff09;热特性 1.概述2.PCB传导与对流3.连续顶层散热焊盘4.覆铜厚度5.散热过孔连接6.散热过孔宽度7.电机控制器电路板热设计总结 1.概述 电机驱动器并不是理想的器件&#xff0c;在实际应用中&#xff0c;它们的一些功率会…

Go 源码之 Chan

Go 源码之 chan go源码之chan - Jxy 博客 目录 Go 源码之 chan一、总结二、源码&#xff08;一&#xff09;hchan&#xff08;二&#xff09;创建&#xff08;三&#xff09;发送&#xff08;四&#xff09;接收&#xff08;五&#xff09;关闭 三、常见问题1.为什么要使用环形…

SV学习笔记(一)

SV&#xff1a;SystemVerilog 开启SV之路 数据类型 內建数据类型 四状态与双状态 &#xff1a; 四状态指0、1、X、Z&#xff0c;包括logic、integer、 reg、 wire。双状态指0、1&#xff0c;包括bit、byte、 shortint、int、longint。 有符号与无符号 &#xff1a; 有符号&am…

12313124

c语言中的小小白-CSDN博客c语言中的小小白关注算法,c,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm1001.2014.3001.5343 给大家分享一句我很喜欢我话&#xff1a; 知不足而奋进&#xff0c;望远山而前行&am…

【Linux】进程管理(2):进程控制

一、进程创建&#xff1a;fork函数 我们在命令行中输入man fork 即可得到fork函数的函数接口的函数的使用方法。 我们可以看到&#xff0c;fork函数位于man手册的第2部分&#xff0c;由于第2部分通常是用于描述系统调用和库函数&#xff0c;所以我们可以了解到fork函数实际是一…

【总结】在嵌入式设备上可以离线运行的LLM--Llama

文章目录 Llama 简介运用另一种&#xff1a;MLC-LLM 一个令人沮丧的结论在资源受限的嵌入式设备上无法运行LLM&#xff08;大语言模型&#xff09;。 一丝曙光&#xff1a;tinyLlama-1.1b&#xff08;10亿参数&#xff0c;需要至少2.98GB的RAM&#xff09; Llama 简介 LLaMA…

自动驾驶的世界模型:综述

自动驾驶的世界模型&#xff1a;综述 附赠自动驾驶学习资料和量产经验&#xff1a;链接 24年3月澳门大学和夏威夷大学的论文“World Models for Autonomous Driving: An Initial Survey”。 在快速发展的自动驾驶领域&#xff0c;准确预测未来事件并评估其影响的能力对安全性…

ssm017网上花店设计+vue

网上花店的设计与实现 摘 要 网络技术和计算机技术发展至今&#xff0c;已经拥有了深厚的理论基础&#xff0c;并在现实中进行了充分运用&#xff0c;尤其是基于计算机运行的软件更是受到各界的关注。加上现在人们已经步入信息时代&#xff0c;所以对于信息的宣传和管理就很关…

[云呐]固定资产盘点报告哪个部门写

固定资产盘点报告通常由哪个部门来完成和签发呢?总体来说,固定资产盘点报告主要由资产管理部门或核算部门具体组织拟定并与财务部门共同签发。个别重大报告还需要上级领导或委员会研讨通过。  资产管理部门:  资产管理部门是直接负责公司固定资产管理工作的核心部门,它主导…

超市销售数据-python数据分析项目

Python数据分析项目-基于Python的销售数据分析项目 文章目录 Python数据分析项目-基于Python的销售数据分析项目项目介绍数据分析结果导出数据查阅 数据分析内容哪些类别比较畅销?哪些商品比较畅销?不同门店的销售额占比哪个时间段是超市的客流高封期?查看源数据类型计算本月…

浅谈iOS开发中的自动引用计数ARC

1.ARC是什么 我们知道&#xff0c;在C语言中&#xff0c;创建对象时必须手动分配和释放适量的内存。然而&#xff0c;在 Swift 中&#xff0c;当不再需要类实例时&#xff0c;ARC 会自动释放这些实例的内存。 Swift 使用 ARC 来跟踪和管理应用程序的内存&#xff0c;其主要是由…

EFPN代码解读

论文 Extended Feature Pyramid Network for Small Object Detection python3 D:/Project/EFPN-detectron2-master/tools/train_net.py --config-file configs/InstanceSegmentation/pointrend_rcnn_R_50_FPN_1x_coco.yaml --num-gpus 1 训练脚本 cfg 中的配置 先获取配置…

JavaWeb 项目运行配置

JavaWeb 项目运行配置

保持ssh断开后,程序不会停止执行

保持ssh断开后&#xff0c;程序不会停止执行 一、前言 笔者做远程部署搞了一阵子&#xff0c;快结项时发现一旦我关闭了ssh连接窗口&#xff0c;远程服务器会自动杀掉我在ssh连接状态下运行的程序。 这怎么行&#xff0c;岂不是想要它一直运行还得要一台电脑一直打开ssh连接咯…

【优选算法专栏】专题十六:BFS解决最短路问题---前言

本专栏内容为&#xff1a;算法学习专栏&#xff0c;分为优选算法专栏&#xff0c;贪心算法专栏&#xff0c;动态规划专栏以及递归&#xff0c;搜索与回溯算法专栏四部分。 通过本专栏的深入学习&#xff0c;你可以了解并掌握算法。 &#x1f493;博主csdn个人主页&#xff1a;小…

【QingHub】企业级应用开发管理

QingHub 企业级应用开发设计器是QingHub Studio的一个核心模块&#xff0c;它可以实现应用搭建、团队管理&#xff0c;共享开发&#xff0c;可以快速接入API接口&#xff0c;复杂功能可以通过自定义脚本快速实现业务逻辑。打通前端开发与后台业务逻辑一体化。通过可视化的方式&…