Java集合框架（Java Collections Framework）是存放大量对象的容器，被广泛使用。Java里包含这四种集合类：Vector, Stack, Hashtable, Array。
集合中存放的是对象的引用。
Java1.2开始提供集合框架，这包括：
-
接口
所有集合类都得实现java.util.Collection。这个接口的方法（文档）包括：- 基本操作：
int size(), boolean isEmpty(), boolean contains(Object element), boolean add(E element), boolean remove(Object element), and Iterator<E> iterator() - 对整个集合类的操作：
boolean containsAll(Collection<?> c), boolean addAll(Collection<? extends E> c), boolean removeAll(Collection<?> c), boolean retainAll(Collection<?> c), and void clear() - Array操作：
Object[] toArray() and <T> T[] toArray(T[] a)
java.util.List,java.util.Set,java.util.Queue和java.util.Map接口也是集合框架的一部分。（Map没用继承自Collection接口） - 基本操作：
实现类
重要的集合类有ArrayList,LinkedList,HashMap,TreeMap,HashSet,TreeSet。（java.util包）
线程安全的类有CopyOnWriteArrayList,ConcurrentHashMap,CopyOnWriteArraySet。（java.util.concurrent包）算法
如查询、排序、打乱
Iterator接口
取代了Enumeration，可以简单地理解为遍历，提供了一个标准化遍历各类容器里面的所有对象的设计模式。方法：
- Object next()：返回迭代器刚越过的元素的引用，返回值是 Object
- boolean hasNext()：判断容器内是否还有可供访问的元素
- void remove()：删除迭代器刚越过的元素
Iterator it = collection.iterator(); // 获得一个迭代起点
while(it.hasNext()) {
Object obj = it.next(); // 得到下一个元素
}
ListIterator是Iterator的子接口，区别在于，只能用于List及其子类型；有add方法；可以实现逆向（顺序向前）遍历；可以定位当前索引的位置；可以实现对象的修改。（参考：JAVA中ListIterator和Iterator详解与辨析）
List接口
有序，允许相同元素，有索引
除了具有Collection接口必备的iterator()方法外，List还有一个listIterator()方法，返回一个 ListIterator接口。
实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。
ArrayList类
类似数组的形式进行存储，随机访问速度快。
线程不同步。
内部的元素直接通过get与set方法进行访问。
当ArrayList中的元素超过它的初始大小时，ArrayList只增加50%的大小。LinkedList类
双链表，在添加和删除元素时具有比ArrayList更好的性能，但在get与set方面弱于ArrayList。
线程不同步。Vector类
和ArrayList类似，但线程同步
当Vector中的元素超过它的初始大小时，Vector会将它的容量翻倍Stack 类
Stack继承自Vector，实现一个后进先出的堆栈。
基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。
Set接口
无序
不包含重复元素
取出只能是Iterator
HashSet
一个按着Hash算法来存储集合中的元素，其元素值可以是NULL。它不能保证元素的排列顺序。LinkedHashList
HashSet的子类TreeSet
红黑树，线程不安全
提供有序的 Set 集合（ 实现SortedSet接口)，储存的类需要实现需要实现Comparable接口
SortedSet<Item> sortByDescription = new TreeSet<Item>(new
Comparator<Item>()
{
public int compare(Item a, Item b)
{
String descrA = a.getDescription();
String descrB = b.getDescription();
return descrA.compareTo(descrB);
}
});
Queue接口
无null
方法：add,addall, remove, clear和element
- PriorityQueue优先队列
非线程安全
PriorityQueue是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator比较器在队列实例化的时排序。
Map接口
没有继承Collection接口
提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个 value。
put(Object key, Object value) 将指定值与指定键相关联
entrySet()返回 Map 中所包含映射的 Set 视图。Set 中的每个元素都是一个 Map.Entry 对象，可以使用 getKey() 和 getValue() 方法（还有一个 setValue() 方法）访问后者的键元素和值元素
keySet()返回 Map 中所包含键的 Set 视图。删除 Set 中的元素还将删除 Map 中相应的映射（键和值）
values()返回 map 中所包含值的 Collection 视图。删除 Collection 中的元素还将删除 Map 中相应的映射（键和值）
Hashtable类
Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空的对象都可作为key或者value。
添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。
Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大，这会影响像get和put这样的操作。
由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方法。
Hashtable是同步的。HashMap类
HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key。
但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap 的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。TreeMap类
通关红黑树实现， 继承 自AbstractMap（即一个key-value集合）。 非线程安全 。
实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。
实现了Cloneable接口，意味着它能被克隆。
实现了java.io.Serializable接口，意味着它支持序列化。
基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n)
按自然顺序或自定义顺序遍历键，TreeMap比HashMap要好；在Map 中插入、删除和定位元素，HashMap 是最好的选择。
- WeakHashMap类
WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。
集合对象排序接口Comparator
实现此接口的类可以进行排序，需要实现compare方法。
基本数据类型实现了这个接口，调用Collections.sort(list)进行排序;
如果Comparator只用一次，可使用匿名类。
