详解Redis缓存击穿以及解决方案

假设，根据误判率，我们生成一个10位的bit数组，，以及2个hash函数((f_1,f_2))，如下图所示(生成的数组的位数和hash函数的数量，我们不用去关心是如何生成的，有数学论文进行过专业的证明)。

假设输入集合为((N_1,N_2)),经过计算(f_1(N_1))得到的数值得为2，(f_2(N_1))得到的数值为5，则将数组下标为2和下表为5的位置置为1，如下图所示：

同理，经过计算(f_1(N_2))得到的数值得为3，(f_2(N_2))得到的数值为6，则将数组下标为3和下表为6的位置置为1，如下图所示：

这个时候，我们有第三个数(N_3)，我们判断(N_3)在不在集合((N_1,N_2))中，就进行(f_1(N_3)，f_2(N_3))的计算

• 若值恰巧都位于上图的红色位置中，我们则认为，(N_3)在集合((N_1,N_2))中
• 若值有一个不位于上图的红色位置中，我们则认为，(N_3)不在集合((N_1,N_2))中

以上就是布隆过滤器的计算原理，下面我们进行性能测试，

(2) 性能测试

代码如下：

a. 新建一个maven工程，引入guava包

<dependencies> 
<dependency> 
<groupId>com.google.guava</groupId> 
<artifactId>guava</artifactId> 
<version>22.0</version> 
</dependency> 
</dependencies> 

b. 测试一个元素是否属于一个百万元素集合所需耗时

package bloomfilter; 
import com.google.common.hash.BloomFilter; 
import com.google.common.hash.Funnels; 
import java.nio.charset.Charset; 
public class Test { 
private static int size = 1000000; 
private static BloomFilter<Integer> bloomFilter =BloomFilter.create(Funnels.integerFunnel(), size); 
public static void main(String[] args) { 
for (int i = 0; i < size; i++) { 
bloomFilter.put(i); 
} 
long startTime = System.nanoTime(); // 获取开始时间 
//判断这一百万个数中是否包含29999这个数 
if (bloomFilter.mightContain(29999)) { 
System.out.println("命中了"); 
} 
long endTime = System.nanoTime(); // 获取结束时间 
System.out.println("程序运行时间： " + (endTime - startTime) + "纳秒"); 
} 
} 

输出如下所示：

命中了 
程序运行时间： 219386纳秒 

也就是说，判断一个数是否属于一个百万级别的集合，只要0.219ms就可以完成，性能极佳。

c. 误判率的一些概念

（编辑：成都站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!