布隆過濾器的工作原理是什么-創(chuàng)新互聯(lián)

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

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

布隆過濾器

布隆過濾器是一種數(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ù)組下標位置置為1。

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

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

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

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

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

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

m的選?。?/p>

k的選?。?/p>

給個例子：假設(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ù)組下標)
  //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;
}

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

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

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

廣告

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