【数据结构】哈希应用网站首页 技术交流

template<size_t N>
class bitset
{
public:
	bitset()
	{
		_bits.resize(N / 8 + 1, 0);
	}

    //将某个比特位置1
	void set(size_t x)
	{}
    
    //将某个比特位置0
	void reset(size_t x)
	{}

    //检查位图中某个比特位是否为1
    bool test(size_t x)
    {}

private:
	vector<char> _bits;
};

2.2、比特位置1

实现代码：

	void set(size_t x)
	{
		size_t i = x / 8;
		size_t j = x % 8;

		_bits[i] |= (1 << j);
	}

用除法计算 x 映射的位在数组的第 i 个 char 类型内。用取模计算 x 映射的位在第 i 个 char 类型的第 j 个比特位。然后用按位或运算把指定比特位置1。

需要注意的是在进行按位或运算时，使用的是 1 左移 j 位，而不是右移。这是因为在我们人类的主观认识上，数位的排列是下面这样的：

但实际上，在计算机的虚拟层储存逻辑上，数位的保存是这样的：

我们所说的左移与右移，并不是向左移动或者向右移动，而是向高位移动与向低位移动。因此为了找到目标位置，需要使用左移，而不是右移。

2.3、比特位置0

实现代码：

	void reset()
	{
		size_t i = x / 8;
		size_t j = x % 8;

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

用除法计算 x 映射的位在数组的第 i 个 char 类型内。用取模计算 x 映射的位在第 i 个 char 类型的第 j 个比特位。然后用按位非与运算把指定比特位置1。

2.4、检测位图中比特位

实现代码：

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

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

3、位图例题

3.1、找到只出现一次的整数

设置状态：出现 0 次，状态是 00 。出现 1 次，状态是 01 。出现 2 次及以上，状态是 10 。

template<size_t N>
class twobitset
{
public:
	void set(size_t x)
	{
		// 00->01
		if (_bs1.test(x) == false
			&& _bs2.test(x) == false)
		{
			_bs2.set(x);
		}

		// 01->10
		else if (_bs1.test(x) == false
			&& _bs2.test(x) == true)
		{
			_bs1.set(x);
			_bs2.reset(x);
		}

		//10
	}

	void Print()
	{
		for (size_t i = 0; i < N; ++i)
		{
			if (_bs2.test(i))
			{
				cout << i << endl;
			}
		}
	}
public:
	bitset<N> _bs1;
	bitset<N> _bs2;
};

测试结果如下：

3.2、找到两个文件交集

方法一：把其中一个文件的值读取到位图中，再读取另一个文件，判断在不在上面的位图中，在就是交集，取出该值，并把对应位图置0。

方法二：创建两个位图，读取文件1的数据映射到位图1，读取文件2的数据映射到位图2。然后让位图1与位图2按位与。最终结果是交集。

3.3、找到出现次数不超过2次的所有整数

设置状态：出现 0 次，状态是 00 。出现 1 次，状态是 01 。出现 2 次，状态是 10 。出现 3 次及以上，状态是 11 。

实现代码与 3.1 中类似。

二、布隆过滤器

1、布隆过滤器提出

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

用哈希表存储用户记录，缺点：浪费空间。
用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
将哈希与位图结合，即布隆过滤器。

2、布隆过滤器概念

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

布隆过滤器可以降低冲突的概率。一个值映射到一个位置，容易误判，映射到多个位置，就可以降低误判率。

布隆过滤器的优点：

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

布隆过滤器的缺点：

有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)。
不能获取元素本身。
一般情况下不能从布隆过滤器中删除元素。
如果采用计数方式删除，可能会存在计数回绕问题。

3、布隆过滤器实现

3.1、布隆过滤器的插入

向布隆过滤器中插入："baidu"：

向布隆过滤器中插入："tencent"：

实现代码：

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 31;
		}
		return hash;
	}
};

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

struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long 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;
	}
};

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 len = N * _X;

		size_t hash1 = Hash1()(key) % len;
		_bs.set(hash1);

		size_t hash2 = Hash2()(key) % len;
		_bs.set(hash2);

		size_t hash3 = Hash3()(key) % len;
		_bs.set(hash3);
	}
private:
	static const size_t _X = 4; // 布隆过滤器的长度与数据数量的倍数关系
	bitset<N*_X> _bs;  //这样可以有效的减少不同数据间的冲突
};

3.2、布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

实现代码：

bool test(const K& key)
{
	size_t len = N * _X;

	size_t hash1 = Hash1()(key) % len;
	if (!_bs.test(hash1))
		return false;

	size_t hash2 = Hash2()(key) % len;
	if (!_bs.test(hash2))
		return false;

	size_t hash3 = Hash3()(key) % len;
	if (!_bs.test(hash3))
		return false;

	return true;

	//依然存在误判，有可能把不在的判断成在
}

需要注意的是，即使使用了三个哈希函数进行判断，仍然存在误判的可能性。如果判断该数据不存在，则该数据一定不存在。如果判断该数据存在，则该数据有一定的可能性其实不存在。

因此，布隆过滤器只能运用于能够容忍误判的场景，比如视频推送等等。而对于一些不容忍误判的场景下，布隆过滤器也有相应的解决方法：如果判断出数据存在，就到数据库中进行二次确认，依然存在就返回存在，不存在就返回不存在。

哈希函数个数，代表一个值映射几个位，哈希函数越多，误判率越低，但是哈希函数越多，平均占的空间就越大。

3.3、布隆过滤器删除

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

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

缺陷：

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

4、布隆过滤器例题

4.1、找到两个存贮query的文件的交集

使用哈希切分，把一个大文件分割成多个小文件，再让小文件之间取交集：

使用这种方法，因为不是平均切分，可能会出现冲突多，某一个Ai、Bi小文件过大的问题。出现这种问题无非两种情况：

单个文件中，有某个大量重复的query。
单个文件中，有大量不同的query。

可以直接使用一个unordered_set/set，依次读取文件query，插入set中：

如果读取了整个小文件的query，都可以成功插入set，说明是情况一。
如果读取了整个小文件的query，插入过程中出现抛异常，说明是情况二。换成其他哈希函数，再次分割，再求交集。

说明：set插入key，如果已经有了，返回false。如果内存用完了就会抛bad_alloc异常，剩下的都会成功。

4.2、哈希切割

给一个超过100G大小的log file，log中存着IP地址，设计算法找到出现次数最多的IP地址。

依然使用哈希切割的方法：

依次处理每一个小文件，使用unordered_map 或 map 统计ip出现的次数。

如果统计过程中，没有抛异常则正常统计。统计完一个小文件，记录最多的那一个。clear内存，再统计下一个小文件。
如果统计过程中，出现抛异常现象，说明单个文件过大，冲突太多。换成其他哈希函数，再次分割。

建立一个k个数据的小堆，每统计一次，就插入小堆，转换成topK问题，最终可以解决。

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

上一篇
代码随想录算法训练营第五十二天|300.最长...

下一篇
leetcode24. 两两交换链表中的节点(java)...

站长推荐

stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程）
SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权
U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决
【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述

您现在的位置是：首页 >技术交流 >【数据结构】哈希应用网站首页技术交流

【数据结构】哈希应用

一、位图

1、位图概念

2、位图实现

2.1、位图结构

2.2、比特位置1

2.3、比特位置0

2.4、检测位图中比特位

3、位图例题

3.1、找到只出现一次的整数

3.2、找到两个文件交集

3.3、找到出现次数不超过2次的所有整数

二、布隆过滤器

1、布隆过滤器提出

2、布隆过滤器概念

3、布隆过滤器实现

3.1、布隆过滤器的插入

3.2、布隆过滤器的查找

3.3、布隆过滤器删除

4、布隆过滤器例题

4.1、找到两个存贮query的文件的交集

4.2、哈希切割

上一篇 代码随想录算法训练营第五十二天|300.最长...

下一篇 leetcode24. 两两交换链表中的节点(java)...

站长推荐

上一篇
代码随想录算法训练营第五十二天|300.最长...

下一篇
leetcode24. 两两交换链表中的节点(java)...