给视频做特效的网站,兼职做网站赚钱吗,小型企业网站建设报告,建设银行怀柔支行营业部网站整理自己过去使用布隆过滤器的应用案例和理解
基本介绍 1970年由布隆提出的一种空间效率很高的概率型数据结构#xff0c;它可以用于检索一个元素是否在一个集合中#xff0c;由只存0或1的位数组和多个hash算法, 进行判断数据 【一定不存在或者可能存在的算法】
如果这些…整理自己过去使用布隆过滤器的应用案例和理解
基本介绍 1970年由布隆提出的一种空间效率很高的概率型数据结构它可以用于检索一个元素是否在一个集合中由只存0或1的位数组和多个hash算法, 进行判断数据 【一定不存在或者可能存在的算法】
如果这些bit数组 有任何一个0则被判定的元素一定不在; 如果都是1则被检元素很可能在
对比bitmap位图布隆过滤器适合更多类型元素通过hash值转换 原理将元素添加到一个bitmap数组中每个散列函数将元素映射到bitmap数组中的一个位置。如果该位置已经被占用则将该位置置为1否则置为0。当要查询一个元素是否存在时只需要计算该元素的散列值并检查bitmap数组中对应的位置是否已经被置为1。如果都是1则该元素可能存在否则肯定不存在。不存在的一定不存在存在的不一定存在
优点占用空间小查询速度快空间效率和查询时间都远远超过一般的算法。
缺点有一定的误识别率有一定的误识别率即某个元素可能存在但实际上并不存在。删除困难因为无法确定某个位置是由哪个元素映射而来的。 在线案例Bloom Filters 布隆过滤器存在误判率数组越小所占的空间越小误判率越高如果要降低误判率则数组越长但所占空间越大 最大限度的避免误差, 选取的位数组应尽量大, hash函数的个数尽量多, 但空间占用的浪费和性能的下降 业务选择的时候 需要误判率与bit数组长度和hash函数数量的平衡 布隆过滤器不能直接删除元素因为所属的bit可能多个元素有使用 如果要删除则需要重新生成布隆过滤器或者把布隆过滤器改造成带引用计数的方式 应用场景
解决海量数据下非精确过滤的业务场景
1垃圾邮件解决方案垃圾短信、黑名单同理 收集一组具有特定特征的垃圾邮件样本这些样本可以是文本内容或其他特征比如发件人、收件人等将这些样本的特征信息进行哈希处理并将处理后的结果存储在布隆过滤器中。接下来当有新的电子邮件到达时将该邮件的特征信息也进行哈希处理并且与布隆过滤器中的信息进行比较。如果布隆过滤器中存在该邮件的特征信息则判断该邮件为垃圾邮件如果不存在则判断该邮件为正常邮件
2解决缓存穿透解决方案 什么是缓存穿透查询不存在数据查询一个不存在的数据由于缓存是不命中的如发起为id为“-1”不存在的数据。如果从存储层查不到数据则不写入缓存导致这个不存在的数据每次请求都要到存储层去查询大量查询不存在的数据可能DB就挂掉了是黑客利用不存在的key频繁攻击应用的一种方式。 方案就是将所有要【缓存的数据】经过处理后存储布隆过滤器中即对应的bit上是1当外部请求发起时首先会把请求的参数通过哈希算法处理获得相应的哈希值根据哈希值计算出位数组中的位置。
如果全部计算的hash值对于的bit存储都是1则表示数据在合理中从缓存读出缓存失效则从数据库中取出
如果计算的hash值对于的bit存储存在一个是0或以上则表示这条数据不合理直接返回数据不存在不查缓存和数据库如果布隆过滤器认为值不存在那么值一定是不存在的无需查询缓存也无需查询数据库
3爬虫URL去重解决方案 需求大量的网页爬取通过解析已经爬取页面中的网页链接然后再爬取这些链接对应的网页同一个网页链接有可能被包含在多个页面中会导致爬虫在爬取的过程中重复爬取相同的网页 方案创建布隆过滤器根据业务数据量设置位数组的大小将位数组全部设置为0 将每个URL地址通过哈希算法处理获得相应的哈希值 根据哈希值计算出位数组中的位置将位数组中的位置设置为1 当新的URL地址进入时重复上述步骤计算出对应的位置检查位数组中的位置是否为0如果是0则表示该URL地址一定没被爬取过 如果URL地址不存在经过爬虫处理后则将其对应的位置设置为1以表示该URL地址已经存在 重复上述步骤直到所有的URL地址都处理完毕完成去重。
POM 依赖
dependenciesdependencygroupIdorg.springframework.boot/groupIdartifactIdspring-boot-starter-web/artifactId/dependencydependencygroupIdorg.springframework.boot/groupIdartifactIdspring-boot-starter-test/artifactIdscopetest/scope/dependencydependencygroupIdorg.apache.commons/groupIdartifactIdcommons-lang3/artifactIdversion3.12.0/version/dependencydependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactIdversion31.1-jre/version/dependency/dependencies Testpublic void testGeneUrl() {try{File file new File(urls.txt);if (!file.exists()) {file.createNewFile(); // 创建新文件,有同名的文件的话直接覆盖}FileOutputStream fos new FileOutputStream(file, true);OutputStreamWriter osw new OutputStreamWriter(fos);BufferedWriter bw new BufferedWriter(osw);StringBuilder builder new StringBuilder();for (int i 0; i 5000000; i) {String name RandomStringUtils.randomAlphabetic(5);String fileName https://www. name .com i \n;builder.append(fileName);}bw.write(String.valueOf(builder));bw.newLine();bw.flush();bw.close();osw.close();fos.close();} catch (FileNotFoundException e1) {e1.printStackTrace();} catch (IOException e2) {e2.printStackTrace();}} //参数一 指定布隆过滤器中存的是什么类型的数据有 IntegerFunnelLongFunnelStringCharsetFunnel
//参数二 预期需要存储的数据量
//参数三 误判率默认是 0.03
BloomFilter.create(Funnels.stringFunnel(Charset.forName(UTF-8)), 5000000, 0.01); 4分库分表下手机号重复注册解决方案 一般业务里面的partitionKey是不可变动的所以不能用手机号作为分片键换手机号需求是存在的所以业务里面的分片键多数是固定的业务id比如user_id 创建布隆过滤器根据业务数据量设置位数组的大小将位数组全部设置为0 把要注册的手机号通过通过哈希算法处理获得相应的哈希值 根据哈希值计算出位数组中的位置如果对应的位数组中的位置有存在0则一定是未注册的 如果经过多个hash函数处理对应的位数组中都是1则认为是注册过的 最后如果用户注册成功后将位数组中的位置设置为1 Beanpublic Set set() throws IOException {SetString set new LinkedHashSet();FileInputStream inputStream new FileInputStream(new File(urls.txt));InputStreamReader streamReader new InputStreamReader(inputStream);BufferedReader reader new BufferedReader(streamReader);String line null;while (true) {line reader.readLine();if (line ! null) {set.add(line);} else {break;}}inputStream.close();return set;}Beanpublic BloomFilter bloomFilter() throws IOException {BloomFilter bloomFilter BloomFilter.create(Funnels.stringFunnel(Charset.forName(UTF-8)), 5000000, 0.01);FileInputStream inputStream new FileInputStream(new File(urls.txt));InputStreamReader streamReader new InputStreamReader(inputStream);BufferedReader reader new BufferedReader(streamReader);String line null;while (true) {line reader.readLine();if (line ! null) {bloomFilter.put(line);} else {break;}}inputStream.close();return bloomFilter;}RestController
RequestMapping(/api)
public class FilterController {Autowiredprivate BloomFilterString bloomFilter;Autowiredprivate Set set;GetMapping(/bloom)public String list() throws IOException {//判断是否包含这个内容if (bloomFilter.mightContain(https://www.dhVrX.com5)) {return 命中了;} else {return 没命中;}}GetMapping(/set)public String set() {if (set.contains(httssps://www.shncb.com999663)) {return 命中了;} else {return 没命中;}}}
