集合框架体系组成

在集合框架的类继承体系中，最顶层有两个接口：

• Collection表示一组纯数据
• Map表示一组key-value对

一般继承自Collection或Map的集合类，会提供两个“标准”的构造函数：

• 没有参数的构造函数，创建一个空的集合类
• 有一个类型与基类（Collection或Map）相同的构造函数，创建一个与给定参数具有相同元素的新集合类

因为接口中不能包含构造函数，所以上面这两个构造函数的约定并不是强制性的，但是在目前的集合框架中，所有继承自Collection或Map的子类都遵循这一约定。

 

集合框架主要实现类

 

Collection

Collection体系中有三种集合：Set、List、Queue

• Set(集)： 元素是无序的且不可重复。
• List(列表)：元素是有序的且可重复。
• Queue(队列)：封装了数据结构中的队列。

1、List：元素是有序的，而且可以重复。通过索引可以访问每个元素。

     实现类组成：

• ArrayList： 数组结构，实现了可变大小的数组，就像传统的数组一样。

       1：ArrayList允许存放所有的元素，允许为null

       2：size，isEmpty，get，set方法运行时间为常数，但add方法运行时间为分摊的常数，添加n个元素需要O(n)的时间

       3：ArrayList也是非同步的（unsynchronized）

       4：ArrayList适合随机访问，使用索引可以很快的找到元素位置

• LinkedList：LinjkedList 实现了List接口，双向链表存储数据

       1：LinkedList也是非同步的（unsynchronized）

       2：ArrayList适合随机访问LinkedList更适合插入和删除，在对性能没有很大要求是是可以忽略这个差别的。

       3：LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快

• Vector: Vector与ArrayList其实是差不多的，只不过Vector是同步的。

       1：Vector是同步的

       2：采用数组方式存储数据

       3：Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差

 

2、Set：不包括重复元素的Collection，允许null值但是只有一个

• HashSet：内部由哈希code来实现，堪称查询最快的集合，内部顺序由哈希码来实现的。
• TreeSet：基于TreeMap，生成一个总是处于排序状态的set，内部以TreeMap来实现。它是使用元素的自然顺序对元素进行排序，或者根据创建Set 时提供的Comparator进行排序，具体取决于使用的构造方法。
• LinkedHashSet：底层是链表实现的,是set集合中唯一一个能保证怎么存就怎么取的集合对象，因为是HashSet的子类,所以也是保证元素唯一的,与HashSet的原理一样。

 

3、Queue接口

• 阻塞式队列（BlockingQueue）：队列满了以后再插入元素则会抛出异常，主要包括ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。

       * ArrayBlockingQueue ：一个由数组支持的有界队列。
　　* LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。
　　* PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。
　　* DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。
　　* SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。

阻塞队列的操作可以根据它们的响应方式分为以下三类：aad、removee和element操作在你试图为一个已满的队列增加元素或从空队列取得元素时 抛出异常。当然，在多线程程序中，队列在任何时间都可能变成满的或空的，所以你可能想使用offer、poll、peek方法。这些方法在无法完成任务时 只是给出一个出错示而不会抛出异常。

注意：poll和peek方法出错进返回null。因此，向队列中插入null值是不合法的

最后，我们有阻塞操作put和take。put方法在队列满时阻塞，take方法在队列空时阻塞。直到队列能够操作。

• 双端队列（Deque）:支持在头、尾两端插入和移除元素，主要包括：ArrayDeque、LinkedBlockingDeque、LinkedList。

 

Map

由一系列键值对组成的集合，提供了key到Value的映射。

不能存在相同的key值，当然value值可以相同

• HashMap：HashMap使用hash映射来存取数据，这个速度是相当快。HashMap是非同步的，并且允许null，即null value和null key。是线程不同步的
• TreeMap：键以某种排序规则排序（自然顺序），内部以red-black（红-黑）树数据结构实现。
• Hashtable：实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。线程同步的

 

三、总结

    1．Vector和ArrayList

      1）vector是线程同步的，所以它也是线程安全的，而arraylist是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用arraylist效率比较高。

       2）如果集合中的元素的数目大于目前集合数组的长度时，vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度的50%.如过在集合中使用数据量比较大的数据，用vector有一定的优势。

       3）如果查找一个指定位置的数据，vector和arraylist使用的时间是相同的，都是0(1),这个时候使用vector和arraylist都可以。而如果移动一个指定位置的数据花费的时间为0(n-i)n为总长度，这个时候就应该考虑到使用linklist,因为它移动一个指定位置的数据所花费的时间为0(1),而查询一个指定位置的数据时花费的时间为0(i)。

      4）ArrayList 和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要设计到数组元素移动等内存操作，所以索引数据快插入数据慢，Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差，LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快！

     2．Aarraylist和Linkedlist

       1）ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

         2）对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。

         3）对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

         4）这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

    3．HashMap与TreeMap

      1）HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。HashMap中元素的排列顺序是不固定的）。

       2）在Map 中插入、删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。 这个TreeMap没有调优选项，因为该树总处于平衡状态。

    4．Hashtable与HashMap

      1）历史原因:Hashtable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现 。

       2）同步性:Hashtable是线程安全的，也就是说是同步的，而HashMap是线程序不安全的，不是同步的 。

       3）值：只有HashMap可以让你将空值作为一个表的条目的key或value 。