Java容器学习笔记（一） 容器中基本概念及Collection接口相关知识
本篇文章主要是总结了java容器中的相关知识点，包括容器层次结构、类图结构，Collection接口的详细信息，以及Collection的一个重要子接口List接口的相关知识点总结。其中涉及到一些类如ArrayList、LinkedList、Vector、Stack、CopyOnWriteArrayList等的底层数据结构、实现机制及用法等的学习总结。
一．基本概念
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接口方法清单
a) 添加和删除集合中的某个元素
? boolean add(E o) ： 将指定的元素追加到集合当中
? boolean remove(Object o) : 将指定的元素从集合中删除
b) 查询与集合有关的数据
? int size() : 返回此集合中元素的个数
? boolean isEmpty() : 测试此集合是否为空
? boolean contains(Object element) : 测试此集合中是否有该元素
? Iterator<E> iterator() : 返回此集合中的各个元素进行迭代的迭代器
c) 对若干个元素以组为单位进行操作
? boolean containsAll(Collection<?> c) : 判断此集合是否包含给定的一组元素，包含返回true，否则false
? boolean addAll(Collection<? extends E> c) : 将指定集合中的所有元素都添加到当前集合中
? void clear() : 移除此集合中的所有元素
? boolean removeAll(Collection<?> c) : 移除此集合中那些也包含在指定集合中的元素（求集合的差集）
? boolean retainAll(Collection<?> c) : 仅保留此集合中那些也包含在指定集合中的元素（求集合的交集）
d) 将集合转换成Object类型的对象数组
? Object[] toArray() : 返回包含此集合中所有元素的数组
? <T> T[] toArray(T[] a) : 返回包含此集合中所有元素的数组；返回数组的运行时类型与指定数组的运行时类型相同
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来构造ls2List<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);}}}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;}} 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; } 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()); } } } 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(); } }