一、List框架图
collection08.jpg
总结
接口：
Iterable接口：支持Iterator，定义Iterator获取方法，支持foreach-loop
Collection接口：集合接口类，定义了基本的添加(add)、删除(remove)、访问(Iterator)接口，支持Iterable
List接口：有序列表接口类，扩展自Collection，支持索引操作（add(index, element)、get(index)、indexOf(element)）
Queue接口：队列接口类，扩展自Collection，先进先出，支持操作（offer()、poll()、element()、peek()）
Duque接口：双端队列接口类，扩展自Queue，支持头尾两端操作
AccessRandom接口：支持随机随机访问，无API
抽象类：
AbstractCollection，implement Collection，实现了Colletion基本方法，减少Collection接口实现难度
AbstractList，extends AbstractCollection，implement List，实现了List基本方法，子类只需实现get()、set()、remove()、size()方法。
AbstractSequentialList，extends AbstractList，将index相关方法使用Iterator实现，减少对于index的依赖，将“sequential access”顺序存储简单化。实现了“链表中，根据index索引值操作链表的全部函数”
实现类：
ArrayList是一个数组队列，相当于动态数组。由数组实现，随机访问效率高，随机插入、随机删除效率低。
Vector是一个矢量队列，相当于动态数组，由数组实现。与ArrayList类似，但是Vector是线程安全的，ArrayList是非线程安全的。
Stack是栈，继承于Vector。有着先进先出（FIFO）的特点。
LinkedList是一个双向链表，也可以被当作栈、队列、或者双端队列进行操作。由链表实现，随机访问效率低，但随机插入、随机删除效率高。
二、使用场景
可以从两个方面进行考虑：
(01) 性能需求
对于需要快速插入，删除元素，应该使用LinkedList。
对于需要快速随机访问元素，应该使用ArrayList。
(02) 线程环境
如果List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。
如果ist可能同时被多个线程操作”，此时应该使用同步的类(如Vector)。
三、性能差异及原因
List可以分为两类，基于数组的ArrayList、Vector、Stack和基于链表的LinkedList，我们来比较下这两种实现方式对于性能的影响
1. 随机添加
ArrayList:
-
检查容量
-
扩容（可能）
-
移动index后的所有元素
System.arraycopy(elementData, index, elementData, index + 1, size - index) -
设置index位置元素
LinkedList：
- 根据index，从头or尾遍历链表，直到到达指定的index
- 添加节点
结论：随机添加／删除时，LinkedList优于ArrayList
2. 随机访问
ArrayList:
- 判断size
- 获取元素
- 返回元素
LinkedList：
- 判断size
- 根据index，从头or尾遍历链表，直到到达指定的index
- 获取元素内容
- 返回元素
结论：随机访问时，ArrayList由于LinkedList
四、Vector和ArrayList比较
相同点：
- 都是List
- 都是通过数组实现，本质上都是动态数组
- 都实现了RandomAccess接口
- 默认数组容量相同，都为10
- 都支持Iterator和ListIterator
不同点：
- 线程安全性不同，ArrayList是非线程安全，而Vector是线程安全的
- 对序列化支持不同
- 容量增加方式不同，Vector中有capacityIncrement
- 对Enumeration的支持不同，Vector支持通过Enumeration去遍历，而List不支持
附1、衍生问题
1. 数组在内存中是怎么存储的？
略
2. foreach实现原理
根据对象不同有不同的逻辑：
- 对于list编译器会调用Iterable接口的 iterator方法来循环遍历数组的元素，iterator方法中是调用Iterator接口的的 next()和hasNext（）方法来做循环遍历。
- 对于数组，就是转化为对数组中的每一个元素的循环引用
4. Collections.synchronizedList实现原理
Collections.synchronizedList()通过重写相关方法，添加一个互斥量mutex，方法调用之前都要尝试先去获取mutex
3. toArray方法抛出java.lang.ClassCastException
这个是个向下转型失败问题。在Java中容许向上转型和向下转型，转型结果根据java虚拟中的对象的类型的来决定的，Java虚拟机中保留了所有对象的类型，数组也是一个对象。
toArrays方法
@Override public Object[] toArray() {
int s = size;
Object[] result = new Object[s];
System.arraycopy(array, 0, result, 0, s);
return result;
}
新创建了一个Object[]对象，类型是[Ljava.lang.Object，把[Ljava.lang.Object转换成[Ljava.lang.String是显然不可能的事情，因此Java虚拟机中只保存了这是一个Object数组，并不能保证其中每个元素都是String类型的，所以这个转型不能成功。数组里面的元素只是对象的引用，并不存储具体的元素，所以数组元素的类型还是保存在Java虚拟机中的。
根据上面的解释，我们可以把这个问题归纳到下面这个模型。
Object objs[]=new Object[10];
String strs[]=(String[])objs;
这样子和刚才上面编译错误是一样的，如果我们把修改一下这个代码，如下：
String strs[]=new String[10];
Object objs[]=strs;
这样子就可以编译通过了，所以这个问题我们可以归结为一个Java转型规则的一个问题。
详见《Java数组对范型的支持问题》http://blog.csdn.net/ithomer/article/details/7532935
5. fast-fail概念和实现方式
概念：
fast-fail是一种错误检测机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。
例如：当一个线程A使用Iterator遍历某集合的过程中，该集合的内容被其他线程改变，那么A线程访问集合时就会抛出ConcurrentModificationException异常，产生fail-fast事件。
原理：
ArrayList中持有一个modCount对象，记录该ArrayList修改次数。ArrayList中的Iterator中持有一个expectedModCount对象。通过比较两者是否相等来确定是否有其他对象修改了集合。在Iterator初始化时将expectedModCount = modCount，在对集合进行访问时，会首先进行modCount != expectedModCount判断，两者不相等时抛出ConcurrentModificationException异常，在操作结束后，更新expectedModCount = modCount。
这是modCoun他的官方说明：
The number of times this list has been structurally modified. Structural modifications are those that change the size of the list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.
两类操作会影响到modCount:
- 修改数组大小的操作，比如add()、remove()等，注意trimToSize()、ensureCapacity()也会影响。
- 影响数组中对象结构的操作，比如replace()、sort()等。
注意点：
只能用于检测错误，因为JDK并不保证fail-fast机制一定会发生。若在多线程环境使用fail-fast机制的集合，建议使用“java.util.concurrent包下的类”去取代“java.util包下的类”。
6. RandomAccess有什么用
List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
将操作随机访问列表的最佳算法（如 ArrayList ）应用到连续访问列表（如 LinkedList ）时，可产生二次项的行为。如果将某个算法应用到连续访问列表，那么在应用可能提供较差性能的算法前，鼓励使用一般的列表算法检查给定列表是否为此接口的一个 instanceof ，如果需要保证可接受的性能，还可以更改其行为。
现在已经认识到，随机和连续访问之间的区别通常是模糊的。例如，如果列表很大时，某些 List 实现提供渐进的线性访问时间，但实际上是固定的访问时间。这样的 List 实现通常应该实现此接口。
支持快速随机访问，即是支持通过下标序号进行快速访问（于是否支持get(index)不同）。RandomAccess用于标记List是否支持快速随机访问。此接口的目的是容许实现类更改访问逻辑，提供更好的顺序／随机访问性能。
在使用过程中，可以使用if(list instanceof RamdomAccess)判断List属于RandomAccess或者是SequenceAccess。两者适合不一样的遍历算法：
RandomAccess适合：
for (int i=0, i<list.size(); i++){
list.get(i);
}
SequenceAccess适合：
for (Iterator i=list.iterator(); i.hasNext(); ){
i.next();
}
7. 怎么实现不可修改的列表？
继承AbstractList，仅实现size()和get()方法。
8. access方式
目前共遇到了两种access方式
- sequential access 顺序存取
- random access 随机存取
9. CopyOnWriteArrayList实现原理
在写操作时，copy一份数组，写完成后替换原有数组
10.List的toString样式
[value1, value2, value3, value4]
11.“有序”的概念
有序可以表示两种含义：
一是指可排序
二是指每个元素都有一个对应的下标，即对某个元素在集合中的位置进行指定。
List的有序是指第二种，每个元素都有一个对应的下标，即对某个元素在集合中的位置进行指定。
TreeMap／TreeSet的有序是指第一种可排序。
附2. 基本数据接口接口介绍
Queue(FIFO (first-in-first-out))
offer(E): boolean
remove(): E
poll(): E
element(): E
peek(): E
Dueue(double ended queue) extends Queue
addFirst(E): void
addLast(E): void
offerFirst(E): boolean
offerLast(E): boolean
removeFirst(): E
removeLast(): E
pollFirst(): E
pollLast(): E
getFirst(): E
getLast(): E
peekFirst(): E
peekLast(): E
removeFirstOccurrence(Object): boolean
removeLastOccurrence(Object): boolean
网友评论