当前位置：首页 > news >正文

位图（bitmap）和布隆过滤器（bloom_filter）

news 来源：原创 2025/7/3 8:40:55

1.位图-Bitmap

1.1问题引入

:给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中？

40亿个无符号整数大约16G的大小，用map或者set显然是无法支持海量数据的存储。那么我们能否不存储数据本身，通过映射关系存储其在（1）或者不再（0）呢？

1.2概念

位图，就是用二进制的bite位来存放某种状态，适用于海量数据，数据无重复。通常是判断某个数在不在的问题的解决办法。

其具体思路是开辟一块连续的空间，将这块连续的空间的第一个bite位置视为1ul，第二个bite位视为2ul，以此类推，每个比特位上数据则表示是否存储（1已经存储 0未存储）

这样，40亿个不重复的无符号整数，无符号整数的上限是2^32，那么我们只需要2^32个连续的bite位，即连续的0.5G的空间就可以将数据信息存储起来。

#pragma once
#include<vector>class bitmap
{
public:bitmap(const size_t& N) //要存储的数据的数上限  {_bitmap.resize(N / 32 + 1, 0);_size = 0;}void set(const size_t x)  //要将x映射到特定的bit位置，让其由0变为1{size_t index = x / 32; //得到映射的第index个int位置size_t pos = x % 32; //得到在这个int的第几个bit位置//将其设置为1_bitmap[index] |= (1 << pos);++_size;}void reset(const size_t x) //将x映射的位置，由0/1变为0{size_t index = x / 32;size_t pos = x % 32;_bitmap[index] &= (~(1 << pos));  --_size;}bool test(const size_t x) //查找x映射的位置是否为1{size_t index = x / 32;size_t pos = x % 32;return (_bitmap[index] >> pos) & 1;}
private:std::vector<int> _bitmap;size_t _size;
};

2.布隆过滤器-bloom_filter

2.1引入

视频推送算法中，我们如何保证给用户推荐的视频不是重复的？

常见的都会给视频一个唯一的字符串代号，就像我们的身份证一样。用unordered_set存储字符串太浪费空间了，位图又只能存储整形类型的数据，该如何破局了？

2.2概念

布隆过滤器的底层是一个位图，其既可以处理int类型，又可以处理string类型的数据。其原理是，当输入的数据是string类型的时候，它会先利用多个字符串哈希算法，将str映射成多个size_t类型，再将其在位图上的位置置为1.

当我们要查找一个string是否存在时，只需要依次利用字符串哈希算法将其映射到size_t上，再通过位图查找映射的这多个位置上是否都为1.如果都为1，那么这个字符串可能存在（因为可能有些位置已经被其他的str映射了）；如果存在一个不为1，那么这个字符串就一定不存在。

参考布隆过滤器的原理及完整公式推导 - 知乎得到 $k=\frac{m}{n}\ln 2$ ， $m=-\frac{n\ln p}{^{_{\ln 2}^{2}}}$ .其中k为哈希函数个数，m为布隆过滤器的长度，n为插入元素个数,p为误报率。

#pragma once
#include"bitmap.h"
#include<string>
//在位图的基础上处理size_t或者string类问题struct BKDRHash
{size_t operator()(const std::string& str){size_t ret = 0;for (size_t i = 0; i < str.size(); ++i){ret *= 131;ret += str[i];}return ret;}
};
struct SDBMHash
{size_t operator()(const std::string& str){size_t ret = 0;for (size_t i = 0; i < str.size(); ++i){ret *= 65599;ret += str[i];}return ret;}
};
struct RSHash
{size_t operator()(const std::string& str){size_t ret = 0;size_t magic = 63689;for (size_t i = 0; i < str.size(); ++i){ret *= magic;ret += str[i];magic *= 378551;}return ret;}
};template<class K = std::string, class Hash1 = BKDRHash, class Hash2 = SDBMHash, class Hash3 = RSHash>
class bloom_filter
{
public:bloom_filter(size_t N)  //大概的数据个数:_bm(5 * N), _N(N*5){}void set(const K& str){size_t index1 = Hash1()(str) % _N;_bm.set(index1);size_t index2 = Hash2()(str) % _N;_bm.set(index2);size_t index3 = Hash3()(str) % _N;_bm.set(index3);}//布隆过滤器不支持删除，因为要置为0的点位有三个，可能与其他元素有重叠的点位bool test(const K& str){size_t index1 = Hash1()(str)%_N;if (_bm.test(index1) == false)return false;size_t index2 = Hash2()(str)%_N;if (_bm.test(index2) == false)return false;size_t index3 = Hash3()(str)%_N;if (_bm.test(index3) == false)return false;return true; // 存在这个值}
private:bitmap _bm;size_t _N;//bloom过滤器的长度
};

常见的字符串哈希算法各种字符串Hash函数 - clq - 博客园

值得注意的是，布隆过滤器并不能支持reset即将一个string1类置为0，因为一个string1对应多个bit位，如果都将其置为0，可能会有string2的比特位与string1的比特位有重叠，这样就可能导致string2被误判为不存在。这样就会破坏布隆过滤器的一个绝对性即：如果test返回false，就一定不存在这个string。

举例一个微信号的例子，每个人的微信号都是唯一的，并且被释放的微信号不支持重新使用，我们就可以合理的猜测，我们的微信号的存储是不是也是在云端用的一个布隆过滤器来存储的？虽然不太可能。

3.优缺点比较

3.1位图的优点

①节省空间，效率高

②可推算出原数据。（或者缺点：数据泄漏）

3.2位图的缺点

只能处理整形

3.3布隆过滤器的优点

①效率高，节省空间

②不可推算原数据

3.4布隆过滤器的缺点

①存在误判，导致不存在的被判为存在

②不支持删除数据的映射。