文章目录

• 一.位图面试题
•     1.给定100亿个整数，设计算法找到只出现一次的整数
•     2.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
•     3.1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
• 二.布隆过滤器
• 总结

给 40 亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在

这 40 亿个数中。【腾讯】

1.遍历，时间复杂度为O(N)

2.排序（NlogN）,二分查找（logN）

3.位图。时间复杂度O（1）

下面我们先讲解一下题目，首先我们要判断一个数是否存在，那么这个数只需要有两种状态即可，要不存在，要不就是不存在，而比特位中0和1就能表示存在和不存在两种状态，所以我们用一个char类型就能判断8个值是否存在（因为一字节有8个bit位），现在我们分析一下题目，首先40亿个无符号整数是多大呢我们算一下：一个整数是4字节，40*4=160亿字节，1G = 1024*1024*1024大约10亿字节，1G是10亿字节那么160亿字节就是16G，这么大的内存仅仅是为了判断某个数存不存在也太浪费了，那么我们再算算位图需要耗费多少内存：一个char可以判断8个数是否存在，所以仅需40亿/8=5亿个char就能判断40亿个数，一个char是1字节，5亿个char就是5亿字节，10亿字节是1G，5亿字节是512MB，从刚刚需要16G内存到现在512MB内存就能搞定，面试官一定会对你刮目相看的。

下面我们画图分析一下位图的原理：

namespace sxy
{
	template <size_t N>
	class biteset
	{
	public:
		biteset()
		{
			_bits.resize(N / 8 + 1, 0);
		}
	private:
		vector<char> _bits;
	};
}

//将某个数映射为比特位将那个比特位置为1
		void set(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			_bits[i] |= (1 << j);
		}
		//将某个数的比特位重新置为0
		void reset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			_bits[i] &= ~(1 << j);
		}

首先我们看set,将某个比特位设置为1很简单，我们只需要让1左移j个比特位然后或上那个位置的char，为什么是或呢？要注意L我们进行某个位的运算是不能改变其他位的，比如我们要修改第2个比特位结果把第5个也修改了，那么一定是错了，让其按位或1如下图：

bool test(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			return _bits[i] & (1 << j);
		}

	//位图中有映射了多少个数
		size_t Count()
		{
			size_t count = 0;
			for (size_t i = 0; i < _bits.size(); i++)
			{
				int j = 0;
				while (j < 8)
				{
					if (_bits[i] & (1 << j))
					{
						++count;
					}
					++j;
				}
			}
			return count;
		}

void testbit()
	{
		//-1给无符号就是整形的最大值，开500多MB内存
		biteset<200> bt;
		bt.set(10);
		cout << bt.test(10) << endl;
		bt.reset(10);
		cout << bt.test(10) << endl;
		/*bt.set(11);
		bt.set(12);
		bt.set(13);
		bt.set(19);
		bt.set(46);
		bt.set(75);
		cout << bt.Count() << endl;*/
	}

template <size_t N>
	class two_biteset
	{
	public:
		void set(size_t x)
		{
			//如果这个值没有被映射过
			if (_bs1.test(x) == false && _bs2.test(x) == false)
			{
				// 00    我们以bs1代表左边那个0，bs2代表右边那个0
				//要想00->01  只需要让s2变1
				_bs2.set(x);
			}
			//如果这个值被映射过1次 01
			else if (_bs1.test(x) == false && _bs2.test(x) == true)
			{
				//将1次改为多次，多次用10表示  01->10
				_bs1.set(x);
				_bs2.reset(x);
			}
		}
		//打印出现1次的数
		void print()
		{
			for (size_t i = 0; i < N; i++)
			{
				if (_bs2.test(i) == true)
				{
					cout << i << " ";
				}
			}
			cout << endl;
		}
	private:
		biteset<N> _bs1;
		biteset<N> _bs2;
	};

void test_twobite()
	{
		int a[] = { 1,1,4,4,89,95,45,45,65,65,25,25 };
		two_biteset<100> bt;
		for (auto& e : a)
		{
			bt.set(e);
		}
		bt.print();
	}

template <size_t N>
	class three_biteset
	{
	public:
		void set(size_t x)
		{
			//如果这个值没有被映射过
			if (_bs1.test(x) == false && _bs2.test(x) == false)
			{
				// 00    我们以bs1代表左边那个0，bs2代表右边那个0
				//要想00->01  只需要让s2变1
				_bs2.set(x);
			}
			//如果这个值被映射过1次 01
			else if (_bs1.test(x) == false && _bs2.test(x) == true)
			{
				//将1次改为2次，2次用10表示  01->10
				_bs1.set(x);
				_bs2.reset(x);
			}
			else
			{
				//多次用11表示
				_bs1.set(x);
				_bs2.set(x);
			}
		}
		void print()
		{
			for (size_t i = 0; i < N; i++)
			{
				if (_bs1.test(i) == true && _bs2.test(i) == false
					|| _bs1.test(i) == false && _bs2.test(i) == true)
				{
					cout << i << " ";
				}
			}
			cout << endl;
		}
	private:
		biteset<N> _bs1;
		biteset<N> _bs2;
	};

下面我们测试一下：

void test_threebite()
	{
		int a[] = { 1,1,1,4,4,4,89,95,45,45,45,65,65,65,25,25,25,45 };
		three_biteset<100> bt;
		for (auto& e : a)
		{
			bt.set(e);
		}
		bt.print();
	}

我们总结一下位图的优缺点：

优点：速度快，节省空间

缺点：只能映射整形，其他类型如：浮点数，string等等不能存储映射。

 二、布隆过滤器

布隆过滤器实际上就是位图和哈希的组合，位图只能处理整形处理不了字符串，而布隆过滤器可以映射字符串，如下图（图片是转载）：

 这个时候向布隆过滤器插入“baidu”:

 也就是说我们让哈希函数将字符串进行转化，转化后将这个值映射到位图中，学过哈希我们都知道哈希冲突是解决不了的，所以一定会存在冲突问题（一个值映射一个位置有很大概率会冲突，一个值映射多个位置就可以减少冲突），为了避免冲突我们就引入多个哈希函数，让多个哈希函数将字符串转化后映射到不同的比特位。

了解了以上知识后问大家一个问题，布隆过滤器是判断在的时候会被冲突还是判断不在的时候会被冲突呢？这里一定是在的时候被冲突，如下图：

 现在有baidu和left两个字符串，如果有一个字符串hello计算出来的哈希值映射到位图中正好是baidu和left被置为1的位置，那么这个时候就会误判hello是存在，但实际上hello并不存在。所以布隆过滤器一定可以判断某个字符串不存在，而对于存在的情况会产生误判。所以布隆过滤器的使用场景是：能容忍误判的场景。比如：注册时快速判断昵称是否使用过

那么手机号码是否注册过可以用布隆过滤器判断吗？可以，但是一定要结合数据库。我们用布隆过滤器判断手机号码是否注册过，因为布隆过滤器判断不存在是准确的，所以如果不存在那么就一定没有注册过，如果判断存在我们就让其去数据库再判断一次，最后的结果是看数据库的结果，这样的效率比直接去数据库查找手机号码是否注册快了很多，因为数据库是在磁盘中存储的。

下面我们实现一下：

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto& e : s)
		{
			hash += e;
			hash *= 31;
		}
		return hash;
	}
};
struct APHash
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (long i = 0; i < s.size(); i++)
        {
            size_t ch = s[i];
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
            }
        }
        return hash;
    }
};
struct DJBHash
{
    size_t operator()(const string& s)
    {
        size_t hash = 5381;
        for (auto ch : s)
        {
            hash += (hash << 5) + ch;
        }
        return hash;
    }
};
template <size_t N, class K = string,
	class Hash1 = BKDRHash,
	class Hash2 = APHash,
	class Hash3 = DJBHash>
class BloomFilter
{
public:
	void set(const K& key)
	{
        size_t hash1 = Hash1()(key) % N;
        //用第一个哈希函数映射位图
        _bs.set(hash1);
        size_t hash2 = Hash2()(key) % N;
        //用第二个哈希函数映射位图
        _bs.set(hash2);
        size_t hash3 = Hash3()(key) % N;
        //用第三个哈希函数映射位图
        _bs.set(hash3);
	}
    bool test(const K& key)
    {
        size_t hash1 = Hash1()(key) % N;
        if (_bs.test(hash1) == false)
        {
            return false;
        }
        size_t hash2 = Hash2()(key) % N;
        if (_bs.test(hash2) == false)
        {
            return false;
        }
        size_t hash3 = Hash3()(key) % N;
        if (_bs.test(hash3) == false)
        {
            return false;
        }
        return true;
    }
private:
	sxy::biteset<N> _bs;
};

首先模板参数中的N代表最多要插入多少个key数据的个数，K是存储数据的类型，然后就是3个哈希函数，当然也可以多来几个哈希函数。set也很简单，就是用哈希函数算出K类型的值然后去位图中映射，要注意的是我们每次算出来后都要对N进行一次取模。查找是否存在也很简单，只需要判断每一个哈希函数算出来的值映射的比特位是否为1，如果有一个为0那么一定不存在(这点我们上面说过，布隆过滤器判断不存在是准确的）。注意：布隆过滤器天生不支持删除，如果实现删除可以像我们用两个位图实现计数那样，要删除只需要--即可。

下面是哈希算法的网址：https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html

下面我们优化一下布隆过滤器：

 也就是说哈希函数的个数和N之间有一个关系，3 = （m/n）*0.69,然后同时除0.69得到m与n之间是4倍的关系。

void set(const K& key)
	{
        size_t len = N * _x;
        size_t hash1 = Hash1()(key) % len;
        //用第一个哈希函数映射位图
        _bs.set(hash1);
        size_t hash2 = Hash2()(key) % len;
        //用第二个哈希函数映射位图
        _bs.set(hash2);
        size_t hash3 = Hash3()(key) % len;
        //用第三个哈希函数映射位图
        _bs.set(hash3);
	}
    bool test(const K& key)
    {
        size_t len = N * _x;
        size_t hash1 = Hash1()(key) % len;
        if (_bs.test(hash1) == false)
        {
            return false;
        }
        size_t hash2 = Hash2()(key) % len;
        if (_bs.test(hash2) == false)
        {
            return false;
        }
        size_t hash3 = Hash3()(key) % len;
        if (_bs.test(hash3) == false)
        {
            return false;
        }
        return true;
    }

 下面我们打印哈希函数看一下冲突的情况：

void test_bloomfilter()
{
    BloomFilter<100> bf;
    bf.set("sort");
    bf.set("bloom");
    bf.set("hello world");
    bf.set("test");
    bf.set("etst");
    bf.set("estt");
}

 我们可以看到sort字符串的hash3这个值和bloom字符串的hash1冲突了都是相同的值，下面我们用一个测试用例来测试布隆过滤器发生冲突的百分比：

void test_bloomfilter2()
    {
        srand(time(0));
        const size_t N = 10000;
        BloomFilter<N> bf;
        std::vector<std::string> v1;
        std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
        for (size_t i = 0; i < N; ++i)
        {
            v1.push_back(url + std::to_string(i));
        }

        for (auto& str : v1)
        {
            bf.set(str);
        }

        // v2跟v1是相似字符串集，但是不一样
        std::vector<std::string> v2;
        for (size_t i = 0; i < N; ++i)
        {
            std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
            url += std::to_string(999999 + i);
            v2.push_back(url);
        }

        size_t n2 = 0;
        for (auto& str : v2)
        {
            if (bf.test(str))
            {
                ++n2;
            }
        }
        cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

        // 不相似字符串集
        std::vector<std::string> v3;
        for (size_t i = 0; i < N; ++i)
        {
            string url = "zhihu.com";
            //string url = "https://www.cctalk.com/m/statistics/live/16845432622875";
            url += std::to_string(i + rand());
            v3.push_back(url);
        }

        size_t n3 = 0;
        for (auto& str : v3)
        {
            if (bf.test(str))
            {
                ++n3;
            }
        }
        cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
    }

 v1是字符串集，v2是v1的相似字符串集合，下面我们运行一下：

 测试后我们发现4倍的误判率在15%左右，下面我们换成5倍看看：

 可以发现5倍时误判率下降到了%6,但这是用空间换来的，以上就是布隆过滤器，下面我们做两道面试题：

 我们之前用两个位图实现了计算数据1次两次或多次，如果要让布隆过滤器支持删除只需要把映射的值改为可以记录次数的，每次删除只需要--即可。

布隆过滤器的查找