一.什么是布隆过滤器？
二.布隆过滤器器误判率推导
三.布隆过滤器代码实现
namespace xzy
{
template<size_t N>
class bitset
{
public:
bitset()
{
_bs.resize(N / 32 + 1);
}
void set(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_bs[i] |= (1 << j);
}
void reset(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_bs[i] &= ~(1 << j);
}
bool test(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
return _bs[i] & (1 << j);
}
private:
vector<int> _bs;
};
}
struct HashFuncBKDR
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash *= 31;
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,
size_t X = 5,
class K = string,
class Hash1 = HashFuncBKDR,
class Hash2 = HashFuncAP,
class Hash3 = HashFuncDJB>
class BloomFilter
{
public:
void Set(const K& key)
{
size_t hash1 = Hash1()(key) % M;
size_t hash2 = Hash2()(key) % M;
size_t hash3 = Hash3()(key) % M;
_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;
}
double getFalseProbability()
{
double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);
return p;
}
private:
static const int M = X * N;
xzy::bitset<M> _bs;
};
void TestBloomFilter1()
{
string strs[] = { "百度","字节","腾讯" };
BloomFilter<10> bf;
for (auto& s : strs)
{
bf.Set(s);
}
for (auto& s : strs)
{
cout << bf.Test(s) << endl;
}
for (auto& s : strs)
{
cout << bf.Test(s + 'a') << endl;
}
cout << bf.Test("摆渡") << endl;
cout << bf.Test("百渡") << endl;
}
void TestBloomFilter2()
{
srand(time(0));
const size_t N = 1000000;
BloomFilter<N> bf;
vector<string> v1;
string url = "猪八戒";
for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + to_string(i));
}
for (auto& str : v1)
{
bf.Set(str);
}
v1.clear();
for (size_t i = 0; i < N; ++i)
{
string urlstr = url;
urlstr += to_string(9999999 + i);
v1.push_back(urlstr);
}
size_t n2 = 0;
for (auto& str : v1)
{
if (bf.Test(str))
{
++n2;
}
}
cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
v1.clear();
for (size_t i = 0; i < N; ++i)
{
string url = "孙悟空";
url += to_string(i + rand());
v1.push_back(url);
}
size_t n3 = 0;
for (auto& str : v1)
{
if (bf.Test(str))
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
cout << "公式计算出的误判率:" << bf.getFalseProbability() << endl;
}
int main()
{
TestBloomFilter1();
TestBloomFilter2();
return 0;
}
四.布隆过滤器删除问题
- 布隆过滤器默认是不支持删除的，因为比如"猪八戒"和"孙悟空"都映射在布隆过滤器中，他们映射的位有一个位是共同映射的(冲突的)，如果我们把孙悟空删掉，那么再去查找"猪八戒"会查找不到，因为那么"猪八戒"间接被删掉了。
- 解决方案：可以考虑计数标记的方式，一个位置用多个位标记，记录映射这个位的计数值，删除时，仅仅减减计数，那么就可以某种程度支持删除。但是这个方案也有缺陷，如果一个值不在布隆过滤器中，被误判为在，那么我们去删除，减减了映射位的计数，那么会影响已存在的值，也就是说，一个确定存在的值，可能会变成不存在，这里就很坑。当然也有人提出，我们可以考虑计数方式支持删除，但是定期重建一下布隆过滤器，这样也是一种思路。
五.布隆过滤器的应用
优点：效率高，节省空间，相比位图，可以适用于各种类型的标记过滤。
缺点：存在误判（在是不准确的，不在是准确的），不好支持删除。
布隆过滤器的应用：
- 爬虫系统中URL去重：在爬虫系统中，为了避免重复爬取相同的URL，可以使用布隆过滤器来进行URL去重。爬取到的URL可以通过布隆过滤器进行判断，已经存在的URL则可以直接忽略（可能不在的URL被误判为在，也就是说少爬了一些URL，不过影响不大），避免重复的网络请求和数据处理。
- 垃圾邮件过滤：在垃圾邮件过滤系统中，布隆过滤器可以用来判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件的特征信息存储在布隆过滤器中，当新的邮件到达时，可以通过布隆过滤器快速判断是否为垃圾邮件，从而提高过滤的效率。
- 预防缓存穿透：在分布式缓存系统中，布隆过滤器可以用来解决缓存穿透的问题。数据库上层设置缓存，先到缓存中找数据，若缓存不在，则到数据库中找数据，并将数据库中的数据加载到缓存中，为了下一次查找相同的数据时不用到数据库中查找，提高效率。但是存在缓存穿透问题，缓存穿透是指恶意用户请求一个不存在的数据，导致请求直接访问数据库，造成数据库压力过大。布隆过滤器可以先判断请求的数据是否存在于布隆过滤器中，如果不存在，直接返回不存在，避免对数据库的无效查询。
- 对数据库查询提效：在数据库中，布隆过滤器可以用来加速查询操作。例如：一个app要快速判断一个电话号码是否注册过，可以使用布隆过滤器来判断一个用户电话号码是否存在于表中，如果不存在，可以直接返回不存在，避免对数据库进行无用的查询操作。如果在（存在误判），再去数据库查询进行二次确认。
六.海量数据处理问题
1.10亿个整数中求最大的前100个
2.100亿个整数中，求某个整数是否出现
3.给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？
分析：假设平均每个query字符串50byte，100亿个query就是5000亿byte，约等于500G（1G约等于10亿多Byte）。哈希表/红黑树等数据结构肯定是为力的。
解决方案1：可以用布隆过滤器解决，一个文件中的query放进布隆过滤器，另一个文件依次查找，在的就是交集，问题就是找到交集不够准确，因为在的值可能是误判的，但是交集一定被找到了。
解决方案2：
- 哈希切分，首先内存的访问速度远大于硬盘，大文件放到内存搞不定，那么我们可以考虑切分为小文件，再放进内存处理。
- 但是不要平均切分，因为平均切分以后，每个小文件都需要依次暴力处理，效率还是太低了。
- 可以利用哈希切分，依次读取文件中query，i=HashFunc(query)%N，N为准备切分多少分小文件，N取决于切成多少份，内存能放下，query放进第i号小文件，这样A和B中相同的query算出的hash值i是一样的，相同的query就进入的编号相同的小文件就可以编号相同的文件直接找交集，不用交叉找，效率就提升了。
- 本质是相同的query在哈希切分过程中，一定进入的同一个小文件Ai和Bi，不可能出现A中的某个query进入Ai，但是B中的相同query进入了和Bj的情况，所以对Ai和Bi进行求交集即可，不需要Ai和Bj求交集（i和j是不同的整数）
- 哈希切分的问题就是每个小文件不是均匀切分的，可能会导致某个小文件很大内存放不下。我们细细分析一下某个小文件很大有两种情况：1.这个小文件中大部分是同一个query。2.这个小文件是有很多的不同query构成，本质是这些query冲突了。针对情况1，其实放到内存的set中是可以放下的，因为set是去重的。针对情况2，需要换个哈希函数继续⼆次哈希切分。所以本体我们遇到大于1G小文件，可以继续读到set中找交集，若set insert时抛出了异常(set插入数据抛异常只可能是申请内存失败了，不会有其他情况)，那么就说明内存放不下是情况2，换个哈希函数进行⼆次哈希切分后再对应找交集。
4.给一个超过100G大小的log file，log中存着ip地址，设计算法找到出现次数最多的ip地址？查找出现次数前10的ip地址？
本题的思路跟上题完全类似，依次读取文件A中ip，i=HashFunc(ip)%500，ip放进Ai号小文件，然后依次用map<string，int>对每个Ai小文件统计ip次数，同时求出现次数最多的ip或者topk ip。本质是相同的ip在哈希切分过程中，一定进入同一个小文件Ai，不可能出现同一个ip进入Ai和Aj的情况，所以对Ai进行统计次数就是准确的ip次数。
