### [布隆過濾器](https://so.csdn.net/so/search?q=布隆過濾器&spm=1001.2101.3001.7020) - [1、布隆過濾器原理](https://codeleader.blog.csdn.net/article/details/130256000#1_ ...
布隆過濾器
1、布隆過濾器原理
1.1 什麼是布隆過濾器
布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進位向量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的演算法要好的多，缺點是有一定的誤識別率和刪除困難。
主要用於判斷一個元素是否在一個集合中，0代表不存在某個數據，1代表存在某個數據。
總結： 一個元素一定不存在 或者 可能存在！ 存在一定的誤判率{通過代碼調節}
1.2 使用場景
大數據量的時候, 判斷一個元素是否在一個集合中。解決緩存穿透問題
1.3 原理
存入過程
布隆過濾器上面說了，就是一個二進位數據的集合。當一個數據加入這個集合時，經歷如下：
-
通過K個哈希函數計算該數據，返回K個計算出的hash值
-
這些K個hash值映射到對應的K個二進位的數組下標
-
將K個下標對應的二進位數據改成1。
例如，第一個哈希函數返回x，第二個第三個哈希函數返回y與z，那麼： X、Y、Z對應的二進位改成1。
如圖所示：
查詢過程
布隆過濾器主要作用就是查詢一個數據，在不在這個二進位的集合中，查詢過程如下：
1、通過K個哈希函數計算該數據，對應計算出的K個hash值
2、通過hash值找到對應的二進位的數組下標
3、判斷：如果存在一處位置的二進位數據是0，那麼該數據不存在。如果都是1，該數據存在集合中。
1.4 布隆過濾器的優缺點
- 優點
- 由於存儲的是二進位數據，所以占用的空間很小
- 它的插入和查詢速度是非常快的，時間複雜度是O（K），空間複雜度：O (M)。
K: 是哈希函數的個數
M: 是二進位位的個數
- 保密性很好，因為本身不存儲任何原始數據，只有二進位數據
- 缺點：
添加數據是通過計算數據的hash值，那麼很有可能存在這種情況：兩個不同的數據計算得到相同的hash值。
例如圖中的“張三”和“張三豐”，假如最終算出hash值相同，那麼他們會將同一個下標的二進位數據改為1。
這個時候，你就不知道下標為1的二進位，到底是代表“張三”還是“張三豐”。
由此得出以下缺點：
1、存在誤判
假如上面的圖沒有存 “張三”，只存了 “張三豐”，那麼用"張三"來查詢的時候，會判斷"張三"存在集合中。
因為“張三”和“張三豐”的hash值是相同的，通過相同的hash值，找到的二進位數據也是一樣的，都是1。
誤判率：
受三個因素影響： 二進位位的個數m, 哈希函數的個數k, 數據規模n (添加到布隆過濾器中的數據)
已知誤判率p, 數據規模n, 求二進位的個數m，哈希函數的個數k {m,k 程式會自動計算 ，你只需要告訴我數據規模，誤判率就可以了}
ln: 自然對數是以常數e為底數的對數，記作lnN（N>0）。在物理學，生物學等自然科學中有重要的意義，一般表示方法為lnx。數學中也常見以logx表示自然對數。
2、刪除困難
還是用上面的舉例，因為“張三”和“張三豐”的hash值相同，對應的數組下標也是一樣的。
如果你想去刪除“張三”，將下標為1里的二進位數據，由1改成了0。
那麼你是不是連“張三豐”都一起刪了。
2、實現方式
2.1 初始化skuId的布隆過濾器
我在service-product模塊中操作
2.1.1 RedisConst常量類
public class RedisConst {
public static final String SKUKEY_PREFIX = "sku:";
public static final String SKUKEY_SUFFIX = ":info";
//單位：秒
public static final long SKUKEY_TIMEOUT = 24 * 60 * 60;
// 定義變數，記錄空對象的緩存過期時間
public static final long SKUKEY_TEMPORARY_TIMEOUT = 10 * 60;
//單位：秒 嘗試獲取鎖的最大等待時間
public static final long SKULOCK_EXPIRE_PX1 = 100;
//單位：秒 鎖的持有時間
public static final long SKULOCK_EXPIRE_PX2 = 10;
public static final String SKULOCK_SUFFIX = ":lock";
public static final String USER_KEY_PREFIX = "user:";
public static final String USER_CART_KEY_SUFFIX = ":cart";
public static final long USER_CART_EXPIRE = 60 * 60 * 24 * 30;
//用戶登錄
public static final String USER_LOGIN_KEY_PREFIX = "user:login:";
// public static final String userinfoKey_suffix = ":info";
public static final int USERKEY_TIMEOUT = 60 * 60 * 24 * 7;
//秒殺商品首碼
public static final String SECKILL_GOODS = "seckill:goods";
public static final String SECKILL_ORDERS = "seckill:orders";
public static final String SECKILL_ORDERS_USERS = "seckill:orders:users";
public static final String SECKILL_STOCK_PREFIX = "seckill:stock:";
public static final String SECKILL_USER = "seckill:user:";
//用戶鎖定時間 單位：秒
public static final int SECKILL__TIMEOUT = 60 * 60 * 1;
// 布隆過濾器使用！
public static final String SKU_BLOOM_FILTER="sku:bloom:filter";
}
123456789101112131415161718192021222324252627282930313233343536
2.1.2 修改啟動類
@SpringBootApplication
@ComponentScan({"com.atguigu.gmall"})
@EnableDiscoveryClient
public class ServiceProductApplication implements CommandLineRunner {
@Autowired
private RedissonClient redissonClient;
public static void main(String[] args) {
SpringApplication.run(ServiceProductApplication.class,args);
}
//初始化布隆過濾器
@Override
public void run(String... args) throws Exception {
//獲取布隆過濾器
RBloomFilter<Object> bloomFilter = redissonClient.getBloomFilter(RedisConst.SKU_BLOOM_FILTER);
//初始化布隆過濾器：計算元素的數量 比如預計有多少個sku
bloomFilter.tryInit(10001,0.001);
}
}
123456789101112131415161718192021
2.2 給商品詳情頁添加布隆過濾器
1、查看商品詳情頁添加布隆過濾器
操作模塊：service-item
更改ItemserviceImpl.item方法
2、添加商品sku加入布隆過濾器數據
操作模塊：service-product
更改ManageServiceImpl.saveSkuInfo方法
這樣就避免了別人用一個不存在的key去瘋狂攻擊我們的緩存資料庫。
我們在分散式鎖中將查詢結果是null的也進行緩存，但是如果有人用隨機數去瘋狂請求我們的介面，那我們的Redis可能會扛不住，所以在這裡用布隆過濾器，只需要在初始化的時候，指定我們存儲數據的數據量和可以承受的誤判率即可。
布隆過濾器指導有哪些數據，這樣別人使用隨機數攻擊的時候直接就給他返回，不用再去查Redis了。
本文來自博客園，作者：自律即自由-，轉載請註明原文鏈接：https://www.cnblogs.com/deyo/p/17561958.html
