如何使用bloomfilter构建大型java缓存系统-java开发java经验技巧

《如何使用bloomfilter构建大型java缓存系统-java开发java经验技巧》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、如何使用bloomfiltcr构建大型Java缓存系统-Java开发Java经验技巧如何使用bloomfilter构建大型Java缓存系统本文illImportNew-刘家财翻译口javacodegeekso欢迎加入翻译小组。转载诘见文末要求。冃乐在如今的软件当中，缓存是解决很多问题的一个关键概念。你的应用叮能会进行CPU密集型运算。你当然不想让这些运算一边又一边的重复执行，相反，你可以只执行一次，把这个结果放在内存屮作为缓存。有时系统的瓶颈在I/O操作上,比如你不想重复的查询数据库，你想把结果缓存起來，只在数据发

2、生变化时才去数据查询来更新缓存。与上面的情况类似，冇些场合下我们需要进行快速的查找來决定如何处理新來的请求。例如，考虑卜•面这种情况，你需要确认一个URL是否指向一个恶意网站，这种需求可能会冇很多。如果我们把所冇恶意网站的URL缓存起来，那么会山用很大的空间。或者另一种情况，需要确认用户输入的字符串是包含了美国的地名。像“华盛顿的博物馆”一一在这个字符串屮，华盛顿是美国的一个地名。我们应该把美国所冇的地名保存在内存中然后再查询吗？那样的话缓存会冇多大？是否能在不使用数据库的前提卜•來高效地完成？这就是为什么我们要跨

3、越基本的数据结构map,在更高级的数据结构像布隆过滤器(bloomfilter)中来寻找答案。你可以把布隆过滤器看做Java中的集合(collection),你可以往它里面添加元素，查询某个元素是否存在(就像一个HashSet)。如果布隆过滤器说没有这个元索，那么口J以肯定不含有这个元索，但是如果布隆过滤器说有某个元素，那么这个结果可能是错谋的。如果我们在设计布隆过滤器时足够细心，我们可以把这种出错的概率控制在可接受范围内。解释布隆过滤器被设计为一个具有N的元素的位数组A(bitarray),初始时所有的位都置为0

4、.添加元素要添加一个元索，我们需要提供k个哈希函数。每个函数都能返回一个值，这个值必须能够作为位数组的索引(可以通过对数组长度进行取模得到)。然后，我们把位数组在这个索引处的值设为1。例如，第一个哈希函数作用于元素1上，返冋X。类似的，笫二个笫三个哈希函数返冋y与Z,那么：A[x]=A[y]=A[z]=1查找元素查找的过程与上面的过程类似，元素将会被会被不同的哈希函数处理三次，每个哈希函数都返回一个作为位数组索引值的整数，然后我们检测位数组在X、y与7处的值是否为1。如果有一处不为1,那么就说明这个元索没有被添加到

5、这个布隆过滤器中。如杲都为1,就说明这个元素在布隆过滤器里面。当然，会有一定误判的概率。算法优化通过上面的解释我们口J以知道，如果想设计出一个好的布隆过滤器，我们必须遵循以下准则：•好的哈希函数能够尽可能的返回宽范围的哈希值。•位数组的大小(用m表示)非常重热如果太小，那么所有的位很快就都会被赋值为1,这样就增加了误判的几率。•哈希两数的个数(川k表示)对索引值的均匀分配也很重要。计算m的公式如下：m=-nlogp/(log2)2;这里p为可接受的误判率。计算k的公式如下：k=m/nlog(2)这里k二哈希函数个数

6、，呼位数组个数，n二待检测元素的个数(后而会用到这几个字母)。哈希算法哈希算法是影响布隆过滤器性能的地方。我们需耍选择一个效率高但不耗时的哈希函数，在论文《更少的哈希函数，相同的性能指标：构造一个更好的布隆过滤器》中，讨论了如何选用2个哈希函数来模拟k个哈希函数。首先，我们需要计算两个哈希函数hl(x)与h2(x)。然后，我们可以用这两个哈希函数来模仿产生k个哈希函数的效果：gi(x)=hl(x)+ih2(x);这里i的取值范围是1到k的整数。Googleguava类库使用这个技巧实现了-•个布隆过滤器，哈希算法的

7、主要逻辑如下：longhash64=…；//calculatea64bithashfunction//splititintwohalvesof32bithashvaluesinthashl二(int)hash64;inthash2二(int)(hash64>>>32);//Generatekdifferenthashfunctionswithasimpleloopfor(inti=1;i<=numHashFunctions;i++){intnextHash=hashl+i*hash2;应用从数学公式屮，我们可以很明

8、显的知道使用布隆过滤器来解决问题。但是，我们需要很好地理解布隆过滤器所能解决问题的领域。像我们可以使用布隆过滤器來存放美国的所有城市，因为城市的数量是可以大概确定的，所以我们可以确定n（待检测元素的个数）的值。根据需求来修改P（误判概率）的值，在这种情况下，我们能够设计出一个查询耗时少，内存使用率高的缓存机制。实现GoogleGuava类库有—•个实现，查看