集合类框架

 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。

HashIterator() {
    expectedModCount = modCount;
    if (size > 0) { // advance to first entry
    Entry[] t = table;
    while (index < t.length && (next = t[index++]) == null)
        ;
    }
}

 

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

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

final Entry nextEntry() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();

 

   在HashMap的API中指出：

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

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