做视频有赚钱的网站,长沙做网站建设的,wordpress调用栏目名称,宁波网站制作出售背景 缓存是解决日常软件问题的重要概念。 您的应用程序可能会执行CPU密集型操作#xff0c;而您又不想一次又一次地执行这些操作#xff0c;而是只导出一次结果并将其缓存在内存中。 有时瓶颈是IO#xff0c;例如您不想重复访问数据库#xff0c;并且想缓存结果并仅在基础… 背景 缓存是解决日常软件问题的重要概念。 您的应用程序可能会执行CPU密集型操作而您又不想一次又一次地执行这些操作而是只导出一次结果并将其缓存在内存中。 有时瓶颈是IO例如您不想重复访问数据库并且想缓存结果并仅在基础数据发生更改时才更新缓存。 同样在其他一些用例中我们需要执行快速查找来决定如何处理传入的请求。 例如考虑这种用例您必须识别一个URL是否指向恶意软件站点。 要在一个实例中执行此操作可能会有很多类似的URL如果我们将所有恶意软件URL缓存在内存中则将需要大量空间来保存它们。 另一个用例可能是识别用户键入的字符串是否对美国的某个地方有任何引用。 就像“华盛顿博物馆”一样华盛顿就是美国一个地方的名字。 我们应该把美国的所有地方都留在记忆中然后查找吗 缓存大小有多大 在没有任何数据库支持的情况下这样做是否有效 这是我们需要脱离基本地图数据结构并在更高级的数据结构例如Bloomfilter中寻找答案的地方。 您可以考虑Bloomfilter就像其他任何Java集合一样您可以在其中放置项目并询问它是否已存在某个项目例如HashSet。 如果Bloomfilter提到它不包含该项目那么肯定不存在该项目。 但是如果它提到看到了该项目则可能是错误的。 如果我们足够谨慎的话我们可以设计一个bloomfilter以便控制错误的可能性。 说明 Bloomfilter设计为m位的数组A。 最初所有这些位都设置为0。 要添加项目 为了添加任何项目需要通过k个散列函数进行馈送。 每个哈希函数都会生成一个数字该数字可以视为位数组的位置哈希模数数组的长度可以为我们提供数组的索引我们应将该位置的值设置为1。例如–第一个哈希函数hash1在项I上生成位位置x类似地第二和第三哈希函数生成位置y和z。 因此我们将设置 A[x]A[y]A[z] 1 查找项目 将重复类似的过程将通过三个不同的哈希函数将项目哈希三次。 每个哈希函数将产生一个整数该整数将被视为数组的位置。 我们将检查位数组的xyz位置并查看它们是否设置为1。 如果不是那么肯定没有人尝试将其添加到bloomfilter中但是如果所有位都已设置则可能是假阳性。 调整的东西 从上面的解释中可以清楚地看出要设计一个好的bloomfilter我们需要跟踪以下内容 良好的哈希函数可以尽快生成广泛的哈希值 m的值位阵列的大小非常重要。 如果大小太小则所有位将很快设置为1并且误报会大大增加。 散列函数k的数量也很重要这样值才能均匀分布。 如果我们可以估计计划在Bloom Bloom过滤器中保留多少个项目则可以计算k和m的最佳值。 跳过数学上的细节计算k和m的公式足以让我们编写一个良好的Bloomfilter。 确定m布隆过滤器的位数的公式如下 m - nlogp / (log2)^2; 其中p 期望的假阳性概率 确定k哈希函数数的公式如下 k m/n log(2) ; 其中k 哈希函数的数量m 位数n 过滤器中的项目数 散列是一个影响bloomfilter性能的区域。 我们需要选择一个有效但又不费时的哈希函数。 在“更少的哈希相同的性能构建更好的Bloom过滤器”一文中讨论了如何使用两个哈希函数生成K个哈希函数。 首先我们需要计算两个哈希函数h1x和h2x。 接下来我们可以使用这两个哈希函数来模拟自然的k个哈希函数 gi(x) h1(x) ih2(x); 我可以在{1..k}范围内 Google番石榴库在其Bloomfilter实现中使用了该技巧哈希逻辑在此处概述 long hash64 …; //calculate a 64 bit hash function//split it in two halves of 32 bit hash values int hash1 (int) hash64; int hash2 (int) (hash64 32);//Generate k different hash functions with a simple loopfor (int i 1; i numHashFunctions; i) {int nextHash hash1 i * hash2;}应用领域 从数学公式可以明显看出要使用Bloomfilter解决问题我们需要非常了解该域。 就像我们可以应用Bloomfilter来保留美国所有城市的名称一样。 此数字是确定性的我们具有先验知识因此我们可以确定n要添加到Bloomfilter的元素总数。 根据业务需求固定p假阳性概率。 在那种情况下我们有一个完美的缓存可以提高内存效率并且查找时间非常短。 实作 Google番石榴库具有Bloomfilter的实现。 检查此类的构造函数如何查询期望的项目和误报率。 import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;//Create Bloomfilter
int expectedInsertions ….;
double fpp 0.03; // desired false positive probability
BloomFilterCharSequence bloomFilter BloomFilter.create(Funnels.stringFunnel(Charset.forName(UTF-8)), expectedInsertions,fpp)资源 http://en.wikipedia.org/wiki/Bloom_filter http://billmill.org/bloomfilter-tutorial/ http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf 翻译自: https://www.javacodegeeks.com/2014/07/how-to-use-bloom-filter-to-build-a-large-in-memory-cache-in-java.html
