面試官：項目中如何實現布隆過濾器？

作者：磊哥 2024-09-25 17:44:08

對于布隆過濾器是什么？以及布隆過濾器的實現原理？相信大部分同學都能回答個七七八八。當如果被問道：項目當中是如何實現布隆過濾器的？這個時候大部分同學就又回答不上來了，所以今天咱們就來探討一下這個問題。

談起“布隆過濾器”相信大家都不陌生，它也算日常面試中的常見面試題了。例如，當面試官在問到 Redis 模塊的相關問題時，可能會問到緩存穿透（Redis 四大經典問題之一），而緩存穿透的經典解決方案之一，則是“布隆過濾器”。

但是，對于布隆過濾器是什么？以及布隆過濾器的實現原理？相信大部分同學都能回答個七七八八。當如果被問道：項目當中是如何實現布隆過濾器的？這個時候大部分同學就又回答不上來了，所以今天咱們就來探討一下這個問題。

布隆過濾器（Bloom Filter）是一種高效的數據結構，由布隆在 1970 年提出。它主要用于判斷一個元素可能是否存在于集合中，其核心特性包括高效的插入和查詢操作，但存在一定的假陽性（False Positives）可能性。

布隆過濾器實現如下圖所示：

根據 key 值計算出它的存儲位置，然后將此位置標識全部標識為 1（未存放數據的位置全部為 0），查詢時也是查詢對應的位置是否全部為 1，如果全部為 1，則說明數據是可能存在的，否則一定不存在。

也就是說，如果布隆過濾器說一個元素不在集合中，那么它一定不在這個集合中；但如果它說一個元素在集合中，則有可能是不存在的（存在誤差，假陽性）。

高效節省空間：布隆過濾器不存儲數據本身，只存儲數據對應的哈希比特位，因此占用空間非常小。
快速的插入和查詢：插入和查詢操作的時間復雜度都為 O(k)，其中 k 為哈希函數的個數，這使得布隆過濾器在處理大量數據時非常高效。
存在假陽性：由于哈希碰撞的可能性，布隆過濾器在判斷元素存在時可能會出現誤判，即元素實際上不在集合中，但過濾器錯誤地認為其存在。這種誤判率取決于哈希函數的個數和位數組的長度。
不支持刪除操作：一旦一個元素被添加到布隆過濾器中，很難將其準確地刪除。因為多個元素可能會共用位數組中的某些位，刪除一個元素可能會影響其他元素的判斷結果。
靈活性與可配置性：布隆過濾器的誤判率、位數組的長度和哈希函數的個數都是可以根據具體應用場景進行調整的，以達到最優的性能和誤判率平衡。

布隆過濾器的主要使用場景有以下幾個：

實現布隆過濾器的方法有很多，可以分為以下兩類：

在項目開發當中，如果使用的是 Redis 4.0+ 版本，我們通常會使用 Redis 布隆過濾器插件來實現布隆過濾器，以下是具體的實現步驟。

git clone https://github.com/RedisLabsModules/redisbloom.git
cd redisbloom
make # 編譯redisbloom

編譯正常執行完，會在根目錄生成一個 redisbloom.so 文件。

重新啟動 Redis 服務，并指定啟動 RedisBloom 插件，具體命令如下：

redis-server redis.conf --loadmodule ./src/modules/RedisBloom-master/redisbloom.so

創建一個布隆過濾器，并設置期望插入的元素數量和誤差率，在 Redis 客戶端中輸入以下命令：

BF.RESERVE my_bloom_filter 0.01 100000

在 Redis 客戶端中輸入以下命令：

BF.ADD my_bloom_filter leige

在 Redis 客戶端中輸入以下命令：

BF.EXISTS my_bloom_filter leige

責任編輯：姜華來源：磊哥和Java