Collection接口相关知识

一．基本概念

Java容器类库的用途是保存对象，根据数据结构不同将其划分为两个不同的概念

（1）    Collection，一个独立元素的序列，其中List按照元素的插入顺序保存元素，而set不能有重复元素，Queue按照先进先出（FIFO）的方式来管理数据，Stack按照后进先出（LIFO）的顺序管理数据。

（2）    Map，一组键值对（key-value）对象的序列，可以使用key来查找value，其中key是不可以重复的，value可以重复。我们可以称其为字典或者关联数组。其中HashMap是无序的，TreeMap是有序的，WeakHashMap是弱类型的，Hashtable是线程安全的。

下面这张图来自于Thinking in Java Fourth Edition第十七章：

除上面图中画到的内容外在java.util.concurrent包中也实现了大量的线程安全的集合类，可以很方便的使用。如ConcurrentHashMap、CopyOnWriteArrayList、CopyOnWriteArraySet等。

二．Collection接口

Ø  由集合类图结构可以得知Collection接口是Java语言中最基本的集合接口，在JDK中没有直接提供Collection接口的具体实现类，Collection的功能实现类主要是对它的两个更具体的子接口List和Set的具体实现类。但是在Collection接口中定义了一套通用操作的实现方法和命名规则。

Ø  在JDK帮助文档中可以看到Collection接口以及各个子接口、各种形式实现类的说明。

Ø  对Collection接口的实现类构造方法一般至少有下面两种：一个是void（无参数）构造方法，用于创建空的Collection对象实例；另一个是带有一个Collection类型参数的构造方法，用于创建一个具有与其参数相同元素的Collection对象实例。例如HashSet类的构造方法有下面四种：

a)        HashSet()：构造一个初始容量为16、加载因子为0.75的HashSet类的实例对象；

b)        HashSet(Collection<? extends E> c)：构造一个包含指定集合对象的HashSet类的对象实例。

c)        HashSet(int initialCapacity)：构造一个指定初始容量的HashSet类的实例对象。

d)        HashSet(int initialCapacity, float loadFactor)：构造一个指定初始容量以及指定加载因子的HashSet类的实例对象。

Ø  Collection接口中共定义了15个通用的方法：

a)        Collection接口方法清单

1.     List接口及其实现类

List接口中方法清单

List可以将元素维护在特定的序列中，并且允许一个相同元素在集合中多次出现。List接口在Collection接口的基础上增加了大量的方法，使得可以在List中间插入和移除元素。除了Abstract类之外，在学习中比较常用的类有ArrayList（基于数组实现），LinkedList（基于循环链表实现），Vector（基于数组实现，线程安全），Stack（是Vector的子类，基于数组实现），CopyOnWriteArrayList（基于数组实现，线程安全）

List接口中提供的面向位置操作的各种方法：（集合中已有的方法略去）

•           void add(int index, E element) : 在列表的指定位置插入指定元素。

•           boolean addAll(int index, Collection<? extends E> c) : 将指定集合中的所有元素插入到集合中的指定位置。

•           E get(int index) : 返回集合中指定位置的元素。

•           int indexOf(Object o) : 返回指定对象在集合中第一次出现的索引，从0位置开始，返回-1为不存在该元素。

•           int lastIndexOf(Object O) : 返回指定对象在集合中最后一次出现的索引位置，返回-1为不存在。

•           ListIterator<E> listIterator() : 以正确的顺序返回集合中元素的列表迭代器。

•           ListIterator<E> listIterator(int index) : 以正确的顺序返回集合中元素的列表迭代器，从集合中指定的位置开始。

•           E remove(int index) : 移除集合中指定位置的元素。

•           E set(int index, E element) : 用指定元素替换集合中指定位置的元素。

•           List<E> subList(int fromIndex, int toIndex) : 返回集合中指定的fromIndex（包括）和toIndex(不包括)之间的部分视图。

List接口提供了名称为ListIterator的特殊迭代器。

List在数据结构中分别表现为数组、向量、链表、堆栈、队列等形式。

Ø  ArrayList的特点、实现机制及使用方法

a)      ArrayList特点：

ArrayList顾名思义，它是用数组实现的一种线性表。常规数组不具备自动递增的功能，但是ArrayList在使用时我们不必考虑这个问题。可以直接按位置进行索引，查找和修改速度较快，缺点是插入或者删除速度较慢。在执行插入删除时调用的是System.arraycopy方法，是一个native方法。

b)      ArrayList的实现机制：

在JDK源码中可以看到ArrayList总共只有两个属性，一个是Object数组类型的elementData，一个是int型的size。

在构造方法中也可以看到，无参构造方法调用的是this(10)，调用的带一个参数的构造方法，默认无参构造方法分配一个size为10的数组。按照Collection接口中定义的构造方法，它必须有一个通过其它集合对象构造自身对象的方法。这是一个相对比较简单的线性表。并且JDK中提供了大量的比较好用的方法可以使用。该动态数组在存储空间不足时按照下面方法重新分配空间：

newCapacity = (oldCapacity*3)/2 + 1;

if(newCapacity < minCapacity) newCapacity = minCapacity;

c)      使用方法（ArrayList的使用方法其实是比较简单，但是也是比较常用和好用的，个人感觉）

下面例子为了尽可能多的用到ArrayList的方法，可能看起来没有多大意义

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class ExampleForArrayList {
    public static void main(String[] args) {
        String[] str = new String[]{"My", "name", "is", "Wang", "Yan", "tao"};
        List<String> ls1 = new ArrayList<String>(10);
        //把数组中的数据添加到ls1中
        for(int i=0; i<str.length; i++) {
            ls1.add(str[i]);
        }
        //使用ls1来构造ls2
        List<String> ls2 = new ArrayList<String>(ls1);
        System.out.println("ls2中元素的个数：" + ls2.size());
        System.out.println("is在ls2中的位置：" + ls2.indexOf("is"));
        System.out.println("Wang在ls2中最后一次出现的位置：" + ls2.lastIndexOf("Wang"));
        System.out.println("ls2中的所有元素：");
        //这里使用iterator遍历
        Iterator<String> it = ls2.listIterator();
        while(it.hasNext()) {
            System.out.println(it.next());
        }
        //我一般使用下面方法遍历,或者基本的for循环遍历
        for(String tmp : ls2) {
            System.out.println(tmp);
        }
    }
}

Ø  LinkedList的特点、实现机制及使用方法

a)      LinkedList的特点：

现在发现java中类的命名真是太好了，比如这个吧，一看就知道它使用链表实现的。链表操作的优点就是插入删除比较快，但是不能按索引直接存取，所以执行更新操作比较快，执行查询操作比较慢。它的整体特性由于ArrayList。

b)      LinkedList实现机制：

查看jdk源码可以得知每个元素在LinkedList中都是一个LinkedList.Entry的实例对象。该类定义如下：

private static class Entry<E> {
    E element;
    Entry<E> next;
    Entry<E> previous;
    Entry(E element, Entry<E> next, Entry<E> previous) {
        this.element = element;
        this.next = next;
        this.previous = previous;
    }
}

在构造方法中这样的定义：

           header.next = header.previous = header;

              也就是说LinkedList底层使用一个循环双向链表实现的。

LinkedList实现了许多对first和last元素进行操作的方法，比如set、get、remove等。

虽然LinkedList获取指定位置的元素时较ArrayList按索引获取较慢，但是JDK中对get方法做了优化：

if (index < (size >> 1)) {
     for (int i = 0; i <= index; i++)
         e = e.next;
} else {
     for (int i = size; i > index; i--)
         e = e.previous;
}

虽然还是顺序挨个查找，但是已经做了优化。size>>1 == size/2，移位运算要比除法运算效率高的多。

c)      LinkedList和ArrayList的使用方法类似，只是看自己的需要进行选择了。除此之外LinkedList还实现了栈操作的所有方法。

Ø  Vector的特点、实现机制及使用方法

a)      Vector的特点：

ArrayList实现的是一种动态数组，LinkedList是一种双向循环链表，Vector并未在前两者的基础上做实现，而是直接实现了List接口。Vector中的所有方法前面都有一个synchronized关键字做修饰。Vector是有序可重复的。

b)      Vector的实现机制：

我暂时还不理解为什么要实现Vector这个类，和ArrayList基本是一样的，不一样的是Vector是线程安全的，但是Collections里面提供了将非线程安全的集合转换成线程安全的集合的方法。

c)      Vector的使用方法(与ArrayList使用方法类似)

Ø  Stack的特点、实现机制及使用方法

a)      Stack的特点：

Stack（栈）是一种后进先出的序列，主要操作有判空、压栈、退栈、取栈顶元素等。

b)      Stack的实现机制：

Stack继承自Vector，同样使用数组保存数据，根据该数据结构的特点进行了限制性操作。JDK中共提供了6个方法用于实现特定要求的操作：

•           Stack() : 构造一个空的栈

•           empty() : 判断栈是否为空

•           peek() : 查看栈顶元素并返回栈顶对象

•           pop() : 删除栈顶元素并返回栈顶对象

•           push(E element) : 将一个元素压入当前栈中

•           search(Object o) : 查看指定对象是否在当前栈中

c)      Stack的使用方法

import java.util.Stack;
public class ExampleForStack {
    /*
     * 这是一个非常简单的例子
     * 用于展现栈的这种后进先出的特性
     * 逆序打印一个字符串
     */
    public static void main(String[] args) {
        String str = "abcdefghijklmnopqrstuvwxyz";
        Stack<Character> stack = new Stack<Character>();
        for(char ch : str.toCharArray()) {
            stack.push(ch);
        }
        while(!stack.empty()) {
            System.out.print(stack.pop());
        }
    }
}

Ø  CopyOnWriteArrayList的特点、实现机制及使用方法

a)      CopyOnWriteArrayList的特点：

CopyOnWriteArrayList是java.util.concurrent包中的一个类，此类是一个线程安全类。由于用到了ReentrantLock（重入锁）同步，所以在修改效率上较ArrayList差。

b)      CopyOnWriteArrayList的实现机制：

刚开始觉得这个名字好长，并且感觉奇怪，为什么要这样命名？首先这是一个为了实现并发同步而设计的类，那么在所有与修改方法相关的地方均会使用lock来保证同步。Copy-on-write的英文释义是“写时拷贝、写时复制”，现在看来觉得这个名字就更容易理解了，那么这个类到底是怎么实现的呢？面试官说：“踏踏实实看源码”。-_-|||

首先说一下写方法：

•           public E set(int index, E element) : 将指定位置的元素使用element替换掉。JDK中的源码如下：

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        Object oldValue = elements[index];
        if (oldValue != element) {
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            setArray(newElements);
        } else {
            setArray(elements);
        }
        return (E)oldValue;
    } finally {
        lock.unlock();
    }
}

在源码中可以看出，首先执行写入（包括set,add,remove等）操作时，首先得到一把当前对象的重入锁，其次获得当前对象元素的一个拷贝（写时拷贝），再次用修改后的元素替换掉原来的元素，最终释放锁。

这里引用两个常识：

1、JAVA中“=”操作只是将引用和某个对象关联，假如同时有一个线程将引用指向另外一个对象，一个线程获取这个引用指向的对象，那么他们之间不会发生ConcurrentModificationException，他们是在虚拟机层面阻塞的，而且速度非常快，几乎不需要CPU时间。

2、JAVA中两个不同的引用指向同一个对象，当第一个引用指向另外一个对象时，第二个引用还将保持原来的对象。

•           public void add(E e) : 向当前对象中加入指定元素。实现方式与set相同，均是copy-on-write。

•           还有remove等修改内容的操作。

除写方法（修改，删除，添加）外，CopyOnWriteArrayList类还提供了ArrayList相类似和功能更齐全的方法供选择使用。

•           public ListIterator<E> listIterator() : 该方法返回一个ListIterator类型的迭代器，但是该迭代器的真正类型是COWIterator类型的，不允许有插入、删除、添加等方法。

使用方法与ArrayList类似，只是用时选择的问题。因为在写操作时大量使用了System.arrayCopy方法，所以在效率上会有所降低。因此它适合使用在读操作远远大于写操作的场景中。