Java集合·06·List总结

一、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:

1. 检查容量

2. 扩容（可能）

3. 移动index后的所有元素

   System.arraycopy(elementData, index, elementData, index + 1, size - index)
   

4. 设置index位置元素

LinkedList：

1. 根据index，从头or尾遍历链表，直到到达指定的index
2. 添加节点

结论：随机添加／删除时，LinkedList优于ArrayList

2. 随机访问

ArrayList:

1. 判断size
2. 获取元素
3. 返回元素

LinkedList：

1. 判断size
2. 根据index，从头or尾遍历链表，直到到达指定的index
3. 获取元素内容
4. 返回元素

结论：随机访问时，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