建站
咨詢
售后
建站咨詢
新聞中心
布隆過濾器（Bloom Filter）是一種空間效率極高的概率型數(shù)據(jù)結(jié)構(gòu)，用于判斷一個元素是否在一個集合中。它基于位數(shù)組和多個哈希函數(shù)的原理，可以高效地進(jìn)行元素的查詢，而且占用的空間相對較小，如下圖所示：
創(chuàng)新互聯(lián)建站專注于羅田企業(yè)網(wǎng)站建設(shè),自適應(yīng)網(wǎng)站建設(shè),商城系統(tǒng)網(wǎng)站開發(fā)。羅田網(wǎng)站建設(shè)公司,為羅田等地區(qū)提供建站服務(wù)。全流程定制網(wǎng)站開發(fā)，專業(yè)設(shè)計，全程項目跟蹤，創(chuàng)新互聯(lián)建站專業(yè)和態(tài)度為您提供的服務(wù)
根據(jù) key 值計算出它的存儲位置，然后將此位置標(biāo)識全部標(biāo)識為 1（未存放數(shù)據(jù)的位置全部為 0），查詢時也是查詢對應(yīng)的位置是否全部為 1，如果全部為 1，則說明數(shù)據(jù)是可能存在的，否則一定不存在。
也就是說，如果布隆過濾器說一個元素不在集合中，那么它一定不在這個集合中；但如果它說一個元素在集合中，則有可能是不存在的（存在誤差）。
1、布隆執(zhí)行過程
布隆過濾器的具體執(zhí)行步驟如下：
- 在 Redis 中創(chuàng)建一個位數(shù)組，用于存儲布隆過濾器的位向量。
- 初始化多個哈希函數(shù)，并將每個哈希函數(shù)的計算結(jié)果對應(yīng)的位數(shù)組位置設(shè)置為 1。
- 添加元素到布隆過濾器時，對元素進(jìn)行多次哈希計算，并將對應(yīng)的位數(shù)組位置設(shè)置為 1。
- 查詢元素是否存在時，對元素進(jìn)行多次哈希計算，并檢查對應(yīng)的位數(shù)組位置是否都為 1。
2、布隆使用場景
布隆過濾器的主要使用場景有以下幾個：
- 大數(shù)據(jù)量去重：可以用布隆過濾器來進(jìn)行數(shù)據(jù)去重，判斷一個數(shù)據(jù)是否已經(jīng)存在，避免重復(fù)插入。
- 緩存穿透：可以用布隆過濾器來過濾掉惡意請求或請求不存在的數(shù)據(jù)，避免對后端存儲的頻繁訪問。
- 網(wǎng)絡(luò)爬蟲的 URL 去重：可以用布隆過濾器來判斷 URL 是否已經(jīng)被爬取，避免重復(fù)爬取。
3、如何實(shí)現(xiàn)布隆過濾器？
在 Redis 中不能直接使用布隆過濾器，但我們可以通過 Redis 4.0 版本之后提供的 modules (擴(kuò)展模塊) 的方式引入，它的實(shí)現(xiàn)步驟如下。
（1）打包RedisBloom插件
“
git clone https://github.com/RedisLabsModules/redisbloom.git
cd redisbloom
make # 編譯redisbloom
”
編譯正常執(zhí)行完，會在根目錄生成一個 redisbloom.so 文件。
（2）啟用RedisBloom插件
重新啟動 Redis 服務(wù)，并指定啟動 RedisBloom 插件，具體命令如下：
“
redis-server redis.conf --loadmodule ./src/modules/RedisBloom-master/redisbloom.so
”
（3）創(chuàng)建布隆過濾器
創(chuàng)建一個布隆過濾器，并設(shè)置期望插入的元素數(shù)量和誤差率，在 Redis 客戶端中輸入以下命令：
“
BF.RESERVE my_bloom_filter 0.01 100000
”
（4）添加元素到布隆過濾器
在 Redis 客戶端中輸入以下命令：
“
BF.ADD my_bloom_filter leige
”
（5）檢查元素是否存在
在 Redis 客戶端中輸入以下命令：
“
BF.EXISTS my_bloom_filter leige
”
課后思考
以上我們介紹了什么是布隆過濾器？它的使用場景和執(zhí)行流程，以及在 Redis 中它的使用，那么問題來了，在日常開發(fā)中，也就是在 Java 開發(fā)中，我們又將如何操作布隆過濾器呢？
網(wǎng)頁標(biāo)題：什么是布隆過濾器？如何實(shí)現(xiàn)布隆過濾器？
文章分享：http://m.5511xx.com/article/cdihgge.html
