哈希图的应用

位图

位图的概念

首先我们根据一个面试题来进入位图的理解 1. 面试题 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

大家思考一下，如果按照我们以往的思维，用直接遍历的方法来进行判断的话，40亿个整数，一共160亿个字节，需要的内存太大了，不符合实际，时间复杂度也很高。可能又会有人说，用二分法，但是这样的时间复杂度依然很高，所以就有了用位图解决的方法！

这个题目只需要判断这40亿个数字在或者不在，所以我们仔细想一想，只需要用标记就可以，用0和1标记即可，位图的概念就引出了： 数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

本来一个数字需要4个字节来存储，但是用位图的话，一个数字就用一个字节的一个比特位来标记即可就比原先的遍历的方法所需的空间缩小了32倍！

比如： 我想要标记这些数字在不在，就将这些数字从左至右分别放入一个字节char内，但是char内部八个比特位的空间的编号时从右至左的！

就比如说： 画出这个图大家就应该理解了

那么位图如何实现呢？

位图的实现

我们构造一个位图的类bitset N是你的数字的个数，N/32后就是你需要的几个整形的空间，记得+1 然后在构造函数中将每个比特位置为0 i对应的是第几个整形空间的位置 j对应的是第i个整形空间的第j个位置 整形一共有32个字节 每个整形的最右边为第一个位置，编号为0 最左边为最后一个位置编号为31

template<size_t N>
class bitset
{
public:
	bitset()
	{
		_bits.resize(N / 32 + 1, 0);
	}
	//将位图中的各个比特位进行标记
	void set(size_t x)
	{
		int i = x / 32;
		int j = x % 32;
		_bit[i] |= (1 << j);
	}
	//将位图中对应x的比特位置零
	void reset(size_t x)
	{
		int i = x / 32;
		int j = x % 32;
		_bit[i] &= ~(1 << j);
	}
	//判断
	bool test(size_t x)
	{
		int i = x / 32;
		int j = x % 32;
		return _bits[i] & (1 << j);
	}

private:
	vector<int> _bits;
};

如果要标记某个位置，就将第i个位置的整形往或上1往左边移动j位后的结果（1和0或1都为1）

如果要删除某个位置，就要将它置零，所以第i个位置的整形与上1往左边移动j位后取反的结果， 1往做移动j位后取反，就只有第j位为0，其他位置都为1，与上第i个位置，第j个位置无论是0还是1都会置为0，其他位置是0就变为0，是1还是1

判断某个数是否存在就要看这个比特位是否为1，所以第i个位置的整形与上1往左边移动j位后的结果，第j位是0就是0，是1就是1，返回bool值即可

放一张图会更加清晰:

位图的应用

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

位图速度快，而且节省空间但是我们可以发现，位图他只能解决整形的问题，如果遇上string呢，就没有办法了，所以就有了下面的这种方法：

布隆式过滤器

布隆式过滤器的提出

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

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

布隆式过滤器的概念

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

就是说一个数据，可以通过多个哈希函数对应多个位置

布隆过滤器的查找

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

所以可以按照以下方式进行查找：

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

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

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

所以说布隆过滤器是存在误判率的！

那么如何降低误判率呢？ 我们可以更多的哈希函数来进行存储计算，越多误判率越低，但是平均空间就越大

布隆过滤器的删除

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

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

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

但是也有不小的缺陷：

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

布隆过滤器的优点

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

布隆过滤器的缺点

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

海量数据题

哈希切割

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

这个题目我们就用一个哈希函数进行切割，将这个100g的log file分成若干个小的文件，然后再对依次对这些小文件进行处理，使用map统计每个小文件里每个ip出现的次数，然后提取出每个map中的出现次数最多的ip，和其他小文件的出现次数最多的比较，选出最大的一个ip 但是如果统计中抛出内存异常的话就是单个小文件过大，还需要换一个哈希函数进行更加仔细的切分

例如：i=hashfunc（ip）%100 ip进入依次第i个小文件里 相同的ip一定是进入相同的小文件！

位图应用

1. 给定100亿个整数，设计算法找到只出现一次的整数？ 将位图每两个比特位进行标记，如果没有出现过一次就是00，出现过一次就是01，出现过一次以上就是10，然后判断每两个比特位的情况，如果第二位的值为1就是只出现过一次的整数
2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？ 将其中一个文件1的整数映射到一个位图中,读取另一个文件2中的整数,然后两个位图进行逻辑与，如果比特位为1的就是文件的交集
3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整 数 和第一题一样，不过没出现是00，出现一次是01，出现两次是10，出现两次以上就是11

布隆过滤器

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出 精确算法和近似算法 将文件1进行哈希切割，将每条query按照切割结果放到对应的文件中。 对文件2中的query进行转化处理，看能落哪个文件中，然后在该文件中检查该query是否出现过，如果出现过，则是交集，否则不是交集，对文件2中的每条query进行该种操作，最终就可以找到交集。

好了，今天的分享到这里就结束了，感谢大家的支持！