文档章节

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

zgw06629
 zgw06629
发布于 2015/04/27 12:38
字数 454
阅读 154
收藏 1
点赞 0
评论 0

在菜谱抓取过程中,需要对已抓取的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
粉丝 15
博文 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中的Set集合

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

西红柿的眼泪
2016/07/13
40
0
java集合介绍

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

The_flying_pig
2017/09/18
0
0
通过分析 JDK 源代码研究 Hash 存储机制

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,HashSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范不同...

红薯
2009/11/30
856
2
equals和hashCode的关系

Java中的equals方法和hashCode方法是Object中的,所以每个对象都是有这两个方法的,有时候我们需要实现特定需求,可能要重写这两个方法,今天就来介绍一些这两个方法的作用。 equals()和has...

单身裤子
2016/11/15
14
0
Java map双括号初始化方式的问题

关于Java双括号的初始化凡是确实很方便,特别是在常量文件中,无可替代。如下所示: Map map = new HashMap() {   {   put("Name", "Unmi");   put("QQ", "1125535");   } }; 好处很明...

Airship
2015/02/28
0
0
byte[]作为key存储在HashSet中

byte[]作为key存储在HashSet中 hashCode和equals方法 当使用ide进行开发时,最简单的重写就是用ide自动生成hashCode和equals方法 例如: package hashcode; /** * Created with IntelliJ ID...

秋风醉了
2014/07/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

sklearn学习笔记之简单线性回归

简单线性回归 线性回归是数据挖掘中的基础算法之一,从某种意义上来说,在学习函数的时候已经开始接触线性回归了,只不过那时候并没有涉及到误差项。线性回归的思想其实就是解一组方程,得到...

wangxuwei
2分钟前
0
0
feign之动态interceptor(二)

背景 上文提到了按照不同的feignClient可以根据多个不同的key来进行多个不同的bean的配置 那么我们如何完成多个interceptor的配置呢? 分析 我们刚提到多个配置的玄机就在FeignClientProper...

Mr_Qi
4分钟前
1
0
Linux Kernel 4.16 系列停止维护,用户应升级至 4.17

知名 Linux 内核维护人员兼开发人员 Greg Kroah-Hartman 近日在发布 4.16.18 版本的同时,宣布这是 4.16 系列的最后一个维护版本,强烈建议用户立即升级至 4.17 系列。 Linux 4.16 于 2018 年...

问题终结者
28分钟前
0
0
Apache配置时.htaccess失效不起作用的原因分析

.htaccess 失效的原因 1. 重写规则有问题,检查自己的重写规则 2.Apache配置问题,配置中没有配置启用 rewrite a2enmod rewrite 3.网站配置文件没有启用配置需要配置 000-default.conf <Dire...

TU-DESGIN
48分钟前
1
0
两个求最大公约数C/C++算法实现

#include<stdio.h> #include<time.h> #include <iostream>using namespace std;//求最大公约数 LCD(Largest Common Division)//短除法 //m=8251, n=6105; int LCD_ShortDiv(int m, ......

失落的艺术
54分钟前
1
0
QueryPerformanceCounter

windows的Sleep函数,睡眠线程指定毫秒数,可以用来做毫秒延时。 对于微秒延时,没有一个现成的函数,但是可以通过 QueryPerformanceFrequency QueryPerformanceCounter 来间接实现。原理就是...

开飞色
今天
1
0
log4j2使用AsyncRoot不显示行号问题处理

<AsyncRoot level="info" includeLocation="true"> <AppenderRef ref="File"/></AsyncRoot><!--1.异步logger,还需要在pom.xml中添加disruptor的依赖。2.includeLocation结合异......

小翔
今天
3
0
安卓手机上 K 歌,声音延迟怎么解决?

这篇文章可以为你提供一个解决录音和播放同步问题的思路,而且解决了声音从手机传输到耳机上有延时的问题。 初识音频 在开始之前,我先简单介绍一下音频相关的基础知识,方便下文理解。 我们...

编辑部的故事
今天
2
0
使用token实现在有效期内APP自动登录功能

使用token实现在有效期内APP自动登录功能 http://sevennight.cc/2016/07/19/auto_login_impl.html

风云海滩
今天
2
0
Spring Boot集成RabbitMQ发送接收JSON

默认情况下RabbitMQ发送的消息是转换为字节码,这里介绍一下如何发送JSON数据。 ObjectMapper 最简单发送JSON数据的方式是把对象使用ObjectMapper等JSON工具类把对象转换为JSON格式,然后发送...

小致dad
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部