前言

數(shù)組、鏈表、樹(shù)等數(shù)據(jù)結(jié)構(gòu)會(huì)存儲(chǔ)元素的內(nèi)容，一旦數(shù)據(jù)量過(guò)大，消耗的內(nèi)存也會(huì)呈現(xiàn)線性增長(zhǎng)

所以布隆過(guò)濾器是為了解決數(shù)據(jù)量大的一種數(shù)據(jù)結(jié)構(gòu)

講述布隆過(guò)濾器的時(shí)候需要了解一些預(yù)備的知識(shí)點(diǎn)：比如哈希函數(shù)

1. 預(yù)備知識(shí)

1.1 哈希函數(shù)

哈希函數(shù)指將哈希表中元素的關(guān)鍵鍵值映射為元素存儲(chǔ)位置的函數(shù)

一般的線性表，樹(shù)中，記錄在結(jié)構(gòu)中的相對(duì)位置是隨機(jī)的，即和記錄的關(guān)鍵字之間不存在確定的關(guān)系，因此，在結(jié)構(gòu)中查找記錄時(shí)需進(jìn)行一系列和關(guān)鍵字的比較。這一類查找方法建立在“比較“的基礎(chǔ)上，查找的效率依賴于查找過(guò)程中所進(jìn)行的比較次數(shù)。 理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)

具體其構(gòu)造器的方法有：

直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法等

解決其沖突的方法有：

拉鏈法、多哈希法、開(kāi)放地址法、建域法等

2. 布隆過(guò)濾器

2.1 概念

它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。（位數(shù)組和哈希函數(shù)）

布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。

它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多（更加高效，存儲(chǔ)空間小）

缺點(diǎn)是有一定的誤識(shí)別率和刪除困難

2.2 實(shí)現(xiàn)原理

之所以要用布隆過(guò)濾器，是因?yàn)镠ashMap 的實(shí)現(xiàn)也有缺點(diǎn)，例如存儲(chǔ)容量占比高，考慮到負(fù)載因子的存在，通?？臻g是不能被用滿的，而且數(shù)據(jù)大了之后不可能一次性

比如存儲(chǔ)碼農(nóng)研究僧這個(gè)值，通過(guò)三個(gè)哈希函數(shù)，算得三個(gè)哈希值，存放在3個(gè)位置中（位數(shù)組）

之后判定查詢碼農(nóng)博士僧的時(shí)候，發(fā)現(xiàn)這三個(gè)值只要有1個(gè)沒(méi)有為1，就是沒(méi)存儲(chǔ)到，也就是沒(méi)在集合中

但是如果存儲(chǔ)的值很多，再去查找的時(shí)候，可能會(huì)出現(xiàn)一定的誤判率，導(dǎo)致本身沒(méi)在集合中，但位數(shù)組卻都是1的情況

具體如何選擇上面所說(shuō)的位數(shù)組長(zhǎng)度和哈希函數(shù)的個(gè)數(shù)呢

布隆器如果過(guò)小，導(dǎo)致很多位置都很快是1，誤判率就很很高，如果布隆器過(guò)長(zhǎng)，誤判率會(huì)越小

哈希函數(shù)的個(gè)數(shù)如果過(guò)少，其速度慢，誤判率也高，如果哈希函數(shù)的個(gè)數(shù)過(guò)多，其位1的速度加快，導(dǎo)致布隆過(guò)濾器的效率越低

2.3 步驟

添加元素的具體的步驟是

將添加的元素給k個(gè)哈希函數(shù)算出對(duì)應(yīng)位數(shù)組上的k個(gè)位置，將這k個(gè)位置設(shè)為1

查詢?cè)氐木唧w步驟是

將要查詢的元素給k個(gè)哈希函數(shù)算出對(duì)應(yīng)于位數(shù)組上的k個(gè)位置，如果k個(gè)位置有一個(gè)為0，則肯定不在集合中。如果k個(gè)位置全部為1，則可能在集合中

在計(jì)數(shù)布隆過(guò)濾器中，進(jìn)行刪除的前提是必須保證，值一定存在。因此單通過(guò)布隆過(guò)濾器無(wú)法保證值一定存在。如果通過(guò)其他的方法確認(rèn)值存在后進(jìn)行刪除，則不能保證該值在后續(xù)布隆過(guò)濾器查詢時(shí)一定返回不存在，因?yàn)樵撝迪鄬?duì)應(yīng)的位置并不一定為零。但確實(shí)可以一定概率上優(yōu)化查詢的效率。因此不能說(shuō)計(jì)數(shù)布隆過(guò)濾器支持刪除，應(yīng)該說(shuō)計(jì)數(shù)布隆過(guò)濾器提供了實(shí)現(xiàn)刪除的可能

2.4 實(shí)現(xiàn)

public class MyBloomFilter {
 
    /**
     * 一個(gè)長(zhǎng)度為10 億的比特位
     */
    private static final int DEFAULT_SIZE = 256 << 22;
 
    /**
     * 為了降低錯(cuò)誤率，使用加法hash算法，所以定義一個(gè)8個(gè)元素的質(zhì)數(shù)數(shù)組
     */
    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};
 
    /**
     * 相當(dāng)于構(gòu)建 8 個(gè)不同的hash算法
     */
    private static HashFunction[] functions = new HashFunction[seeds.length];
 
    /**
     * 初始化布隆過(guò)濾器的 bitmap
     */
    private static BitSet bitset = new BitSet(DEFAULT_SIZE);
 
    /**
     * 添加數(shù)據(jù)
     *
     * @param value 需要加入的值
     */
    public static void add(String value) {
        if (value != null) {
            for (HashFunction f : functions) {
                //計(jì)算 hash 值并修改 bitmap 中相應(yīng)位置為 true
                bitset.set(f.hash(value), true);
            }
        }
    }
 
    /**
     * 判斷相應(yīng)元素是否存在
     * @param value 需要判斷的元素
     * @return 結(jié)果
     */
    public static boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (HashFunction f : functions) {
            ret = bitset.get(f.hash(value));
            //一個(gè) hash 函數(shù)返回 false 則跳出循環(huán)
            if (!ret) {
                break;
            }
        }
        return ret;
    }
 
    /**
     * 測(cè)試。。。
     */
    public static void main(String[] args) {
 
        for (int i = 0; i < seeds.length; i++) {
            functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
        }
 
        // 添加1億數(shù)據(jù)
        for (int i = 0; i < 100000000; i++) {
            add(String.valueOf(i));
        }
        String id = "123456789";
        add(id);
 
        System.out.println(contains(id));   // true
        System.out.println("" + contains("234567890"));  //false
    }
}
 
class HashFunction {
 
    private int size;
    private int seed;
 
    public HashFunction(int size, int seed) {
        this.size = size;
        this.seed = seed;
    }
 
    public int hash(String value) {
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i);
        }
        int r = (size - 1) & result;
        return (size - 1) & result;
    }
}

到此這篇關(guān)于Java布隆過(guò)濾器的原理和實(shí)現(xiàn)分析的文章就介紹到這了,更多相關(guān)Java布隆過(guò)濾器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論