[数据结构与算法] 哈希的应用——位图、布隆过滤器、海量数据

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 哈希的应用——位图、布隆过滤器、海量数据 -> 正文阅读

[数据结构与算法]哈希的应用——位图、布隆过滤器、海量数据

位图

位图的概念

所谓的位图，就是用每一位来存放一种状态，适用于海量数据，数据无重复的场景。通常是用来判断该数据是否存在。
例题：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
解决方案：

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

位图的应用

快速查找某个数据是否在一个集合中
排序
求两个集合的交集，并集等
操作系统中磁盘块标记
内核中信号标志位（信号屏蔽和未决信号集）

位图中成员函数及使用

在这里插入图片描述

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

int main()
{
	bitset<8> bs;
	bs.set(2); //设置第2位
	bs.set(4); //设置第4位
	cout << bs << endl; //00010100
	
	bs.flip(); //反转所有位
	cout << bs << endl; //11101011
	cout << bs.count() << endl; //6

	cout << bs.test(3) << endl; //1

	bs.reset(0); //清空第0位
	cout << bs << endl; //11101010

	bs.flip(7); //反转第7位
	cout << bs << endl; //01101010

	cout << bs.size() << endl; //8

	cout << bs.any() << endl; //1

	bs.reset(); //清空所有位
	cout << bs.none() << endl; //1

	bs.set(); //设置所有位
	cout << bs.all() << endl; //1
	return 0;
}

位图的实现

class bitset
{
public:
 bitset(size_t bitCount)
 : _bit((bitCount>>5)+1), _bitCount(bitCount)
 {}
 // 将which比特位置1
 void set(size_t which)
 {
 if(which > _bitCount)
 return;
 size_t index = (which >> 5);
 size_t pos = which % 32;
 _bit[index] |= (1 << pos);
 }
 // 将which比特位置0
 void reset(size_t which)
 {
 if(which > _bitCount)
 return;
 size_t index = (which >> 5);
 size_t pos = which % 32;
 _bit[index] &= ~(1<<pos);
 }
 // 检测位图中which是否为1
 bool test(size_t which)
 {
 if(which > _bitCount)
 return false;
 size_t index = (which >> 5);
 size_t pos = which % 32;
 return _bit[index] & (1<<pos);
 }
 // 获取位图中比特位的总个数
 size_t size()const{ return _bitCount;}
 // 位图中比特为1的个数
 size_t Count()const
 {
 int bitCnttable[256] = {
 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,
 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
 6, 7, 6, 7, 7, 8};
 
 size_t size = _bit.size();
 size_t count = 0;
 for(size_t i = 0; i < size; ++i)
 {
 int value = _bit[i];
 int j = 0;
 while(j < sizeof(_bit[0]))
 {
 unsigned char c = value;
 count += bitCntTable[c];
 ++j;
 value >>= 8;
 }
 }
 return count;
 }
private:
 vector<int> _bit;
 size_t _bitCount;
};

布隆过滤器

实际是位图的变形和延申。将哈希和位图进行结合。

布隆过滤器的概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
在这里插入图片描述
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。
在查找时，分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，
代表该元素一定不在哈希表中，否则可能在哈希表中。但是判断是否该数据存在会存在误判，因为，有可能会有某些是一样的，我们只是判断该位置是否为1，没有其他的判断方式，容易出现误判。

布隆过滤器删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素，因为有可能两个元素之间存在交集。
一种支持删除的方法:将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器（k个哈希函数计算出来的哈希地址）加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。
缺陷：无法确认元素是否真正的在布隆过滤器中、存在计数回绕。