|
前言 Hello，大家好，欢迎来到我的 C++ 系列专题！今天的主题是布隆过滤器。 如果你没听过布隆过滤器，没关系，先来看这样一个问题：“如何从上亿条数据中查找某个记录是否存在？”你很容易想到的是数据库或者哈希表。数据库就不说了，我们来谈谈哈希表。了解过哈希表的同学都知道，哈希节点里存储了 key 和 value。如果每个节点里的 key 和 value 占用 10 个字节，那么 1 亿条数据大约就要占用 1G，对于现代计算机来说， 1G 其实不算大，但是它还是消耗了太多内存，有没有更好的解决方案呢？答案就是布隆过滤器。 布隆过滤器 布隆过滤器的实现依赖 bitset，关于什么是 bitset，请翻阅本专题系列之前的文章。 假设系统的最大数据量为 1 亿，定义一个长度为 5 亿的 bit 数组。选择一个哈希冲突比较小的哈希函数计算每一个数据的哈希值，并设置 bit 数组相应哈希值位置的值为1。为了避免哈希冲突，我们用多个不同的哈希函数来计算同一个数据，来产生不同的哈希值，同时把这多个哈希值对应的数组位置都置为1。为什么定义一个长度为 5 亿的 bitset，而不是 1 亿呢？ 这也是为了减小冲突的一种方式（容量越大，冲突越小）。当一个 1 亿条数据量级，5 亿的 bit 数组占用内存才几百 M 而已，比哈希表要小一个数量级。 布隆过滤器的 C++ 实现 #include <iostream>#include <bitset>#include <array>#include <string>#include <sstream>class Entity {};class BloomFilter {public: std::bitset<20> bits;public: BloomFilter () { bits.reset(); } void Set(std::string& key) { int idx1 = Hash1(key); int idx2 = Hash2(key); int idx3 = Hash3(key); int idx4 = Hash4(key); bits[idx1] = 1; bits[idx2] = 1; bits[idx3] = 1; bits[idx4] = 1; } bool Get(std::string& key) { int idx1 = Hash1(key); int idx2 = Hash2(key); int idx3 = Hash3(key); int idx4 = Hash4(key); return bits[idx1] && bits[idx2] && bits[idx3] && bits[idx4]; } int Hash1(std::string& key) { int hash = 5381; unsigned long count = key.size(); while (count > 0) { hash += (hash << 5) + key[key.size() - count]; count--; } return (hash & 0x7FFFFFFF) % bits.size(); } int Hash2(std::string& key) { int seed = 131; int hash = 0; std::string str = key + 'key2'; unsigned long count = str.size(); while(count > 0) { hash = hash * seed + str[str.size() - count]; count--; } return (hash & 0x7FFFFFFF) % bits.size(); } int Hash3(std::string& key) { int hash = 0; std::string str = key + 'keykey3'; unsigned long count = str.size(); for (int i = 0; i < count; i++) { if ((i * 1) == 0) { hash ^= ((hash << 7) ^ (str[i] ^ hash >> 3)); } else { hash ^= (~((hash << 11) ^ (str[i]) ^ (hash >> 5))); } count--; } return (hash & 0x7FFFFFFF) % bits.size(); } int Hash4(std::string key) { int hash = 5381; std::string str = key + 'keykeykey4'; unsigned long count = str.size(); while(count > 0) { hash += (hash << 5) + (str[str.size() - count]); count--; } return (hash & 0x7FFFFFFF) % bits.size(); }};int main(){ // 插入 hash 节点 BloomFilter bf; Entity e1, e2; std::ostringstream oss; // 任意类型转为 string 类型 oss << &e1; std::string s1 = oss.str(); if (bf.Get(s1) == true) { std::cout << 'objecy e1 has existed!' << std::endl; } else { std::cout << 'insert object e1' << std::endl; bf.Set(s1); std::cout << bf.bits << std::endl; } std::ostringstream oss2; // 任意类型转为 string 类型 oss2 << &e2; std::string s2 = oss2.str(); if (bf.Get(s2) == true) { std::cout << 'objecy e2 has existed!' << std::endl; } else { std::cout << 'insert object e2' << std::endl; bf.Set(s1); std::cout << bf.bits << std::endl; } // 查找指定对象是否在数据库中 if (bf.Get(s1) == true) { std::cout << 'objecy e1 has existed!' << std::endl; } else { std::cout << 'object e1 not existing' << std::endl; } std::cin.get();} 布隆过滤器示例 总结
|
|
|
