设为首页 - 加入收藏 内江站长网 (http://www.0832zz.com)- 国内知名站长资讯网站,提供最新最全的站长资讯,创业经验,网站建设等!
热搜: 已经 我的 千万 英国
当前位置: 首页 > 运营中心 > 建站资源 > 优化 > 正文

内存崩溃了?其实你只需要换一种方式

发布时间:2019-11-04 23:06 所属栏目:[优化] 来源:平头哥
导读:在上一篇 Java 多线程爬虫及分布式爬虫架构探索 中,我们使用了 JDK 自带的 Set 集合来进行 URL 去重,看上去效果不错,但是这种做法有一个致命了缺陷,就是随着采集的 URL 增多,你需要的内存越来越大,最终会导致你的内存崩溃。那我们在不使用数据库的情

在上一篇 Java 多线程爬虫及分布式爬虫架构探索 中,我们使用了 JDK 自带的 Set 集合来进行 URL 去重,看上去效果不错,但是这种做法有一个致命了缺陷,就是随着采集的 URL 增多,你需要的内存越来越大,最终会导致你的内存崩溃。那我们在不使用数据库的情况下有没有解决办法呢?还记得我们在上一篇文章中提到的布隆过滤器吗?它就可以完美解决这个问题,布隆过滤器有什么特殊的地方呢?接下来就一起来学习一下布隆过滤器。

内存崩溃了?其实你只需要换一种方式

什么是布隆过滤器

布隆过滤器是一种数据结构,比较巧妙的概率型数据结构,它是在 1970 年由一个名叫布隆提出的,它实际上是由一个很长的二进制向量和一系列随机映射函数组成,这点跟哈希表有些相同,但是相对哈希表来说布隆过滤器它更高效、占用空间更少,布隆过滤器有一个缺点那就是有一定的误识别率和删除困难。布隆过滤器只能告诉你某个元素一定不存在或者可能存在在集合中, 所以布隆过滤器经常用来处理可以忍受判断失误的业务,比如爬虫 URL 去重。

布隆过滤器原理

在说布隆过滤器原理之前,我们先来复习一下哈希表,在上一篇文章中,我们利用的是 Set 来进行 URL 去重,我们来看看 Set 的存储模型

内存崩溃了?其实你只需要换一种方式

Set url 去重

URL 经过一个哈希函数后,将 URL 存入了数组里,这样查询时也是非常高效的,但是由于数组里存入的是 URL,随着 URL 的增多,需要的数组越来越大,意味着你需要更多的内存,比如我们采集了几亿的 URL,那么可能就需要上百G 的内存,这是条件不允许的,因为内存特别的昂贵,所以这个在 url 去重中是不可取的,占内存更小的布隆过滤器就是一种不错的选择。

布隆过滤器实质上由长度为 m 的位向量或位列表(仅包含 0 或 1 位值的列表)组成,最初所有值均设置为 0,如下所示。

内存崩溃了?其实你只需要换一种方式

布隆过滤器

因为底层是 bit 数组,所以意味着数组只有 0、1 两个值,跟哈希表一样,我们将 URL 通过 K 个函数映射 bit 数组里,并且将指向的 Bit 数组对应的值改成 1 。我们以 /nba/2492297.html 为例,如下图所示。

内存崩溃了?其实你只需要换一种方式

布隆过滤器

/nba/2492297.html经过三个哈希函数分别映射到了 1、4、9 的位置,这三个 bit 数组的值就变成了 1,我们再存入一个 /nba/2492298.html,此时 bit 数组就变成下面这样:

内存崩溃了?其实你只需要换一种方式

布隆过滤器

/nba/2492298.html被映射到了 0、4、11 的位置,所以此时 bit 数组上有 5 个位置的值为 1,本应该是有 6 个值为 1 的,但是因为在 4 这个位置重复了,所以会覆盖。

布隆过滤器是如何判断某个值一定不存在或者可能存在呢?通过判断哈希函数映射到对应数组的值,如果都为 1,说明可能存在,如果有一个不为 1,说明一定不存在。对于一定不存在好理解,但是都为 1 时,为什么说可能存在呢?这跟哈希表一样,哈希函数会产生哈希冲突,也就是说两个不同的值经过哈希函数都会得到同一个数组下标,布隆过滤器也是一样的。我们以判断 /nba/2492299.html 是否已经采集过为例,经过哈希函数映射的 bit 数组上的位置如下图所示:

内存崩溃了?其实你只需要换一种方式

布隆过滤器

/nba/2492299.html 被哈希函数映射到了 4、9、11 的位置,而这几个位置的值都为 1 ,所以布隆过滤器就认为 /nba/2492299.html 被采集过了,实际上是没有采集过的,这就说明了布隆过滤器存在误判,这也是我们业务允许的。布隆过滤器的误判率跟 bit 数组的大小和哈希函数的个数有关系,如果 bit 数组过小,哈希函数过多,那么 bit 数组的值很快都会变成 1,这样误判率就会越来越高,bit 数组过大,就会浪费更多的内存,所以就要平衡好 bit 数组的大小和哈希函数的个数,关于如何平衡这两个的关系,不是我们这篇文章的重点。

布隆过滤器的原理我们已经了解了,为了加深对布隆过滤器的理解,我们用 Java 来实现一个简易版的布隆过滤器,代码如下:

  1. public class SimpleBloomFilterTest { 
  2.     // bit 数组的大小 
  3.     private static final int DEFAULT_SIZE = 1000; 
  4.     // 用来生产三个不同的哈希函数的 
  5.     private static final int[] seeds = new int[]{7, 31, 61,}; 
  6.     // bit 数组 
  7.     private BitSet bits = new BitSet(DEFAULT_SIZE); 
  8.     // 存放哈希函数的数组 
  9.     private SimpleHash[] func = new SimpleHash[seeds.length]; 
  10.     public static void main(String[] args) { 
  11.         SimpleBloomFilterTest filter = new SimpleBloomFilterTest(); 
  12.         filter.add("https://voice.hupu.com/nba/2492440.html"); 
  13.         filter.add("https://voice.hupu.com/nba/2492437.html"); 
  14.         filter.add("https://voice.hupu.com/nba/2492439.html"); 
  15.         System.out.println(filter.contains("https://voice.hupu.com/nba/2492440.html")); 
  16.         System.out.println(filter.contains("https://voice.hupu.com/nba/249244.html")); 
  17.     } 
  18.     public SimpleBloomFilterTest() { 
  19.         for (int i = 0; i < seeds.length; i++) { 
  20.             func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]); 
  21.         } 
  22.     } 
  23.     /** 
  24.      * 向布隆过滤器添加元素 
  25.      * @param value 
  26.      */ 
  27.     public void add(String value) { 
  28.         for (SimpleHash f : func) { 
  29.             bits.set(f.hash(value), true); 
  30.         } 
  31.     } 
  32.     /** 
  33.      * 判断某元素是否存在布隆过滤器 
  34.      * @param value 
  35.      * @return 
  36.      */ 
  37.     public boolean contains(String value) { 
  38.         if (value == null) { 
  39.             return false; 
  40.         } 
  41.         boolean ret = true; 
  42.         for (SimpleHash f : func) { 
  43.             ret = ret && bits.get(f.hash(value)); 
  44.         } 
  45.         return ret; 
  46.     } 
  47.  
  48.     /** 
  49.      * 哈希函数 
  50.      */ 
  51.     public static class SimpleHash { 
  52.         private int cap; 
  53.         private int seed; 
  54.         public SimpleHash(int cap, int seed) { 
  55.             this.cap = cap; 
  56.             this.seed = seed; 
  57.         } 
  58.         public int hash(String value) { 
  59.             int result = 0; 
  60.             int len = value.length(); 
  61.             for (int i = 0; i < len; i++) { 
  62.                 result = seed * result + value.charAt(i); 
  63.             } 
  64.             return (cap - 1) & result; 
  65.         } 
  66.     } 

【免责声明】本站内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。

网友评论
推荐文章