布隆過(guò)濾器

布隆過(guò)濾器是一種數(shù)據(jù)結(jié)構(gòu)，比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure），特點(diǎn)是高效地插入和查詢，可以用來(lái)告訴你 “一定不存在或者可能存在”。

相比于傳統(tǒng)的 List、Set、Map 等數(shù)據(jù)結(jié)構(gòu)，它更高效、占用空間更少，但是缺點(diǎn)是其返回的結(jié)果是概率性的，而不是確切的。

布隆過(guò)濾器的工作原理

假設(shè)一個(gè)長(zhǎng)度為m的bit類型的數(shù)組，即數(shù)組中每個(gè)位置只占一個(gè)bit，每個(gè)bit只有兩種狀態(tài)：0，1，所有bit的初始狀態(tài)都為0。

再假設(shè)一共有k個(gè)哈希函數(shù)，這些函數(shù)的輸出域大于或者等于m，并且這些哈希函數(shù)，彼此之間相互獨(dú)立，每個(gè)哈希函數(shù)計(jì)算出來(lái)的結(jié)果是獨(dú)立的，可能相同也可能不相同，對(duì)每一個(gè)計(jì)算出來(lái)的結(jié)果都對(duì)m取余（%m），然后再將數(shù)組下標(biāo)位置置為1。

我們這里假設(shè)m為13,k為3的布隆過(guò)濾器，來(lái)看看布隆過(guò)濾器的工作原理：

當(dāng)我們要映射一個(gè)值到布隆過(guò)濾器時(shí)，首先計(jì)算三個(gè)哈希函數(shù)的值，然后對(duì)13取余，映射到對(duì)應(yīng)位中，圖中映射到2，6，10，這樣我們就完成了一個(gè)值的映射。

那么怎么判斷一個(gè)值是否存在，當(dāng)一個(gè)值輸入時(shí)，通過(guò)三個(gè)哈希函數(shù)，然后取余，我們就可以得到對(duì)應(yīng)的三個(gè)位置，我們只需要判斷這三個(gè)位置是否都為1，如果都為1，則該值存儲(chǔ)，反之不存在。

但是有一個(gè)特殊情況，前面說(shuō)了不同的哈希函數(shù)可能計(jì)算可能相同也可能不相同，而且不同的哈希函數(shù)對(duì)不同的值計(jì)算出來(lái)的值可能一樣，這就造成一個(gè)結(jié)果，一個(gè)值通過(guò)哈希和取余得到的位置，早就被其它值給置1了，當(dāng)我們存儲(chǔ)的值過(guò)多，而這個(gè)bit數(shù)組過(guò)小，都會(huì)造成這種情況更多的發(fā)生，一個(gè)值明明不存在，而它的所有位置早就被其它不同值置1，造成了誤判，這里就對(duì)布隆過(guò)濾器提出了一個(gè)指標(biāo)：失誤率p。

在同樣數(shù)據(jù)規(guī)模下，不同大小的bit數(shù)組及不同數(shù)量k的哈希函數(shù)對(duì)誤判率的結(jié)果：

如何選取最合適的m（bit數(shù)組的大小）及k（哈希函數(shù)的數(shù)量），在已知n（需要映射的值得數(shù)量）及失誤率p的情況下：

m的選取：

k的選?。?/p>

給個(gè)例子：假設(shè)n=100億，p=0.01%

通過(guò)公式計(jì)算出來(lái)m=19.19n，向上取整位20n，即2000億個(gè)bit，也就是25gb。

通過(guò)公式計(jì)算出來(lái)k=14。

計(jì)算真實(shí)失誤率：

根據(jù)公式計(jì)算出來(lái)的真實(shí)失誤率位0.006%。

c語(yǔ)言實(shí)現(xiàn)

#include <stdio.h>

#define Size 100
#define BitSIZE Size * 4 * 8
//c語(yǔ)言中一個(gè)整型數(shù)據(jù)類型4個(gè)字節(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";
  
  //在布隆過(guò)濾器中插入某值
  Insert(SDBMHash(str1));
  Insert(RSHash(str1));
  Insert(JSHash(str1));
  
  //在布隆過(guò)濾器中判斷某值是否存在
  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;
}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。