位图

概念

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

适用场景： 如果我们需要对大量的数据进行处理，判断该数据在不在，比如40亿个整形数据，如果我们用unordered_set来存放这些数据，大约需要占用16G的内存，显然这是不妥的，如果我们选择用一个数据结构，该数据结构可以存放40亿个数据在不在的状态，也就是开42亿个比特位大小的空间（整形数据总共是约42亿个），约500M，这样就可以将数据存下去了。
如下图： （其中1代表在，0代表不在，所以1，2，5，7这几个元素是在的）

原理

补充知识

什么是高地址、低地址？

什么是数据的低位、高位？

小端模式

数据的低位放在低地址空间，数据的高位放在高地址空间

实例讲解

例子1：存放二进制数：1011-0100-1111-0110-1000-1100-0001-0101

注意注意：我们在存放的时候是以一个存储单元为单位来存放，存储单元内部不需要再转变顺序啦！

就例如下面的低位0001-0101存放在0号地址，我们不需要把它变成1010-1000，不需要！！不需要！！

读取数据：注意一定一定是从低地址读起！！！我们知道这是小端存储，所以在读出来的时候会从低位开始放！！！

例子2：存放十六进制数：2AB93584FE1C

十六进制数每一位转化为二进制就是4位：2对应0010，A对应1010，以此类推。所以在存放的时候两个十六进制位就占用一个存储单元

大端模式

数据的高位放在低地址空间，数据的低位放在高地址空间

实例演示：

例子1：存放二进制数：1011-0100-1111-0110-1000-1100-0001-0101

读取数据：注意仍然是从低地址开始读，我们知道这是大端模式，当我们从0号地址读到1011-0100时，我们知道它是高位，所以放到高位的位置上去

例子2：存放十六进制数：2AB93584FE1C

读取数据：注意从低地址开始读取，读到的从高地址开始放！！！

位图原理

位图中的每个数据单元都是一个bit位，这样子平时我们都要话32位4字节来存储数据，而现在我们只需要花1个字节就能”存储数据”，在空间上减少了约32倍的容量。例如40G的数据我们只要花1.3G来存储。但是我们平时操作的数据类型最小就是一个字节，我们不能直接对位进行操作，所以我们可以借助位运算来对数据进行操作。下面我们来看看数据在位图中是如何存储的
我们这里给出一个数组
int arr[] = {1,2,4,5,7,10,11,14,16,17,21,23,24,28,29,31}；则我们只需要花1个字节来存这些数据

解释：我们目前很多的机器都是小端存储，也就是低地址存低位，一个整形数据中，第一个字节用来存储0-7的数字，第二个字节用来存储8-15的数字，第三个字节用来存储16-23的数字，第四个字节用来存储24-31的数字。我们来看看数字10是如何存储的。先通过模上32，取余还是10，然后再将4字节中第10个比特位置为1，则表示该数字出现过。由于我们的机器是小端存储，所以我们的每个比特位都是要从右边开始计算的

所以说我们只需要将对应的比特位置为1即可。但是如果我们要存储的数据很大呢？其实也很简单，我们可以定义一个数组，当做一个位图，如果该数字在0-31之间，我们就存储在0号下标的元素中进行操作，如果在32-63之间，则就在1号下标之间进行操作。计算下标我们可以通过模32来获得下标

实现

整体框架

在实现位图中，我们的成员变量只需要一个数组就可以实现。而这个数组有多我们要开多大呢？数组多开一个整形空间，就能多存32个数字，所以我们可以让用户提供一个准确的数，这个数是一个数据量，也是数的最大范围。我们可以通过该数模上32，就可以获得该数组的大小，但是0~31模上32为0，我们开0个空间那显然不合适，所以我们要开bitCount/32 + 1个空间大小的数组

class bitset
{
public:
	bitset(size_t bitCount)
		:bitCount(bitCount)
	{
		//resize会将vector中的元素初始化为0
		_bitset.resize(bitCount / 32 + 1);
	}
private:
	vector<int> _bitset;
	int bitCount;// 开num比特位的空间
};	

把某位置为1

分为三步：

1. 计算出x对应的数组下标： 先确定这个数应该处在第几个数组中，也就是index=x/32
2. 计算处x在对应数组中的比特位的位置： 通过把x对32取模，得到x在第index个整形的第pos个位置
3. 将计算出来的比特位置为1：操作位，我们可以通过位运算来操作，可以先将1左移pos位后再和整数进行或运算

举例：假设pos=5，数据为10010011

1. 将1进行左移5位==>100000
2. 将数据和第一步计算出来的结果进行或运算----->10010011 | 100000 =10110011，此时我们就将指定位置置位1了

代码实现：

// 每个字节用0和1记录某个数字存在状态
	// 把x所在的数据在位图的那一位变成1
	void set(int x)
	{
		if (x > bitCount) return;

		int index = x / 32;// x是第index个整数
		int pos = x % 32;// x是第index个整数的第pos个位

		_bitset[index] |= (1 << pos);
	}

把某位置为0

分为两步：

1. 找到那一位：和上面的方法一样
2. 把这位设置为0：通过先将1进行左移pos位，然后取反，将结果再和原来数据进行与运算

举例：假设pos=5，数据为10110011

1. 将1进行左移5位后并取反011111
2. 将第一步计算出来的结果和数据进行与运算----->10110011 & 011111 = 10010011，删除成功

代码实现：

// 把x所在的数据在位图的那一位变成0
	void reset(int x)
	{
		if (x > bitCount) return;

		int index = x / 32;// x是第index个整数
		int pos = x % 32;// x是滴index个整数的第pos个位
		_bitset[index] &= ~(1 << pos);
	}

判断某位是否为1

分为两步：

1. 找到那一位： 和上面的方法一样
2. 把这位设置为0：将数组下标为index的整数向右移pos位，然后再和1进行与运算，如果为1则表示存在，否则不存在

举例：pos=5，数据为10110011

1. 将数据进行右移5位00000101
2. 将第一步计算出来的结果和1进行与运算----->00000101 & 1 = 1，此时表示该数字存在，返回true

// 判断x是否存在
	bool test(int x)
	{
		if (x > bitCount) return false;

		int index = x / 32;// x是第index个整数
		int pos = x % 32;// x是滴index个整数的第pos个位

		return _bitset[index] & (1 << pos);
	}

完整代码以及测试

#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入头文件
#include<vector>
#include <string>
#include <new>
#include<algorithm> 
using namespace std; //标准命名空间
class bitset
{
public:
	bitset(size_t bitCount)
		:bitCount(bitCount)
	{
		//resize会将vector中的元素初始化为0
		_bitset.resize(bitCount / 32 + 1);
	}
	// 每个字节用0和1记录某个数字存在状态
	// 把x所在的数据在位图的那一位变成1
	void set(int x)
	{
		if (x > bitCount) return;

		int index = x / 32;// x是第index个整数
		int pos = x % 32;// x是第index个整数的第pos个位

		_bitset[index] |= (1 << pos);
	}
	// 把x所在的数据在位图的那一位变成0
	void reset(int x)
	{
		if (x > bitCount) return;

		int index = x / 32;// x是第index个整数
		int pos = x % 32;// x是滴index个整数的第pos个位
		_bitset[index] &= ~(1 << pos);
	}
	// 判断x是否存在
	bool test(int x)
	{
		if (x > bitCount) return false;

		int index = x / 32;// x是第index个整数
		int pos = x % 32;// x是滴index个整数的第pos个位

		return _bitset[index] & (1 << pos);
	}

private:
	vector<int> _bitset;
	int bitCount;// 开num比特位的空间
};
void TesstBitset1()
{
	bitset bs(100);

	bs.set(99);
	bs.set(0);
	bs.set(98);
	bs.set(55);
	bs.set(75);
	bs.set(35);

	;
	bs.reset(99);
	bs.reset(87);

	for (size_t i = 0; i <= 100; ++i)
	{
		cout << i << ":" << bs.test(i) << " ";
		if (i != 0 && i % 10 == 0)
			cout << endl;
	}
}

int main() {
	TesstBitset1();
	system("pause");
	return EXIT_SUCCESS;
}

运行结果如下：

位图的应用

有以下几个：

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

缺点： 只能处理整形数据

布隆过滤器

引入

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

如何快速查找？

1. 哈希表： 用哈希表存储用户的历史记录。缺点： 空间消耗比较大
2. 位图： 用位图存储用户的历史记录。 缺点： 位图一般只能处理整形，如果内容编号是字符串，就无法处理了。但我们可以使用一些哈希算法把字符串类型转换成整型，比如BKDR哈希算法，但是这里还存在一个问题。字符串的组合方式太多了，一个字符的取值有256种，一个数字只有10种，所以不可避免会出现哈希冲突
3. 布隆过滤器： 将哈希表和位图结合使用。

概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑的、比较巧妙的概率型数据结构，特点是高效地插入和查询

布隆过滤器其实就是位图的一个变形和延申，虽然无法避免哈希冲突，但我们可以想办法降低误判的概率；当一个数据映射到位图中时，布隆过滤器会用多个哈希函数映射到多个比特位，当判断一个数据是否在位图当中时，需要分别根据这些哈希函数计算出对应的比特位，比特位设置了代表着当前状态的默认值，设置为 1 则判定为该数据存在，这一点很类似于我们定义红黑数的节点颜色。

布隆过滤器使用多个哈希函数进行映射，目的就在于降低哈希冲突的概率，一个哈希函数产生冲突的概率可能比较大，但多个哈希函数同时产生冲突的概率可就没那么大了！
举个例子：针对值 “source” 和三个不同的哈希函数分别生成了哈希值 2、4、7

现在，如果我们要查询"source"这个字符串是否存在，就要判断位图中下标2，4，7对应的值是否均为1，若是，则说明此字符串“可能”存在。注意这里就可能出现误判了（下面介绍）

布隆过滤器误判

布隆过滤器是一个大型位图（bit数组或向量） + 多个无偏哈希函数

如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1，例如针对值 “source” 和三个不同的哈希函数分别生成了哈希值 2、4、7，则有下图

现在，如果我们要查询"source"这个字符串是否存在，就要判断位图中下标2，4，7对应的值是否均为1，若是，则说明此字符串“可能”存在。注意这里就可能出现误判了，至于为什么我们先再存一个字符串"create"，假设哈希函数返回3，4，8，则对应的图如下：

• 值得注意的是，4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位，因此它被覆盖了。现在我们如果想查询 “flower” 这个值是否存在，哈希函数返回了 2、5、8三个值，结果我们发现 5 这个 bit 位上的值为 0，说明没有任何一个值映射到这个 bit 位上，因此我们可以很确定地说 “flower” 这个值不存在。而当我们需要查询 “source” 这个值是否存在的话，那么哈希函数必然会返回 2、4、7，然后我们检查发现这三个 bit 位上的值均为 1，那么我们可以说 “source” 存在了么？答案是不可以，只能是 “source” 这个值可能存在（发生了误判）。
• 这是为什么呢？答案很简单，因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值 “taobao” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “taobao” 这个值存在。像上面的字符串source，哈希函数返回的是2，4，7，可是先前的字符串create，哈希函数返回的是3，4，8，你怎么知道比特位4的值对应的是字符串source呢？我说它是字符串create的也没毛病吧，因此“source”可能存在。这就是误判出现的典型现象。

总结：布隆过滤器是无法解决误判的问题的，一个key通过多种哈希函数映射多个比特位只能说是降低误判的概率，但无法去除。

布隆过滤器优缺点

优点：

• 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关

• 哈希函数相互之间没有关系，方便硬件并行运算

• 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

• 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势

• 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

• 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺点：

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

误判控制

• 很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。
• 另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

大佬在权衡过其中的关系后得出了一套比较得当的公式：

k 是哈希函数个数
m 为布隆过滤器长度
n为插入的元素个数
p为误判率

实现

整体框架

这里用到了上一篇博客中的位图实现，其中这里放置了3个哈希函数，用了映射不同的概率。

在这里完整代码bitset.h文件

#pragma once
#include<iostream> //引入头文件
#include<vector>
#include <string>
#include <new>
#include<algorithm> 
using namespace std; //标准命名空间
class bitset
{
public:
	bitset(size_t bitCount)
		:bitCount(bitCount)
	{
		//resize会将vector中的元素初始化为0
		_bitset.resize(bitCount / 32 + 1);
	}
	// 每个字节用0和1记录某个数字存在状态
	// 把x所在的数据在位图的那一位变成1
	void set(int x)
	{
		if (x > bitCount) return;

		int index = x / 32;// x是第index个整数
		int pos = x % 32;// x是第index个整数的第pos个位

		_bitset[index] |= (1 << pos);
	}
	// 把x所在的数据在位图的那一位变成0
	void reset(int x)
	{
		if (x > bitCount) return;

		int index = x / 32;// x是第index个整数
		int pos = x % 32;// x是滴index个整数的第pos个位
		_bitset[index] &= ~(1 << pos);
	}
	// 判断x是否存在
	bool test(int x)
	{
		if (x > bitCount) return false;

		int index = x / 32;// x是第index个整数
		int pos = x % 32;// x是滴index个整数的第pos个位

		return _bitset[index] & (1 << pos);
	}

private:
	vector<int> _bitset;
	int bitCount;// 开num比特位的空间
};

哈希函数个数和布隆过滤器长度的关系：

m = -n*ln(p) / (ln(2)^2)
k = m/n * ln(2)

k 是哈希函数个数
m 为布隆过滤器长度
n为插入的元素个数
p为误判率

其中k=3，整体算下来，m≈4.34n，所以这里我们选择m为5

template<class T = string, class Hash1 = BKDRHash, class Hash2 = SDBHash, class Hash3 = RSHash>
class BloomFilter
{
public:
	// 布隆过滤器的长度 近似等于4.3~5倍插入元素的个数
	// 这里取 5
	BloomFilter(size_t size)
		:_bs(5 * size)
		, _N(5 * size)
	{}
private:
	bitset _bs;
	size_t _N;// 能够映射元素个数 
};

三个字符串哈希函数如下： 用他们作为缺省参数，默认处理字符串类型

// BKDRHash
struct BKDRHash
{
	size_t operator()(const string& str)
	{
		register size_t hash = 0;
		for (size_t i = 0; i < str.length(); ++i)
		{
			hash = hash * 131 + str[i];
		}

		return hash;
	}
};

// SDBHash
struct SDBHash
{
	size_t operator()(const string str)
	{
		register size_t hash = 0;
		for (size_t i = 0; i < str.length(); ++i)
		{
			hash = 65599 * hash + str[i];
			//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;  
		}
		return hash;
	}
};

// RSHash
struct RSHash
{
	size_t operator()(const string str)
	{
		register size_t hash = 0;
		size_t magic = 63689;
		for (size_t i = 0; i < str.length(); ++i)
		{
			hash = hash * magic + str[i];
			magic *= 378551;
		}
		return hash;
	}
};

插入

布隆过滤器的插入就是提供一个Set接口，核心思想就是把插入的元素通过三个哈希函数获取对应的整型并%比特位数从而获得对应的3个映射位置，再把这三个位置置为1即可

步骤

1. 先用不同的哈希函数计算出该数据分别要映射到位图的哪几个位置
2. 然后把位图中的这几个位置设置为1

void set(const T& x)
{
	size_t index1 = Hash1()(x) % _N;
	size_t index2 = Hash2()(x) % _N;
	size_t index3 = Hash3()(x) % _N;

	_bs.set(index1);
	_bs.set(index2);
	_bs.set(index3);
}

查找

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

步骤：

• 先用不同的哈希函数计算出该数据分别要映射到位图的哪几个位置

• 然后判断位图中的这几个位置是否都为1，如果有一个不为1，说明该元素一定不在容器中，否则表示在容器中

注意： 可能会误报，判断在是不准确的，判断不在是准确的。（因为一个数据判断出它是在的，可能是它映射的几个数据可能是其它数据映射导致这几个位置为1的，所以判断结果为在，该结果有误判；而判断一个数据为不在时，那这个数据是一定不在的，因为它映射的几个位置不全为1）

bool IsInBloomFilter(const T& x)
{
	size_t index1 = Hash1()(x) % _N;
	size_t index2 = Hash2()(x) % _N;
	size_t index3 = Hash3()(x) % _N;

	return _bs.test(index1)
		&& _bs.test(index2)
		&& _bs.test(index3);// 可能会误报，判断在是不准确的，判断不在是准确的
}

删除

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

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

一种支持删除的方法（计数法删除）：

• 将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。
• 缺陷：
  1. 无法确认元素是否真正在布隆过滤器中
  2. 存在计数回绕

当然，为什么至今过滤器都没有提供对应的删除接口呢？其实过滤器的本来目的就是为了提高效率和节省空间，但是在确认存在时去遍历文件，文件 IO 和磁盘 IO 的时间开销是不小的，其次在每个比特位增加额外的计数器，更是让空间开销飙升到本身的好几倍。

完整代码以及测试

BloomFilter.cpp文件

#define _CRT_SECURE_NO_WARNINGS
#include"bitset.h"
template<class T>
struct Hash
{
	const T& operator()(const T& key)
	{
		return key;
	}
};
// BKDRHash
struct BKDRHash
{
	size_t operator()(const string& str)
	{
		register size_t hash = 0;
		for (size_t i = 0; i < str.length(); ++i)
		{
			hash = hash * 131 + str[i];
		}

		return hash;
	}
};

// SDBHash
struct SDBHash
{
	size_t operator()(const string str)
	{
		register size_t hash = 0;
		for (size_t i = 0; i < str.length(); ++i)
		{
			hash = 65599 * hash + str[i];
			//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;  
		}
		return hash;
	}
};

// RSHash
struct RSHash
{
	size_t operator()(const string str)
	{
		register size_t hash = 0;
		size_t magic = 63689;
		for (size_t i = 0; i < str.length(); ++i)
		{
			hash = hash * magic + str[i];
			magic *= 378551;
		}
		return hash;
	}
};
template<class T = string, class Hash1 = BKDRHash, class Hash2 = SDBHash, class Hash3 = RSHash>
class BloomFilter
{
public:
	// 布隆过滤器的长度 近似等于4.3~5倍插入元素的个数
	// 这里取 5
	BloomFilter(size_t size)
		:_bs(5 * size)
		, _N(5 * size)
	{}
	void set(const T& x)
	{
		size_t index1 = Hash1()(x) % _N;
		size_t index2 = Hash2()(x) % _N;
		size_t index3 = Hash3()(x) % _N;

		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}
	bool IsInBloomFilter(const T& x)
	{
		size_t index1 = Hash1()(x) % _N;
		size_t index2 = Hash2()(x) % _N;
		size_t index3 = Hash3()(x) % _N;

		return _bs.test(index1)
			&& _bs.test(index2)
			&& _bs.test(index3);// 可能会误报，判断在是不准确的，判断不在是准确的
	}


private:
	bitset _bs;
	size_t _N;// 能够映射元素个数 
};
void TestBloomFilter()
{
	BloomFilter<string> bf(100);

	bf.set("douyin");
	bf.set("kuaishou");
	bf.set("pass cet6");
	bf.set("aabb");


	cout << bf.IsInBloomFilter("pass cet6") << endl;
	cout << bf.IsInBloomFilter("kuaishou") << endl;
	cout << bf.IsInBloomFilter("douyin") << endl;
	cout << bf.IsInBloomFilter("abab") << endl;
}

int main() {
	TestBloomFilter();
	system("pause");
	return EXIT_SUCCESS;
}

布隆过滤器优缺点

优点：

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

缺点：

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

海量数据处理问题

哈希切割

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

a. 先创建1000个小文件A0-A999，然后计算i = hash(IP)%1000，i是多少，IP就进入编号为i的文件中，也就是Ai文件中，这样相同的IP就都进入了同一个文件中。先将一个小文件加载到内存中，依次读取放入unordered_map<string, int> 中，同时用一个pair<string, int> max记录当前出现次数最多的IP，然后不断更新记录当前的max，这样就得到出现次数最多的IP地址
b. 和上面的方法一样，这里用一个大小为K的堆来存储topK的IP

位图应用

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

100亿个整数占用40G的空间，如果直接加载到内存中，空间肯定是不够的，所以我们这里可以考虑用位图来处理。
方案一： 改进位图，用两个比特位表示整数，用其中的三种状态00（没出现）、01（出现一次）和10（出现两次及以上）。消耗内存为：2*4 *(2^32-1)/32 byte≈1G
方案二： 用两个位图同时操作，对应比特位无数据时，两个位图此处设为0，有一个数据时，将两个位图中一个设为0，一个设为1，有两个及以上数据时，两个位图中对于比特位都设置为1。消耗空间和上面那种方法一样，也是1G

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

方案一： 将文件1的整数映射到一个位图中，然后读取文件2中的数据，判断是否在位图中，在就是交集，消耗内存500M
方案二： 将文件1的整数映射到一个位图中， 将文件2的整数映射到另一个位图中，然后将两个位图进行按位与，与之后位图中为1的位就是两个文件的交集

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

方案： 和第一题思路一致，找出状态为00、01和10的即可，其中状态为11代表的是出现3次及以上。消耗内存为1G

布隆过滤器

1.给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

query是一个查询语句的意思，一个query语句的大小平均约为30-60字节100亿个query大约占用300-600G。
方案一（近似算法）： 将文件1的query映射到布隆过滤器中，读取文件2中的query，判断是否在布隆过滤器中，在就是交集，是交集的一定在里面。（缺陷：交集中的数会不准确，因为有些数会误判，混到交集里面，判断在是不准确的，判断不在是准确的）
方案二（精确算法）：
1.把文件1和文件2分别切分成A0、A1…A999和B0、B1…B999，两个文件分别切分成1000个小文件，然后将A0加载到内存放到unordered_set中，再依次和B0、B1…B999这10001个文件进行比较，然后加载A1到内存中，以此类推。用unordered_set的效率还是很高的，基本上是常数次。

2.优化：哈希切分
不再使用平均切分，使用哈希切分，用公式：i = Hash(query)%1000。i是多少就进入编号为i的文件中。不同的query可能会进入编号不同的文件中，但相同的query一定会进入编号相同的文件中。
先将文件Ai加载到内存中，放到unordered_set中，然后读取Bi中query，判断是否在，在就是交集。这里只需要比较1000次，比上面那种方式比较次数少很多。

2.如何扩展BloomFilter使得它支持删除元素的操作

方案： 用几个比特位来表示计数器。缺陷：给的为如果少了，容易导致计数溢出，如果位数多了，那么空间开销就会很多，是以牺牲布隆过滤器的优势为代价的。

本栏目推荐文章
• Jmeter 如何连接mysql数据库？
• SQL Server 检测是不是数字型数据的两种方法
• 微信小程序 wxs的概念
• 如何通过Navicat把MySQL远程数据库导入到本地数据库
• 和利时MACS6通过dat文件实现任意时间范围与测点的历史数据提取与科研分析
• 深入理解spring框架：剖析多线程模式下数据库连接
• 数据可视化是如何帮助大型企业提高效率的？
• redis 数据库
• openpyxl模块--------------------------------重复数据
• Django客户端应用1向服务端应用2发送POST请求并接收解析数据

位图 数据处理 过滤器 海量 概念位图 数据处理 过滤器 海量 位图 过滤器 原理 位图 数据结构 算法 结构 数据 一致性 海量 数据库 复杂度 海量 时间 数据 海量 数据查询 数据1000 海量clickhouse数据 问题 数据 数据挖掘 海量 模式 海量logstash动态 数据 指数 数据 数据分析 海量