Bloom Filter是1970年由Bloom提出的，最初广泛用于拼写检查和数据库系统中。近年来，随着计算机和互联网技术的发展，数据集的不断扩张使得 Bloom filter获得了新生，各种新的应用和变种不断涌现。Bloom filter是一个空间效率很高的数据结构，它由一个位数组和一组hash映射函数组成。Bloom filter可以用于检索一个元素是否在一个集合中，它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
/* bloom.h */#ifndef __BLOOM_H__#define __BLOOM_H__#include<stdlib.h>typedef unsigned int (*hashfunc_t)(const char *);typedef struct {size_t asize;unsigned char *a;size_t nfuncs;hashfunc_t *funcs;} BLOOM;BLOOM *bloom_create(size_t size, size_t nfuncs, ...);int bloom_destroy(BLOOM *bloom);int bloom_add(BLOOM *bloom, const char *s);int bloom_check(BLOOM *bloom, const char *s);#endif/* bloom.c */#include<limits.h>#include<stdarg.h>#include"bloom.h"#define SETBIT(a, n) (a[n/CHAR_BIT] |= (1<<(n%CHAR_BIT)))#define GETBIT(a, n) (a[n/CHAR_BIT] & (1<<(n%CHAR_BIT)))BLOOM *bloom_create(size_t size, size_t nfuncs, ...){BLOOM *bloom;va_list l;int n;if(!(bloom=malloc(sizeof(BLOOM)))) return NULL;if(!(bloom->a=calloc((size+CHAR_BIT-1)/CHAR_BIT, sizeof(char)))) {free(bloom);return NULL;}if(!(bloom->funcs=(hashfunc_t*)malloc(nfuncs*sizeof(hashfunc_t)))) {free(bloom->a);free(bloom);return NULL;}va_start(l, nfuncs);for(n=0; n<nfuncs; ++n) {bloom->funcs[n]=va_arg(l, hashfunc_t);}va_end(l);bloom->nfuncs=nfuncs;bloom->asize=size;return bloom;}int bloom_destroy(BLOOM *bloom){free(bloom->a);free(bloom->funcs);free(bloom);return 0;}int bloom_add(BLOOM *bloom, const char *s){size_t n;for(n=0; n<bloom->nfuncs; ++n) {SETBIT(bloom->a, bloom->funcs[n](s)%bloom->asize);}return 0;}int bloom_check(BLOOM *bloom, const char *s){size_t n;for(n=0; n<bloom->nfuncs; ++n) {if(!(GETBIT(bloom->a, bloom->funcs[n](s)%bloom->asize))) return 0;}return 1;}新闻热点
疑难解答
