请用C实现一个布隆过滤器的代码
时间: 2024-05-16 17:15:50 浏览: 14
好的,以下是一个简单的布隆过滤器的 C 代码实现:
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define PRIME_SIZE 10
// 哈希函数,使用 BKDR Hash 算法
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}
// 创建布隆过滤器
bool *createBloomFilter(int size)
{
bool *bloomFilter = (bool *)malloc(size * sizeof(bool));
memset(bloomFilter, false, size * sizeof(bool));
return bloomFilter;
}
// 向布隆过滤器中添加元素
void addElement(bool *bloomFilter, char *str)
{
int i;
unsigned int hash;
for (i = 0; i < PRIME_SIZE; i++)
{
hash = BKDRHash(str) % (i + 1);
bloomFilter[hash] = true;
}
}
// 判断元素是否在布隆过滤器中
bool checkElement(bool *bloomFilter, char *str)
{
int i;
unsigned int hash;
for (i = 0; i < PRIME_SIZE; i++)
{
hash = BKDRHash(str) % (i + 1);
if (!bloomFilter[hash])
{
return false;
}
}
return true;
}
// 测试代码
int main()
{
bool *bloomFilter = createBloomFilter(100);
addElement(bloomFilter, "hello");
addElement(bloomFilter, "world");
addElement(bloomFilter, "bloom");
addElement(bloomFilter, "filter");
printf("check hello: %d\n", checkElement(bloomFilter, "hello"));
printf("check world: %d\n", checkElement(bloomFilter, "world"));
printf("check bloom: %d\n", checkElement(bloomFilter, "bloom"));
printf("check filter: %d\n", checkElement(bloomFilter, "filter"));
printf("check foo: %d\n", checkElement(bloomFilter, "foo"));
return 0;
}
```
在这个实现中,我们使用了 BKDR Hash 算法来计算哈希值。在 `createBloomFilter` 函数中,我们使用了 `malloc` 动态分配了一个布尔数组。在 `addElement` 函数中,我们使用哈希函数计算出元素对应的哈希值,并将对应的布尔数组位置设置为 true。在 `checkElement` 函数中,我们使用哈希函数计算出元素对应的哈希值,并检查对应的布尔数组位置是否为 true。
需要注意的是,在实际使用中,需要选择合适的哈希函数和合适的布隆过滤器大小。
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)