- 浏览: 19941 次
文章分类
- 全部博客 (17)
- Struts (0)
- Servlet (1)
- Interview (1)
- Shell (1)
- java (5)
- Linux (0)
- ACM (1)
- 程序员 (0)
- Sprint (0)
- Spring (1)
- WEB (0)
- 学习方法 (0)
- JSP (0)
- other problems Collecting (0)
- Hibernate (0)
- Thread (1)
- AWT (0)
- 生活哲理 (0)
- IT 人物 (1)
- IT knowledge (0)
- 版本管理软件 (1)
- 深入java (0)
- Oracle (0)
- Activity (0)
- GUI (1)
- English (0)
- 网络编程 (0)
- Practice (0)
- 项目实践 (0)
- 金融 (0)
- 面试 (1)
- 新知识 (0)
- 温故旧知识 (0)
- 账户管理 (0)
- IT 警言 (1)
- 学习 (0)
- Strus (0)
- 问题 (0)
- 武术 (0)
- 经济 (0)
- 项目 (0)
- 项目构建工具 (0)
- 每天学习 (0)
- 面试题 (0)
- 编程实践-解题(Solution) (0)
- 领悟 (0)
- log (0)
- 编程 (0)
- 算法 (0)
- Java 学习 (0)
- 好好学习,天天进步-每一天的时间都一样,但是可以有不同的价值 (0)
- 幸福 (0)
- hibernate 实践笔记 (0)
- Spring 实践笔记 (0)
- 设计模式系列 (0)
- acm 练习总结 (0)
- JVM 学习 (0)
- 目标 (0)
- 人生准则 (0)
- 开源 框架 (0)
- AOP 学习系列 (0)
- java 网络编程 (0)
- 源码学习 (0)
- ClassLoader (0)
- 动态代理 (0)
- 开源项目 (0)
- 编码 (0)
- 我的生活领悟 (0)
- 事务安排 (0)
- 电话面试 (0)
- 学习笔记 (0)
- 开源软件学习 (0)
- PLSQL (0)
- 面试准备 (0)
- 日记 (0)
- 离职找工作日记 (0)
- hibernate 学习 (0)
- tomcat 源码学习 (0)
- 成长日记 (0)
- 算法学习-从概念开始一点一点的学习 (0)
- Spring MVC (0)
- 进步的人生 (0)
- 一定要坚定 (0)
- 程序员的实力 (0)
- 学习进步-日知其所亡,月无忘其所能,学无先后,快慢,达者为先,通者为先。 (0)
- 日知其所亡,月无忘其所能,学无先后,快慢,达者为先,通者为上 (0)
- 公积金 (0)
- test (0)
今天在做如何从两个数组中取出相同的元素时碰到了一个问题,想知道下面哪种算法更快,(听说是HashSet 的会更快,但是想知道为什么会更快呢?):
具体测试程序:
运行结果:
HashSet Result :10001
HashSet Algorithm using time :15
two loops Result :10001
two loops Algorithm using time :11060
结果分析:
java 的HashSet 的contains(Object o) 方法内部采用的是map.containsKey()方法。
上面的具体实现用到了哈希算法,即根据一个对象的hashCode 可以用(1)的时间判断该对象是否在这个map 里,如果在,只需要跟一些hashCode 值跟该对象一样的对象比较一下内容,就可得出答案,而这个在双重循环里需要一个一个跟所有的对象比较,显然效率不一样。
在上面的代码实现中用到了API一些函数,列出在此了解参考
/**
* Check for equality of non-null reference x and possibly-null y.
*/
static boolean eq(Object x, Object y) {
return x == y || x.equals(y);
}
Entry class : static class Entry<K,V> implements Map.Entry<K,V>
// Returns internal representation for key. Use NULL_KEY if key is null.
static <T> T maskNull(T key) {
return key == null ? (T)NULL_KEY : key;
}
具体测试程序:
/** * get the same element in two arrays */ import java.util.*; import java.io.*; public class AlgorithmTest{ public static void main(String[] args)throws Exception{ // read the data from file FileReader fr = new FileReader("C:/test_data_1.txt"); int temp; StringBuilder sb= new StringBuilder(); while((temp=fr.read())!=-1){ sb.append((char)temp); } // System.out.println(sb); String[] a = sb.toString().split(" "); Integer[] in1 = new Integer[a.length]; for(int i=0;i<a.length;i++){ in1[i] = Integer.parseInt(a[i]); } Integer[] in2 = new Integer[10000]; for(int i=0;i<10000;i++){ in2[i] = in1[i*2]; } long before,after; // Algorithm 1 Set bs = new HashSet(Arrays.asList(in2)); List<Integer> result = new ArrayList<Integer>(); before = System.currentTimeMillis(); for(int i=0;i<in1.length;i++){ if(bs.contains(in1[i])){ // System.out.println(a[i]); result.add(in1[i]); } } after = System.currentTimeMillis(); System.out.println("HashSet Result :" + result.size()); System.out.println("HashSet Algorithm using time :" + (after-before)); // Algorithm 2 result = new ArrayList<Integer>(); before = System.currentTimeMillis(); for(int i=0;i<in1.length;i++) for(int j=0;j<in2.length;j++) { if(in1[i].equals(in2[j])){ result.add(in1[i]); } } after = System.currentTimeMillis(); System.out.println("two loops Result :" + result.size()); System.out.println("two loops Algorithm using time :" + (after-before)); } } 其中,test data file 是用这个类生成的 /** * generate the large test data */ import java.io.*; public class GenTestData{ public static void main(String[] args)throws Exception{ String fn = "C:/test_data_1.txt"; FileWriter fs = new FileWriter(fn); for(int i=0;i<100000;i++){ // 直接写字符串 fs.write(i+" "); } } }
运行结果:
HashSet Result :10001
HashSet Algorithm using time :15
two loops Result :10001
two loops Algorithm using time :11060
结果分析:
java 的HashSet 的contains(Object o) 方法内部采用的是map.containsKey()方法。
private transient HashMap<E,Object> map; public boolean contains(Object o) { return map.containsKey(o); } 而containsKey 方法的具体实现: /** * Returns <tt>true</tt> if this map contains a mapping for the * specified key. * * @param key The key whose presence in this map is to be tested * @return <tt>true</tt> if this map contains a mapping for the specified * key. */ public boolean containsKey(Object key) { Object k = maskNull(key); int hash = hash(k.hashCode()); int i = indexFor(hash, table.length); Entry e = table[i]; while (e != null) { if (e.hash == hash && eq(k, e.key)) return true; e = e.next; } return false; }
上面的具体实现用到了哈希算法,即根据一个对象的hashCode 可以用(1)的时间判断该对象是否在这个map 里,如果在,只需要跟一些hashCode 值跟该对象一样的对象比较一下内容,就可得出答案,而这个在双重循环里需要一个一个跟所有的对象比较,显然效率不一样。
在上面的代码实现中用到了API一些函数,列出在此了解参考
/**
* Check for equality of non-null reference x and possibly-null y.
*/
static boolean eq(Object x, Object y) {
return x == y || x.equals(y);
}
Entry class : static class Entry<K,V> implements Map.Entry<K,V>
// Returns internal representation for key. Use NULL_KEY if key is null.
static <T> T maskNull(T key) {
return key == null ? (T)NULL_KEY : key;
}
发表评论
-
java 内置的比较器
2012-06-28 12:04 947在java 里,有一些内置的比较器,比如CaseInsensi ... -
java 每日学习
2012-06-22 11:57 0今天看了简单工厂模式与工厂方法模式,然后看的过程中碰到一些问题 ... -
java RTTI- runtime type information (think in java )
2012-06-18 23:53 0Class 类 equals 方法比较与 instanceof ... -
ant 使用
2012-05-30 00:39 0ant : a neat tool 1.下载 ant ht ... -
java multithread
2012-05-24 13:24 0java 多线程 使用condition 来控制协调。 区别 ... -
java Queue
2012-05-24 10:39 0java Collection Queue 的实现及 Pri ... -
网络连接例子
2012-05-20 20:39 0来自java 学习室 -
java io 集合 笔试题
2012-05-18 18:44 0摩根笔试题: import java.io.Buffere ... -
f(n) = f(n-1) + f(n-2) 实现(递归与非递归运行时间比较)
2012-05-18 15:40 2512Fibonacci 算法递归实现与非递归实现时间比较: ... -
学习 JAVA IO
2012-05-17 00:29 0http://www.java3z.com/cwbwebhom ... -
java Runtime
2012-05-16 22:47 0Java垃圾回收时需要用到Runtime(这是一个单例模式), ... -
装饰模式
2012-05-16 12:19 0问题: 根据问题来学习,并学习如何理解讲解问题更透彻明白,及学 ... -
java io 设计
2012-05-15 22:46 0转载自: http://www.blogjav ... -
垃圾回收
2012-05-14 21:34 0参考垃圾回收电子书: ... -
java 基础
2012-05-03 23:50 710读 《研读设计模式》 简单工厂的优缺点: 帮助封装 简单工厂 ... -
java 多态的情况
2012-04-15 23:34 1073参考 http://topic.csdn.net/u/2012 ...
相关推荐
java集合 java集合思维导图 java集合总结
xmind格式的Java集合框架学习导图,包括Collection接口/Map接口以及具体实现类。 同样包含大厂面试题,也在导图中有所体现。 能学到什么: 更加成体系的知识框架,更加全面的、系统的知识。 思维导图: 思维导图具有...
键盘录入5个学生信息(姓名,语文成绩,数学成绩,英语成绩),按照总分从高到低输出到控制台java 集合练习题
java集合基础习题及答案,
Java集合整体讲解,其中包含了Collection,Map,Iterator和一些工具类,以及集合整体大框架
java 集合 List arrayList vector map set
Java 集合排序 及java集合类 详解.pdf
该文档主要详细总结了Java集合的相关知识,包括Collection和Map接口、Collection接口的子接口List和Set接口以及具体的实现类、存储原理等;Map接口的子接口HashMap、LinkedHashMap、TreeMap、Properties等
Java 集合排序及java 集合类详解,Java里面最重要、最常用也就是集合那部分了,能够用好集合和理解好集合对于做Java程序的开发拥有无比的好处。本教程详细解释了关于Java中的集合是如何实现的, 以及他们的实现原理...
Java集合框架总结Java集合框架总结Java集合框架总结Java集合框架总结Java集合框架总结Java集合框架总结
内含大量java集合框架方面常被面试官问到的经典面试题。
Java集合排序及java集合类详解,对list,set,map等java集合进行详细讲解
集合是将多个元素组成一个单元的...Java集合框架,为我们提供了一套性能优良、使用方便的接口和类,我们不必再重新发明轮子,只需学会如何使用它们,就可以处理实际应用中出现的问题了Java集合框架位于java.util包中
关于java集合资料的整理 集合接口:6个接口,表示不同集合类型,是集合框架的基础。 抽象类:5个抽象类,对集合接口的部分实现。可扩展为自定义集合类。 实现类:8个实现类,对接口的具体实现。 在很大程度上,...
Java集合框架详解Java集合框架详解Java集合框架详解
java集合框架图java集合框架图java集合框架图java集合框架图java集合框架图
Java集合详解,详细讲解java的集合类,对java集合类的最详细的讲解。我自己的总结,保证大家看了很有收获
java集合
java 集合分组排序帮助类有好的意见可以互相交流不甚感激