C++：位图

目录

一.位图

位图应用题1：

set 增加值：

位图题1代码：

位图应用题2：给定100亿个整数，设计算法找到只出现一次的整数?

二.布隆过滤器

1.概念

2.布隆过滤器删除

3.应用场景

4.哈希切割

---

一.位图

位图应用题1：

位图：直接定址法哈希---用一个比特位标识映射值在不在

方法：

原本4个字节存一个数，现在1个bit存一个数的状态，1字节=8bit，4字节=32bit，16G/32=500MB，现在消耗500MB即可

set 增加值：

        //x映射的位标记成1
		void set(size_t x)    //增加x到这些数中，把x对应的比特位设置为1
		{
			// x映射的比特位在第几个char对象
			size_t i = x / 8;
 
			// x在char第几个比特位
			size_t j = x % 8;
 
			_bits[i] |= (1 << j);
		}

位图题1代码：

#pragma once
#include 
 
namespace bit
{
	// N个比特位的位图  10  16
	template<size_t N>    //总的数的数量，这里设成100先
	class bitset
	{
	public:
		bitset()
		{
			// +1保证足够比特位，最多浪费8个
			_bits.resize(N/8 + 1, 0);
		}
 
		//x映射的位标记成1
		void set(size_t x)    //增加x到这些数中，把x对应的比特位设置为1
		{
			// x映射的比特位在第几个char对象
			size_t i = x / 8;
 
			// x在char第几个比特位
			size_t j = x % 8;
 
			_bits[i] |= (1 << j);
		}
 
		void reset(size_t x)    //删除x，把x对应的比特位设置为0
		{
			// x映射的比特位在第几个char对象
			size_t i = x / 8;
 
			// x在char第几个比特位
			size_t j = x % 8;
 
			//! && ||
			//~ &  | 
			_bits[i] &= (~(1 << j));
		}
 
		bool test(size_t x)
		{
			// x映射的比特位在第几个char对象
			size_t i = x / 8;
 
			// x在char第几个比特位
			size_t j = x % 8;
 
			return _bits[i] & (1 << j);
		}
 
	private:
		std::vector<char> _bits;
		//vector _bits;
	};
 
	void test_bit_set1()
	{
		bitset<100> bs;
		bs.set(18);
		bs.set(19);
 
		cout << bs.test(18) << endl;
		cout << bs.test(19) << endl;
		cout << bs.test(20) << endl;
 
 
		bs.reset(18);
		bs.reset(18);
 
		cout << bs.test(18) << endl;
		cout << bs.test(19) << endl;
		cout << bs.test(20) << endl;
 
		//bitset bigBS;
		bitset<0xFFFFFFFF> bigBS;
		//bitset<-1> bigBS;
 
 
 
		//bit_set<2^32-1> bigBS; // pow
	}
}

位图应用题2：给定100亿个整数，设计算法找到只出现一次的整数?

方法：用两个 bitset 数组  _bs1，_bs2记录，x对应两个数组的比特位来记录这个数出现的次数，_bs1对应比特位是0，_bs2对应比特位是0，就是出现0次；_bs1对应比特位是0，_bs2对应比特位是1，就是出现1次；_bs1对应比特位是1，_bs2对应比特位是0，就是出现2次；

#pragma once
#include 
 
namespace bit
{
	template<size_t N>
	class two_bitset
	{
	public:
		void set(size_t x)
		{
			int in1 = _bs1.test(x);
			int in2 = _bs2.test(x);
			if (in1 == 0 && in2 == 0)
			{
				_bs2.set(x);
			}
			else if (in1 == 0 && in2 == 1)
			{
				_bs1.set(x);
				_bs2.reset(x);
			}
		}
 
		bool is_once(size_t x)
		{
			return _bs1.test(x) == 0 && _bs2.test(x) == 1;
		}
 
	private:
		bitset _bs1;
		bitset _bs2;
	};
 
	void test_two_bitset()
	{
		int a[] = { 4, 3, 2, 4, 5, 2, 2, 4, 7, 8, 9, 2, 1,3,7 };
		two_bitset<10> tbs;
		for (auto e : a)
		{
			tbs.set(e);
		}
 
		for (size_t i = 0; i < 10; ++i)
		{
			if (tbs.is_once(i))
			{
				cout << i << endl;
			}
		}
	}
}

二.布隆过滤器

1.概念

无法解决哈希冲突
存在冲突既是误判——在:存在误判。不在:是准确的，这个数据只要有一个映射值不在就一定不在。
给出几个网址ip形式的字符串，set添加数据：通过不同的函数将字符串转换成整数记录在哈希表上，这里假设只用了3个不同函数进行映射，比如 123.0.3.22 这个字符串映射3个数：100 33 22，set(123.0.3.22 ) 以后就加入这3个数。

test查看：假如下面前3个字符串都set了，若test查看第2个字符串 192.0.3.21 是否存在，则看对应的映射值 23 33 99 是否都存在，都在就说明已经set过了，存在，但是还是有误判的可能，只不过函数越多，误判的概率越小。比如：test查看第4个字符串：

若test查看第4个字符串 31.22.1.1 是否存在，则看对应的映射值 55 88 70是否都存在，比如查55存在，和第3个重了；查88存在，和第3个重了；查70不存在，说明没有这个字符串，所以  31.22.1.1不存在。

2.布隆过滤器删除

删除一个值，只需要——映射位置的计数
删除这个值以后，可能存在判断他还在! -- 误判
布隆过滤器的特点节省空间，支持删除就不那么节省了

3.应用场景

（1）注册的时候，快速判断一 个昵称是否使用过?
a、不在：没有用过 绿色对钩
b、在：再去数据库查确认一遍

（2）黑名单
a、不在        就通行
b、在 就再次去系统确认

（3）过滤层，提高查找数据效率

a、不在        就返回
b、在 就再次去数据系统找一遍

这样不在的情景就效率极高

4.哈希切割

题目：给一个超过100G大小的log file, log中存着IP地址,设计算法找到出现次数最多的IP地址?

（1）统计次数,如何统计次数?

平分100个文件，统计次数是不对的。因为相同ip可能分到不同的文件中去了

正确做法：

哈希切割(分)：利用哈希函数得出字符串对应的映射值 i，把这个字符串放到对应的 Ai文件中，则相同的ip，一定进入同一个小文件