从seo角度谈网站建设,杭州品牌vi设计公司,在dw里网站页面列表怎么做,wordpress激活码充值背景介绍在互联网中#xff0c;我们经常遇到需要在大量数据中判断目标数据是否存在的情况。例如#xff0c;在网络爬虫中#xff0c;我们需要判断某个网址是否已经被访问过。为了实现这一功能#xff0c;通常需要使用一个容器来存储已访问过的网址。如果将这些数据直接存储…背景介绍 在互联网中我们经常遇到需要在大量数据中判断目标数据是否存在的情况。例如在网络爬虫中我们需要判断某个网址是否已经被访问过。为了实现这一功能通常需要使用一个容器来存储已访问过的网址。如果将这些数据直接存储在磁盘中每次判断都要进行磁盘查询这将导致大量的IO操作效率较低。因此我们希望将这些数据保存在内存中。在数据量较小的情况下可以使用Redis来存储这些数据。但是当数据量超过上千万时将会消耗几GB甚至几十GB的内存空间。然而对于仅需要记录数据是否存在的情况而言这样使用大量内存显然是浪费的。为了解决这个问题我们可以使用布隆过滤器(Bloom Filter)。布隆过滤器是一种占用空间少且时间效率高的工具。布隆过滤器介绍布隆过滤器是一种空间效率极高的概率型数据结构用于快速判断一个元素是否可能存在于一个集合中。它的核心特点是以极小的存储空间换取高效的查询性能但存在一定的误判率False Positive。核心原理位数组Bit Array布隆过滤器使用一个长度为m的二进制位数组初始全为0作为底层存储例如[0, 0, 0, 0, 0, 0, 0, 0]m8多个哈希函数使用k个不同的哈希函数h₁, h₂, ..., hₖ每个函数都能将输入元素映射到位数组的某个位置当一个元素被添加到集合中时它会通过k个哈希函数映射到位数组中的m个位置并将这些位置的值设置为 1。在检查元素是否在集合中时检查这些位置是否全为 1。如果其中有任何一个位置为 0则该元素一定不在集合中如果所有位置均为 1则该元素可能在集合中。简单举例假设现在有3个哈希函数和一个8位的bit数组。元素a和b都经过三次哈希函数生成三个哈希值并映射到位数组的不同的位置并设置为1。元素a映射的位置是0,3,7元素b映射的位置是2,5,7.如果一个元素c过来我们检查它映射后的三个位置是否全是1就可以判断元素C是否在当前集合中了。其实我们可以发现元素a和元素b映射的位置7都是1也就是说位置是可能重叠的。假设当前集合已经有a和b了但是呢一个元素c过来它映射的位置为0,2,7这时候它的所有位置都是1布隆过滤器是认为它可能在集合中但是我们看到元素c是不在当前集合中的。也是就说布隆过滤器是可能存在误判的通俗点说就是假阳性。关键特性没有假阴性False Negative如果查询返回不存在则元素一定不在集合中存在假阳性False Positive可能误判不存在的元素为存在概率通常1%原因不同元素的哈希位置可能重叠不支持元素删除简单的布隆过滤器无法安全删除元素会影响到其他元素使用样例依赖导入dependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactIdversion30.1-jre/version !-- Use the latest version --/dependencyJava代码
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;public class BloomFilterIntersection {public static void main(String[] args) {// 生成两个测试数据集SetInteger set1 generateRandomSet(1_000_000, 10000000);SetInteger set2 generateRandomSet(1_000_000, 10000000);// 人为添加一些共同元素for (int i 0; i 1000; i) {int commonElement 20000000 i;set1.add(commonElement);set2.add(commonElement);}System.out.println(集合1大小: set1.size());System.out.println(集合2大小: set2.size());// 使用布隆过滤器查找交集long startTime System.currentTimeMillis();SetInteger intersection findIntersection(set1, set2);long endTime System.currentTimeMillis();System.out.println(检测到的交集元素数量: intersection.size());System.out.println(计算耗时: (endTime - startTime) ms);// 验证前10个交集元素System.out.println(\n前10个交集元素示例:);intersection.stream().limit(10).forEach(System.out::println);}/*** 使用布隆过滤器找出两个集合的交集* param set1 第一个集合* param set2 第二个集合* return 两个集合的交集*/public static SetInteger findIntersection(SetInteger set1, SetInteger set2) {// 创建布隆过滤器预计插入set1的大小误判率1%//Funnel 是 Guava 提供的一个接口用于 将对象转换为字节流PrimitiveSinkBloomFilterInteger filter BloomFilter.create(Funnels.integerFunnel(),set1.size(),0.01);// 将第一个集合的所有元素添加到布隆过滤器for (Integer item : set1) {filter.put(item);}// 检查第二个集合中的哪些元素可能在第一个集合中SetInteger possibleMatches new HashSet();for (Integer item : set2) {if (filter.mightContain(item)) {possibleMatches.add(item);}}// 由于布隆过滤器可能有假阳性需要二次验证SetInteger actualIntersection new HashSet(set1);actualIntersection.retainAll(possibleMatches);return actualIntersection;}/*** 生成随机整数集合* param size 集合大小* param bound 随机数范围* return 包含随机整数的集合*/private static SetInteger generateRandomSet(int size, int bound) {SetInteger set new HashSet();Random random new Random();while (set.size() size) {set.add(random.nextInt(bound));}return set;}
}
