位图和布隆过滤器是两种常用的数据结构，它们在计算机科学领域有着广泛的应用。本文将介绍这两种数据结构的基本原理和应用场景。

位图

前提

位图的概念

位图（Bitmap）是一种用于表示集合的数据结构，它将每个元素映射为一个位（bit），以表示其存在或不存在。在位图中，通常使用一个数组来存储位，其中数组的每个元素代表一个位。

位图的基本思想是，对于给定的集合，为每个元素定义一个唯一的编号或索引。根据这个编号，将位图中的相应位置设置为1或0，表示元素的存在与否。例如，如果一个集合有100个元素，可以用一个长度为100的位数组来表示这个集合，其中每个元素的位置代表相应元素的编号，位置上的位值表示该元素是否存在。如果位值为1，表示元素存在；如果位值为0，表示元素不存在。

由于位图使用的是位操作，可以节省大量的内存空间。相比传统的存储方式，位图所需的内存空间较小。这使得位图在许多领域都有广泛的应用，特别是当需要快速判断元素是否存在于集合中时。

位图的实现

template<size_t N>class bitset{public:bitset(){_bits.resize(N / 32 + 1, 0);}//把x的映射位标记为1void set(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;//通过或运算，将对应位变为1_bits[i] |= (1 << j);}//把x映射的标记为0void reset(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;//通过与运算，将对应位变为0，~将数倒置_bits[i] &= ~(1 << j);}//判断当前x映射的位置是否为1bool test(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;//如果存在，就会返回一个非0的数；return _bits[i] & (1 << j);}private:vector<int> _bits;};

测试：

void Test1(){bitset<150> bs1;bs1.set(50);bs1.set(101);bs1.set(89);for (size_t i=0; i < 150; i++){if (bs1.test(i)){cout << i << "->" << "在" << "  ";}else{cout << i << "->" << "不在" << "  ";}}cout << endl;bs1.reset(89);if (bs1.test(89)){cout << 89<< "->" << "在" << endl;}else{cout << 89 << "->" << "不在" << endl;}}

位图的应用拓展

template<size_t N>class two_bit_set{public:void set(size_t x){if (_bs1.test(x) == false && _bs2.test(x) == false){//00->01_bs2.set(x);}else if (_bs1.test(x) == false && _bs2.test(x) == true){//01->10_bs2.reset(x);_bs1.set(x);}}bool test(size_t x){if (_bs1.test(x) == false&& _bs2.test(x) == true){return true;}return false;}private:bitset<N> _bs1;bitset<N> _bs2;};

位图常用于数据压缩、数据库索引、图像处理等领域。在数据压缩中，位图可以将大量的数据压缩成较小的文件，这在网络传输和存储空间方面有着重要的作用。在数据库索引中，位图可以快速定位到包含某个元素的记录，提高检索效率。在图像处理中，位图可以对图像进行像素级别的操作，实现各种图像处理功能。

布隆过滤器

前提

对于位图来说，只能处理整数类型的元素，如果遇到字符串的话，如果只通过一个哈希函数来计算对应的哈希值，那么在位图中很大概率会存在相同的索引（哈希值），这样就导致了重复；所以，就有人提出了通过多个哈希函数对key值进行不同位置的映射，这样就能让重复的概率大大降低，当然没有办法百分百避免。

概念

布隆过滤器（Bloom Filter）是一个数据结构，用于快速判断一个元素是否属于某个集合中。它利用了一系列随机映射函数和一个二进制向量来实现。

具体而言，布隆过滤器由一个长度为m的二进制向量（bit数组）和k个不同的哈希函数组成。初始时，所有的位都被置为0。

当一个元素要被添加到布隆过滤器中时，会将该元素经过k个不同的哈希函数计算得到k个哈希值，并将对应的位置在二进制向量中置为1。

当需要判断一个元素是否在布隆过滤器中时，同样将该元素经过k个哈希函数计算得到k个哈希值，并检查对应的位置在二进制向量中是否都为1。如果有任何一个位置不为1，则可以确定该元素不在集合中。但如果所有位置都为1，那么该元素可能在集合中，但也可能是误判。

因此，布隆过滤器存在一定的误判率。当哈希函数的选取和位向量的大小合理时，误判率可以被控制在一个较低的范围内。

布隆过滤器的实现

struct HashFuncBKDR
{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash *= 131;hash += ch;}return hash;}
};struct HashFuncAP
{size_t operator()(const string& s){size_t hash = 0;for (size_t i = 0; i < s.size(); i++){if ((i & 1) == 0)//偶数位字符{hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));}else//奇数位字符{hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));}}return hash;}
};struct HashFuncDJB
{size_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash = hash * 33 ^ ch;}return hash;}
};template<size_t N,class K=string,class Hash1=HashFuncBKDR,class Hash2=HashFuncAP,class Hash3=HashFuncDJB>
class BloomFilter
{
public:void Set(const K& key){//Hash2 hs2;size_t hash1 = Hash1()(key) % M;size_t hash2 = Hash2()(key) % M;size_t hash3 = Hash3()(key) % M;//cout << hash1 << " " << hash2 << " " << hash3 << endl;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool Test(const K& key){size_t hash1 = Hash1()(key) % M;if (_bs.test(hash1) == false)return false;size_t hash2 = Hash2()(key) % M;if (_bs.test(hash2) == false)return false;size_t hash3 = Hash3()(key) % M;if (_bs.test(hash3) == false)return false;return true;}
private:static const size_t M = 10 * N;fnc::bitset<M> _bs;
};

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

性能测试

//性能测试
void TestBF2()
{srand(time(0));const size_t N = 100000;BloomFilter<N> bf;std::vector<std::string> v1;std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";for (size_t i = 0; i < N; ++i){v1.push_back(url + std::to_string(i));}for (auto& str : v1){bf.Set(str);}// v2跟v1是相似字符串集（前缀一样），但是后缀不一样std::vector<std::string> v2;for (size_t i = 0; i < N; ++i){std::string urlstr = url;urlstr += std::to_string(9999999 + i);v2.push_back(urlstr);}size_t n2 = 0;for (auto& str : v2){if (bf.Test(str)) // 误判{++n2;}}cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;// 不相似字符串集  前缀后缀都不一样std::vector<std::string> v3;for (size_t i = 0; i < N; ++i){string url = "zhihu.com";url += std::to_string(i + rand());v3.push_back(url);}size_t n3 = 0;for (auto& str : v3){if (bf.Test(str)){++n3;}}cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}