文档章节

集合类操作优化经验总结(三)

M
 Mysoft
发布于 2015/09/24 14:01
字数 3358
阅读 45
收藏 4

集合类实践

ArrayList、Vector、LinkedList 均来自 AbstractList 的实现,而 AbstractList 直接实现了 List 接口,并扩展自 AbstarctCollection。ArrayList 和 Vector 使用了数组实现,ArrayList 没有对任何一个方法提供线程同步,因此不是线程安全的,Vector 中绝大部分方法都做了线程同步,是一种线程安全的实现。LinkedList 使用了循环双向链表数据结构,由一系列表项连接而成,一个表项总是包含 3 个部分,元素内容、前驱表项和后驱表项。

当 ArrayList 对容量的需求超过当前数组的大小时,需要进行扩容。扩容过程中,会进行大量的数组复制操作,而数组复制时,最终将调用 System.arraycopy() 方法。LinkedList 由于使用了链表的结构,因此不需要维护容量的大小,然而每次的元素增加都需要新建一个 Entry 对象,并进行更多的赋值操作,在频繁的系统调用下,对性能会产生一定的影响,在不间断地生成新的对象还是占用了一定的资源。而因为数组的连续性,因此总是 在尾端增加元素时,只有在空间不足时才产生数组扩容和数组复制。

ArrayList 是基于数组实现的,而数组是一块连续的内存空间,如果在数组的任意位置插入元素,必然导致在该位置后的所有元素需要重新排列,因此其效率较差,尽可能将数据插入到尾部。LinkedList 不会因为插入数据导致性能下降。

ArrayList 的每一次有效的元素删除操作后都要进行数组的重组,并且删除的元素位置越靠前,数组重组时的开销越大,要删除的元素位置越靠后,开销越小。LinkedList 要移除中间的数据需要便利完半个 List。

清单 4. ArrayList 和 LinkedList 使用代码
import java.util.ArrayList;
import java.util.LinkedList;

public class ArrayListandLinkedList {
 public static void main(String[] args){
 long start = System.currentTimeMillis();
 ArrayList list = new ArrayList();
 Object obj = new Object();
 for(int i=0;i<5000000;i++){
 list.add(obj);
 }
 long end = System.currentTimeMillis();
 System.out.println(end-start);
 
 start = System.currentTimeMillis();
 LinkedList list1 = new LinkedList();
 Object obj1 = new Object();
 for(int i=0;i<5000000;i++){
 list1.add(obj1);
 }
 end = System.currentTimeMillis();
 System.out.println(end-start);
 
 start = System.currentTimeMillis();
 Object obj2 = new Object();
 for(int i=0;i<1000;i++){
 list.add(0,obj2);
 }
 end = System.currentTimeMillis();
 System.out.println(end-start);
 
 start = System.currentTimeMillis();
 Object obj3 = new Object();
 for(int i=0;i<1000;i++){
 list1.add(obj1);
 }
 end = System.currentTimeMillis();
 System.out.println(end-start);
 
 start = System.currentTimeMillis();
 list.remove(0);
 end = System.currentTimeMillis();
 System.out.println(end-start);
 
 start = System.currentTimeMillis();
 list1.remove(250000);
 end = System.currentTimeMillis();
 System.out.println(end-start);
 
 
 }
}

清单 5. 运行输出
639
1296
6969
0
0
15

HashMap 是将 Key 做 Hash 算法,然后将 Hash 值映射到内存地址,直接取得 Key 所对应的数据。在 HashMap 中,底层数据结构使用的是数组,所谓的内存地址即数组的下标索引。HashMap 的高性能需要保证以下几点:

  1. Hash 算法必须是高效的;

  2. Hash 值到内存地址 (数组索引) 的算法是快速的;

  3. 根据内存地址 (数组索引) 可以直接取得对应的值。

HashMap 实际上是一个链表的数组。前面已经介绍过,基于 HashMap 的链表方式实现机制,只要 HashCode() 和 Hash() 方法实现得足够好,能够尽可能地减少冲突的产生,那么对 HashMap 的操作几乎等价于对数组的随机访问操作,具有很好的性能。但是,如果 HashCode() 或者 Hash() 方法实现较差,在大量冲突产生的情况下,HashMap 事实上就退化为几个链表,对 HashMap 的操作等价于遍历链表,此时性能很差。

HashMap 的一个功能缺点是它的无序性,被存入到 HashMap 中的元素,在遍历 HashMap 时,其输出是无序的。如果希望元素保持输入的顺序,可以使用 LinkedHashMap 替代。

LinkedHashMap 继承自 HashMap,具有高效性,同时在 HashMap 的基础上,又在内部增加了一个链表,用以存放元素的顺序。

HashMap 通过 hash 算法可以最快速地进行 Put() 和 Get() 操作。TreeMap 则提供了一种完全不同的 Map 实现。从功能上讲,TreeMap 有着比 HashMap 更为强大的功能,它实现了 SortedMap 接口,这意味着它可以对元素进行排序。TreeMap 的性能略微低于 HashMap。如果在开发中需要对元素进行排序,那么使用 HashMap 便无法实现这种功能,使用 TreeMap 的迭代输出将会以元素顺序进行。LinkedHashMap 是基于元素进入集合的顺序或者被访问的先后顺序排序,TreeMap 则是基于元素的固有顺序 (由 Comparator 或者 Comparable 确定)。

LinkedHashMap 是根据元素增加或者访问的先后顺序进行排序,而 TreeMap 则根据元素的 Key 进行排序。

清单 6 所示代码演示了使用 TreeMap 实现业务逻辑的排序。

清单 6. TreeMap 实现排序
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;


public class Student implements Comparable<Student>{

public String name;
public int score;
public Student(String name,int score){
this.name = name;
this.score = score;
}

@Override
//告诉 TreeMap 如何排序
public int compareTo(Student o) {
// TODO Auto-generated method stub
if(o.score<this.score){
return 1;
}else if(o.score>this.score){
return -1;
}
return 0;
}

@Override
public String toString(){
StringBuffer sb = new StringBuffer();
sb.append("name:");
sb.append(name);
sb.append(" ");
sb.append("score:");
sb.append(score);
return sb.toString();
}

public static void main(String[] args){
TreeMap map = new TreeMap();
Student s1 = new Student("1",100);
Student s2 = new Student("2",99);
Student s3 = new Student("3",97);
Student s4 = new Student("4",91);
map.put(s1, new StudentDetailInfo(s1));
map.put(s2, new StudentDetailInfo(s2));
map.put(s3, new StudentDetailInfo(s3));
map.put(s4, new StudentDetailInfo(s4));

//打印分数位于 S4 和 S2 之间的人
Map map1=((TreeMap)map).subMap(s4, s2);
for(Iterator iterator=map1.keySet().iterator();iterator.hasNext();){
Student key = (Student)iterator.next();
System.out.println(key+"->"+map.get(key));
}
System.out.println("subMap end");

//打印分数比 s1 低的人
map1=((TreeMap)map).headMap(s1);
for(Iterator iterator=map1.keySet().iterator();iterator.hasNext();){
Student key = (Student)iterator.next();
System.out.println(key+"->"+map.get(key));
}
System.out.println("subMap end");

//打印分数比 s1 高的人
map1=((TreeMap)map).tailMap(s1);
for(Iterator iterator=map1.keySet().iterator();iterator.hasNext();){
Student key = (Student)iterator.next();
System.out.println(key+"->"+map.get(key));
}
System.out.println("subMap end");
}

}

class StudentDetailInfo{
Student s;
public StudentDetailInfo(Student s){
this.s = s;
}
@Override
public String toString(){
return s.name + "'s detail information";
}
}

清单 7 .运行输出
name:4 score:91->4's detail information
name:3 score:97->3's detail information
subMap end
name:4 score:91->4's detail information
name:3 score:97->3's detail information
name:2 score:99->2's detail information
subMap end
name:1 score:100->1's detail information
subMap end

WeakHashMap 特点是当除了自身有对 Key 的引用外,如果此 Key 没有其他引用,那么此 Map 会自动丢弃该值。如清单 8 所示代码声明了两个 Map 对象,一个是 HashMap,一个是 WeakHashMap,同时向两个 map 中放入 A、B 两个对象,当 HashMap 删除 A,并且 A、B 都指向 Null 时,WeakHashMap 中的 A 将自动被回收掉。出现这个状况的原因是,对于 A 对象而言,当 HashMap 删除并且将 A 指向 Null 后,除了 WeakHashMap 中还保存 A 外已经没有指向 A 的指针了,所以 WeakHashMap 会自动舍弃掉 a,而对于 B 对象虽然指向了 null,但 HashMap 中还有指向 B 的指针,所以 WeakHashMap 将会保留 B 对象。

清单 8.WeakHashMap 示例代码
import java.util.HashMap; 
import java.util.Iterator; 
import java.util.Map; 
import java.util.WeakHashMap; 

public class WeakHashMapTest { 
 public static void main(String[] args) throws Exception { 
 String a = new String("a"); 
 String b = new String("b"); 
 Map weakmap = new WeakHashMap(); 
 Map map = new HashMap(); 
 map.put(a, "aaa"); 
 map.put(b, "bbb");
 weakmap.put(a, "aaa"); 
 weakmap.put(b, "bbb");
 map.remove(a);
 a=null; 
 b=null;
 System.gc(); 
 Iterator i = map.entrySet().iterator(); 
 while (i.hasNext()) { 
 Map.Entry en = (Map.Entry)i.next(); 
 System.out.println("map:"+en.getKey()+":"+en.getValue()); 
 } 
 Iterator j = weakmap.entrySet().iterator(); 
 while (j.hasNext()) { 
 Map.Entry en = (Map.Entry)j.next(); 
 System.out.println("weakmap:"+en.getKey()+":"+en.getValue()); 
 } 
 } 
}

清单 9 .运行输出
map:b:bbb
weakmap:b:bbb

WeakHashMap 主要通过 expungeStaleEntries 这个函数来实现移除其内部不用的条目,从而达到自动释放内存的目的。基本上只要对 WeakHashMap 的内容进行访问就会调用这个函数,从而达到清除其内部不再为外部引用的条目。但是如果预先生成了 WeakHashMap,而在 GC 以前又不曾访问该 WeakHashMap, 那不是就不能释放内存了吗?

清单 10. WeakHashMapTest1
import java.util.ArrayList;
import java.util.List;
import java.util.WeakHashMap;

public class WeakHashMapTest1 {
 public static void main(String[] args) throws Exception {
 List<WeakHashMap<byte[][], byte[][]>> maps = new ArrayList<WeakHashMap<byte[][], byte[][]>>();
 for (int i = 0; i < 1000; i++) {
 WeakHashMap<byte[][], byte[][]> d = new WeakHashMap<byte[][], byte[][]>();
 d.put(new byte[1000][1000], new byte[1000][1000]);
 maps.add(d);
 System.gc();
 System.err.println(i);
 }
 }
}

不改变任何 JVM 参数的情况运行清单 10 所示代码,由于 Java 默认内存是 64M,抛出内存溢出了错误。

清单 11. 运行输出
241
242
243
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at WeakHashMapTest1.main(WeakHashMapTest1.java:10)

果不其然,WeakHashMap 这个时候并没有自动帮我们释放不用的内存。清单 12 所示代码不会出现内存溢出问题。

清单 12. WeakHashMapTest2
import java.util.ArrayList;
import java.util.List;
import java.util.WeakHashMap;

public class WeakHashMapTest2 {
 public static void main(String[] args) throws Exception {
 List<WeakHashMap<byte[][], byte[][]>> maps = new ArrayList<WeakHashMap<byte[][], byte[][]>>();
 for (int i = 0; i < 1000; i++) {
 WeakHashMap<byte[][], byte[][]> d = new WeakHashMap<byte[][], byte[][]>();
 d.put(new byte[1000][1000], new byte[1000][1000]);
 maps.add(d);
 System.gc();
 System.err.println(i);
 for (int j = 0; j < i; j++) {
 System.err.println(j + " size" + maps.get(j).size());
 }
 }
 }
}

运行结果发现这次测试输出正常, 不再出现内存溢出问题。

总的来说,WeakHashMap 并不是你什么也干它就能自动释放内部不用的对象的,而是在你访问它的内容的时候释放内部不用的对象。

WeakHashMap 实现弱引用,是因为它的 Entry<K,V>是继承自 WeakReference<K>的,

在 WeakHashMap$Entry<K,V>的类定义及构造函数里面如清单 13 所示。

清单 13. WeakHashMap 类定义
private static class Entry<K,V> extends WeakReference<K> 
implements Map.Entry<K,V> Entry(K key, V value, ReferenceQueue<K> queue,int hash, Entry<K,V> next) { 
super(key, queue); 
this.value = value; 
this.hash = hash; 
this.next = next; 
}

请注意它构造父类的语句:“super(key, queue);”,传入的是 Key,因此 Key 才是进行弱引用的,Value 是直接强引用关联在 this.value 之中。在 System.gc() 时,Key 中的 Byte 数组进行了回收,而 Value 依然保持 (Value 被强关联到 Entry 上,Entry 又关联在 Map 中,Map 关联在 ArrayList 中)。

For 循环中每次都 New 一个新的 WeakHashMap,在 Put 操作后,虽然 GC 将 WeakReference 的 Key 中的 Byte 数组回收了,并将事件通知到了 ReferenceQueue,但后续却没有相应的动作去触发 WeakHashMap 去处理 ReferenceQueue,所以 WeakReference 包装 Key 依然存在于 WeakHashMap 中,其对应的 value 也当然存在。

那 value 是何时被清除的呢? 对清单 10 和清单 11 两个示例程序进行分析可知,清单 11 的 maps.get(j).size() 触发了 Value 的回收,那又如何触发的呢?查看 WeakHashMap 源码可知,Size 方法调用了 expungeStaleEntries 方法,该方法对 JVM 要回收的的 Entry(Quene 中) 进行遍历,并将 Entry 的 Value 置空,回收了内存。所以效果是 Key 在 GC 的时候被清除,Value 在 Key 清除后访问 WeakHashMap 被清除。

WeakHashMap 类是线程不同步的,可以使用 Collections.synchronizedMap 方法来构造同步的 WeakHashMap, 每个键对象间接地存储为一个弱引用的指示对象。因此,不管是在映射内还是在映射之外,只有在垃圾回收器清除某个键的弱引用之后,该键才会自动移除。需要注 意的是,WeakHashMap 中的值对象由普通的强引用保持。因此应该小心谨慎,确保值对象不会直接或间接地强引用其自身的键,因为这会阻止键的丢弃。注意,值对象可以通过 WeakHashMap 本身间接引用其对应的键,这就是说,某个值对象可能强引用某个其他的键对象,而与该键对象相关联的值对象转而强引用第一个值对象的键。

处理此问题的一种方法是,在插入前将值自身包装在 WeakReferences 中,如:m.put(key, new WeakReference(value)),然后,分别用 get 进行解包,该类所有“collection 视图方法”返回的迭代器均是快速失败的,在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器自身的 Remove 或 Add 方法,其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器很快就完全失败,而不是冒着在将来不确定的时间任意发生不确定行为的风险。

注意,我们不能确保迭代器不失败,一般来说,存在不同步的并发修改时,不可能做出任何完全确定的保证。

总结

综 合前面的介绍和实例代码,我们可以知道,如果涉及到堆栈、队列等操作,应该考虑用 List。对于需要快速插入、删除元素等操作,应该使用 LinkedList。如果需要快速随机访问元素,应该使用 ArrayList。如果程序在单线程环境中,或者访问仅仅在一个线程中进行,考虑非同步的类,其效率较高。如果多个线程可能同时操作一个类,应该使用同 步的类。要特别注意对哈希表的操作,作为 Key 的对象要正确复写 Equals 和 HashCode 方法。尽量返回接口而非实际的类型,如返回 List 而非 ArrayList,这样如果以后需要将 ArrayList 换成 LinkedList 时,客户端代码不用改变,这就是针对抽象进行编程思想。

本文只是针对应用层面的分享,后续文章会针对具体源代码级别的实现进行深入介绍,也会对具体实现所基于的算法进行深入介绍,请有需要的读者关注后续文章。


© 著作权归作者所有

M
粉丝 4
博文 58
码字总数 24535
作品 0
广州
高级程序员
私信 提问
基于MVC4+EasyUI的Web开发框架经验总结(11)--使用Bundles处理简化页面代码

在Web开发的时候,我们很多时候,需要引用很多CSS文件、JS文件,随着使用更多的插件或者独立样式文件,可能我们的Web界面代码会越来越臃肿,看起来也很累赘,在MVC里面提供了一个Bundle的对象...

walb呀
2017/12/04
0
0
基于MVC4+EasyUI的Web开发框架形成之旅--框架总体界面介绍

在前面介绍了一些关于最新基于MVC4+EasyUI的Web开发框架文章,虽然Web开发框架的相关技术文章会随着技术的探讨一直写下去,不过这个系列的文章,到这里做一个总结,展示一下整体基于MVC4+Ea...

walb呀
2017/12/04
0
0
集合类操作优化经验总结(一)

本文首先针对 Java 集合接口进行了一些介绍,并对这些接口的实现类进行详细描述,包括 LinkedList、ArrayList、Vector、Stack、Hashtable、HashMap、WeakHashMap 等,然后对一些实现类的实现...

Mysoft
2015/09/24
20
0
基于MVC4+EasyUI的Web开发框架经验总结(9)--在Datagrid里面实现外键字段的转义操作

我们在使用EasyUI的时候,很多情况下需要使用到表格控件datagrid,这个控件控件非常强大,使用起来很简洁,但是我在使用中,发现对于一个表里面的外键字段进行转义,并显示引用表的一些名称的...

walb呀
2017/12/04
0
0
基于MVC4+EasyUI的Web开发框架经验总结(13)--DataGrid控件实现自动适应宽带高度

在默认情况下,EasyUI的DataGrid好像都没有具备自动宽度的适应功能,一般是指定像素宽度的,但是使用的人员计算机的屏幕分辨率可能不一样,因此导致有些地方显示太大或者太小,总是不能达到好...

walb呀
2017/12/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

mysql-connector-java升级到8.0后保存时间到数据库出现了时差

在一个新项目中用到了新版的mysql jdbc 驱动 <dependency>     <groupId>mysql</groupId>     <artifactId>mysql-connector-java</artifactId>     <version>8.0.18</version> ......

ValSong
今天
5
0
Spring Boot 如何部署到 Linux 中的服务

打包完成后的 Spring Boot 程序如何部署到 Linux 上的服务? 你可以参考官方的有关部署 Spring Boot 为 Linux 服务的文档。 文档链接如下: https://docs.ossez.com/spring-boot-docs/docs/r...

honeymoose
今天
6
0
Spring Boot 2 实战:使用 Spring Boot Admin 监控你的应用

1. 前言 生产上对 Web 应用 的监控是十分必要的。我们可以近乎实时来对应用的健康、性能等其他指标进行监控来及时应对一些突发情况。避免一些故障的发生。对于 Spring Boot 应用来说我们可以...

码农小胖哥
今天
9
0
ZetCode 教程翻译计划正式启动 | ApacheCN

原文:ZetCode 协议:CC BY-NC-SA 4.0 欢迎任何人参与和完善:一个人可以走的很快,但是一群人却可以走的更远。 ApacheCN 学习资源 贡献指南 本项目需要校对,欢迎大家提交 Pull Request。 ...

ApacheCN_飞龙
今天
5
0
CSS定位

CSS定位 relative相对定位 absolute绝对定位 fixed和sticky及zIndex relative相对定位 position特性:css position属性用于指定一个元素在文档中的定位方式。top、right、bottom、left属性则...

studywin
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部