Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2793260
  • 博文数量: 471
  • 博客积分: 7081
  • 博客等级: 少将
  • 技术积分: 5369
  • 用 户 组: 普通用户
  • 注册时间: 2012-01-04 21:55
文章分类

全部博文(471)

文章存档

2014年(90)

2013年(69)

2012年(312)

分类: Java

2012-05-17 11:31:46



 HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,HashSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范不同,但 HashSet底层许多方法是基于HashMap来实现的,因此它们底层的 Hash 存储机制完全一样。

TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员,其中 TreeMap 是 Map 接口的常用实现类,而 TreeSet 是 Set 接口的常用实现类。虽然 TreeMap 和 TreeSet 实现的接口规范不同,但 TreeSet 底层是通过 TreeMap 来实现的,因此二者的实现方式完全一样。而 TreeMap 的实现就是红黑树算法。


对于 TreeMap 而言,由于它底层采用一棵“红黑树”来保存集合中的 Entry,这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低:当 TreeMap 添加元素时,需要通过循环找到新增 Entry 的插入位置,因此比较耗性能;当从 TreeMap 中取出元素时,需要通过循环才能找到合适的 Entry,也比较耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于:TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态,TreeSet 中所有元素总是根据指定排序规则保持有序状态。



LinkedHashMap/LinkedHashSet 顾名思义,就是在Hash的实现上添加了Linked的支持。对HashMap/HashSet的每个节点上通过一个链表串联起来,这样就可以保证确定的顺序。对于希望有常量复杂度的高效存取性能要求,同时有要求排序的情况下,现在可以直接使用LinkedHashMap/Set了。
对于LinkedHashMap还有一点特别注意,LinkedHashMap支持两种排序:插入顺序、访问顺序。前者是
指按照插入时的顺序排序,后者是指按照最旧使用到最近使用的顺序。即如果在一个LinkedHashMap中
有5个节点,现在的顺序是e1, e2, e3, e4, e5. 如果是使用顺序的话,现在访问了一次e2, 那么e2节
点将移至链表的尾部。现在顺序变为:e1, e3, e4, e5, e2.
这会造成严重的性能问题吗?答案当然是否定的。因为在这儿的链表操作是常量级的。这也是
LinkedHashMap/Set在这儿比TreeMap/Set性能更高的原因。

对于LinkedHashMap而言,它继承于HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操
作与父类HashMap相似,它通过重写父类相关的方法,来实现自己的链接列表特性。
   LinkedHashMap实现与HashMap的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。
此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。

LinkedHashSet继承于HashSet,同样是根据元素的hashCode值来决定元素的存储位置,但是它同时使用链表维护元素的次序。这样使得元素看起 来像是以插入顺序保存的,也就是说,当遍历该集合时候,LinkedHashSet将会以元素的添加顺序访问集合的元素。 
LinkedHashSet在迭代访问Set中的全部元素时,性能比HashSet好,但是插入时性能稍微逊色于HashSet。

1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 
2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。 
3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。 



同步问题:

C ollections类中提供了多个synchronizedXxx,该方法返回指定集合对象对应的同步对象,从而可以解决多线程并发访问集合时的线程安全问题.

   正如Java中常用的集合框架推荐使用的三个实现类:HashSet\ArrayList\HashMap都是线程不安全的.如果有多条线程访问它们,而且有超过一条的线程试图修改它们,则可能出现错务.Collections提供了多个静态方法用于创建同步集合
下面程序创建了四个同步的集合对象

import java.util.*;
public class  TestSynchronized
{
public static void main(String[] args)
{
 //下面程序创建了四个同步的集合对象
 Collection c=Collections.synchronizedCollection(new ArrayList());
 List list=Collections.synchronizedList(new ArrayList());
 Set s=Collections.synchronizedSet(new HashSet());
 Map m=Collections.synchronizedMap(new HashMap());
}
}

   在上面的程序中,直接将创建的集合对象传给了Collections的synchronizedXxx方法,这样就直接获取List,Set和Map的线程安全实现版本了

 补充一点说明

Vector,HashTable是线程安全的集合类,不过,这两种类是很早的用法,现在一般要尽量少采用

 
Fail-Fast机制:

   我们知道java.util.HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛出ConcurrentModificationException,这就是所谓fail-fast策略。

   这一策略在源码中的实现是通过modCount域,modCount顾名思义就是修改次数,对HashMap内容的修改都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

Java代码  收藏代码
  1. HashIterator() {  
  2.     expectedModCount = modCount;  
  3.     if (size > 0) { // advance to first entry  
  4.     Entry[] t = table;  
  5.     while (index < t.length && (next = t[index++]) == null)  
  6.         ;  
  7.     }  
  8. }  

 

   在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等就表示已经有其他线程修改了Map:

   注意到modCount声明为volatile,保证线程之间修改的可见性。

Java代码  收藏代码
  1. final Entry nextEntry() {     
  2.     if (modCount != expectedModCount)     
  3.         throw new ConcurrentModificationException();  

 

   在HashMap的API中指出:

   由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器本身的 remove 方法,其他任何时间任何方式的修改,迭代器都将抛出ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不冒在将来不确定的时间发生任意不确定行为的风险。

   注意,迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。

阅读(1977) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

nba76ers2012-07-11 15:16:54

在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针Entry<K,V>(引用),所有的数据结构都可以用这两个基本结构来构造的