容器的使用

线性表，链表，集合，哈希表是常用的数据结构，在进行Java 开发时，JDK 已经为我们提供了一系列相应的类来实现基本的数据结构。这些类均在java.util 包中。

Collection

├List

│-├LinkedList

│-├ArrayList

│-└Vector

│ └Stack

└Set

Map

├Hashtable

├HashMap

└WeakHashMap

主要分为两个分支：Collection 和Map ,其中Map 中存储的对象是以名值对的方式储存的，如：

是字典的实现。

由Collection 接口派生的两个接口是List 和Set 。

其中，List 的特点是：有顺序而可以重复 。Set 的特点是：无顺序而不可重复 。

什么是重复？

不是说容器中有两个格子装了同一个对象，重复是指：a.equals(b) == true; 所以，当我们自定义对象作为容器的储存元素时，我们必须重写 java.lang.Object 的equals 方法，Object 的默认equals 只有当比较的参数是本身时才返回true ，明显不是我们想要的，所以必须重写，而且，如果重写equals 就必须重写hashCode()方法，因为，当我们的对象作为字典Map 的键key 时，我们的定位是同过 hashCode 方法，这样来提高效率。注：两个对象equals 若为TRUE ，hashCode 一定返回同样的int; 但是，如果Equals 返回 FALSE ，hashCode 不一定不同。

List 接口

List 是有序的Collection ，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List 中的位置，类似于数组下标）来访问List 中的元素，这类似于Java 的数组。

和下面要提到的Set 不同，List 允许有相同的元素。

除了具有Collection 接口必备的iterator()方法外，List 还提供一个listIterator()方法，返回一个 ListIterator 接口，和标准的Iterator 接口相比，ListIterator 多了一些add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。

实现List 接口的常用类有LinkedList ，ArrayList ，Vector 和Stack 。

LinkedList 类

LinkedList 实现了List 接口，允许null 元素。此外LinkedList 提供额外的get ，remove ，insert 方法在 LinkedList 的首部或尾部。这些操作使LinkedList 可被用作堆栈（stack ），队列（queue ）或双向队列（deque ）。

注意LinkedList 没有同步方法。如果多个线程同时访问一个List ，则必须自己实现访问同步。一种解决方法是在创建List 时构造一个同步的List ：

List list = Collections.synchronizedList(new LinkedList(...));

ArrayList 类

ArrayList 实现了可变大小的数组。它允许所有元素，包括null 。ArrayList 没有同步。

size ，isEmpty ，get ，set 方法运行时间为常数。但是add 方法开销为分摊的常数，添加n 个元素需要O(n)的时间。其他的方法运行时间为线性。

每个ArrayList 实例都有一个容量（Capacity ），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity 方法来增加ArrayList 的容量以提高插入效率。

和LinkedList 一样，ArrayList 也是非同步的（unsynchronized ）。

一般情况下使用这两个就可以了，因为非同步，所以效率比较高。

Vector 类

Vector 非常类似ArrayList ，但是Vector 是同步的。由Vector 创建的Iterator ，虽然和ArrayList 创建的 Iterator 是同一接口，但是，因为Vector 是同步的，当一个 Iterator 被创建而且正在被使用，另一个线程改变了Vector 的状态（例如，添加或删除了一些元素），这时调用Iterator 的方法时将抛出 ConcurrentModificationException ，因此必须捕获该异常。

Stack 类

Stack 继承自Vector ，实现一个后进先出的堆栈。Stack 提供5个额外的方法使得Vector 得以被当作堆栈使用。基本的push 和pop 方法，还有 peek 方法得到栈顶的元素，empty 方法测试堆栈是否为空，search 方法检测一个元素在堆栈中的位置。Stack 刚创建后是空栈。

Set 接口

Set 的构造函数有一个约束条件，传入的Collection 参数不能包含重复的元素。

Map 接口

请注意，Map 没有继承Collection 接口，Map 提供key 到value 的映射。一个Map 中不能包含相同的key ，每个key 只能映射一个 value 。Map 接口提供3种集合的视图，Map 的内容可以被当作一组key 集合，一组value 集合，或者一组key-value 映射。

Hashtable 类

Hashtable 继承Map 接口，实现一个key-value 映射的哈希表。任何非空（non-null ）的对象都可作为key 或者value 。

添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。 Hashtable 通过initial capacity 和load factor 两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor 可以节省空间但相应的查找时间将增大，这会影响像get 和put 这样的操作。

Hashtable 是同步的。

HashMap 类

HashMap 和Hashtable 类似，不同之处在于HashMap 是非同步的，并且允许null ，即null value 和null key。，但是将HashMap 视为Collection 时（values()方法可返回 Collection ），其迭代子操作时间开销和HashMap 的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap 的初始化容量设得过高，或者load factor过低。

WeakHashMap 类

WeakHashMap 是一种改进的HashMap ，它对key 实行“弱引用”，如果一个key 不再被外部所引用，那么该key 可以被GC 回收。

一般情况下数据结构的选择：

多查少改选ArrayList

多改少查选LinkedList

如果大量数据进行检索选Map,

详细：

如果涉及到堆栈，队列等操作，应该考虑用List ，对于需要快速插入，删除元素，应该使用LinkedList ，如果需要快速随机访问元素，应该使用ArrayList 。

如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较高，如果多个线程可能同时操作一个类，应该使用同步的类。

要特别注意对哈希表的操作，作为key 的对象要正确复写equals 和hashCode 方法。 尽量返回接口而非实际的类型，如返回List 而非ArrayList ，这样如果以后需要将ArrayList 换成LinkedList 时，客户端代码不用改变。这就是针对抽象编程。

同步性

Vector 是同步的。这个类中的一些方法保证了Vector 中的对象是线程安全的。而ArrayList 则是异步的，因此ArrayList 中的对象并不是线程安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用ArrayList 是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销。

数据增长

从内部实现机制来讲ArrayList 和Vector 都是使用数组(Array)来控制集合中的对象。当你向这两种类型中增加元素的时候，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector 缺省情况下自动增长原来一倍的数组长度，ArrayList 是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector 有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。

辅助类java.lang.Collections

这个类封装了一些List 的算法，包括排序，逆向，随机排序等等。

重要需要实现的接口：

Comparable 接口，当两个对象涉及比较操作时，使用这个接口的compareT o 方法。

Iterator 接口，涉及遍历时使用。