菜鸟笔记
提升您的技术认知

哈希的应用(位图,布隆过滤器)

阅读 : 129

位图(整型)

1.面试题
给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数 中。【腾讯】

  1. 遍历,时间复杂度O(N)
  2. 排序(O(NlogN)),利用二分查找: logN
  3. 位图解决 数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比 特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在。

位图概念
所谓位图,就是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

#pragma once
#include<vector>
#include<iostream>
using namespace std;
class BitSet
{ 
public:
	BitSet(size_t Bitnum)
		:_Bitnum(Bitnum)
	{ 
		_bits.resize((Bitnum >> 8) + 1, 0);

	}
	void Set(size_t x)//把那个位设置成1,代表存在
	{ 
		//size_t index = x / 8;
		size_t index = x >> 3;
		size_t num = x % 8;

		_bits[index] |= (1 << num);
	}
	void Reset(size_t x)//把那个位设置成0,代表不存在
	{ 
		//size_t index = x / 8;
		size_t index = x >> 3;
		size_t num = x % 8;

		_bits[index] &= (~(1 << num));
	}
	bool Test(size_t x)//存在返回1,不存在返回0
	{ 
		size_t index = x >> 3;
		size_t num = x % 8;

		return _bits[index] & (1 << num);
	}
private:
	vector<char> _bits;//一个char,8个bite
	size_t _Bitnum;
};

void TestBitSet()
{ 
	BitSet bs(10000);
	bs.Set(9999);
	bs.Set(999);
	bs.Set(99);
	bs.Set(9);

	cout << bs.Test(9999) << endl;
	cout << bs.Test(999) << endl;
	cout << bs.Test(99) << endl;
	cout << bs.Test(9) << endl;
}

int main()
{ 
	TestBitSet();
	system("pause");
	return 0;
}

布隆过滤器(任意类型)

优点:节省空间,快(直接找到那个位)

缺点:容易误判,判断在一定是准确的,判断不在不一定准确

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

  1. 用哈希表存储用户记录,缺点:浪费空间
  2. 用位图存储用户记录,缺点:不能处理哈希冲突
  3. 将哈希与位图结合,即布隆过滤器

概念

布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。

emplate<class K, class HashFunc1, class HashFunc2, class HashFunc3>//一个值映射三个位置
class BloomFilter
{ 
public:
	void Set(const K& key)//不支持Reset,因为布隆过滤器映射了很多个位,把冲突的位置为零,会影响其他冲突的映射
	{ 
		size_t index1 = HashFunc1()(key);
		size_t index2 = HashFunc2()(key);
		size_t index3 = HashFunc3()(key);

		_bs.Set(index1);
		_bs.Set(index2);
		_bs.Set(index3);

	}
	void Test(const K& key)//只要有一个位不在,就能判断他不在
	{ 
		size_t index1 = HashFunc1()(key);
		if (_bs.Test(index1) == false)
		{ 
			return false;
		}
		size_t index2 = HashFunc2()(key);
		if (_bs.Test(index1) == false)
		{ 
			return false;
		}
		size_t index3 = HashFunc3()(key);
		if (_bs.Test(index1) == false)
		{ 
			return false;
		}

		return true;//存在误判
	}
private:
	BitSet _bs;
};

int main()
{ 
	system("pause");
	return 0;
}