哈希表应用(位图和布隆过滤器)

目录

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. 快速查找某个数据是否在集合中
2. 排序+去重。
3. 求两个集合的交集，并集等
4. 操作系统中的磁盘标记

优点：空间小

确定：只能处理整形

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;//数据个数
};