引言
数据结构（data structure） 是以某种形式将数据组织在一起的集合。
Java框架主要支持一下两种类型的容器
- 一种是为了存储一个元素的 集合（Collection）
- 一种是为了存储键/值对，称为 图（Map）
ArrayList
下面介绍会涉及到，先做简单介绍。
简单说，ArrayList就是动态数组，可以动态的增加和减少元素
构造方法(3个)
// 默认构造方法，大小 16
public ArrayList() { }
// 包含ICollection 对象的ArrayList
public ArrayList(ICollection) {}
(LinkedHashSet<String>)input.readObject();
// 指定初始化大小
public ArrayList(Int) {}
细节可以参考 官方文档
集合概述
Java集合框架支持三种主要类型的集合,规则集（Set），线性表（List）和队列（Queue）。
- Set 存储一组不重复的元素
- List 存储一个由元素构成的有序集合
- Queue用于存储先进先出方式处理的对象
集合都被定义在通用的接口中，如图
Collection接口和AbstractCollection
Collection接口是处理对象集合的根接口。AbstractCollection类提供Collection接口部分实现的便利类。除了size()和iterator()方法外，他实现了Collection接口中所有方法。size和iterator 方法在合适的类中实现。
规则集
Set接口扩展了Collection接口，它没有引入新的方法和常量只是规定set的实例不包含重复元素。
AbstractSet类是一个便利类，他扩展AbstractCollection类并实现Set接口。AbstractSet类提供equals和hashCode方法的具体实现。没有实现size和iterator
Set类的三个接口是：hashSet LinkedSet TreeSet
散列集HashSet
HsahSet类是一个用于实现Set接口的具体类。（初始容量16， 客座率，0.75）。
LinkedHashSet
LinkedHashSet用一个链表实现扩展HashSet类，他支持对规则集内元素排序，HashSet中的元素是没有被排序的，而LInkedHashSet中的元素可以按照他们插入的规则集顺序提取。
树形集TreeSet
SortSet是Set的字接口，他可以确保规则集中的元素是有序的。
NavigableSet扩展了SortSet，并扩展了一些导航方法。
TreeSet实现了SortSet接口的一个具体类。只要对象是可以互相比较的，就可以将他们添加到一个树形集中。（在添加元素或初始化时会进行一次排序）
比较器接口Comparator
有时希望将元素插入到树集合中，这些元素可能不是java.lang.Comparable的实例。这是可以定义一个比较器来比较这些元素。要做到这一点，需要实现java.util.Comparator接口的类。Comparator接口有两个方法：compare和equals。
线性表
规则集只能存储不重复的元素，若要在一个集合中存储重复的元素，需要使用线性表。线性表可以存储重复的元素，允许用户指定他们存储的位置。并且用户可以用下标访问。List接口扩展了了Collectoin接口，以定义一个允许重复的有序集合。List接口增加了面向位置的操作，并增加了一个能够双向遍历线性表的新列表迭代器。
线性表类ArrayList和链表类LinkedList
ArrayList用数组存储元素，且数组是动态创建的，即如果元素超出容量就创建一个更大的数组，并将当前数组元素复制到新数组。LinkedList则是在一个链表中存储元素。
从可变长参数创建线性表，Java提供了静态的asList方法。
List<String> list = Arrays.asList("a", "b", "c");
线性表和集合的静态方法
可以使用TreeSet在规则集中存储有序元素。但是线性表不支持有序存储。但是，Java集合框架在Collections类中提供了用于对线性表进行排序的静态方法。。Collections类还包含用于线性表的binarySearch、 reverse、shuffle、copy和fill方法。以及用于集合的max、min、disjiont和frequency方法。
规则集合线性表的性能
规则集比线性表更高效，如果用规则集就足够就是用规则集，如果不需要特别的顺序就使用散列集。
向量类Vector和栈类Stack
Java集合框架是在Java2中引入的，Java2之前版本也支持一些数据结构，其中就有向量类Vector和栈类Stack，但是为了向后兼容，在引入集合框架时保留了它们所有旧形式的方法。
除了用于访问和修改向量的同步方法之外，Vecator类与ArrayList是一样的。同步方法用于防止两个或多个线程同时访问某个向量时候引起的数据损坏。
在Java集合框架中，栈类Stack是作为Vecator类的扩展来实现的。
队列和优先队列
队列是一种先进先出的数据结构。元素被追加到队列末尾，然后从队列头删除。在优先队列（PriorityQueue）中，元素被赋予优先级。当访问元素时，拥有最高优先级的元素首先被删除。
双端队列Deque和链表LinkedList
LinkedList类实现了Deque接口，Deque又扩展了Queue接口。因此，可以使用LInkedList创建一个队列。
图（Map）
Map是一种依照键值对存储元素的容器。键很像下标。在List中，下标是整数，在Map中键可以是任意类型的对象。Map中不能有重复的键，每个键对应一个值，一个键值对对应构成一个条目，存储在map中的是这个条目。
图的类型有三种HahMap，LinkMap，TreeMap。
继承关系如图
具体方法参考Map具体方法
- AbstractMap，实现了除了entrySet()方法之外的所有方法。
- SortedMap，扩展了Map接口，并保持映射以键的值得升序排列。
- NavigableMap，扩展了SortMap，提供了导航方法。
在Java2以前，一般使用java.util.HashTable来映射键值对。 重新设计时为了向后兼容保留了所有方法，HashTable继承了Map接口，除了具有同步功能之外，他与HashMap的用法是一样的。
小结
纵观Java的两种集合框架，设计模式在很大程度上是相似的，即 Hash，Linked，Tree。而Set和Map框架继承关系基本相同。Hash即散列集，无序，方法也相对较少，但效率相对较高，如果没有顺序和特别的查找要求就用Hash。Linked是用链表存储顺序是加入顺序，而Tree则是自然顺序排好，同时又继承了Navigable接口，有了导航功能。而在加入TreeSet排序时，需要考虑是否实现了Comparable接口，若没有实现则可以使用Compartor接口实现后再加入。
线性表，ArrayList和LinkedList，方法基本相同，使用时，如果查找操作较多就用ArrayList，在List内部删除添加（不是尾部）较多就用LinkedList。（还有Array.asList("a", "b", "c")静态方法）
Queue，队列。LinkedList继承了Deque接口，所以LinkList也支持队列的相关操作。而优先队列（PriorityQueue），默认使用Comparable接口以自然顺序进行排序，并且最小元素具有最高优先级，被优先删除。
Iterator，Collection中有iterator()方法，所以Collection容器类都支持iterator()遍历。而list接口中用定义了listIterator()方法，listIterator方法支持双向遍历，继承了list接口的方法，可以调用此方法。（即list接口下的方法（ArrayList，LinkedList以及Vector和stack））。
参考书：Java语言程序设计进阶篇（原书第八版）
