JAVA的容器ListMapSet
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 = erator(); // 获得一个迭代子
while(ithasNext()) {
Object obj = itnext(); // 得到下一个元素
}
由Collection接口派生的两个接口是List和Set
List接口
List是有序的Collection使用此接口能够精确的控制每个元素插入的位置用户能够使用索引（元素在List中的位置类似于数组下标）来访问List中的元素这类似于Java的数组
和下面要提到的Set不同List允许有相同的元素
除了具有Collection接口必备的iterator()方法外List还提供一个listIterator()方法返回一个 ListIterator接口和标准的Iterator接口相比ListIterator多了一些add()之类的方法允许添加删除设定元素 还能向前或向后遍历
实现List接口的常用类有LinkedListArrayListVector和Stack
LinkedList类
LinkedList实现了List接口允许null元素此外LinkedList提供额外的getremoveinsert方法在 LinkedList的首部或尾部这些操作使LinkedList可被用作堆栈（stack）队列（queue）或双向队列（deque）
注意LinkedList没有同步方法如果多个线程同时访问一个List则必须自己实现访问同步一种解决方法是在创建List时构造一个同步的List
List list = CollectionssynchronizedList(new LinkedList());
ArrayList类
ArrayList实现了可变大小的数组它允许所有元素包括nullArrayList没有同步
sizeisEmptygetset方法运行时间为常数但是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提供个额外的方法使得Vector得以被当作堆栈使用基本的push和pop 方法还有peek方法得到栈顶的元素empty方法测试堆栈是否为空search方法检测一个元素在堆栈中的位置Stack刚创建后是空栈
Set接口
Set是一种不包含重复的元素的Collection即任意的两个元素e和e都有eequals(e)=falseSet最多有一个null元素
很明显Set的构造函数有一个约束条件传入的Collection参数不能包含重复的元素
请注意必须小心操作可变对象（Mutable Object）如果一个Set中的可变元素改变了自身状态导致Objectequals(Object)=true将导致一些问题
Map接口
请注意Map没有继承Collection接口Map提供key到value的映射一个Map中不能包含相同的key每个key只能映射一个 valueMap接口提供种集合的视图Map的内容可以被当作一组key集合一组value集合或者一组keyvalue映射
Hashtable类
Hashtable继承Map接口实现一个keyvalue映射的哈希表任何非空（nonnull）的对象都可作为key或者value
添加数据使用put(key value)取出数据使用get(key)这两个基本操作的时间开销为常数
Hashtable通过initial capacity和load factor两个参数调整性能通常缺省的load factor 较好地实现了时间和空间的均衡增大load factor可以节省空间但相应的查找时间将增大这会影响像get和put这样的操作
使用Hashtable的简单示例如下将放到Hashtable中他们的key分别是onetwothree
Hashtable numbers = new Hashtable();
numbersput(one new Integer());
numbersput(two new Integer());
numbersput(three new Integer());
要取出一个数比如用相应的key
Integer n = (Integer)numbersget(two);
Systemoutprintln(two = + n);
由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置因此任何作为key的对象都必须实现hashCode和equals方 法hashCode和equals方法继承自根类Object如果你用自定义的类当作key的话要相当小心按照散列函数的定义如果两个对象相 同即objequals(obj)=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时客户端代码不用改变这就是针对抽象编程
bcbl
