内存瓦解了？着实你只必要换一种方法

在上一篇 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 来实现一个浅显版的布隆过滤器，代码如下：

public class SimpleBloomFilterTest { 
    // bit 数组的巨细 
    private static final int DEFAULT_SIZE = 1000; 
    // 用来出产三个差异的哈希函数的 
    private static final int[] seeds = new int[]{7, 31, 61,}; 
    // bit 数组 
    private BitSet bits = new BitSet(DEFAULT_SIZE); 
    // 存放哈希函数的数组 
    private SimpleHash[] func = new SimpleHash[seeds.length]; 
    public static void main(String[] args) { 
        SimpleBloomFilterTest filter = new SimpleBloomFilterTest(); 
        filter.add("https://voice.hupu.com/nba/2492440.html"); 
        filter.add("https://voice.hupu.com/nba/2492437.html"); 
        filter.add("https://voice.hupu.com/nba/2492439.html"); 
        System.out.println(filter.contains("https://voice.hupu.com/nba/2492440.html")); 
        System.out.println(filter.contains("https://voice.hupu.com/nba/249244.html")); 
    } 
    public SimpleBloomFilterTest() { 
        for (int i = 0; i < seeds.length; i++) { 
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]); 
        } 
    } 
    /** 
     * 向布隆过滤器添加元素 
     * @param value 
     */ 
    public void add(String value) { 
        for (SimpleHash f : func) { 
            bits.set(f.hash(value), true); 
        } 
    } 
    /** 
     * 判定某元素是否存在布隆过滤器 
     * @param value 
     * @return 
     */ 
    public boolean contains(String value) { 
        if (value == null) { 
            return false; 
        } 
        boolean ret = true; 
        for (SimpleHash f : func) { 
            ret = ret && bits.get(f.hash(value)); 
        } 
        return ret; 
    } 
 
    /** 
     * 哈希函数 
     */ 
    public static class SimpleHash { 
        private int cap; 
        private int seed; 
        public SimpleHash(int cap, int seed) { 
            this.cap = cap; 
            this.seed = seed; 
        } 
        public int hash(String value) { 
            int result = 0; 
            int len = value.length(); 
            for (int i = 0; i < len; i++) { 
                result = seed * result + value.charAt(i); 
            } 
            return (cap - 1) & result; 
        } 
    } 
} 

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!