哈希表应用(位图和布隆过滤器)
目录
1.位图
1.1 位图概念
1.2 位图的应用
1.3 位图的实现
1.4 完整代码
2. 布隆过滤器
2.1 布隆过滤器的概念
2.2 布隆过滤器的优缺点
2.3 实现
2.4 完整代码
1.位图
1.1 位图概念
位图,是用比特位来表示某种状态。一个位有两种状态0和1,0可以表示一种状态,1可以表示一种状态。通常是用来判断某个数据存不存在。比如:判断一个数据是否保存,可以用一个位图来表示,数据对应位为1表示保存了,对应位为0表示未保存。如果想知道某个数是否存在,直接找该数对应位的状态即可。
注意:位图没有保存数据,而是保存的状态。
1.2 位图的应用
位图适用于海量数据,和数据无重复的情况。因为用的是比特位,占据空间会比较小。
- 快速查找某个数据是否在集合中
- 排序+去重。
- 求两个集合的交集,并集等
- 操作系统中的磁盘标记
优点:空间小
确定:只能处理整形
1.3 位图的实现
我们用一个数组来保存整形,一个整形4个字节。一个字节8位。所以数组一个元素占32位。
查找数据对应位
保存数据将某一位置1,删除数据将某一位置0。查找数据有保存。都需要查找数对应的位。如何查找呢?
1.先找到数据在数组中保存在哪个下标。
2.再找到数据在该下标的哪一位。
//找到这数在第几个整形里
int i = N / 32;//找到这个数在这个整形的第几位
int j = N % 32;
将某一位置记为1
可以使用按位或操作'|'。按位或,有1为1,全0为0。
这样就需要得到一个相应为为1,其它位为0的数。可以使用移位操作,将1左移pos位。
将数组当前元素按位或上1左移pos位,就将相应位置1了。
//找到这个数的比特位,将其变为1void set(size_t N){//找到这数在第几个整形里int i = N / 32;//找到这个数在这个整形的第几位int j = N % 32;//"或",有1为1,将该比特位变为1_a[i] |= (1 << j);}
将某一位置记为0
可以使用按位与操作'&'。按位与,全1为1,有0为0。
这样就需要得到一个相应为为0,其它位为1的数。可以使用移位操作,将1左移pos位,然后按位取反。将数组当前元素按位与上这个数,就将相应位置1了。
//找到这个数的比特位,将其变为0
void retset(size_t N)
{//找到这数在第几个整形里int i = N / 32;//找到这个数在这个整形的第几位int j = N % 32;//"与",有0为0,将该比特位变为0_a[i] &= (~(1 << j));
}
检查该位置是否为1
可以使用按位&,用对应位为1,其它位为0与上数组元素
按位或不行,用对应位为0,其它位为1。会改变其它位的状态。
//检查该位置是否为1
bool test(size_t N)
{int i = N / 32;int j = N % 32;//"与",右0为0,如果该位置为1时,则该整形不为空,返回真//如果该位置为0时,则该整形为空,返回假return _a[i] & (1 << j);
}
1.4 完整代码
#pragma once
#include<vector>
#include<iostream>
using namespace std;namespace CH1
{//N代表多少比特位template<size_t N>class bitset{public:bitset(){_a.resize(N / 32 + 1);//开空间}//找到这个数的比特位,将其变为1void set(size_t N){//找到这数在第几个整形里int i = N / 32;//找到这个数在这个整形的第几位int j = N % 32;//"或",有1为1,将该比特位变为1_a[i] |= (1 << j);}//找到这个数的比特位,将其变为0void retset(size_t N){//找到这数在第几个整形里int i = N / 32;//找到这个数在这个整形的第几位int j = N % 32;//"与",有0为0,将该比特位变为0_a[i] &= (~(1 << j));}//检查该位置是否为1bool test(size_t N){int i = N / 32;int j = N % 32;//"与",右0为0,如果该位置为1时,则该整形不为空,返回真//如果该位置为0时,则该整形为空,返回假return _a[i] & (1 << j);}private:vector<int> _a;};
}
2. 布隆过滤器
2.1 布隆过滤器的概念
由上我们知道位图的缺点是只能记录是否保存整数数据,布隆过滤器则是针对这一缺点,还可以记录除整数以外的其它类型的数据。
布隆过滤器底层是通过位图实现的,通过哈希函数将其它类型转化成整形。但是这样会有一个缺点,可能不同的数据可能会通过哈希函数转化成相同的值。比如:string类型的"abcd"和"aadd"哈希函数是将所有字符ASCII码值加起来,这两个字符串就会得到相同的值。
这样就会导致误判,已经保存了的数据一定不会再保存。但是,没有保存的数据,通过哈希函数求出来的值与其中一个已经保存的值的整形值一样时,也不会保存了。
这种误判并不能得到实质性的解决,但是可以通过一些方法来降低误判。
布隆过滤器是通过,将需要保存的值通过多个哈希函数,得到多个值,将位图中的多个位置置1。将测在不在时,需要检测所有的位置是否为1。
比如:
2.2 布隆过滤器的优缺点
优点:
- 增加和查询元素时间复杂度为O(K),(K为哈希函数的个数,一般比较小),与数据量无关。
- 哈希函数之间没有关系,方便硬件并行计算。
- 布隆过滤器不需要保存函数本身,在某些保密要求严格的场合由很大优势。
- 节省空间,高效
缺点:
- 存在误判,不支持删除。
2.3 实现
- 布隆过滤器时参数
bitset _bloom;//位图
size_t _count = 0;//数据个数
- 布隆过滤器时初始化
bloomfilter(size_t num)//这个是开辟的空间的大小————单位比特:_bloom(num * 5)//长度太小起不到过滤作用,也不能太大,研究出来乘5最好, _count(0)
{}
位图为的个数可以通过数据的个数来确定,通过上面我们知道,一个数据对应多个位,如果布隆过滤器的位图的位数正好是数据的个数,很快,布隆过滤器就满了。数据不好保存,起不到过滤的作用。但是位数太大,空间有太大。于是有人研究出来,一般位数开辟元素个数的5倍最好。
- 布隆过滤器的插入
插入通过哈希函数转化成整形后,在位图中,将对应位置1。
void insert(const K& num)
{//先转成整形int index1 = KToInt1()(num) % _bloom.bitcount();//余上所有位数,防止越界std::cout << index1 << std::endl;int index2 = KToInt2()(num) % _bloom.bitcount();std::cout << index2 << std::endl;int index3 = KToInt3()(num) % _bloom.bitcount();std::cout << index3 << std::endl;//将对应位置1_bloom.set(index1);_bloom.set(index2);_bloom.set(index3);
}
- 布隆过滤器的查找
查找通过哈希函数转化成整形后,在位图中,检测每一位是否为1,有一位不为1,则不存在。
//只要有一位为0,就不存在bool IsBloomFilter(const K& num){int index1 = KToInt1()(num) % _bloom.bitcount();//余上所有位数,防止越界if (!_bloom.test(index1)){return false;}int index2 = KToInt2()(num) % _bloom.bitcount();if (!_bloom.test(index2)){return false;}int index3 = KToInt3()(num) % _bloom.bitcount();if (!_bloom.test(index3)){return false;}return true;}
- 布隆过滤器的删除
布隆过滤器不支持删除,因为不同的数据,可能通过多个哈希函数,在多个位上置1。但是可能不同数据,通过不同哈希函数的多个位有相同的位置。
比如:
如果删除了abcd,对应位图2位置会被置0,相应aadd会被检测为不存在,实际时存在的。所以不能有删除操作。
注意:布隆过滤器是通过多个哈希函数将多个位置1,来降低误判,并没有解决误判。
2.4 完整代码
#pragma once
//布隆过滤器是用位图实现的
#include"bitset.h"
#include<string>template<class T>
struct KeyToInt1{T& operator()(const T& k){return k;}
};template<>
struct KeyToInt1<std::string>
{size_t operator()(const std::string& s){if (s.size() == 0){return 0;}size_t hash = 0;for (size_t i = 0; i < s.size(); i++){hash *= 131;hash += s[i];}return hash;}
};template<class T>
struct KeyToInt2{T& operator()(const T& k){return k;}
};template<>
struct KeyToInt2<std::string>
{size_t operator()(const std::string& s){if (s.size() == 0){return 0;}size_t hash = 0;for (size_t i = 0; i < s.size(); i++){hash *= 65599;hash += s[i] ;}return hash;}
};template<class T>
struct KeyToInt3{T& operator()(const T& k){return k;}
};template<>
struct KeyToInt3<std::string>
{size_t operator()(const std::string& s){if (s.size() == 0){return 0;}int magic = 63689;size_t hash = 0;for (size_t i = 0; i < s.size(); i++){hash *= magic;hash += s[i];magic *= 378551;}return hash;}
};//KToInt是K类型转化成int,多个函数,将一个数据转成多个整形,多个位保存一个数据的状态
template<class K, class KToInt1 = KeyToInt1<K>, class KToInt2 = KeyToInt2<K>, class KToInt3 = KeyToInt3<K>>
class bloomfilter{
public:bloomfilter(size_t num):_bloom(num * 5)//长度太小起不到过滤作用,也不能太大,研究出来乘5最好, _count(0){}void insert(const K& num){//先转成整形int index1 = KToInt1()(num) % _bloom.bitcount();//余上所有位数,防止越界std::cout << index1 << std::endl;int index2 = KToInt2()(num) % _bloom.bitcount();std::cout << index2 << std::endl;int index3 = KToInt3()(num) % _bloom.bitcount();std::cout << index3 << std::endl;//将对应位置1_bloom.set(index1);_bloom.set(index2);_bloom.set(index3);}//只要有一位为0,就不存在bool IsBloomFilter(const K& num){int index1 = KToInt1()(num) % _bloom.bitcount();//余上所有位数,防止越界if (!_bloom.test(index1)){return false;}int index2 = KToInt2()(num) % _bloom.bitcount();if (!_bloom.test(index2)){return false;}int index3 = KToInt3()(num) % _bloom.bitcount();if (!_bloom.test(index3)){return false;}return true;}private:bitset _bloom;size_t _count = 0;//数据个数
};