文档章节

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

zgw06629
 zgw06629
发布于 2015/04/27 12:38
字数 454
阅读 195
收藏 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
Java中的Set集合

Set集合不允许包含相同的元素,如果试图把两个相同的元素加入同一个Set集合里面,则添加操作失败,add()方法返回false,且新元素不会被添加入。 1.HashSet是Set的接口的典型实现,大多数时...

西红柿的眼泪
2016/07/13
40
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

没有更多内容

加载失败,请刷新页面

加载更多

js之正则表达式修饰符/ig

正则表达式中/i,/g,/ig,/gi,/m的区别和含义 /i (忽略大小写) /g (全文查找出现的所有匹配字符) /m (多行查找) /gi(全文查找、忽略大小写) /ig(全文查找、忽略大小写) 修饰符 修饰符 描述 i ...

youfen
32分钟前
1
0
druid架构及原理

应用场景 设计一个系统来预估未来一年的广告流量,不是总流量,是任意时间段任何定向(Targeting)条件约束情况下的流量。定向条件有近百种(内容类别,设备平台,用户地域,用户人口属性等),...

hblt-j
39分钟前
3
0
solr使用

solr 7.3安装配置、中文分词配置 solr7.4 配置ikanalyzer和自带的中文分词器

微小宝
47分钟前
1
0
常用的HTTP方法有哪些?

1、常用的HTTP方法有哪些? GET: 用于请求访问已经被URI(统一资源标识符)识别的资源,可以通过URL传参给服务器 POST:用于传输信息给服务器,主要功能与GET方法类似,但一般推荐使用POST方...

晚风0623
59分钟前
2
0
windows系统使用技巧

windows使用一段时间,系统盘剩余空间会变小,如下目录可以删除,清理出一些物理空间。 1.将桌面文件移动到其他硬盘。 2.【下面目录下的文件都是可以删除的】 C:\Users\dell\AppData\Local\...

硅谷课堂
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部