java 集合框架（2）

<span style="font-size: 18px;">package com.itm.connection;</span>

<span style="font-size: 18px;">
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class ArrayListDemo {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		/**********************************
		 * 
		 * 第一种 练习。
		 */
		ArrayList<String> list = new ArrayList<String>();
		list.add("x");
		list.add("y");
		for (Object o : list) {
			System.out.println("ArrayList " + ",遍历的值 : " + o);
		}

		/************************************************
		 * 
		 * 第二种 练习。
		 * 
		 */
		ArrayList<Map<String, Object>> listMap = new ArrayList<Map<String, Object>>();
		Map<String, Object> map = new HashMap<String, Object>();
		map.put("key1", "value1");
		map.put("key2", "value2");
		listMap.add(map);

		for (Object object : listMap) {
			// 解决思想：想要拿到哪个map的值，就要用 哪个map集合也即：map.entrySet();
			for (Entry<String, Object> entry : map.entrySet()) {
				// entry.getKey();
				// entry.getValue();
				System.out.println("遍历Map的值 ： " + entry);
			}
			System.out.println("object = " + object);
		}

		System.out.println("打印  : " + listMap.toString());

	}

}
</span>

结果如下：

ArrayList ,遍历的值 : x
ArrayList ,遍历的值 : y
遍历Map的值 ： key2=value2
遍历Map的值 ： key1=value1
object = {key2=value2, key1=value1}
打印 : [{key2=value2, key1=value1}]

转自：http://blog.csdn.net/linyt/article/details/1562197

Java集合框架是sun公司发布的Java应用程序接口(API)的重要组成部分，并放在java.util包里面。Java平台的集合框架提供了一个表示和操作对象集合的统一架构，允许用户独立地操作各种数据结构而不需要了解具体的实现。Java集合框架中包含了大量集合接口，以及这些接口的实现类和操作它们的算法。依此，可用如下公式表示Java集合框架。

Java集合框架=集合接口+实现+算法

Java是一个比较C++更纯的面向对象语言，因此Java的出现，伴随着很多良好的面向对象设计思想的出现。Java是一个提倡面向接口编程而非实现编程的语言，因此Java所提供的应用程序接口(API)中出现大量的接口，目的是使接口与实现分离，允许用户基于接口编程，同时也提供很好的互操作性。

Java集合框架中的数据结构

Java集合框架作为java应用程序中的工具类，是为了为开发人员提供一个良好的应用程序接口。Java集合框架为开始提供了大量的数据结构，包括列表(List)，队列(Queue)，栈(Stack)以及一个键值映射数据结构(Map)。同时这些数据结构的实现中还涉及到红黑树，哈希表等数据结构，并且为程序员提供使用的方便。

上图是Java1.6中API集合框架中所提供的主要数据结构接口，提供List、Set、Queue和Map等数据结构。从上面的类图结构可以看到，Collection类是所有除Map以外其它接口的基类，它提供访问一组对象的基本接口，以确保它们的实现具互操作性和实现独立性。下面详细说明各个接口的功能和主要方法。

Collection接口

Collection是整个集合框架的基础，它表示不同类型的Collections(Collections表示不同的数据结构，如List，Set和Queue等等)。

Collection从概念上来说，是一个抽象，它里面储存一组对象。该组对象是否有序，是否允许重复，具体依赖它的不同实现。它只是提供维护一组对象的基本接口。下面是主要方法的介绍。

方法概述
boolean	add(Ee) 把元素e加入Collection对象中，如果改变Collection对象则返回true，否则返回false。
boolean	addAll(Collection<? extendsE>c) 把c中所有元素加入当前Collection中。
void	clear() 清除Collection中的所有元素。
boolean	contains(Objecto) 当前Collection是否包含对象o，如是则返回true，否则为false。
boolean	containsAll(Collection<?>c) 当前Collection是否包含c中的所有元素，如是则返回true，否则为false。
boolean	equals(Objecto) 当前Collection与对象o是否相等，所谓相等应遵从Object类中equals方法的要求，详见Object.equals方法说明。
int	hashCode() 返回当前Collection的哈希码。
boolean	isEmpty() 返回当前Collection对象是否为空，如是空则为true,否则为false。
Iterator<E>	iterator() 返回当前Collection元素的迭代器。
boolean	remove(Objecto) 删除当前Collection中对象为o的元素，如果有多个只删除一个。如果删除成功则返回true，否则为false。
boolean	removeAll(Collection<?>c) 删除当前Collection中在c出现的所有元素。如果当前Collection改变就返回true，否则返回false。
boolean	retainAll(Collection<?>c) 只保留当前Collection中在c所出现的元素。如果Collection改变则返回true，否则false。
int	size() 返回Collection中元素的个数。
Object[]	toArray() 返回包含Collection所有元素的数组。
<T> T[]	toArray(T[]a) 返回包含Collection所有元素的数组，数组元素类型由运行时类型T指定。

在Collection所提供的方法中，以Collection类型作为参数的函数，都为Collection的实现类提供了互操作的功能。如可以把一个List中所有元素加到一个Set中，反之亦然。toArray方法可以把一个Collection转换成相应的数组，为Collection使用数组的算法提供了方便。特别是某些算法如排序，对数组的运行效率最高。因此，如果要对一个Collection里面的元素进行排序的话，通常是先转换成数组再排序。

List接口

List接口是Collection的一个子接口，它提供了线性表的操作接口。Java集合所提供的List接口与我们数据结构上的线性表是一致的。List又称为有序的Collection，此接口允许用户对列表中的每个元素的插入和删除位置进行精确的控制。因此，List是一个提供随机访问接口的线性表。同时List通常允许存在重复的元素。下面是List接口中在Collection的基础上新增的方法。

方法概述
void	add(intindex,Eelement) 在列表的指定下标增加元素。
boolean	addAll(intindex,Collection<? extendsE>c) 在列表指定下标增加c中所有元素到列表中。
E	get(intindex) 访问列表中指定下标的元素。
int	indexOf(Objecto) 返回对象o在列表中第一次出现的下标，如列表不包含元素o则返回-1。
int	lastIndexOf(Objecto) 返回元素o在列表中最后一次出现的下标，如列表不包含则返回-1。
ListIterator<E>	listIterator() 返回列表元素的列表迭代器。
ListIterator<E>	listIterator(intindex) 返回列表元素的列表迭代器，该迭代器从指定下标元素开始。
E	remove(intindex) 删除列表中指定下标的元素。
E	set(intindex,Eelement) 设置列表中指定下标元素的值。
List<E>	subList(intfromIndex, inttoIndex) 返回子列表[fromIndex, toIndex)。

在List接口中，增加的方法主要是为随机访问提供方便。通常这些函数的参数都指定访问元素的下标；再者是返回元素的下标和得到列表的子列表。至于List基于不同的物理结构，有不同的实现（如ArrayList和LinkedList）和随机访问的代价不同，提供了列表迭代器对元素进行操作。使访问元素独立于具体的实现。

Set

Set接口同样是Collection接口的一个子接口，它表示数学意义上的集合概念。Set中不包含重复的元素，即Set中不存两个这样的元素e1和e2，使得e1.equals(e2)为true。由于Set接口提供的数据结构是数学意义上集合概念的抽象，因此它需要支持对象的添加、删除，而不需提供随机访问。故Set接口与Collection的接口相同，在此对里面的方法不作介绍。

Queue

Queue为用户提供了队列的操作接口，同样是Collection的子接口。除于提供基本的Collection操作外，Queue还提供了队列的进队、出队和检查操作。从数据结构来说，Queue应提供一个先进先出的数据结构(FIFO)；但在Java集合框架中，这并非一成不变的要求。优先级队列和 LIFO 队列就是一个例外。因此，我们可以认为Java集合框架中的Queue是这样的一个数据结构；Queue为用户提代了一个在尾端插入，在头端删除这样的数据结构，元素与元素的关系依赖于具体实现。如一般的队列存在先进先出的关系，但在优先队列中，存在元素按大小的关系。因此在Queue的实现中，必须说明元素之间的关系，即元素间的顺序属性。下面是提供列队操作方法的说明。

方法概述
E	element() 检过队头元素，但不删除。如果队列为空则抛出NoSuchElementException异常。
boolean	offer(Ee) 进队操作。
E	peek() 检索队头元素，但不删除。如果队列为空则返回null。
E	poll() 删除并返回队头元素，如果队列为空则返回null。
E	remove() 删除并返回队头元素，如果队列为空抛出NoSuchElementException异常。

队列接口为用户提供了一个进队方法，两个检索队头元素的方法和两个出队的方法，如果队列为空时，分别有一个返回null值，另一个抛出NoSuchElementException异常。用户可根据自己的需进行选取。

Deque

Deque是”double ended queue”，即为双端队列。相信在很多数据结构的书都把双端队列称为高级数据结构的一种。双端队列提供的灵活性比队列要大，但它的逻辑意义和实现绝对不会比队列要难很多，因此，在我们看来，双端队列还是很容易使用的。

Deque从Queue接口继承而来，因而能提供基本的队列操作。然而它最富有特色的地方是可以在两端进行插入和删除操作。下面是该接口的详细说明。

方法概述
void	addFirst(Ee) 在前端插入元素。
void	addLast(Ee) 在尾端插入元素。
Iterator<E>	descendingIterator() 返回双端队列中元素的逆序迭代器。
E	getFirst() 查看前端元素，但不删除。
E	getLast() 查看尾端元素，但不删除。
Iterator<E>	iterator() 返回双端队列元素的迭代器。
boolean	offerFirst(Ee) 在前端插入元素。
boolean	offerLast(Ee) 在尾端插入元素。
E	peekFirst() 查看前端元素。
E	peekLast() 查看尾端元素。
E	pollFirst() 查看并删除前端元素。
E	pollLast() 查看并删除尾端元素。
void	push(Ee) 在前端插入元素，此时双端队列可看作栈进行操作。
E	pop() 在前端删除元素，此时又端除列可看栈进行操作。
E	removeFirst() 查看并删除前端元素。
E	removeLast() 查看并删除尾端元素。

从双端队列提供的接口中可以看出来，它与队列的接口很类似。对在两端进行查看，和删除都提供了两种方法，在处理双端队列为空时一个返回null值，一个抛出NoSuchElementException异常。此外，双端队列还提供栈的接口，push和pop这两个方法是专为栈而设置的。最后双端队列仍然是一个队列。

Map

写到这里，突然想到Java集合框架里面还有一个接口，那就是Map。它提供一个从键映射到值的数据结构，我们姑且把它称为映射吧。映射中不能包含重复的键，每个键最多映射到一个值上。从直观上分析Map也应是Collection，因为Map里面装着很多元素，不同的是元素是一个<Key-Value>对而已。但API设计人员并没有把Map从Collection中扩展而来，这与Eclipse不从Circle中扩展而来有异曲同工之妙：两者有功能是具有相同的部分，但在细节和接口上还是有很多的差别。在面向对象中，代码的复用和互操作并不一定得表现在继承上，引用另一个对象也是一种表现方式。Map的设计者采用了后者，进而减少两个接口的依赖。下面是Map的主要方法介绍。

方法概述
boolean	containsKey(Objectkey) 返回映射是否包含键key，如是返回true，否则false。
boolean	containsValue(Objectvalue) 返回映射是否有键映射到值value中，如有则返回true，否则false。
Set<Map.Entry<K,V>>	entrySet() 返回映射中的所有<key-value>对的集合。
V	get(Objectkey) 返回映射中键key所对应的值，如不存在key则返回null。
boolean	isEmpty() 如果映射不<key-value>对，则返回true，否则为false。
Set<K>	keySet() 返回映射中所有键的集合。
V	put(Kkey,Vvalue) 指定键key所关联的值value。
void	putAll(Map<? extendsK,? extendsV>m) 把m中所有<key-value>对加入当前映射中。
V	remove(Objectkey) 删除键key所对应的<key-value>对。
Collection<V>	values() 返回映射中所有值的Collection形式。

Map虽然不从Collection中扩展而来，但它与Collection的关系还是很紧密地联系在一起。Map主要提供了增加、更改和删除<.key-value>对的操作。同时还返回<key-value>对、键以及值的集合视图，以方便使用。

Java集合框架中Collection的实现

上面分析了Java集合框架提供的接口，这一节点我们继续对它的各种实现进行剖析。Java API的设计者想人所想，对不同接口根据不同的物理结构，分别作出不同的实现，如有的采用链表进行实现，也有采用哈希散列的方法以及红黑树（一种平衡二叉树）等方法进行实现。Collections中的所有实现中，类名都采用了<Implementation-style><Interface>这样的命名方式，下表是各种接口在不同的物理结构下实现。

	Implementations
Hash Table	Resizable Array	Balanced Tree	Linked List	Hash Table + Linked List
Interfaces	Set	HashSet		TreeSet		LinkedHashSet
List		ArrayList		LinkedList
Deque		ArrayDeque		LinkedList
Map	HashMap		TreeMap		LinkedHashMap

上面的各种实现，所提供的接口与它直接implements的接口有一样的方法。因此它们在implements过程中没有提供额外的方法。在此，我们需要分析各种实现的性能和效率。

Resizable Array实现方式

Resizable Array方式类似于动态数组，对象分配一个数组，也即物理结构上分配在一块连续内存区域里面。由于Java中不存在动态数组，它是采用静态数组而实现的。首先是对象先new一定固定大小的数组对象，大小可以根据默认值或用户指定；此后把要加入Collections的对象依次放到数组中，如果数组放满时，再申请一个原来更大的数组，通常是原来的2倍大小，然后把原来数组的内存拷贝到新数组中，然后再加入元素。采用Resizable Array实现方式的数据结构有ArrayList和ArrayDeque。对于ArrayList来说，由于采用数组的结构方式，所以ArrayList所提供的随机访问方法很高效，同时有列表最后位置添加和删除元素的效率也很高，不适合在其它位置频繁进行插入和删除元素操作，因此它要对数组中很大部分元素要进行移动才能完成，这就使得插入和删除元素的代价为O(n)，n为元素个数。ArrayDeque采用数据结构上的循环队列来储存对象。当分配的数组大小不够的时候，重新分配一个原来大小两倍的数组，然后再拷贝过去。原来的队列和队尾位置信息不变。通过采用循环队列的组织形式，双端队列的在两端的插入和删除元素的代价均为O(1)。

Linked List实现方式

Linked List方式是双向链表的实现方式，List和Deque接口均由LinkedList类实现。LinkedList由于采用了双向链表的实现形式，它与ArrayList有着互补的特性。它支持高效的频繁插入和删除元素操作，但随机访问的效率却很低。不要忘记LinkedList也实现了Deque接口，LinkedList除了是链表，同时也是队列和双端队列，并且也可以把它看作栈（它提供了栈操作的两个方法）。LinkedList作为队列来说，它在两端的插入和删除元素操作的代价同样是O(1)，但由于里面要维护双向链表的数结构，与ArrayDeque相比，效率稍低一点。

Balanced Tree实现方式

Balanced Tree即平衡二叉树。它里面维护是的二叉树的数据结构，并且是平衡的。每个子树的高度相差不超过1，使得插入、删除和查找元素的代价为O(logn)。Java集合框架中的平衡二叉树采用红黑树，而非采用AVL平等二叉树（很多类库如STL都采用红黑树来实现set类）。采用了平衡二叉树的数据结构，在结构是有序的，即元素间是可比较的，因此，插入元素和删除元素以及查找元素的代价均为O(logn)。采用这种实现方式的类有TreeSet和TreeMap，在内部结构都采红黑树作为底层数据结构。使用TreeSet或TreeMap类的好处是，他们内部是有序的，当操作它们要求元素的大小有严格要求时（如每次取出最小的），它提供的方法是相当高效的。

Hash Table实现方式

Hash Table即哈希表，它的神奇之处是通各对象的哈希码值映射到对象所储存的物理地址。当元素间有哈希冲突时，Java集合框架采用链地址法，即把具有相同hash Code的对象放在一个链表中。学习过哈希表的朋友还会记得哈希表中有一个重要的参数，那就是装填因子a，它表示哈希表的装满程度。装填因子越小，则产生冲突的机会就会越小，反之亦然。哈希表的平均查找长度跟有直接的关系，如果采用链地址法解决哈希冲突问题，那么哈希表的查找长度为1+a/2。通常Java集合框架中的装填因子默认值为0.75，也可以用户自行指定。从哈希表方式的平均查找长度可以得知，它的查找方法是相当高效的，平均长度不超1.5，能快速定位，而基于平衡二叉树的平均查找长度是O(logn)。因此，需要快速查找元素的应用可以使用哈希表的实现方式。但是，哈希表的实现方式中还有一个很重要的参数，那就是容量。当哈希表的容量为M(通常为素数以减少冲突次数)，装填因子为a时，该哈希表能存放的元素个数为a*M，并且占用系统内存大小为O((1+a)*M)。因此浪费了部分无用的储存空间，即要求系统为n个元素的哈希表分配多于n个元素的空间。如果哈希表中存放的元素个数超过a*M时，哈希表会向系统申请一个更大容量的内存空间（新容量仍是一个素数）。HashSet和HashMap都采用哈希表的实现方式，能提供快速的查找方法，代价是常数级的。基于哈希表和平衡二叉树实现方式的实现各有千秋：哈希表实现方式查找方法快速高效，而平衡二叉树需要对数级的代价；平衡二叉树的实现方式提供按元素大小关系的访问方式，这点是哈希表实现方式所不能及的。如果在应用中需在快速查找，同时也需要利用元素的大小关系进行操作，最好的方法莫过于利用两种对种的组合：分别生成两个类的对象各一个，保持两个对象数据的一致性；如需要快速查找时，只需用哈希表方式实现的对象进行查找，而要利用大小关系时，可访问平衡二叉树方式实现的对象；这样的优点是运行效率高，缺点是点用系统内存更大。

Hash Table + Linked List实现方式

Hash Table+LinkedList实现方式即哈希表与双向连表的实现方式，这种方式与Hash table方式大致相同，不同的地方是在原来的结构上增加了一个双向链表维护容纳的对象。由于增加了维护链接列表的开支，其性能很可能会比Hash Table稍逊一筹，但有一点是例外的：在Hash Table+LinkedList实现方式中迭代所有元素需要的时间与集合的大小成正比，而与容量无关；在Hash实现方式中迭代所有元素代价较大，因为它所需迭代时间与其容量成正比。基于此实现方式的类有HashLinkedListSet和HashLinkedMap，都类似于HashSet和HashMap，提供的接口也一致。

线程安全问题

上述的Collections实现都是非线程安全的。如果多个线程同时访问同一个Collections时，则它必须保持外部同步。一般通过对自然封装该集合的对象进行同步操作来完成，如果不存在这样的对象，则应该使用Collections.synchronizedSet方法来“包装”该集合。最好在创建时完成这一操作，以防止意外的非同步访问：

List l = Collections.synchronizedList(new LinkedList(…));

Set s = Collections.synchronizedSet(new LinkedHashSet(...));

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

这三个方法是Collections类（一个算法类）提供生产线程安全的集合，更详细说明请参考Java API说明文档。

Java集合框架中的算法

Java.util包里面除了提供丰富的数据结构，还提供了大量的算法，这些算法在Collections类中。Collections是集合的算法类，所提供的算法通过static方法来实现，下面对Collections提供的算法进行说明。

排序算法（sort）

Collections类为列表(List)提供了排序算法，可按自然顺序或用户指定排序进行排序。Collections提供的排序算法是改进的合并排序算法，并且是稳定的排序算法，能保证性能是nlog(n)。它将列表先转换成数组，然后再对数组进行排序，这是由于排序过程中要实现随机访问过程。

查找算法(binarySearch)

Collections类为列表提供了一个高效的查找算法，二分查找算法。在调用此算法前，列表必须是有序的，否则结果不可预知。

除了上述两个为List提供的重要算法外，Collections类为所有Collection提供了很多通用的算法，如copy(复制)、fill(填充)、max(最大值)、min（最小值）和reverse(逆序)等算法，更多的算法请参考Java API的说明文档。

Java集合框架的基础类(Infrastructure)

Java类库的开发人员把迭代器，顺序(ordering)称为集合框架中的基础设施，我们这里把它称作基础类。

使用迭代器，可以有效地遍历集合的所有元素而不需了解它的物理结构，提供了一种透明的访问机制。Iterator是一种单向的迭代器，沿着next进行访问所有元素，只能删除元素，而不能改更元素；ListIterator是一种双向的迭代器，可以向前和向后访问元素，同时能够删除元素，也能更改元素。迭代器是整个集合框架中所有集合的粘合剂，无须了解集合的物理结构就可以遍历集合的所有元素。除了List接口提了了按下标访问集合元素外，其它集合都没有提供。因此，要遍历这些集合中的元素，只能使用迭代器遍历或转换成数组再进行随机访问。故迭代器在集合框架中功不可没。

部分集合（如TreeSet和TreeMap）要求元素是有序的，即可能相互比较的。Java集合框架中使用Comparable和Comparator这两个接口来实现元素的相互比较。一个类implements Comparable接口，那么它的对象是自然有序的，可排序的。如果某个类没有implements Comparable接口，那么可以使用另外一个类implements Comparator接口，来制定该类中对象的排序依据，使它在外界对象（比较器）的作用，也是可以有序的。值得一提的是，Comparable和Comparator这两个接口之中并没有重复的部分，也就是不能说一个类implements了Comparator，就不需要提供它的Comparator，这不是绝对的。String类implemetns了Comparable接口，如果想改变它的比较方法的话，那就显得无能为力了；但是我们可能以通过提供另一个比较器(Comparator)来重写它的比较方法，以满足我们新的需求。

写在后面的话

本文粗略地介绍了J2SE1.6平台下的集合框架的部分内容，包括它提供的集合接口、集合的实现以及算法等一些重要类。对于集合框架来说，远远不止这些东西。集合实现中还有很多根据需要的实现，如并发实现，特别用途实现等等。其中并发实现主要在包java.util.concurrent中。最后本文能希望对大家了解Java集合框架有帮助。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

集合类说明及区别：

摘自：http://blog.csdn.net/softwave/article/details/4166598

Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap

Collection接口
　　Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些 Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。
　　所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个 Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后 一个构造函数允许用户复制一个Collection。
　　如何遍历Collection中的每一个元素？不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下：
　　　　Iterator it = collection.iterator(); // 获得一个迭代子
　　　　while(it.hasNext()) {
　　　　　　Object obj = it.next(); // 得到下一个元素
　　　　}
　　由Collection接口派生的两个接口是List和Set。

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，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。
　　很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。
　　请注意：必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

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的简单示例如下，将1，2，3放到Hashtable中，他们的key分别是”one”，”two”，”three”：
　　　　Hashtable numbers = new Hashtable();
　　　　numbers.put(“one”, new Integer(1));
　　　　numbers.put(“two”, new Integer(2));
　　　　numbers.put(“three”, new Integer(3));
　　要取出一个数，比如2，用相应的key：
　　　　Integer n = (Integer)numbers.get(“two”);
　　　　System.out.println(“two = ” + n);
　　由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方 法。hashCode和equals方法继承自根类Object，如果你用自定义的类当作key的话，要相当小心，按照散列函数的定义，如果两个对象相 同，即obj1.equals(obj2)=true，则它们的hashCode必须相同，但如果两个对象不同，则它们的hashCode不一定不同，如 果两个不同对象的hashCode相同，这种现象称为冲突，冲突会导致操作哈希表的时间开销增大，所以尽量定义好的hashCode()方法，能加快哈希 表的操作。
　　如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个。
　　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回收。

总结
　　如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。
　　如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较高，如果多个线程可能同时操作一个类，应该使用同步的类。
　　要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。
　　尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果以后需要将ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。

同步性
Vector是同步的。这个类中的一些方法保证了Vector中的对象是线程安全的。而ArrayList则是异步的，因此ArrayList中的对象并 不是线程安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带 来的不必要的性能开销。
数据增长
从内部实现机制来讲ArrayList和Vector都是使用数组(Array)来控制集合中的对象。当你向这两种类型中增加元素的时候，如果元素的数目 超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector缺省情况下自动增长原来一倍的数组长度，ArrayList是原来的50%,所以最 后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初 始化大小来避免不必要的资源开销。
使用模式
在ArrayList和Vector中，从一个指定的位置（通过索引）查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的，这个时间我们用 O(1)表示。但是，如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长：O(n-i)，其中n代表集合中元素的个数，i代表元素增加或移除 元素的索引位置。为什么会这样呢？以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作。这一切意味着什么呢？
这意味着，你只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是其他操作，你最好选择其他 的集合操作类。比如，LinkList集合类在增加或移除集合中任何位置的元素所花费的时间都是一样的?O(1)，但它在索引一个元素的使用缺比较慢 －O(i),其中i是索引的位置.使用ArrayList也很容易，因为你可以简单的使用索引来代替创建iterator对象的操作。LinkList也 会为每个插入的元素创建对象，所有你要明白它也会带来额外的开销。
最后，在《Practical Java》一书中Peter Haggar建议使用一个简单的数组（Array）来代替Vector或ArrayList。尤其是对于执行效率要求高的程序更应如此。因为使用数组 (Array)避免了同步、额外的方法调用和不必要的重新分配空间的操作。

相互区别

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)。

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

arraylist和linkedlist

1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数 据，LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

HashMap与TreeMap
(注)
文章出处：http://www.diybl.com/course/3_program/java/javaxl/200875/130233.html

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

HashMap中元素的排列顺序是不固定的）。

2、 HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该 使用TreeMap（HashMap中元素的排列顺序是不固定的）。集合框架”提供两种常规的Map实现：HashMap和TreeMap (TreeMap实现SortedMap接口)。

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

结过研究，在原作者的基础上我还发现了一点，二树map一样，但顺序不一样，导致hashCode()不一样。
同样做测试：
在hashMap中，同样的值的map,顺序不同，equals时，false;
而在treeMap中，同样的值的map,顺序不同,equals时，true，说明，treeMap在equals()时是整理了顺序了的。

hashtable与hashmap

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

二.同步性:Hashtable是线程安全的，也就是说是同步的，而HashMap是线程序不安全的，不是同步的

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