Java集合框架

Java集合框架（Java Collections Framework）是存放大量对象的容器，被广泛使用。Java里包含这四种集合类：Vector, Stack, Hashtable, Array。
集合中存放的是对象的引用。

Java1.2开始提供集合框架，这包括：

• 接口
  所有集合类都得实现java.util.Collection。这个接口的方法（文档）包括：

  1. 基本操作：
     int size(), boolean isEmpty(), boolean contains(Object element), boolean add(E element), boolean remove(Object element), and Iterator<E> iterator()
  2. 对整个集合类的操作：
     boolean containsAll(Collection<?> c), boolean addAll(Collection<? extends E> c), boolean removeAll(Collection<?> c), boolean retainAll(Collection<?> c), and void clear()
  3. 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只用一次，可使用匿名类。

参考：

• Collections in Java – Tutorial
• Java集合类详解
• java集合类框架