鹿泉外贸网站建设,微信开发流程四步,青岛建设工程信息网站,响应式网站建设咨询在C中#xff0c;哈希这种思想的应用场景有很多#xff0c;位图就是其中的一种。
位图
位图#xff1a;位图是一种哈希思想的产物#xff0c;可以通过它来对数据进行快速的查找的方法#xff0c;在位图中#xff0c;有2种状态来表示在或者不在#xff0c;即1/0。
位图…在C中哈希这种思想的应用场景有很多位图就是其中的一种。
位图
位图位图是一种哈希思想的产物可以通过它来对数据进行快速的查找的方法在位图中有2种状态来表示在或者不在即1/0。
位图应用场景
设想一下如果给定10000个数据让你判断其中的元素存不存在你有几种方法
1.用unordered_map来进行元素和个数的映射如果存在就返回true 2. 排序二分的思想 3. set find
这时我们发现1w个数据好像都可以用这种方式来查找内存放得下但是当数据量足够大的时候我们就不能将数据直接放到内存中这时我们就需要用到位图了。
一个字节 8bit用每一个bit来表示存不存在这大大减少了空间。 下面看bitset的简单定义
templatesize_t Nclass bitset{public:bitset(){_bits.resize(N / 32 1, 0);}//将元素对应的下标标志为1void set(size_t x){assert(x N);size_t i x / 32;size_t j x % 32;_bits[i] | (1 j);}void reset(size_t x){assert(x N);size_t i x / 32;size_t j x % 32;_bits[i] ~(1 j);}bool test(size_t x){assert(x N);size_t i x / 32;size_t j x % 32;return _bits[i] (1 j);}private:vectorsize_t _bits;};面试题
给定100亿个整数设计算法找到只出现一次的整数
10亿字节 1GB 100亿个整数 400亿字节 40GB 可以发现内存存放不下海量数据用bitset就可以解决了。 我们定义2个位图00 来表示出现了0次的元素01表示出现了1次的元素10表示2次及以上的元素 templatesize_t Nclass two_bit_set{public:void set(size_t x){// 00 - 01if (_bs1.test(x) false _bs2.test(x) false){_bs2.set(x);}else if (_bs1.test(x) false _bs2.test(x) true){// 01 - 10_bs1.set(x);_bs2.reset(x);}}//判断元素是否存在bool test(size_t x){if (_bs1.test(x) false _bs2.test(x) true){return true;}return false;}private:bitsetN _bs1;bitsetN _bs2;};布隆过滤器
布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询****可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。
实现原理
布隆过滤器的结构其实一个数组如下图
当我们向布隆过滤器中插入baidu的时候需要我们使用多个哈希函数来生成多个哈希值将对应的位置置为1。baidu就是将1、4、7的位置设置为了1.
tencent就是将通过hash1、hash2、hash3函数来将对应的3、4、8设置为了1.
当我们去查询的时候meituan的时候如果通过布隆过滤器映射的位置是2、4、8由于4是两个哈希值都将这个bit位设置为了18这个bit位在tencent中设置为了1就只有2这个bit位没有设置为1这是我们就可以说meituan这个值不存在。
随着增加的值越多被设置为1的位置也就越多如果这是出现了一个“taobao”即使它没有被存储过但是对应的位置也有可能被其他存储的值通过映射设置为了1。 所以不能判断是存在的。
总结 布隆过滤器可以准确的判断一个值是不是不存在但是不能肯定一个值存在
布隆过滤器的删除
布隆过滤器不能直接支持删除操作因为在删除一个元素的时候可能会影响其他元素
比如删除上图中tencent元素如果直接将该元素所对应的二进制比特位置0“baidu”元素也被删除了因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作
布隆过滤器的优点
增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关哈希函数相互之间没有关系方便硬件并行运算布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势数据量很大时布隆过滤器可以表示全集其他数据结构不能使用同一组散列函数的布隆过滤器可以进行交、并、差运算
面试题
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址 接着我们继续定义一个priority_queuepiarstring,int,lesser minHeap; 然后将问题转化为topk问题。
