哈希思想应用【C++】(位图，布隆过滤器，海量数据处理面试题)

一，位图

1. 位图概念

2.实现

3. 测试题

位图的优缺点

二，布隆过滤器

1). 布隆过滤器提出

2). 概念

3). 布隆过滤器的查找

4). 布隆过滤器删除(了解)

5). 布隆过滤器优点

6). 布隆过滤器缺陷

三，海量数据面试题

1）哈希切割

一，位图

我们首先由一道面试题来理解位图

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在

这40亿个数中。【腾讯】

1. 遍历，时间复杂度O(N)

2. 排序(O(NlogN))，利用二分查找: logN

3. 位图解决：

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0

代表不存在。比如：

40亿无符号整形，我们知道1G大概是10亿个字节，也就是说起码 16G数据，排序，二分查找都需要在内存下进行，16G的内存性价比着实有些低。而我们使用位图的方法，用40亿个比特位来表示这40亿个数是否存在，大概就是要消耗 512MB(40亿bit == 5亿字节 == 512MB)的内存。

注意：

1. 位图概念

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

2.实现

#include <iostream>
#include <vector>
using namespace std;

template < size_t N>
class bitset
{
public:
	bitset()
	{
		_bit.resize(N / 8 + 1, 0); // + 1防止有越界
	}

	// 映射的比特位设置为1
	void set(size_t x)
	{
		size_t spa_bit = x / 8;
		size_t in_bit = x % 8;

		_bit[spa_bit] &= (1 << in_bit);
	}

    // 映射的比特位设置为0
	void reset(size_t x)
	{
		size_t spa_bit = x / 8;
		size_t in_bit = x % 8;
	}

    // 测试x,是否存在
	bool test(size_t x)
	{
		size_t spa_bit = x / 8;
		size_t in_bit = x % 8;
		return _bit[spa_bit] & (1 << in_bit);
		// 返回0: 则不存在
		// 返回一个很大的数：存在
	}

private:
	vector<char> _bit;
};

测试案例：

再回到题目，我们知道有40亿个数，我们知道这只是数量，不是范围，所以，我们尽量开到无符号的最大值，在开大小的时候我们可以这么来设置：

bitset<-1> st 或者 bitset<0xffffffff> st;

3. 测试题

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

思路：用两个位图存储，用 00, 01, 10表示0次，1次，两次及两次这三种情况。

位图一储存第一位

位图二储存第二位

template <size_t N>
class two_set
{
public:
	void set(size_t x)
	{
		if (st1.test(x) == false
			&& st2.test(x) == false)
		{// 00 -> 01 情况
			st2.set(x);
		}
		else if (st1.test(x) == false
			&& st2.test(x) == true)
		{// 01 -> 10 情况
			st1.set(x);
			st2.reset(x);
		}
	}
private:
	// 我们用 01，00，10 表示三种情况
	bitset<N> st1; // 记录第一位 
	bitset<N> st2; // 记录第二位
};

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

方法一：

两个文件用两个位图存储，然后依次比较两个位图之间，42亿次数据即可。

template <size_t N>
class cross_set
{
public:
	void set1(size_t x)
	{
		st1.set(x);
	}

	void set2(size_t x)
	{
		st2.set(x);
	}

	void test()
	{
		for (size_t i = 0; i < N; i++)
		{
			if (st1.test(i) && st2.test(i))
				cout << i << " ";
		}
	}

private:
	bitset<N> st1;
	bitset<N> st2;
};

方法二：

用一个位图存储一个文件的整数，然后用第二个文件的数据来查找位图，如果位图中存在则是交集，同时查找完了的设置为0即可防止重复输出交集。

class cross_set2
{
public:
	void set(size_t x )
	{
		st.set(x);
	}

	void test(size_t x)
	{
		if (st.test(x))
		{
			cout << x << " ";
			st.reset(x); //第一次检测完后设置为0
		}
	}
private:
	bitset<N> st;
};

3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

思想：还是用2个位图，用 00 , 01, 10, 11 表示这四种状态，跟第1题类似。

位图的优缺点

优点：速度快，节省空间。

缺点：只映射整型，像浮点数，string等类不能作为存储，进行映射。

二，布隆过滤器

1). 布隆过滤器提出

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

1. 用哈希表存储用户记录，缺点：浪费空间

2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。

3. 将哈希与位图结合，即布隆过滤器。

2). 概念

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

哈希的详细知识点，请查看本篇文章：详解布隆过滤器的原理，使用场景和注意事项 - 知乎 (zhihu.com)

上面博客里面的这张图也展示其中效率与哈希函数个数的关系：

使用布隆过滤器，优点之一是节省空间。虽然哈希函数个数越多，冲突的概率越低；但占用的平均内存也会提高

然后就是当我们的哈希函数为3时，过滤器的长度与插入个数的关系。（K是哈希函数个数，m是长度，n是插入个数）

根据里面提供的关系可以得出，布隆过滤器长度应是插入个数的 5 倍

3). 布隆过滤器的查找

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

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

比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

4). 布隆过滤器删除(了解)

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

比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

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

缺陷：

1. 无法确认元素是否真正在布隆过滤器中

2. 存在计数回绕

关于哈希函数的选择，我们参考这篇大佬hash函数算法博客的推荐：各种字符串Hash函数 - clq - 博客园 (cnblogs.com)

// 三个哈希函数

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

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

struct DJBHash
{
	size_t operator()(const string& str)
	{
		if (!str[0])   // 这是由本人添加，以保证空字符串返回哈希值0  
			return 0;
		size_t hash = 5381;
		for (auto e : str)
		{
			size_t ch = size_t(e);
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

template <size_t N, class K = string,
class Hash1 = BKDRHash,
class Hash2 = APHash,
class Hash3 = DJBHash>
class bloom_set
{
public:
	// 插入
	void set(const string&  str)
	{
		Hash1 hash1;
		size_t len = N * time;
		st.set(hash1(str) % len);

		Hash2 hash2;
		st.set(hash2(str) % len);

		Hash3 hash3;
		st.set(hash3(str) % len);
	}

	// 判断是否存在
	// 1. 如果其中一个不存在，那么一定不存在
	// 2. 如果三位置都存在，那么可能存在，需要确认
	bool test(const string& str)
	{
		Hash1 hash1;
		Hash2 hash2;
		Hash3 hash3;
		size_t len = N * time;
		if (!st.test(hash1(str) % len))
			return false;

		if (!st.test(hash2(str) % len))
			return false;

		if (!st.test(hash3(str) % len))
			return false;

		return true; // 都存在，那可能存在
	}
private:

	static const size_t time = 5;  // 过滤器长度与插入个数关系
	bitset < N * time > st;
};