一家公司可以做几个网站网站项目计划书模板范文

当前位置： 首页 > news >正文

一家公司可以做几个网站,网站项目计划书模板范文,北京社交网站建设,wordpress淘宝客主题带条件筛选1.布隆过滤器的场景 在Redis 缓存击穿#xff08;失效#xff09;、缓存穿透、缓存雪崩怎么解决#xff1f;中我们说到可以使用布隆过滤器避免「缓存穿透」。 你会说我们只要记录了每个用户看过的历史记录#xff0c;每次推荐的时候去查询数据库过滤存在的数据实现去重。 …1.布隆过滤器的场景 在Redis 缓存击穿失效、缓存穿透、缓存雪崩怎么解决中我们说到可以使用布隆过滤器避免「缓存穿透」。 你会说我们只要记录了每个用户看过的历史记录每次推荐的时候去查询数据库过滤存在的数据实现去重。 实际上如果历史记录存储在关系数据库里去重就需要频繁地对数据库进行 exists 查询当系统并发量很高时数据库是很难扛住压力的。 我们不能使用缓存 将历史数据存在Redis中这么多的历史记录那要浪费多大的内存空间所以这个时候我们就能使用布隆过滤器去解决这种去重问题。又快又省内存互联网开发必备杀招 当我们遇到数据量比较大又需要去重的时候就可以考虑布隆过滤器如下场景 解决 Redis 缓存穿透问题面试重点 利用布隆过滤器我们可以预先把数据查询的主键比如用户 ID 或文章 ID 缓存到过滤器中。当根据 ID 进行数据查询的时候我们先判断该 ID 是否存在若存在的话则进行下一步处理。若不存在的话直接返回这样就不会触发后续的数据库查询。需要注意的是缓存穿透不能完全解决我们只能将其控制在一个可以容忍的范围内。 邮件过滤使用布隆过滤器实现邮件黑名单过滤反垃圾邮件从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱网页爬虫对 URL 去重避免爬取相同的 URL 地址Google Chrome 使用布隆过滤器识别恶意 URLMedium 使用布隆过滤器避免推荐给用户已经读过的文章推荐过的新闻不再推荐Google BigTableApache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。 2.布隆过滤器的概述 布隆过滤器 (Bloom Filter)是由 Burton Howard Bloom 于 1970 年提出它是一种 space efficient 的概率型数据结构用于判断一个元素是否在集合中。 当布隆过滤器说某个数据存在时这个数据可能不存在当布隆过滤器说某个数据不存在时那么这个数据一定不存在。 哈希表也能用于判断元素是否在集合中但是布隆过滤器只需要哈希表的 ¹⁄₈ 或 ¹⁄₄ 的空间复杂度就能完成同样的问题。 布隆过滤器可以插入元素但不可以删除已有元素。 其中的元素越多false positive rate(误报率)越大但是 false negative (漏报)是不可能的。 3.布隆过滤器原理 BloomFilter 的算法是首先分配一块内存空间做 bit 数组数组的 bit 位初始值全部设为 0。加入元素时采用 k 个相互独立的 Hash 函数计算然后将元素 Hash 映射的 K 个位置全部设置为 1。检测 key 是否存在仍然用这 k 个 Hash 函数计算出 k 个位置如果位置全部为 1则表明 key 存在否则不存在。 如下图所示 布隆过滤器原理 哈希函数会出现碰撞所以布隆过滤器会存在误判。 这里的误判率是指BloomFilter 判断某个 key 存在但它实际不存在的概率因为它存的是 key 的 Hash 值而非 key 的值。 所以有概率存在这样的 key它们内容不同但多次 Hash 后的 Hash 值都相同。 对于 BloomFilter 判断不存在的 key 则是 100% 不存在的反证法如果这个 key 存在那它每次 Hash 后对应的 Hash 值位置肯定是 1而不会是 0。布隆过滤器判断存在不一定真的存在。 布隆过滤器Bloom Filter本质上是由长度为 m 的位向量或位列表仅包含 0 或 1 位值的列表组成最初所有的值均设置为 0如下图所示。 为了将数据项添加到布隆过滤器中我们会提供 K 个不同的哈希函数并将结果位置上对应位的值置为 “1”。在前面所提到的哈希表中我们使用的是单个哈希函数因此只能输出单个索引值。而对于布隆过滤器来说我们将使用多个哈希函数这将会产生多个索引值。 如上图所示当输入 “semlinker” 时预设的 3 个哈希函数将输出 2、4、6我们把相应位置 1。假设另一个输入 ”kakuqo“哈希函数输出 3、4 和 7。你可能已经注意到索引位 4 已经被先前的 “semlinker” 标记了。此时我们已经使用 “semlinker” 和 ”kakuqo“ 两个输入值填充了位向量。当前位向量的标记状态为 当对值进行搜索时与哈希表类似我们将使用 3 个哈希函数对 ”搜索的值“ 进行哈希运算并查看其生成的索引值。假设当我们搜索 ”fullstack“ 时3 个哈希函数输出的 3 个索引值分别是 2、3 和 7 从上图可以看出相应的索引位都被置为 1这意味着我们可以说 ”fullstack“ 可能已经插入到集合中。事实上这是误报的情形产生的原因是由于哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上。幸运的是布隆过滤器有一个可预测的误判率FPP
n 是已经添加元素的数量总的元素数量k 哈希的次数m 布隆过滤器的长度如比特数组的大小 极端情况下当布隆过滤器没有空闲空间时满每一次查询都会返回 true 。这也就意味着 m 的选择取决于期望预计添加元素的数量 n 并且 m 需要远远大于 n 。 实际情况中布隆过滤器的长度 m 可以根据给定的误判率FPP的和期望添加的元素个数 n 的通过如下公式计算 FPP越小说明了m的值越大 来实现m远大于n实现比特数组的长度更长。 了解完上述的内容之后我们可以得出一个结论当我们搜索一个值的时候若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“那么该值肯定不在集合中。但如果所有哈希索引值均为 ”1“则只能说该搜索的值可能存在集合中。 为什么不允许删除元素 删除意味着需要将对应的 k 个 bits 位置设置为 0其中有可能是其他元素对应的位。 因此 remove 会引入 false negative这是绝对不被允许的。 4.布隆过滤器优缺点 4.1.布隆过滤器优点 增加和查询元素的时间复杂度为O(K), (K为哈希函数的个数一般比较小)与数据量大小无关哈希函数相互之间没有关系方便硬件并行运算布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势数据量很大时布隆过滤器可以表示全集其他数据结构不能使用同一组散列函数的布隆过滤器可以进行交、并、差运算空间效率和查询时间都比一般的算法要好的多 4.2.布隆过滤器缺点 有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再建立一个白名单存储可能会误判的数据)不能获取元素本身一般情况下不能从布隆过滤器中删除元素如果采用计数方式删除可能会存在计数回绕问题存在一定的误识别率和删除困难 5.布隆过滤器的应用 布隆过滤器有很多实现和优化由 Google 开发著名的 Guava 库就提供了布隆过滤器Bloom Filter的实现。在基于 Maven 的 Java 项目中要使用 Guava 提供的布隆过滤器只需要引入以下环境 dependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactIdversion30.0-jre/version /dependency在导入 Guava 库后我们新建一个 BloomFilterDemo 类在 main 方法中我们通过 BloomFilter.create 方法来创建一个布隆过滤器接着我们初始化 1 百万条数据到过滤器中然后在原有的基础上增加 10000 条数据并判断这些数据是否存在布隆过滤器中 package cn.wen;import com.google.common.base.Charsets; import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels;/*** 布隆过滤器测试*/ public class BloomFilterDemo {public static void main(String[] args) {int total 1000000; // 总数量BloomFilterCharSequence bf BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total,0.0002);// 初始化 1000000 条数据到过滤器中for (int i 0; i total; i) {bf.put( i);}// 判断值是否存在过滤器中int count 0;for (int i 0; i total 10000; i) {if (bf.mightContain( i)) {count;}}System.out.println(已匹配数量 count);}} 当以上代码运行后控制台会输出以下结果 已匹配数量 1000309 很明显以上的输出结果已经出现了误报因为相比预期的结果多了 309 个元素误判率为 309/(1000000 10000) * 100 ≈ 0.030594059405940593 如果要提高匹配精度的话我们可以在创建布隆过滤器的时候设置误判率 fpp BloomFilterCharSequence bf BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total, 0.0002);在 BloomFilter 内部误判率 fpp 的默认值是 0.03 // com/google/common/hash/BloomFilter.class public static T BloomFilterT create(Funnel? super T funnel, long expectedInsertions) {return create(funnel, expectedInsertions, 0.03D); }在重新设置误判率为 0.0002 之后我们重新运行程序这时控制台会输出以下结果 已匹配数量 1000003 通过观察以上的结果可知误判率 fpp 的值越小匹配的精度越高。当减少误判率 fpp 的值需要的存储空间也越大所以在实际使用过程中需要在误判率和存储空间之间做个权衡。 方案1开发定时任务每隔几个小时自动创建一个新的布隆过滤器数组替换老的有点CopyOnWriteArrayList的味道 方案2布隆过滤器增加一个等长的数组存储计数器主要解决冲突问题每次删除时对应的计数器减一如果结果为0更新主数组的二进制值为0 6、手写布隆过滤器 /**

• ClassName: BloomFilter
• Author: 小飞
• Date: 2023/5/17 21:50
• Description: 布隆过滤器 */ public class BloomFilter {// 默认大小private static final int DEFAULT_SIZE Integer.MAX_VALUE;// 最小的大小private static final int MIN_SIZE 1000;// 大小为默认大小private int SIZE DEFAULT_SIZE;// hash函数的种子因子private static final int[] HASH_SEEDS new int[]{3, 5, 7, 11, 13, 17, 19, 23, 29, 31};// 位数组0/1,表示特征private BitSet bitSet null;// hash函数private HashFunction[] hashFunctions new HashFunction[HASH_SEEDS.length];// 无参数初始化public BloomFilter() {// 按照默认大小init();}// 带参数初始化public BloomFilter(int size) {// 大小初始化小于最小的大小if (size MIN_SIZE) {SIZE size;}init();}// 初始化private void init() {// 初始化位大小bitSet new BitSet(SIZE);// 初始化hash函数for (int i 0; i HASH_SEEDS.length; i) {hashFunctions[i] new HashFunction(SIZE, HASH_SEEDS[i]);}}// 添加元素相当于把元素的特征添加到位数组中public void add(Object value) {for (HashFunction f : hashFunctions) {// 将hash值计算出来的值为truebitSet.set(f.hash(value), true);}}// 判断元素的特征是否存在于位数组public boolean contains(Object value) {boolean result true;for (HashFunction f : hashFunctions) {result result bitSet.get(f.hash(value));// hash函数只要有一个计算出为false则直接返回if (!result) {return false;}}return true;}// hash函数public static class HashFunction {// 位数组大小private int size;// hash种子private int seed;public HashFunction(int size, int seed) {this.size size;this.seed seed;}// hash函数public int hash(Object value) {if (value null) {return 0;} else {// hash值int hash1 value.hashCode();// 高位的hash值int hash2 hash1 16;// 合并hash值 结合高低位特征int combineHash hash1 ^ hash2;// 相乘取余return Math.abs(combineHash * seed) % size;}}}public static void main(String[] args) {Integer num1 new Integer(12321);Integer num2 new Integer(12345);BloomFilter myBloomFilter new BloomFilter();System.out.println(myBloomFilter.contains(num1));System.out.println(myBloomFilter.contains(num2));myBloomFilter.add(num1);myBloomFilter.add(num2);System.out.println(myBloomFilter.contains(num1));System.out.println(myBloomFilter.contains(num2));} } 上面未提供Hash函数的数量默认值实现hash函数。 // 带参数初始化 public BloomFilter(int num,double rate) {// 计算位数组的大小this.SIZE (int) (-num * Math.log(rate) / Math.pow(Math.log(2), 2));// hash 函数个数this.s (int) (this.SIZE * Math.log(2) / num);// 初始化位数组this.bitSet new BitSet(SIZE); }上面的构造函数就是对误差率的初始化值。