详解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. 误判率的一些观念

起首，我们先差池误判率做表现的配置，举办一个测试，代码如下所示：

package bloomfilter; 
import java.util.ArrayList; 
import java.util.List; 
import com.google.common.hash.BloomFilter; 
import com.google.common.hash.Funnels; 
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); 
} 
List<Integer> list = new ArrayList<Integer>(1000); 
//存心取10000个不在过滤器里的值，看看有几多个会被以为在过滤器里 
for (int i = size + 10000; i < size + 20000; i++) { 
if (bloomFilter.mightContain(i)) { 
list.add(i); 
} 
} 
System.out.println("误判的数目：" + list.size()); 
} 
} 

输出功效如下：

误判对数目：330 

假如上述代码所示，我们存心取10000个不在过滤器里的值，却尚有330个被以为在过滤器里，这声名白误判率为0.03.即，在不做任何配置的环境下，默认的误判率为0.03。

（编辑：湖南网）

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