文档章节

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

zgw06629
 zgw06629
发布于 2015/04/27 12:38
字数 454
阅读 163
收藏 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
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

没有更多内容

加载失败,请刷新页面

加载更多

Mac OS X下Maven的安装与配置

Mac OS X 安装Maven: 下载 Maven, 并解压到某个目录。例如/Users/robbie/apache-maven-3.3.3 打开Terminal,输入以下命令,设置Maven classpath $ vi ~/.bash_profile 添加下列两行代码,之后...

TonyStarkSir
今天
3
0
关于编程,你的练习是不是有效的?

最近由于工作及Solution项目的影响,我在重新学习DDD和领域建模的一些知识。然后,我突然就想到了这个问题,以及我是怎么做的? 对于我来说,提升技能的项目会有四种: 纯兴趣驱动的项目。即...

问题终结者
今天
3
0
打开eclipse出现an error has occurred see the log file

解决方法: 1,打开eclipse安装目录下的eclipse.ini文件; 2,打开的文本文件最后添加一行 --add-modules=ALL-SYSTEM 3,保存重新打开Eclipse。...

任梁荣
昨天
4
0
搞定Northwind示例数据库,无论哪个版本的SQLServer都受用

Northwind数据库 从这里可以找到突破口: http://social.msdn.microsoft.com/Forums/zh-CN/Vsexpressvb/thread/8490a1c6-9018-40c9-aafb-df9f79d29cde 下面是MSDN: http://msdn2.microsoft......

QQZZFT
昨天
1
0
mysql主从同步,安装配置操作

准备 两台mysql服务,我这里准备了如下: 主库:192.168.176.128 从库:192.168.176.131 如何在Linux上安装mysql服务,请看https://blog.csdn.net/qq_18860653/article/details/80250499 操作...

小致dad
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部