bloom filter概念講解以及代碼分析
一. 簡(jiǎn)介
1.什么是bloom filter？
Bloom filter 是由 Howard Bloom 在 1970 年提出的二進(jìn)制向量數(shù)據(jù)結(jié)構(gòu)，它具有很好的空間和時(shí)間效率，被用來(lái)檢測(cè)一個(gè)元素是不是集合中的一個(gè)成員，這種檢測(cè)只會(huì)對(duì)在集合內(nèi)的數(shù)據(jù)錯(cuò)判，而不會(huì)對(duì)不是集合內(nèi)的數(shù)據(jù)進(jìn)行錯(cuò)判，這樣每個(gè)檢測(cè)請(qǐng)求返回有“在集合內(nèi)（可能錯(cuò)誤）”和“不在集合內(nèi)（絕對(duì)不在集合內(nèi)）”兩種情況，可見(jiàn) Bloom filter 是犧牲了正確率換取時(shí)間和空間。
2.bloom filter的計(jì)算方法？
如需要判斷一個(gè)元素是不是在一個(gè)集合中，我們通常做法是把所有元素保存下來(lái)，然后通過(guò)比較知道它是不是在集合內(nèi)，鏈表、樹(shù)都是基于這種思路，當(dāng)集合內(nèi)元素個(gè)數(shù)的變大，我們需要的空間和時(shí)間都線性變大，檢索速度也越來(lái)越慢。 Bloom filter 采用的是哈希函數(shù)的方法，將一個(gè)元素映射到一個(gè) m 長(zhǎng)度的陣列上的一個(gè)點(diǎn)，當(dāng)這個(gè)點(diǎn)是 1 時(shí)，那么這個(gè)元素在集合內(nèi)，反之則不在集合內(nèi)。這個(gè)方法的缺點(diǎn)就是當(dāng)檢測(cè)的元素很多的時(shí)候可能有沖突，解決方法就是使用 k 個(gè)哈希 函數(shù)對(duì)應(yīng) k 個(gè)點(diǎn)，如果所有點(diǎn)都是 1 的話，那么元素在集合內(nèi)，如果有 0 的話，元素則不在集合內(nèi)。
3.bloom filter的特點(diǎn)？
Bloom filter 優(yōu)點(diǎn)就是它的插入和查詢時(shí)間都是常數(shù)，另外它查詢?cè)貐s不保存元素本身，具有良好的安全性。它的缺點(diǎn)也是顯而易見(jiàn)的，當(dāng)插入的元素越多，錯(cuò)判“在集合內(nèi)”的概率就越大了，另外 Bloom filter 也不能刪除一個(gè)元素，因?yàn)槎鄠€(gè)元素哈希的結(jié)果可能在 Bloom filter 結(jié)構(gòu)中占用的是同一個(gè)位，如果刪除了一個(gè)比特位，可能會(huì)影響多個(gè)元素的檢測(cè)。
二. 代碼實(shí)現(xiàn)
現(xiàn)下面在linux下實(shí)現(xiàn)了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"
//下面為兩種哈希算法函數(shù)
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
相關(guān)文章
FFmpeg實(shí)現(xiàn)多線程編碼并保存mp4文件
這篇文章主要為大家介紹了FFmpeg如何持續(xù)的從指定內(nèi)存中讀取原始數(shù)據(jù),再將解碼數(shù)據(jù)存入隊(duì)列中,并通過(guò)單獨(dú)的線程進(jìn)行編碼,最后保存為mp4文件,感興趣的可以了解下2023-08-08
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言打印輸出楊輝三角，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-12-12
C語(yǔ)言中for循環(huán)問(wèn)題（一個(gè)小坑需注意）
這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中for循環(huán)問(wèn)題的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
C++ windows LOG4plus的使用小結(jié)
這篇文章主要介紹了C++ windows LOG4plus的使用小結(jié),本文通過(guò)圖文示例代碼相結(jié)合給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧2024-05-05
Cocos2d-x中CCEditBox文本輸入框的使用實(shí)例
這篇文章主要介紹了Cocos2d-x中CCEditBox文本輸入框的使用實(shí)例,本文在代碼中用大量注釋講解了CCEditBox的使用方法,需要的朋友可以參考下2014-09-09
C++實(shí)現(xiàn)將s16le的音頻流轉(zhuǎn)換為float類型
這篇文章主要為大家詳細(xì)介紹了如何利用C++實(shí)現(xiàn)將s16le的音頻流轉(zhuǎn)換為float類型，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起了解一下2023-04-04
c++類型轉(zhuǎn)換及RTTI運(yùn)行階段類型識(shí)別
這篇文章主要為大家介紹了c++類型轉(zhuǎn)換及RTTI運(yùn)行階段類型識(shí)別詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪2023-05-05
C++標(biāo)準(zhǔn)模板庫(kù)map的常用操作
今天小編就為大家分享一篇關(guān)于C++標(biāo)準(zhǔn)模板庫(kù)map的常用操作，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2018-12-12
Boost是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱。Boost庫(kù)是一個(gè)可移植、提供源代碼的C++庫(kù)，作為標(biāo)準(zhǔn)庫(kù)的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開(kāi)發(fā)引擎之一，是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱2022-11-11
這篇文章主要為大家詳細(xì)介紹了C++帶有指針成員的類處理方式，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-08-08