如何在java項(xiàng)目中實(shí)現(xiàn)一個(gè)布隆過濾器-創(chuàng)新互聯(lián)

這篇文章將為大家詳細(xì)講解有關(guān)如何在java 項(xiàng)目中實(shí)現(xiàn)一個(gè)布隆過濾器，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。

成都創(chuàng)新互聯(lián)公司堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站建設(shè)、成都做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的孫吳網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

一.布隆過濾器

布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。

如果想判斷一個(gè)元素是不是在一個(gè)集合里，一般想到的是將集合中所有元素保存起來，然后通過比較確定。鏈表、樹、散列表（又叫哈希表，Hash table）等等數(shù)據(jù)結(jié)構(gòu)都是這種思路。但是隨著集合中元素的增加，我們需要的存儲(chǔ)空間越來越大。同時(shí)檢索速度也越來越慢，上述三種結(jié)構(gòu)的檢索時(shí)間復(fù)雜度分別為：O(n), O(log n), O(n/k)。

布隆過濾器的原理是，當(dāng)一個(gè)元素被加入集合時(shí)，通過K個(gè)Hash函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組中的K個(gè)點(diǎn)，把它們置為1。檢索時(shí)，我們只要看看這些點(diǎn)是不是都是1就（大約）知道集合中有沒有它了：如果這些點(diǎn)有任何一個(gè)0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。

布隆過濾器數(shù)據(jù)結(jié)構(gòu)

布隆過濾器是一個(gè) bit 向量或者說 bit 數(shù)組，長這樣：

如果我們要映射一個(gè)值到布隆過濾器中，我們需要使用多個(gè)不同的哈希函數(shù)生成多個(gè)哈希值，并對(duì)每個(gè)生成的哈希值指向的 bit 位置 1，例如針對(duì)值 “baidu” 和三個(gè)不同的哈希函數(shù)分別生成了哈希值 1、4、7，則上圖轉(zhuǎn)變?yōu)椋?/p>

值得注意的是，4 這個(gè) bit 位由于兩個(gè)值的哈希函數(shù)都返回了這個(gè) bit 位，因此它被覆蓋了?，F(xiàn)在我們?nèi)绻氩樵?“dianping” 這個(gè)值是否存在，哈希函數(shù)返回了 1、5、8三個(gè)值，結(jié)果我們發(fā)現(xiàn) 5 這個(gè) bit 位上的值為 0，說明沒有任何一個(gè)值映射到這個(gè) bit 位上，因此我們可以很確定地說 “dianping” 這個(gè)值不存在。而當(dāng)我們需要查詢 “baidu” 這個(gè)值是否存在的話，那么哈希函數(shù)必然會(huì)返回 1、4、7，然后我們檢查發(fā)現(xiàn)這三個(gè) bit 位上的值均為 1，那么我們可以說 “baidu” 存在了么？答案是不可以，只能是 “baidu” 這個(gè)值可能存在。

這是為什么呢？答案跟簡單，因?yàn)殡S著增加的值越來越多，被置為 1 的 bit 位也會(huì)越來越多，這樣某個(gè)值 “taobao” 即使沒有被存儲(chǔ)過，但是萬一哈希函數(shù)返回的三個(gè) bit 位都被其他值置位了 1 ，那么程序還是會(huì)判斷 “taobao” 這個(gè)值存在。

支持刪除么

目前我們知道布隆過濾器可以支持 add 和 isExist 操作，那么 delete 操作可以么，答案是不可以，例如上圖中的 bit 位 4 被兩個(gè)值共同覆蓋的話，一旦你刪除其中一個(gè)值例如 “tencent” 而將其置位 0，那么下次判斷另一個(gè)值例如 “baidu” 是否存在的話，會(huì)直接返回 false，而實(shí)際上你并沒有刪除它。

如何解決這個(gè)問題，答案是計(jì)數(shù)刪除。但是計(jì)數(shù)刪除需要存儲(chǔ)一個(gè)數(shù)值，而不是原先的 bit 位，會(huì)增大占用的內(nèi)存大小。這樣的話，增加一個(gè)值就是將對(duì)應(yīng)索引槽上存儲(chǔ)的值加一，刪除則是減一，判斷是否存在則是看值是否大于0。

代碼簡單實(shí)現(xiàn)布隆過濾器

package com.jd.demo.test;

import java.util.Arrays;
import java.util.BitSet;
import java.util.concurrent.atomic.AtomicBoolean;

public class MyBloomFilter {
  //你的布隆過濾器容量
  private static final int DEFAULT_SIZE = 2 << 28;
  //bit數(shù)組，用來存放結(jié)果
  private static BitSet bitSet = new BitSet(DEFAULT_SIZE);
  //后面hash函數(shù)會(huì)用到，用來生成不同的hash值，可隨意設(shè)置，別問我為什么這么多8，圖個(gè)吉利
  private static final int[] ints = {1, 6, 16, 38, 58, 68};

  //add方法，計(jì)算出key的hash值，并將對(duì)應(yīng)下標(biāo)置為true
  public void add(Object key) {
    Arrays.stream(ints).forEach(i -> bitSet.set(hash(key, i)));
  }

  //判斷key是否存在，true不一定說明key存在，但是false一定說明不存在
  public boolean isContain(Object key) {
     boolean result = true;
    for (int i : ints) {
    	//短路與，只要有一個(gè)bit位為false，則返回false
      result = result && bitSet.get(hash(key, i));
    }
    return result;
  }

  //hash函數(shù)，借鑒了hashmap的擾動(dòng)算法
  private int hash(Object key, int i) {
    int h;
    return key == null &#63; 0 : (i * (DEFAULT_SIZE - 1) & ((h = key.hashCode()) ^ (h >>> 16)));
  }
}

文章標(biāo)題：如何在java項(xiàng)目中實(shí)現(xiàn)一個(gè)布隆過濾器-創(chuàng)新互聯(lián)
鏈接地址：http://muchs.cn/article36/ddpjpg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供營銷型網(wǎng)站建設(shè)、品牌網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)公司、響應(yīng)式網(wǎng)站、關(guān)鍵詞優(yōu)化、做網(wǎng)站

廣告

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