這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)布隆過濾器的工作原理是什么，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

目前創(chuàng)新互聯(lián)已為上千多家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)站空間、網(wǎng)站改版維護(hù)、企業(yè)網(wǎng)站設(shè)計(jì)、古丈網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

布隆過濾器

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

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

布隆過濾器的工作原理

假設(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ì)算出來的結(jié)果是獨(dú)立的，可能相同也可能不相同，對(duì)每一個(gè)計(jì)算出來的結(jié)果都對(duì)m取余（%m），然后再將數(shù)組下標(biāo)位置置為1。

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

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

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

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

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

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

m的選取：

k的選?。?/p>

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

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

通過公式計(jì)算出來k=14。

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

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

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

#include <stdio.h>

#define Size 100
#define BitSIZE Size * 4 * 8
//c語言中一個(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";
  
  //在布隆過濾器中插入某值
  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;
}

上述就是小編為大家分享的布隆過濾器的工作原理是什么了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

分享題目：布隆過濾器的工作原理是什么-創(chuàng)新互聯(lián)
地址分享：http://m.rwnh.cn/article2/dddioc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動(dòng)態(tài)網(wǎng)站、虛擬主機(jī)、全網(wǎng)營(yíng)銷推廣、網(wǎng)站營(yíng)銷、品牌網(wǎng)站制作、App開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)