【C++】哈希的应用

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储。比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。数据是否在给定的整形数据中，结果是在或者不在，刚好是两

2401_88238436

909人浏览 · 2025-10-26 10:15:33

2401_88238436 · 2025-10-26 10:15:33 发布

位图

Q:给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在
这40亿个数中。
1.遍历，时间复杂度O(N)
2. 排序(O(NlogN))，利用二分查找: logN
3. 位图解决
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。
概念：位图就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常用来判断某个数据存不存在。
应用：

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

#include <vector>
namespace Q
{
	//非类型模板参数
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_a.resize(N / 32 + 1);
		}
		//x映射的位置标记成1
		void set(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			_a[i] |= (1 << j);
		}
		//x映射的位置标记成0
		void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			_a[i] &= (~(1 << j));
		}
		bool test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

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

	template<size_t N>
	class twobitset
	{
	public:
		void set(size_t x)
		{
			//00->01
			if (!_bs1.test(x) && !_bs2.test(x))
			{
				_bs1.set(x);
			}//01->10
			else if (!_bs1.test(x) && _bs2.test(x))
			{
				_bs1.set(x);
				_bs2.reset(x);
			}
		}
		bool is_once(size_t x)
		{
			return !_bs1.test(x) && _bs2.test(x);
		}
		//01 1次  
		//10 2次
		//11 2次以上
	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};
}

#include <iostream>
using namespace std;
#include "BitSet.h"
int main()
{
	/*Q::bitset<1000> bs;
	bs.set(1);
	bs.set(10);
	bs.set(100);

	cout << bs.test(1) << endl;
	cout << bs.test(10) << endl;
	cout << bs.test(100) << endl;
	cout << bs.test(999) << endl<<endl;

	bs.set(999);
	bs.reset(10);

	cout << bs.test(1) << endl;
	cout << bs.test(10) << endl;
	cout << bs.test(100) << endl;
	cout << bs.test(999) << endl << endl;

    getchar();*/

	int a[] = { 1,2,3,3,4,4,4,4,4,2,3,6,3,1,5,5,8,9 };
	Q::twobitset<10> tbs;
	for (auto e : a)
	{
		tbs.set(e);
	}
	for (auto e : a)
	{
		if (tbs.is_once(e))
		{
			cout << e << " ";
		}
	}
	return 0;
}

int main()
{
	int a1[] = { 1,2,3,3,4,4,4,4,4,2,3,6,3,1,5,5,8,9 };
	int a2[] = { 8,4,8,4,1,1,1,1 };

	Q::bitset<10> bs1;
	Q::bitset<10> bs2;

	//去重
	for (auto e : a1)
	{
		bs1.set(e);
	}
	for (auto e : a2)
	{
		bs2.set(e);
	}
	for (int i = 0; i < 10; i++)
	{
		if (bs1.test(i) && bs2.test(i))
		{
			cout << i << " ";
		}
	}
	cout << endl;
}

位图的应用：

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

布隆过滤器

我们在使用新闻客户端看新闻时，它会给我们推荐新的内容，每次推荐时要去重，去掉
那些已经看过的内容。那么新闻客户端推荐系统如何实现推送去重的？
 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那
些已经存在的记录。 如何快速查找呢？

1.用哈希表存储用户记录，缺点：浪费空间
2.用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
3.将哈希与位图结合，即布隆过滤器。
概念：
布隆过滤器是一种紧凑型的，比较巧妙的数据结构，特点是高效的插入和查询，可用来得知“某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此方法不仅可以提升查询效率，也可以节省大量的内存空间。
在这里插入图片描述

//BloomFilter.h
#pragma once
#include <bitset>
#include <string>
struct BKDRHash
{
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (auto ch : str)
		{
			hash = hash * 131 + ch;
		}
		return hash;
	}
};

struct APHash
{
    size_t operator()(const string& str)
    {
        size_t hash = 0;
        for (size_t i = 0; i < str.size(); i++)
        {
            size_t ch = str[i];
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
            }
        }

        //cout << "APHash:" << hash << endl;
        return hash;
    }
};

struct DJBHash
{
    size_t operator()(const string& str)
    {
        size_t hash = 5381;
        for (auto ch : str)
        {
            hash += (hash << 5) + ch;
        }

        //cout << "DJBHash:" << hash << endl;
        return hash;
    }
};

template<size_t N,class K=string,class Hash1= BKDRHash,class Hash2 = APHash,class Hash3 = DJBHash>
class BloomFilter
{
public:
    void Set(const K& key)
    {
        size_t hash1 = Hash1()(key) % N;
        _bs.set(hash1);
        size_t hash2 = Hash2()(key) % N;
        _bs.set(hash2);
        size_t hash3 = Hash3()(key) % N;
        _bs.set(hash3);
    }
    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;
    }
private:
    bitset<N> _bs;
};

//test.cpp
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
#include "BloomFilter.h"
void TestBloomFilter()
{
	BloomFilter<15> bf;
	bf.Set("孙悟空");
	bf.Set("猪八戒");
	bf.Set("牛魔王");
	bf.Set("二郎神");

	cout<<bf.Test("孙悟空") << endl;
	cout<<bf.Test("猪八戒") << endl;
	cout<<bf.Test("沙悟净") << endl;
}
void TestBloomFilter2()
{
	srand(time(0));
	const size_t N = 100000;
	BloomFilter<N*8> bf;
	std::vector<std::string> v1;
	//std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
	std::string url = "猪八戒";

	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 = "zhihu.com";
		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;
}
int main()
{
	TestBloomFilter2();
	return 0;
}

布隆过滤器的查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可
能存在，因为有些哈希函数存在一定的误判
布隆过滤器删除
布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储
空间的代价来增加删除操作。
缺陷：

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

布隆过滤器优点
1.增加和查询元素的时间复杂度为：O(K),(k为哈希函数的个数，一般比较小)，与数据量大小无关。
2.哈希函数之间没有关系，方便硬件并行运算。
3.布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势。
4.在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势。
3. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能。
4. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算。
布隆过滤器缺陷
1.有误判率，存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再
建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身。
3. 一般情况下不能从布隆过滤器中删除元素。
4. 如果采用计数方式删除，可能会存在计数回绕问题。

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

在这里插入图片描述

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

零信任时代，802.1X 准入架构是否已成“明日黄花”？

2048 AI社区

第7篇_为什么PLCBroker会有延迟_从TCP_Write一帧一写到批量粘包写出

这一篇讲真实性能优化。早期 PLC Broker 在高频小消息场景下出现 1~3 秒尾部延迟，根因不是 QoS2、Retain 或订阅匹配，而是一次 TCP_Write 只写一帧。优化方向是批量编码多个 MQTT 帧，并在一次 TCP 写出中发送。

2048 AI社区

Windows 版 Open Claw 一键安装：3 分钟部署，1 句话让 AI 干完一天活

2048 AI社区

所有评论(0)

查看更多评论

2401_88238436

@2401_88238436

已为社区贡献3条内容

【C++】哈希的应用

2401_88238436

位图

布隆过滤器

所有评论(0)

温馨提示：您尚未绑定手机号

2401_88238436