哈希应用全解

小灵蛇

发布于 2024-06-06 21:35:05

1020

发布于 2024-06-06 21:35:05

文章被收录于专栏：文章部

一. 位图

1.1 概念

所谓位图(bitset)，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

例如：给你40亿个不重复的无符号整数，没有排过序，给你一个无符号整数，如何快速判断这个树在不在这40亿个数之中？

第一眼看是不是人都傻了，40亿个整数，相当于16G的内存，如果我们将他放到一个数组中，这个数组的长度就爆炸了，而且内存也开不了这么大的空间。那怎么办呢？

我们放在数组中是以一个整型的形式存储的，那我们是不是可以缩小一下用一个bite位来看呢，是不是这个内存占用就减小了8倍，是不是大大节约了空间。

这就是我们位图的基本思想，那好我们就用每一个bite位的状态(0或者1)来显示在不在。

1.2 bitset使用

根据上面的分析，可以看出我们位图有着三个基本的实现。

将一个bite位的状态变为1。
将一个bite位的状态变为0。
检查这个数所在的位置状态是不是1，为1就返回true。

set(size_t pos);//将pos数所映射的bit位标记为1

reset(size_t pos);//将pos数所映射的bit标记回0

test(size_t pos);//检测pos数所映射的bit为是否为1，为1则返回true

1.3 实现

我们这里用vector<int>来实现位图这个结构，为什么要用int呢？因为我们是用32位bite位为一个单位，刚好是一个整形，所以就用int，也可以用char。

那么如果有N个数，首先对vector进行开空间，我们这里要开N/32+1个整型空间，并把每个位置的初始值给0，为什么要多开一个呢？因为不能保证N一定是32的倍数，可能会多余几个数，所以多开32个bite位，即+1。而且即使浪费也只多浪费一个整型。

set函数：将某个数字对应的位置的状态变为1。具体操作是：首先看这个数是位于第几个空间(一个空间32个bite位)-》x/32，再看这个数在这个空间的那个位置-》x%32，那么让这个位置的状态变为1，可以用到或(|)运算。
reset函数：将某个数字对应的位置的状态变为0。具体操作是：还是先找到位于哪个空间的哪个位置，然后用与(&)运算。
test函数：检测某个数的状态是否为1。具体操作是：找到这个数的位置，然后用这个位置的状态与运算1。

//把x映射的位置标记成1
void set(size_t x)
{
	assert(x <= N);
	size_t i = x / 32;
	size_t j = x % 32;
	_bits[i] |= (1 << j);//此处左移是向高位移的意思，不是普通意义上想左移
	//此处是以一个整型为单位
}

//把x映射的位置标记成0
void reset(size_t x)
{
	assert(x <= N);
	size_t i = x / 32;
	size_t j = x % 32;
	_bits[i] &= ~(1 << j);
}

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

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

需要注意的是：我们这里不论是&还是|，都是对于同一bite位上的数来运算。因此要用到移位操作符(<<)，这里左移指的是向高位移动，并不是书面上的向左移。

对于set来说：

对于reset来说：

对于test来说：

1.4 位图的应用

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

二. 布隆过滤器

2.1 布隆过滤器的提出

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

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

2.2 概念

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

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位就为1。

2.3 布隆过滤器基本结构定义

布隆过滤器用到了位图的三个函数。

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
{
private:
	static const size_t M = 5 * N;
	std::bitset<M>* _bs=new std::bitset<M>;
};

2.4 插入

void set(const K& key)
{
	size_t hash1 = Hash1()(key) % M;//匿名对象调用
	size_t hash2 = Hash2()(key) % M;
	size_t hash3 = Hash3()(key) % M;

	_bs->set(hash1);
	_bs->set(hash2);
	_bs->set(hash3);
}

用哈希函数算出对应映射的位置，将位置的状态变为1即可。

2.5 查找

bool Test(const K& key)
{
	size_t hash1= Hash1()(key) % M;
	if (_bs->test(hash1) == false)
	{
		return false;
	}

	size_t hash2 = Hash2()(key) % M;
	if (_bs->test(hash2) == false)
	{
		return false;
	}

	size_t hash3 = Hash3()(key) % M;
	if (_bs->test(hash3) == false)
	{
		return false;
	}
	return true;
}

分别计算每个哈希值对应的比特位置存储的是否为0，只要有一个为0，代表该元素一定不在哈希表中，否则可能在哈希表中。

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。