位图

每一个比特位来表示当前比特位对应的数据是否存在，存在为1，不存在为0

整数数组：

整数位置：n/32
整数位置中具体的bit位置：n%32

右移相当于除，右移n位 == 数字➗2^n^

位图实现：哈希表

实现：整数数组
数据单元是bit位
节省空间，一个字节可以存放8个整数的二值信息（存在与否），不存放数据本身
操作效率高，通过哈希映射获取位置，通过位运算执行操作，时间效率O(1)
位置映射：
1. 获取整数位置，n / 32
2. 获取整数的比特位：n % 32
位图需要的空间大小和数据的范围有关，和数据本身大小没有关系
适合的场景：数据不重复，信息简单

class BitMap
{
public:
	BitMap(size_t range)
	{
		_bit.resize(range / 32 + 1);
	}
	//查询: Test
	bool Test(size_t n)
	{
		//整数位置
		int idx = n >> 5;//等价于n/32
		int bitIdx = n % 32;
		//获取对应二进制值
		if ((_bit[idx] >> bitIdx) & 1)
			return true;
		else
			return false;
	}
	//存储: Set
	void Set(size_t n)
	{
		int idx = n / 32;
		int bitIdx = n % 32;

		_bit[idx] |= (1 << bitIdx);
	}
	//删除: Reset
	void Reset(size_t n)
	{
		int idx = n >> 5;
		int bitIdx = n % 32;

		_bit[idx] &= ~(1 << bitIdx);
	}
private:
	vector<int> _bit;
};

布隆过滤器

多个位置映射来记录数据是否存在，不能直接支持删除操作，可以通过将每个比特为扩展为一个整形，作为数据的计数器，添加元素加一，删除减一，但会多占用几倍的存储空间，并且其仍不能保证某个数据一定存在，同时该方式存在计数回绕

m：布隆过滤器的长度，n：插入元素个数，p：误报率

$m=-\frac {nlnp}{(ln2)^2}$

k：哈希函数个数

$k=\frac mnln 2$

缺陷：

有误判率，即存在假阳性，即不能准确判断元素是否在集合中(补救方法：再建立一个白

名单，存储可能会误判的数据)

不能获取元素本身
一般情况下不能从布隆过滤器中删除元素
如果采用计数方式删除，可能会存在计数回绕问题

优点:

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

struct strToint1
{};
struct strToint2
{};
struct strToint3
{};
template<class T, class HF1, class HF2, class HF3>
class BloomFilter
{
public:
	//bit位数量 = hash函数个数 * 数据量 / ln2
	BloomFilter(size_t num)
		: _bit(5 * num)
		, _bitCount(5 * num)
	{ }
	void Set(const T& value)
	{
		HF1 hf1;
		HF2 hf2;
		HF3 hf3;

		size_t hashCode1 = hf1(value);
		size_t hashCode2 = hf2(value);
		size_t hashCode3 = hf3(value);

		_bit.Set(hashCode1 % _bitCount);
		_bit.Set(hashCode2 % _bitCount);
		_bit.Set(hashCode3 % _bitCount);
	}
	bool Test(const T& value)
	{
		HF1 hf1;
		size_t hashCode1 = hf1(value);
		if (!_bit.Test(hashCode1 % _bitCount))
			return false;

		HF2 hf2;
		size_t hashCode2 = hf2(value);
		if (!_bit.Test(hashCode2 % _bitCount))
			return false;

		HF3 hf3;
		size_t hashCode3 = hf3(value);
		if (!_bit.Test(hashCode3 % _bitCount))
			return false;

		return true;
	}
private:
	BitMap _bit;
	size_t _bitCount;
};

对于大数据的处理

常规的思路对于海量的数据来说，要么过于耗费时间，要么空间占用过高，而哈希思想可以在大数据中发挥很好的作用。

比如：给定100亿个整数，想要找到其中只出现一次的整数

此时即可以应用位图来操作，使用两个比特为来表示一个数据：

00：数据不存在；

01：出现过一次；

10：出现过多次；

将数据映射到位图中，如果对应位置的比特位为00，则将其改为01；如果对应位置为01，则将其改写为10，如果对应位置为10，则不做操作。

全部映射完成后，每两个比特位进行统计，找到对应比特位为01的那个数据即可

假如要找到出现次数不超过两次的数据，则只需扩充10：出现过两次；11：出现过多次，映射完成之后统计10与01所对应的数据即可

有两个分别有100亿个整数的文件，设法找到两个文件的交集

同样应用位图来处理，分别使用两个位图，将两个文件映射到其中去，然后两个位图进行按位与，统计结果中位图为1的比特位即为两个文件的交集

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

哈希切割，将文件拆分成多个文件
将IP地址转化成整数，并模文件份数，将对应的IP放在对应的文件中
采用unordered_map统计每个文件中IP的出现次数，找到最多即可
topK问题则是在哈希切割之后，采用小堆，其节点为键值对，同时需要一个仿函数类来实现大于比较，先用K个元素建堆，之后遍历所有元素，如果次数小于堆顶元素，不做任何操作，如果大于堆顶元素，删除堆顶元素并插入该元素，遍历完之后，堆内的元素即为topK

综上所述，位图、布隆过滤器对于大数据的处理是极为合适的，只需要找到对应的处理办法，它（哈希）可以以比传统方法更高效的完成需求

小赵的学习笔记

位图、布隆过滤器与大数据处理

位图

布隆过滤器

对于大数据的处理