Java 中Iterator 、Vector、ArrayList、List 使用深入剖析

Iterator模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来，从而避免向客户端暴露集合的内部结构。

例如，如果没有使用Iterator，遍历一个数组的方法是使用索引：

       for(int i=0; i<array.size(); i++) { ... get(i) ... }

而访问一个链表（LinkedList）又必须使用while循环：

       while((e=e.next())!=null) { ... e.data() ... }

以上两种方法客户端都必须事先知道集合的内部结构，访问代码和集合本身是紧耦合，无法将访问逻辑从集合类和客户端代码中分离出来，每一种集合对应一种遍历方法，客户端代码无法复用。

更恐怖的是，如果以后需要把ArrayList更换为LinkedList，则原来的客户端代码必须全部重写。

为解决以上问题，Iterator模式总是用同一种逻辑来遍历集合：

       for(Iterator it = c.iterater(); it.hasNext(); ) { ... }

奥秘在于客户端自身不维护遍历集合的"指针"，所有的内部状态（如当前元素位置，是否有下一个元素）都由Iterator来维护，而这个Iterator由集合类通过工厂方法生成，因此，它知道如何遍历整个集合。

客户端从不直接和集合类打交道，它总是控制Iterator，向它发送"向前"，"向后"，"取当前元素"的命令，就可以间接遍历整个集合。

首先看看java.util.Iterator接口的定义：

       public interface Iterator {
           boolean hasNext();
           Object next();
           void remove();
       }

依赖前两个方法就能完成遍历，典型的代码如下：

       for(Iterator it = c.iterator(); it.hasNext(); ) {
           Object o = it.next();
           // 对o的操作...
       }

在JDK1.5中，还对上面的代码在语法上作了简化：

       // Type是具体的类型，如String。
       for(Type t : c) {
           // 对t的操作...
       }

每一种集合类返回的Iterator具体类型可能不同，Array可能返回ArrayIterator，Set可能返回SetIterator， Tree可能返回TreeIterator，但是它们都实现了Iterator接口，因此，客户端不关心到底是哪种Iterator，它只需要获得这个 Iterator接口即可，这就是面向对象的威力。

让我们来看看AbstracyList如何创建Iterator。首先AbstractList定义了一个内部类（inner class）：

       private class Itr implements Iterator {
           ...
       }

而iterator()方法的定义是：

       public Iterator iterator() {
           return new Itr();
       }

因此客户端不知道它通过Iterator it = a.iterator();所获得的Iterator的真正类型。

现在我们关心的是这个申明为private的Itr类是如何实现遍历AbstractList的：

       private class Itr implements Iterator {
           int cursor = 0;
           int lastRet = -1;
           int expectedModCount = modCount;
       }

Itr类依靠3个int变量（还有一个隐含的AbstractList的引用）来实现遍历，cursor是下一次next()调用时元素的位置，第一次调用next()将返回索引为0的元素。lastRet记录上一次游标所在位置，因此它总是比cursor少1。

变量cursor和集合的元素个数决定hasNext()：

       public boolean hasNext() {
           return cursor != size();
       }

方法next()返回的是索引为cursor的元素，然后修改cursor和lastRet的值：

       public Object next() {
           checkForComodification();
           try {
               Object next = get(cursor);
               lastRet = cursor++;
               return next;
           } catch(IndexOutOfBoundsException e) {
               checkForComodification();
               throw new NoSuchElementException();
           }
       }

expectedModCount表示期待的modCount值，用来判断在遍历过程中集合是否被修改过。AbstractList包含一个 modCount变量，它的初始值是0，当集合每被修改一次时（调用add，remove等方法），modCount加1。因此，modCount如果不 变，表示集合内容未被修改。

Itr初始化时用expectedModCount记录集合的modCount变量，此后在必要的地方它会检测modCount的值：

       final void checkForComodification() {
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
       }

如果modCount与一开始记录在expectedModeCount中的值不等，说明集合内容被修改过，此时会抛出ConcurrentModificationException。

这个ConcurrentModificationException是RuntimeException，不要在客户端捕获它。如果发生此异常，说明程序代码的编写有问题，应该仔细检查代码而不是在catch中忽略它。

但是调用Iterator自身的remove()方法删除当前元素是完全没有问题的，因为在这个方法中会自动同步expectedModCount和modCount的值：

       public void remove() {
           ...
           AbstractList.this.remove(lastRet);
           ...
           // 在调用了集合的remove()方法之后重新设置了expectedModCount：
           expectedModCount = modCount;
           ...
       }

要确保遍历过程顺利完成，必须保证遍历过程中不更改集合的内容（Iterator的remove()方法除外），因此，确保遍历可靠的原则是只在一个线程中使用这个集合，或者在多线程中对遍历代码进行同步。

最后给个完整的示例：

       Collection c = new ArrayList();
       c.add("abc");
       c.add("xyz");
       for(Iterator it = c.iterator(); it.hasNext(); ) {
           String s = (String)it.next();
           System.out.println(s);
       }

如果你把第一行代码的ArrayList换成LinkedList或Vector，剩下的代码不用改动一行就能编译，而且功能不变，这就是针对抽象编程的原则：对具体类的依赖性最小。

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)避免了同步、额外的方法调用和不必要的重新分配空间的操作。















































































在使用 java的时候，我们都会遇到使用集合（collection）的时候，但是 java api提供了多种集合的实现。

总的说来， java api中所用的集合类，都是实现了collection接口，他的一个类继承结构如下：

                  collection<--list<--vector
                          collection<--list<--arraylist
                          collection<--list<--linkedlist
                          collection<--set<--hashset
                          collection<--set<--hashset<--linkedhashset
                          collection<--set<--sortedset<--treeset

vector : 基于array的list，其实就是封装了array所不具备的一些功能方便我们使用，它不可能走入array的限制。性能也就不可能超越array。所 以，在可能的情况下，我们要多运用array。另外很重要的一点就是vector&ldquo;sychronized&rdquo; 的，这个也是vector和arraylist的唯一的区别。

arraylist：同vector一样是一个基于array上的链表，但是不同的是arraylist不是同步的。所以在性能上要比vector优越一些，但是当运行到多 线程环境中时，可需要自己在管理 线程的同步问题。

linkedlist：linkedlist 不同于前面两种list，它不是基于array的，所以不受array性能的限制。它每一个节点（node）都包含两方面的内容：1.节点本身的数据 （data）；2.下一个节点的信息（nextnode）。所以当对linkedlist做添加，删除动作的时候就不用像基于array的list一样， 必须进行大量的数据移动。只要更改nextnode的相关信息就可以实现了。这就是linkedlist的优势。

list总结：

1. 所有的list中只能容纳单个不同类型的对象组成的表，而不是key－value键值对。例如：[ tom,1,c ]；

2. 所有的list中可以有相同的元素，例如vector中可以有 [ tom,koo,too,koo ]；

3. 所有的list中可以有null元素，例如[ tom,null,1 ]；

4. 基于array的list（vector，arraylist）适合查询，而linkedlist（链表）适合添加，删除操作。

hashset： 虽然set同list都实现了collection接口，但是他们的实现方式却大不一样。list基本上都是以array为基础。但是set则是在 hashmap的基础上来实现的，这个就是set和list的根本区别。hashset的存储方式是把hashmap中的key作为set的对应存储项。 看看hashset的add（object  obj）方法的实现就可以一目了然了。

    public boolean add(object obj)
    {
        return map.put(obj, present) == null;
    }

这个也是为什么在set中不能像在list中一样有重复的项的根本原因，因为hashmap的key是不能有重复的。

linkedhashset：hashset的一个子类，一个链表。

treeset：sortedset的子类，它不同于hashset的根本就是treeset是有序的。它是通过sortedmap来实现的。

set总结：

1. set实现的基础是map（hashmap）；

2.  set中的元素是不能重复的，如果使用add(object obj)方法添加已经存在的对象，则会覆盖前面的对象。

java.util包中包含了一系列重要的集合类。本文将从分析源码入手，深入研究一个集合类的内部结构，以及遍历集合的迭代模式的源码实现内幕。 

　　下面我们先简单讨论一个根接口Collection，然后分析一个抽象类AbstractList和它的对应Iterator接口，并仔细研究迭代子模式的实现原理。 

　　本文讨论的源代码版本是JDK 1.4.2，因为JDK 1.5在java.util中使用了很多泛型代码，为了简化问题，所以我们还是讨论1.4版本的代码。 

　　集合类的根接口Collection 

　　Collection接口是所有集合类的根类型。它的一个主要的接口方法是： 

　　boolean add(Object c) 

　　add()方法将添加一个新元素。注意这个方法会返回一个boolean，但是返回值不是表示添加成功与否。仔细阅读doc可以看到，Collection规定：如果一个集合拒绝添加这个元素，无论任何原因，都必须抛出异常。这个返回值表示的意义是add()方法执行后，集合的内容是否改变了（就是元素有无数量，位置等变化），这是由具体类实现的。即：如果方法出错，总会抛出异常；返回值仅仅表示该方法执行后这个Collection的内容有无变化。 

　　类似的还有： 

　　boolean addAll(Collection c); 
　　boolean remove(Object o); 
　　boolean removeAll(Collection c); 
　　boolean remainAll(Collection c); 

　　Object[] toArray()方法很简单，把集合转换成数组返回。Object[] toArray(Object[] a)方法就有点复杂了，首先，返回的Object[]仍然是把集合的所有元素变成的数组，但是类型和参数a的类型是相同的，比如执行： 

　　String[] o = (String[])c.toArray(new String[0]); 

　　得到的o实际类型是String[]。 

　　其次，如果参数a的大小装不下集合的所有元素，返回的将是一个新的数组。如果参数a的大小能装下集合的所有元素，则返回的还是a，但a的内容用集合的元素来填充。尤其要注意的是，如果a的大小比集合元素的个数还多，a后面的部分全部被置为null。 

　　最后一个最重要的方法是iterator()，返回一个Iterator（迭代子），用于遍历集合的所有元素。 

　　用Iterator模式实现遍历集合 
　　 
　　Iterator模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来，从而避免向客户端暴露集合的内部结构。 

　　例如，如果没有使用Iterator，遍历一个数组的方法是使用索引： 

　　for(int i=0; i<array.size();
 
　　而访问一个链表（LinkedList）又必须使用while循环： 

　　while((e=e.next())!=null) { ... e.data() ... } 

　　以上两种方法客户端都必须事先知道集合的内部结构，访问代码和集合本身是紧耦合，无法将访问逻辑从集合类和客户端代码中分离出来，每一种集合对应一种遍历方法，客户端代码无法复用。 

　　更恐怖的是，如果以后需要把ArrayList更换为LinkedList，则原来的客户端代码必须全部重写。 

　　为解决以上问题，Iterator模式总是用同一种逻辑来遍历集合： 

　　for(Iterator it = c.iterater(); it.hasNext(); ) { ... } 

　　奥秘在于客户端自身不维护遍历集合的"指针"，所有的内部状态（如当前元素位置，是否有下一个元素）都由Iterator来维护，而这个Iterator由集合类通过工厂方法生成，因此，它知道如何遍历整个集合。 

　　客户端从不直接和集合类打交道，它总是控制Iterator，向它发送"向前"，"向后"，"取当前元素"的命令，就可以间接遍历整个集合。 

　　首先看看java.util.Iterator接口的定义： 

　　public interface Iterator { 
　　boolean hasNext(); 
　　Object next(); 
　　void remove(); 
　　} 

　　依赖前两个方法就能完成遍历，典型的代码如下： 

　　for(Iterator it = c.iterator(); it.hasNext(); ) { 
　　Object o = it.next(); 
　　// 对o的操作... 
　　} 

　　在JDK1.5中，还对上面的代码在语法上作了简化： 

　　// Type是具体的类型，如String。 
　　for(Type t : c) { 
　　// 对t的操作... 
　　} 


　　每一种集合类返回的Iterator具体类型可能不同，Array可能返回ArrayIterator，Set可能返回SetIterator，Tree可能返回TreeIterator，但是它们都实现了Iterator接口，因此，客户端不关心到底是哪种Iterator，它只需要获得这个Iterator接口即可，这就是面向对象的威力。 
　　 Iterator源码剖析 

　　让我们来看看AbstracyList如何创建Iterator。首先AbstractList定义了一个内部类（inner class）： 

　　private class Itr implements Iterator { 
　　... 
　　} 

　　而iterator()方法的定义是： 

　　public Iterator iterator() { 
　　return new Itr(); 
　　} 

　　因此客户端不知道它通过Iterator it = a.iterator();所获得的Iterator的真正类型。 

　　现在我们关心的是这个申明为private的Itr类是如何实现遍历AbstractList的： 

　　private class Itr implements Iterator { 
　　int cursor = 0; 
　　int lastRet = -1; 
　　int expectedModCount = modCount; 
　　} 

　　Itr类依靠3个int变量（还有一个隐含的AbstractList的引用）来实现遍历，cursor是下一次next()调用时元素的位置，第一次调用next()将返回索引为0的元素。lastRet记录上一次游标所在位置，因此它总是比cursor少1。 

　　变量cursor和集合的元素个数决定hasNext()： 

　　public boolean hasNext() { 
　　return cursor != size(); 
　　} 

　　方法next()返回的是索引为cursor的元素，然后修改cursor和lastRet的值： 

　　public Object next() { 
　　checkForComodification(); 
　　try { 
　　Object next = get(cursor); 
　　lastRet = cursor++; 
　　return next; 
　　} catch(IndexOutOfBoundsException e) { 
　　checkForComodification(); 
　　throw new NoSuchElementException(); 
　　} 
　　} 

　　expectedModCount表示期待的modCount值，用来判断在遍历过程中集合是否被修改过。AbstractList包含一个modCount变量，它的初始值是0，当集合每被修改一次时（调用add，remove等方法），modCount加1。因此，modCount如果不变，表示集合内容未被修改。 

　　Itr初始化时用expectedModCount记录集合的modCount变量，此后在必要的地方它会检测modCount的值：

　　final void checkForComodification() { 
　　if (modCount != expectedModCount) 
　　throw new ConcurrentModificationException(); 
　　} 

　　如果modCount与一开始记录在expectedModeCount中的值不等，说明集合内容被修改过，此时会抛出ConcurrentModificationException。 

　　这个ConcurrentModificationException是RuntimeException，不要在客户端捕获它。如果发生此异常，说明程序代码的编写有问题，应该仔细检查代码而不是在catch中忽略它。 

　　但是调用Iterator自身的remove()方法删除当前元素是完全没有问题的，因为在这个方法中会自动同步expectedModCount和modCount的值： 

　　public void remove() { 
　　... 
　　AbstractList.this.remove(lastRet); 
　　... 
　　// 在调用了集合的remove()方法之后重新设置了expectedModCount： 
　　expectedModCount = modCount; 
　　... 
　　} 

　　要确保遍历过程顺利完成，必须保证遍历过程中不更改集合的内容（Iterator的remove()方法除外），因此，确保遍历可靠的原则是只在一个线程中使用这个集合，或者在多线程中对遍历代码进行同步。 

　　最后给个完整的示例： 

　　Collection c = new ArrayList(); 
　　c.add("abc"); 
　　c.add("xyz"); 
　　for(Iterator it = c.iterator(); it.hasNext(); ) { 
　　String s = (String)it.next(); 
　　System.out.println(s); 
　　} 

　　如果你把第一行代码的ArrayList换成LinkedList或Vector，剩下的代码不用改动一行就能编译，而且功能不变，这就是针对抽象编程的原则：对具体类的依赖性最小。