布隆過濾器
布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)，比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure），特點是高效地插入和查詢，可以用來告訴你 “一定不存在或者可能存在”。
相比于傳統(tǒng)的 List、Set、Map 等數(shù)據(jù)結(jié)構(gòu)，它更高效、占用空間更少，但是缺點是其返回的結(jié)果是概率性的，而不是確切的。
布隆過濾器的工作原理
假設(shè)一個長度為m的bit類型的數(shù)組，即數(shù)組中每個位置只占一個bit，每個bit只有兩種狀態(tài)：0，1，所有bit的初始狀態(tài)都為0。
再假設(shè)一共有k個哈希函數(shù)，這些函數(shù)的輸出域大于或者等于m，并且這些哈希函數(shù)，彼此之間相互獨立，每個哈希函數(shù)計算出來的結(jié)果是獨立的，可能相同也可能不相同，對每一個計算出來的結(jié)果都對m取余（%m），然后再將數(shù)組下標(biāo)位置置為1。
我們這里假設(shè)m為13,k為3的布隆過濾器，來看看布隆過濾器的工作原理：
當(dāng)我們要映射一個值到布隆過濾器時，首先計算三個哈希函數(shù)的值，然后對13取余，映射到對應(yīng)位中，圖中映射到2，6，10，這樣我們就完成了一個值的映射。
那么怎么判斷一個值是否存在，當(dāng)一個值輸入時，通過三個哈希函數(shù)，然后取余，我們就可以得到對應(yīng)的三個位置，我們只需要判斷這三個位置是否都為1，如果都為1，則該值存儲，反之不存在。
但是有一個特殊情況，前面說了不同的哈希函數(shù)可能計算可能相同也可能不相同，而且不同的哈希函數(shù)對不同的值計算出來的值可能一樣，這就造成一個結(jié)果，一個值通過哈希和取余得到的位置，早就被其它值給置1了，當(dāng)我們存儲的值過多，而這個bit數(shù)組過小，都會造成這種情況更多的發(fā)生，一個值明明不存在，而它的所有位置早就被其它不同值置1，造成了誤判，這里就對布隆過濾器提出了一個指標(biāo)：失誤率p。
在同樣數(shù)據(jù)規(guī)模下，不同大小的bit數(shù)組及不同數(shù)量k的哈希函數(shù)對誤判率的結(jié)果：
如何選取最合適的m（bit數(shù)組的大小）及k（哈希函數(shù)的數(shù)量），在已知n（需要映射的值得數(shù)量）及失誤率p的情況下：
m的選取：
k的選取：
給個例子：假設(shè)n=100億，p=0.01%
通過公式計算出來m=19.19n，向上取整位20n，即2000億個bit，也就是25gb。
通過公式計算出來k=14。
計算真實失誤率：
根據(jù)公式計算出來的真實失誤率位0.006%。
c語言實現(xiàn)
#include stdio.h>
#define Size 100
#define BitSIZE Size * 4 * 8
//c語言中一個整型數(shù)據(jù)類型4個字節(jié)
int bit[Size]={0};
int SDBMHash(char *str)
{
unsigned int hash = 0;
while (*str)
{
// equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash 6) + (hash 16) - hash;
}
return (hash 0x7FFFFFFF);
}
int RSHash(char *str)
{
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;
while (*str)
{
hash = hash * a + (*str++);
a *= b;
}
return (hash 0x7FFFFFFF);
}
int JSHash(char *str)
{
unsigned int hash = 1315423911;
while (*str)
{
hash ^= ((hash 5) + (*str++) + (hash >> 2));
}
return (hash 0x7FFFFFFF);
}
void Insert(int hash){
//int value = hash%BitSIZE; ([0-3200]范圍的值)
//int listindex = value / 32; (listindex為數(shù)組下標(biāo))
//int bitindex = value % 32; (某位)
int value = hash%BitSIZE;
int listindex = value / 32;
int bitindex = value % 32;
int temp = bit[listindex];
bit[listindex] = bit[listindex] (1 bitindex);
bit[listindex] = bit[listindex] | temp;
}
int Serach(int hash){
int value = hash%BitSIZE;
int listindex = value / 32;
int bitindex = value % 32;
if (bit[listindex] | (1 bitindex)){
return 1;
}
return 0;
}
int main () {
char str1[] = "abc123";
//在布隆過濾器中插入某值
Insert(SDBMHash(str1));
Insert(RSHash(str1));
Insert(JSHash(str1));
//在布隆過濾器中判斷某值是否存在
int i = 0;
i = i+Serach(SDBMHash(str1));
i = i+Serach(RSHash(str1));
i = i+Serach(JSHash(str1));
if(i == 3){
printf("字符串：%s存在\n",str1);
}
return 0;
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:- 布隆過濾器的概述及Python實現(xiàn)方法
- Python+Redis實現(xiàn)布隆過濾器
- python實現(xiàn)布隆過濾器及原理解析
- Java實現(xiàn)布隆過濾器的方法步驟
- JAVA實現(xiàn)較完善的布隆過濾器的示例代碼
- Redis 中的布隆過濾器的實現(xiàn)
- C++ 數(shù)據(jù)結(jié)構(gòu)之布隆過濾器
- 布隆過濾器(Bloom Filter)的Java實現(xiàn)方法
