Bloom Filter模拟的C++代码实现
时间: 2023-11-14 09:11:00 浏览: 42
以下是Bloom Filter的C++代码实现:
```c++
#include <bitset>
#include <iostream>
#include <string>
using namespace std;
// Bloom Filter类
class BloomFilter {
private:
bitset<1000000> bloom; // 位向量
int hash(string key, int seed) { // 计算哈希值
int hash = seed;
for (int i = 0; i < key.length(); i++) {
hash = hash * 131 + key[i];
}
return hash;
}
public:
void insert(string key) { // 插入元素
int seed[4] = {5, 7, 11, 13};
for (int i = 0; i < 4; i++) {
int hashcode = hash(key, seed[i]);
bloom.set(hashcode % bloom.size()); // 将对应位置设为1
}
}
bool contains(string key) { // 判断元素是否存在
int seed[4] = {5, 7, 11, 13};
for (int i = 0; i < 4; i++) {
int hashcode = hash(key, seed[i]);
if (!bloom.test(hashcode % bloom.size())) { // 如果对应位置为0,则元素不存在
return false;
}
}
return true;
}
};
int main() {
BloomFilter bf;
bf.insert("hello");
bf.insert("world");
cout << bf.contains("hello") << endl; // 输出1,表示元素存在
cout << bf.contains("world") << endl; // 输出1,表示元素存在
cout << bf.contains("hi") << endl; // 输出0,表示元素不存在
return 0;
}
```
代码中使用`std::bitset`来实现位向量,其中`bloom.set()`函数将对应位置设为1,`bloom.test()`函数用于判断对应位置是否为1。哈希函数使用了四个不同的种子,计算出对应的哈希值,并将对应位置设为1。在插入和查询元素时,都需要使用相同的哈希函数和种子。