bloom filter概念講授和代碼剖析。本站提示廣大學習愛好者：（bloom filter概念講授和代碼剖析）文章只能為提供參考，不一定能成為您想要的結果。以下是bloom filter概念講授和代碼剖析正文
一. 簡介
1.甚麼是bloom filter？
Bloom filter 是由 Howard Bloom 在 1970 年提出的二進制向量數據構造，它具有很好的空間和時光效力，被用來檢測一個元素是否是聚集中的一個成員，這類檢測只會對在聚集內的數據錯判，而不會對不是聚集內的數據停止錯判，如許每一個檢測要求前往有“在聚集內（能夠毛病）”和“不在聚集內（相對不在聚集內）”兩種情形，可見 Bloom filter 是就義了准確率換取時光和空間。
2.bloom filter的盤算辦法？
如須要斷定一個元素是否是在一個聚集中，我們平日做法是把一切元素保留上去，然後經由過程比擬曉得它是否是在聚集內，鏈表、樹都是基於這類思緒，當聚集內元素個數的變年夜，我們須要的空間和時光都線性變年夜，檢索速度也愈來愈慢。 Bloom filter 采取的是哈希函數的辦法，將一個元素映照到一個 m 長度的陣列上的一個點，當這個點是 1 時，那末這個元素在聚集內，反之則不在聚集內。這個辦法的缺陷就是當檢測的元素許多的時刻能夠有抵觸，處理辦法就是應用 k 個哈希 函數對應 k 個點，假如一切點都是 1 的話，那末元素在聚集內，假如有 0 的話，元素則不在聚集內。
3.bloom filter的特色？
Bloom filter 長處就是它的拔出和查詢時光都是常數，別的它查詢元素卻不保留元素自己，具有優越的平安性。它的缺陷也是不言而喻的，當拔出的元素越多，錯判“在聚集內”的幾率就越年夜了，別的 Bloom filter 也不克不及刪除一個元素，由於多個元素哈希的成果能夠在 Bloom filter 構造中占用的是統一個位，假如刪除一個比特位，能夠會影響多個元素的檢測。
二. 代碼完成
現上面在linux下完成了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;
}
// test.c:
#include<stdio.h>
#include<string.h>
#include"bloom.h"
//上面為兩種哈希算法函數
unsigned int sax_hash(const char *key)
{
unsigned int h=0;
while(*key) h^=(h<<5)+(h>>2)+(unsigned char)*key++;
return h;
}
unsigned int sdbm_hash(const char *key)
{
unsigned int h=0;
while(*key) h=(unsigned char)*key++ + (h<<6) + (h<<16) - h;
return h;
}
int main(int argc, char *argv[])
{
FILE *fp;
char line[1024];
char *p;
BLOOM *bloom;
if(argc<2) {
fprintf(stderr, "ERROR: No word file specified\n");
return EXIT_FAILURE;
}
if(!(bloom=bloom_create(2500000, 2, sax_hash, sdbm_hash))) {
fprintf(stderr, "ERROR: Could not create bloom filter\n");
return EXIT_FAILURE;
}
if(!(fp=fopen(argv[1], "r"))) {
fprintf(stderr, "ERROR: Could not open file %s\n", argv[1]);
return EXIT_FAILURE;
}
while(fgets(line, 1024, fp)) {
if((p=strchr(line, '\r'))) *p='\0';//回車
if((p=strchr(line, '\n'))) *p='\0';//換行
bloom_add(bloom, line);
}
fclose(fp);
while(fgets(line, 1024, stdin)) {
if((p=strchr(line, '\r'))) *p='\0';
if((p=strchr(line, '\n'))) *p='\0';
p=strtok(line, " \t,.;:\r\n?!-/()");
while(p) {
if(!bloom_check(bloom, p)) {
printf("No match for ford \"%s\"\n", p);
}
else
printf("match for ford \"%s\"\n",p);
p=strtok(NULL, " \t,.;:\r\n?!-/()");
}
}
bloom_destroy(bloom);
return EXIT_SUCCESS;
}
// Makefile:
all: bloom
bloom: bloom.o test.o
cc -o bloom -Wall -pedantic bloom.o test.o
bloom.o: bloom.c bloom.h
cc -o bloom.o -Wall -pedantic -ansi -c bloom.c
test.o: test.c bloom.h
cc -o test.o -Wall -pedantic -ansi -c test.c
