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;}新聞熱點
疑難解答
