[C++]位图+布隆过滤器
一、位图
1、概念
位图，就是用每一位（bit）来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
如：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。我们将每一个数据都以某种方式映射到位图中，那么一个位置就代表了其所对应的数据，一个数据只映射到其对应的位置中（一一对应）。
应用
- 快速查找某个数据是否在一个集合中
- 排序
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
2、模拟实现
#include<vector>
namespace bitset
{
template<size_t N>
class bitset
{
public:
bitset()
{
_bs.resize(N);
}
void set(size_t key)
{
size_t i = key / 32; //找到存储的int块
size_t j = key % 32; //找到该块内存储的位置
_bs[i] |= (1 << j);
}
void reset(size_t key)
{
size_t i = key / 32; //找到存储的int块
size_t j = key % 32; //找到该块内存储的位置
_bs[i] &= ~(1 << j);
}
bool test(size_t key)
{
size_t i = key / 32; //找到存储的int块
size_t j = key % 32; //找到该块内存储的位置
return _bs[i] & (1 << j);
}
private:
vector<int> _bs;
};
}二、布隆过滤器
1、概念
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
注：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。
2、模拟实现
#include"bitset.h"
#include<string>
struct BKDRHash
{
size_t operator()(const string& key)
{
// BKDR
size_t hash = 0;
for (auto e : key)
{
hash *= 31;
hash += e;
}
return hash;
}
};
struct APHash
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (size_t i = 0; i < key.size(); i++)
{
char ch = key[i];
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
}
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const string& key)
{
size_t hash = 5381;
for (auto ch : key)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
template<size_t N, class K = string, class HashF1 = BKDRHash, class HashF2 = APHash, class HashF3 = DJBHash>
class BloomFilter
{
typedef bitset::bitset<N> bitset;
public:
void set(const K& key)
{
size_t hashi1 = HashF1()(key) % N;
_bs.set(hashi1);
size_t hashi2 = HashF2()(key) % N;
_bs.set(hashi2);
size_t hashi3 = HashF3()(key) % N;
_bs.set(hashi3);
}
bool test(const K& key)
{
size_t hashi1 = HashF1()(key) % N;
if (!_bs.test(hashi1))
return false;
size_t hashi2 = HashF2()(key) % N;
if (!_bs.test(hashi2))
return false;
size_t hashi3 = HashF3()(key) % N;
if (!_bs.test(hashi3))
return false;
return true;
}
private:
bitset _bs;
};
原文地址：https://blog.csdn.net/m0_71071692/article/details/140415776
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！