日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

創(chuàng)新互聯(lián)長期為上1000家客戶提供的網站建設服務，團隊從業(yè)經驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網生態(tài)環(huán)境。為寧河企業(yè)提供專業(yè)的網站制作、網站設計，寧河網站改版等技術服務。擁有10年豐富建站經驗和眾多成功案例,為您定制開發(fā)。

相比于 Set 集合的去重功能而言，布隆過濾器在空間上能節(jié)省 90% 以上，但是它的不足之處是去重率大約在 99% 左右，也就是說有 1% 左右的誤判率，這種誤差是由布隆過濾器的自身結構決定的。俗話說“魚與熊掌不可兼得”，如果想要節(jié)省空間，就需要犧牲 1% 的誤判率，而且這種誤判率，在處理海量數(shù)據(jù)時，幾乎可以忽略。

應用場景

布隆過濾器是 Redis 的高級功能，雖然這種結構的去重率并不完全精確，但和其他結構一樣都有特定的應用場景，比如當處理海量數(shù)據(jù)時，就可以使用布隆過濾器實現(xiàn)去重。

下面舉兩個簡單的例子：

1) 示例：

百度爬蟲系統(tǒng)每天會面臨海量的 URL 數(shù)據(jù)，我們希望它每次只爬取最新的頁面，而對于沒有更新過的頁面則不爬取，因策爬蟲系統(tǒng)必須對已經抓取過的 URL 去重，否則會嚴重影響執(zhí)行效率。但是如果使用一個 set（集合）去裝載這些 URL 地址，那么將造成資源空間的嚴重浪費。

2) 示例：

垃圾郵件過濾功能也采用了布隆過濾器。雖然在過濾的過程中，布隆過濾器會存在一定的誤判，但比較于犧牲寶貴的性能和空間來說，這一點誤判是微不足道的。

工作原理

布隆過濾器（Bloom Filter）是一個高空間利用率的概率性數(shù)據(jù)結構，由二進制向量（即位數(shù)組）和一系列隨機映射函數(shù)（即哈希函數(shù)）兩部分組成。

布隆過濾器使用
exists()來判斷某個元素是否存在于自身結構中。當布隆過濾器判定某個值存在時，其實這個值只是有可能存在；當它說某個值不存在時，那這個值肯定不存在，這個誤判概率大約在 1% 左右。

1) 工作流程-添加元素

布隆過濾器主要由位數(shù)組和一系列 hash 函數(shù)構成，其中位數(shù)組的初始狀態(tài)都為 0。

下面對布隆過濾器工作流程做簡單描述，如下圖所示：

當使用布隆過濾器添加 key 時，會使用不同的 hash 函數(shù)對 key 存儲的元素值進行哈希計算，從而會得到多個哈希值。根據(jù)哈希值計算出一個整數(shù)索引值，將該索引值與位數(shù)組長度做取余運算，最終得到一個位數(shù)組位置，并將該位置的值變?yōu)?1。每個 hash 函數(shù)都會計算出一個不同的位置，然后把數(shù)組中與之對應的位置變?yōu)?1。通過上述過程就完成了元素添加(add)操作。

2) 工作流程-判定元素是否存在

當我們需要判斷一個元素是否存時，其流程如下：首先對給定元素再次執(zhí)行哈希計算，得到與添加元素時相同的位數(shù)組位置，判斷所得位置是否都為 1，如果其中有一個為 0，那么說明元素不存在，若都為 1，則說明元素有可能存在。

3) 為什么是可能“存在”

您可能會問，為什么是有可能存在？其實原因很簡單，那些被置為 1 的位置也可能是由于其他元素的操作而改變的。比如，元素1 和 元素2，這兩個元素同時將一個位置變?yōu)榱?1（圖1所示）。在這種情況下，我們就不能判定“元素 1”一定存在，這是布隆過濾器存在誤判的根本原因。

安裝與使用

在 Redis 4.0 版本之后，布隆過濾器才作為插件被正式使用。布隆過濾器需要單獨安裝，下面介紹安裝 RedisBloom 的幾種方法：

1) docker安裝

docker 安裝布隆過濾器是最簡單、快捷的一種方式：

docker pull redislabs/rebloom:latest
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
docker exec -it redis-redisbloom bash
redis-cli
#測試是否安裝成功
127.0.0.1:6379> bf.add www.biancheng.net hello

2) 直接編譯安裝

如果您對 docker 不熟悉，也可以采用直接編譯的方式來安裝。

下載地址：
https://github.com/RedisBloom/RedisBloom
解壓文件：
unzip RedisBloom-master.zip
進入目錄：
cd RedisBloom-master
執(zhí)行編譯命令，生成redisbloom.so 文件：
make
拷貝至指定目錄：
cp redisbloom.so /usr/local/redis/bin/redisbloom.so
在redis配置文件里加入以下配置：
loadmodule /usr/local/redis/bin/redisbloom.so
配置完成后重啟redis服務：
sudo /etc/init.d/redis-server restart
#測試是否安裝成功
127.0.0.1:6379> bf.add www.biancheng.net hello

常用命令匯總

1) 命令應用

127.0.0.1:6379> bf.add spider:url www.biancheng.net
(integer) 1
127.0.0.1:6379> bf.exists spider:url www.biancheng.net
(integer) 1
127.0.0.1:6379> bf.madd spider:url www.taobao.com www.123qq.com
1) (integer) 1
2) (integer) 1
127.0.0.1:6379> bf.mexists spider:url www.jd.com www.taobao.com
1) (integer) 0
2) (integer) 1

Python使用布隆過濾器

下面使用 Python 測試布隆過濾器的誤判率，代碼如下所示：

import redis
size=10000
r = redis.Redis()
count = 0
for i in range(size):
    #添加元素，key為userid，值為user0...user9999
    r.execute_command("bf.add", "userid", "user%d" % i)
    #判斷元素是否存在，此處切記 i+1
    res = r.execute_command("bf.exists", "userid", "user%d" % (i + 1))
    if res == 1:
        print(i)
        count += 1
#求誤判率，round()中的5表示保留的小數(shù)點位數(shù)
print("size: {} ,error rate:{}%".format(size, round(count / size * 100, 5)))

執(zhí)行三次測試，size 從小到大。輸出結果如下：

size: 1000 , error rate: 1.0%
size: 10000 , error rate: 1.25%
size: 100000 , error rate: 1.305%

通過上述結果可以看出布隆過濾器的錯誤率為 1% 多點，當 size 越來越大時，布隆過濾器的錯誤率就會升高，那么有沒有辦法降低錯誤率呢？這就用到了布隆過濾器提供的
bf.reserve方法。如果不使用該方法設置參數(shù)，那么布隆過濾器將按照默認參數(shù)進行設置，如下所示：

key  #指定存儲元素的鍵，若已經存在,則bf.reserve會報錯
error_rate=0.01 #表示錯誤率
initial_size=100 #表示預計放入布隆過濾器中的元素數(shù)量

當放入過濾器中的元素數(shù)量超過了 initial_size 值時，錯誤率 error_rate 就會升高。因此就需要設置一個較大 initial_size 值，避免因數(shù)量超出導致的錯誤率上升。

解決錯誤率過高的問題

錯誤率越低，所需要的空間也會越大，因此就需要我們盡可能精確的估算元素數(shù)量，避免空間的浪費。我們也要根據(jù)具體的業(yè)務來確定錯誤率的許可范圍，對于不需要太精確的業(yè)務場景，錯誤率稍微設置大一點也可以。

注意：如果要使用自定義的布隆過濾器需要在 add 操作之前，使用 bf.reserve 命令顯式地創(chuàng)建 key，格式如下：

client.execute_command("bf.reserve", "keyname", 0.001, 50000)

布隆過濾器相比于平時常用的的列表、散列、集合等數(shù)據(jù)結構，其占用空間更少、效率更高，但缺點就是返回的結果具有概率性，并不是很準確。在理論情況下，添加的元素越多，誤報的可能性就越大。再者，存放于布隆過濾器中的元素不容易被刪除，因為可能出現(xiàn)會誤刪其他元素情況。