自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

如何快速檢查元素是否存在?

開發(fā) 前端
BloomFilter雖然看起來簡單,但是其內(nèi)部的實現(xiàn)包含了很多的數(shù)學(xué)與算法知識,我們只是通過其簡單的API就能各種復(fù)雜的功能。關(guān)于如何將目前說到的這些在具體的項目中進行實踐與集成 后面會來介紹,首先我們能夠先了解一些技術(shù)一起能解決上面問題,理解了原理與目的,使用也就不是難事。

大家好,我是指北君。

如標(biāo)題一樣,我們今天看一下一個經(jīng)常聽到,可能沒用到的技術(shù)。

Guava BloomFilter

布隆過濾器是一個很長的二進制向量和一系列隨機映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都比一般的算法要好的多,缺點是有一定的誤識別率和刪除困難。

基本概念

當(dāng)需要判斷某個元素是否在某個數(shù)據(jù)集中時,一般會怎么做?

將數(shù)據(jù)集封裝成集合,比如List、Set等

通過集合提供的API判斷該元素是否存在于集合

這樣的實現(xiàn)比較簡單,同時通過現(xiàn)有的JDK都能很快達到目的,但是設(shè)想一下,如果上面說到的集合數(shù)據(jù)量非常的大,這樣不僅會耗費較大的存儲空間,同時 在集合中檢索元素的時間復(fù)雜度也會隨之增加。那么有沒比較好的方法去實現(xiàn)判斷元素是否存在這樣的情形呢?

也就是布隆過濾器。

通過一系列的Hash函數(shù)將元素映射到一個位陣列(Bit Array)中的多個點位上,判斷元素是否存在,則是判斷所有點位是不是都為1。然而,位陣列上都為1并不一定能夠保證該元素一定存在,也有可能是其他元素Hash后落在了該點位上,這就是布隆過濾器的誤判。

因此通過布隆過濾器我們可以確定:

  • 元素可能在集合中
  • 元素一定不在集合中

應(yīng)用場景

  • 網(wǎng)頁爬蟲時忽略已經(jīng)判定的URL路徑
  • 郵箱通過設(shè)置過濾垃圾郵件
  • 集合重復(fù)元素的判別,有效判斷元素不在集合中
  • 防止數(shù)據(jù)緩存時的緩存穿透問題

優(yōu)缺點

  • 優(yōu)點

相比于其它的數(shù)據(jù)結(jié)構(gòu),布隆過濾器在空間和時間方面都有巨大的優(yōu)勢。

布隆過濾器存儲空間和插入/查詢時間都是常數(shù)。

Hash函數(shù)相互之間沒有關(guān)系,方便由硬件并行實現(xiàn)。

布隆過濾器不需要存儲元素本身,對保密要求非常嚴格的場合有優(yōu)勢。

布隆過濾器可以表示全集,其它任何數(shù)據(jù)結(jié)構(gòu)都不能。

  • 缺點

元素存在的誤判

一般情況下不支持元素(位陣列)的刪除

實現(xiàn)原理

圖片

核心其實是元素如何存儲?如何判斷元素是否存在?核心方法就兩個,一個“存”一個檢查,里面涉及到了算法相關(guān)知識,感興趣可以深入研究下其實現(xiàn)原理與思想。

  • put 將元素放入過濾器中,但不是存儲
        public <T> boolean put(@ParametricNullness T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
long bitSize = bits.bitSize(); // 位數(shù)組,可以通過redis來實現(xiàn)分布式的布隆過濾器
long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong(); //通過funnel將對象轉(zhuǎn)換成基本類型并計算64位hash
int hash1 = (int)hash64; // 取低32位
int hash2 = (int)(hash64 >>> 32); // 取高32位
boolean bitsChanged = false;
//
for(int i = 1; i <= numHashFunctions; ++i) {
int combinedHash = hash1 + i * hash2;
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}

bitsChanged |= bits.set((long)combinedHash % bitSize);
}

return bitsChanged;
}
  • mightContain 與put相似,計算的過程相同,不同的是值的判斷
        public <T> boolean mightContain(@ParametricNullness T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
long bitSize = bits.bitSize();
long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
int hash1 = (int)hash64;
int hash2 = (int)(hash64 >>> 32);

for(int i = 1; i <= numHashFunctions; ++i) {
int combinedHash = hash1 + i * hash2;
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}

if (!bits.get((long)combinedHash % bitSize)) {
return false;
}
}

return true;
}

我們可以簡單第理解其實現(xiàn)原理?比如現(xiàn)在有一個容器,我們定義為String[] bitArray = new String[26]作為位陣列, 現(xiàn)在有一堆由小寫英文組成的元素,我們假定Hash算法為a-z到1~26的映射。

  • 現(xiàn)在有一個元素abc,hash后為1110000000...,保存到bitArray :1110000000...
  • 現(xiàn)在有一個元素cde, hash后為0011100000...,保存到bitArray :1111100000...
  • 現(xiàn)在又有一個新的元素ade,hash后同樣為100110000...,很明顯會認為該元素存在,這就是FFP

為什么判斷元素一定不在集合中呢?很顯然,如果一個元素存在,則該元素hash后的bit數(shù)組必須全部都是1,反之則不存在

示例

    @Test
public void match(){
BloomFilter filter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),10000,0.2);
List<String> ids = new ArrayList<>();

IntStream.rangeClosed(1,10000).forEach(index->{
String id = UUID.randomUUID().toString();
ids.add(id);
filter.put( id );
});

ids.forEach(id->{
// 正常情況下全部失敗,但是會有 20%的返回true
System.out.println( id + ":" + filter.mightContain( id+1 ));
});
}

流程很簡單:

  • 根據(jù)配置構(gòu)建BloomFilter對象
  • 通過put方法,初始化數(shù)據(jù)到filter
  • 通過方法mightContain判斷元素是否存在

結(jié)束語

BloomFilter雖然看起來簡單,但是其內(nèi)部的實現(xiàn)包含了很多的數(shù)學(xué)與算法知識,我們只是通過其簡單的API就能各種復(fù)雜的功能。關(guān)于如何將目前說到的這些在具體的項目中進行實踐與集成 后面會來介紹,首先我們能夠先了解一些技術(shù)一起能解決上面問題,理解了原理與目的,使用也就不是難事。

責(zé)任編輯:武曉燕 來源: Java技術(shù)指北
相關(guān)推薦

2023-02-01 15:00:45

2009-12-01 09:13:51

shell腳本linux

2024-02-05 13:37:16

Go語言方法

2018-03-22 19:30:26

LinuxMeltdownSpectre

2018-12-14 09:16:31

裝載數(shù)據(jù)數(shù)組

2021-04-22 06:03:17

SonarQube檢查項目CI

2018-12-14 09:32:06

億級數(shù)據(jù)存在

2019-08-23 06:22:47

LinuxShell監(jiān)控腳本

2011-05-25 10:46:39

Javascript

2021-11-02 19:01:41

WWWGrepHTML安全安全工具

2023-10-30 10:40:29

檢查用戶app注冊數(shù)據(jù)庫

2023-09-04 10:10:47

插件頁面元素

2018-06-12 11:12:09

2019-10-25 22:06:38

服務(wù)器開發(fā)工具

2024-01-17 17:36:06

Linuxsystemd

2011-06-08 10:11:25

JavaScript

2020-12-31 08:00:00

機器學(xué)習(xí)人工智能工程師

2021-01-28 07:52:39

JS數(shù)組變量

2019-10-16 15:50:53

Windows10PC藍牙

2019-04-23 09:27:32

Linux端口
點贊
收藏

51CTO技術(shù)棧公眾號