1.位图

1.1 相关面试题

• 给40亿个不重复的无符号整数，没排过序。给⼀个无符号整数，如何快速判断⼀个数是否在这40亿个数中。
  1. 1G=1024MB=1024*1024KB=1024*1024*1024Byte约等于10亿多Byte
  2. 使用一个二进制比特位来表示数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在 ----》 位图

1.2 位图的设计及实现

• 数据存到vector<int>中，相当于每个int值映射对应的32个值，比如第⼀个整型映射0-31对应的位，第二个整型映射32-63对应的位，后面的以此类推，那么来了⼀个整形值 x，i=x/32；j=x%32；计算出x映射的值在vector的第i个整形数据的第j位

namespace ssp
{
	//N是需要多少比特位
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			// 1个int有32位（2的5次方），要存N个，所以除以32位需要的个数，
			// 又因为除是向下取整所以+1
			_bits.resize((N >> 5) + 1, 0);
		}

		// 把x映射的位标为1
		void set(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			_bits[i] |= (1 << j);	//置1
		}

		// 把x映射的位标为0
		void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			_bits[i] &= ~(1 << j);	//置0，不能影响其他值
		}
			
		bool test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			return _bits[i] & (1 << j);
		}
		
	private:
		vector<int> _bits;
	};
}

1.3 C++库中的位图

• 和上面的使用差不多
• 如to_string将位图按位转成01字符串
  

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

int main() {
	// 1. 默认构造：创建一个16位的位图，所有位初始为0
	bitset<16> b1;

	// 2. 用整数初始化：将整数0xFFFF（二进制全1）填充到16位
	bitset<16> b2(0xFFFF);

	// 3. 用字符串初始化：字符串"101010"对应位图的低位到高位
	bitset<16> b3(string("101010"));

	cout << "b1: " << b1 << endl; // 0000000000000000
	cout << "b2: " << b2 << endl; // 1111111111111111
	cout << "b3: " << b3 << endl; // 0000000000101010
	
	bitset<8> b;
	
	b.set(1);    // 将第1位设为1 → 00000010
	b.set();     // 将所有位设为1 → 11111111

	b.reset(1);  // 将第1位设为0 → 11111101
	b.reset();   // 将所有位设为0 → 00000000
	
	bool bit3 = b.test(3); // 检查第3位是否为1
	//若该位是 1 则返回 `true`，若为 0 则返回 `false`
	
	return 0;
}

1.4 位图的优缺点

• 优点：增删查改块，节省空间
• 缺点：只适用于整型

1.5 位图相关考察题目

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

• 按范围开空间，所以开2^32个位，和前面题目一样

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

• 把数据读出来，分别放到两个位图中，一次遍历，同时在两个位图存在的值就是交集

1.5.3 一个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数

• 还是用位图，不过用两个位标记，使用双位图（一个位图标识第一位，另一个位图标识第二位）
• 00表示出现0次，01表示出现1次，10表示出现2次，11表示出现2次以上，最后统计出所有01和10标记的值即可

2.布隆过滤器

2.1 什么是布隆过滤器

• 布隆过滤器的思路是把key先映射成哈希整型值，再映射一个位，如果只映射一个位的话，冲突率会比较高，所以可以通过多个哈希函数映射多个位，降低冲突率
• 存储的不是值，而是标记映射的位
• 判断一个值key在是不准确的，判断一个值key不在是准确的
  

2.2 布隆过滤器误判率

• m：布隆过滤器的bit长度
• n：布隆过滤器的元素个数
• k：哈希函数的个数
• 布隆过滤器的误判率：
  $$\boxed{f(k)={\left(1-e^{-\frac{kn}{m}}\right)}^k}$$
• 在哈希函数个数一定的情况下，当布隆过滤器的元素个数增加时，误判率增加；布隆过滤器的bit长度增加时，误判率减少

2.3 布隆过滤器代码实现思路

• 通过多个哈希函数对字符串计算出不同的哈希值，然后用一张大位图，将这些哈希值对应的位置标记为 1。
• 判断元素是否存在时，同样用这些哈希函数算出位置，去位图里检查：只要有一个位置是 0，就说明该元素一定不存在；如果所有位置都为 1，则说明元素可能存在

2.4 布隆过滤器删除问题

• 默认不支持删除，标记为1，当它删除时其他映射到该位置的字符串也会查找不到
• 解决方案：可以考虑计数标记方式支持删除，一个位置用多个位标记（双位图，多位图），删除时减少计数就行
  • 问题：删除一个不在布隆过滤器的值时，减少映射位计数会影响已存在的值
  • 改进：定期重建⼀ 下布隆过滤器

2.5 布隆过滤器优缺点

• 优点：效率高，节省空间；相比位图，可以适用于各种类型的标记过滤
• 缺点：存在误判（在是不准确的，不在是准确的），不好支持删除

3.海量数据处理问题

3.1 10亿个证书里面求最大的前100个

• 用堆解决（topk问题）

3.2 上面位图相关题目

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

• 方案1：布隆过滤器
  • 把一个文件的query放进布隆过滤器，另一个文件一次查找，在的就是交集
  • 问题：
    • 找到的交集不够准确，因为在的值可能是误判的
• 方案2：哈希切分
  • 把文件切分成小文件，再放进内存处理
  • 利用哈希切分，一次读取文件中qvery，i=HashFunc(query)%N,N为准备切分成多少小文件。这样A和B中相同的query算出的 hash值i是⼀样的，相同的query就进入的编号相同的小文件就可以编号相同的⽂件直接找交集，不用交叉找，效率就提升了
  • 问题：
    • 每个小文件切分不均匀，可能导致某个小文件很大，内存放不下
      • 1.情况1：这个小文件大部分是同一个query。
        • 放到内存的set中去重
      • 2.情况2：这个小文件是有很多不同的query组成（hash冲突了）
        • 继续哈希切分

3.4 给一个超过100G大小的logfile,log中存着ip地址,设计算法找到出现次数最多的ip地址？查找出现次数前10的ip地址

• 依次读取文件A中query，i=HashFunc(query)%500，query放进Ai号小文件，然后依次用map对每个Ai小文件统计ip次数，同时求出现次数最多的ip或者topk ip
• 相同的ip一定会进入同一个小文件Ai，所以对Ai进行统计次数就是准确的ip次数