C语言实现布隆过滤器

C言可以通过位操作和哈希函数来实现布隆过滤器。下面是一个简单的示代码：

#include <stdio.h>
#include <stdbool.h>

#define FILTER_SIZE 10

typedef struct {
    unsigned char bits[FILTER_SIZE];
} BloomFilter;

void set_bit(BloomFilter *filter, int index) {
    int byte_index = index / 8;
    int bit_index = index % 8;
    filter->bits[byte_index] |= (1 << bit_index);
}

bool get_bit(BloomFilter *filter, int index) {
    int byte_index = index / 8;
    int bit_index = index % 8;
    return (filter->bits[byte_index] >> bit_index) & 1;
}

void add_element(BloomFilter *filter, int element) {
    // 使用不同的哈希函数生成多个哈希值
    int hash1 = element % FILTER_SIZE;
    int hash2 = (element / FILTER_SIZE) % FILTER_SIZE;
    
    set_bit(filter, hash1);
    set_bit(filter, hash2);
}

bool contains_element(BloomFilter *filter, int element) {
    int hash1 = element % FILTER_SIZE;
    int hash2 = (element / FILTER_SIZE) % FILTER_SIZE;
    
    // 只要有一个位为0，说明元素一定不存在
    if (!get_bit(filter, hash1)) {
        return false;
    }
    
    if (!get_bit(filter, hash2)) {
        return false;
    }
    
    return true;
}

int main() {
    BloomFilter filter;
    
    // 初始化布隆过滤器
    for (int i = 0; i < FILTER_SIZE; i++) {
        filter.bits[i] = 0;
    }
    
    // 添加元素
    add_element(&filter, 123);
    add_element(&filter, 456);
    
    // 检查元素是否存在
    printf("Contains 123: %d\n", contains_element(&filter, 123));
    printf("Contains 789: %d\n", contains_element(&filter, 789));
    
    return 0;
}