文档章节

当内存是瓶颈时,HashSet的一个替代类

zgw06629
 zgw06629
发布于 2015/04/27 12:38
字数 454
阅读 184
收藏 1

在菜谱抓取过程中,需要对已抓取的url进行去重,一开始使用的HashSet来去重,但占用内存较大。于是改用BloomFilter(goolge guava jar包中的一个工具类)来去重。

下面是对HashSet与BloomFilter的内存占用与误报率(明明不在集合中,却被当做已存在)的比较。

比较内存占用:

分别插入90万个由六位数字字符组成的字符串到HashSet与BloomFilter中。

Set<String> set = new HashSet<>();
for(int i=10_0000; i<100_0000; i++)
        set.add(""+i);
//第一个参数表示将字符串插入到集合中 第二个参数表示预期插入数量 第三个表示可以接受的误报率
BloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 100_0000, 0.001);
for(int i=10_0000; i<100_0000; i++)
    bf.put(i+"");

通过一个工具类计算得到它们内存占用量分别为:

set memory: 87,588,704 (约为87M)
bloom filter memory: 1,797,624 (约为1M)

再比较误报率:

int falseHitCount = 0;
Set<String> set = new HashSet<>();
for(int i=10_0000; i<100_0000; i++){
    if(set.contains(i+"")) //插入set中之前 先判断是否存在
        falseHitCount ++ ;
    set.add(i+"");
}
int falseHitCount = 0;
BloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 100_0000, 0.001);
for(int i=10_0000; i<100_0000; i++){
    if(bf.mightContain(i+"")) // 插入bloom filter中之前 先判断是否存在
        falseHitCount++;
    bf.put(i+"");
}

hashset flase hit count: 0
bloom filter false hit count : 54

即HashSet不存在误报的情况, 而构造BloomFilter时第三个参数指定了误报率为千分之一,而实际的误报率为54 / 90_0000.

总结:

若业务可以容忍个别的误报(如漏抓个别菜谱)的话, 可以考虑使用BloomFilter来代替HashSet。

补充:

计算对象大小,可以参考此篇博文:

http://blog.csdn.net/xieyuooo/article/details/7068216

Guava maven坐标:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>15.0</version>
</dependency>



© 著作权归作者所有

共有 人打赏支持
zgw06629
粉丝 16
博文 54
码字总数 30471
作品 0
海淀
程序员
私信 提问
HashSet的hashCode方法和equals方法的重写,TreeSet中compareTo方法的重写,Comparator在treeSet中的应用。

HashSet的hashCode方法和equals方法的重写,TreeSet中compareTo方法的重写,Comparator在treeSet中的应用。 HashSet: 首先,hashset底层是hash值的地址,它里面存的对象是无序的。 当需要在...

day戴
2014/04/28
0
0
Android中的数据结构和算法

Android客户端面试基础(五)-数据结构与算法- http://blog.csdn.net/johnWcheung/article/details/72843223 数据结构:是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之...

shareus
2017/12/18
0
0
Effective-java 3 中文翻译系列 (Item 18)

看了Effective-java2的中文翻译版之后...就打算自己翻译一下第3版。会将翻译的文章上传到 github (欢迎关注,欢迎大神提点。) ITEM 18 重组合,轻继承 继承是实现代码重用的有效方法,但是...

薛银亮
06/11
0
0
重写equal 的同时为什么必须重写hashcode?

hashCode是编译器为不同对象产生的不同整数,根据equal方法的定义:如果两个对象是相等(equal)的,那么两个对象调用hashCode必须产生相同的整数结果,即:equal为true,hashCode必须为tru...

未明儿
2014/03/30
0
1
java集合介绍

对于高级语言来说,集合(容器)是非常的重要的知识点,也是非常基础的,相信很多刚毕业的同学包括初级程序员和求职的过程中,经常会被问到集合相关的知识。我觉得该文只是对集合的一个简单的...

The_flying_pig
2017/09/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Sentry使用

Sentry使用 以django为例.实际上sentry本身文档已经有介绍了.这里只是再总结 1、全局异常捕获 此方法可以全局捕获任何的异常(甚至包括你自己raise的异常),在实际使用过程中不太推荐.但胜在快...

_Change_
15分钟前
0
0
linux系统包管理工具详解 yum rpm apt-get pip wget

在Linux系统下,根据系统版本的不同会有各种各样的包管理工具,下面就简单的梳理一下这几种安装命令. 1、yum Yum(全称为 Yellow dog Updater, Modified)是一个在Fedora、RedHat、CentOS中的...

huoyoung
18分钟前
0
0
阿里巴巴Dubbo实现的源码分析

1. Dubbo概述 Dubbo是阿里巴巴开源出来的一个分布式服务框架,致力于提供高性能和透明化的RPC远程服务调用方案,以及作为SOA服务治理的方案。它的核心功能包括: #remoting:远程通讯基础,提...

别打我会飞
19分钟前
3
0
tomcat的maxThreads、acceptCount(最大线程数、最大排队数)

tomcat 6的Connector配置如下: <Connector port="8080" protocol="HTTP/1.1" connectionTimeout="20000" redirectPort="8443" maxThreads......

为了美好的明天
23分钟前
1
0
阿里P9架构师谈:高并发网站的监控系统选型、比较、核心监控指标

在高并发分布式环境下,对于访问量大的业务、接口等,需要及时的监控网站的健康程度,防止网站出现访问缓慢,甚至在特殊情况出现应用服务器雪崩等场景,在高并发场景下网站无法正常访问的情况...

架构师springboot
23分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部