第 1 部分 List 概括
先回顾一下 List 的框架图
(01) List 是一个接口, 它继承于 Collection 的接口. 它代表着有序的队列.
(02) AbstractList 是一个抽象类, 它继承于 AbstractCollection.AbstractList 实现 List 接口中除 size(),get(int location)之外的函数.
(03) AbstractSequentialList 是一个抽象类, 它继承于 AbstractList.AbstractSequentialList 实现了 "链表中, 根据 index 索引值操作链表的全部函数".
(04) ArrayList, LinkedList, Vector, Stack 是 List 的 4 个实现类.
ArrayList 是一个数组队列, 相当于动态数组. 它由数组实现, 随机访问效率高, 随机插入, 随机删除效率低.
LinkedList 是一个双向链表. 它也可以被当作堆栈, 队列或双端队列进行操作. LinkedList 随机访问效率低, 但随机插入, 随机删除效率低.
Vector 是矢量队列, 和 ArrayList 一样, 它也是一个动态数组, 由数组实现. 但是 ArrayList 是非线程安全的, 而 Vector 是线程安全的.
Stack 是栈, 它继承于 Vector. 它的特性是: 先进后出(FILO, First In Last Out).
第 2 部分 List 使用场景
学东西的最终目的是为了能够理解, 使用它. 下面先概括的说明一下各个 List 的使用场景, 后面再分析原因.
如果涉及到 "栈","队列","链表" 等操作, 应该考虑用 List, 具体的选择哪个 List, 根据下面的标准来取舍.
(01) 对于需要快速插入, 删除元素, 应该使用 LinkedList.
(02) 对于需要快速随机访问元素, 应该使用 ArrayList.
(03) 对于 "单线程环境" 或者 "多线程环境, 但 List 仅仅只会被单个线程操作", 此时应该使用非同步的类(如 ArrayList).
对于 "多线程环境, 且 List 可能同时被多个线程操作", 此时, 应该使用同步的类(如 Vector).
通过下面的测试程序, 我们来验证上面的 (01) 和(02)结论. 参考代码如下:
View Code
运行结果如下:
- Stack : insert 100000 elements into the 1st position use time:1640 ms
- Vector : insert 100000 elements into the 1st position use time:1607 ms
- LinkedList : insert 100000 elements into the 1st position use time:29 ms
- ArrayList : insert 100000 elements into the 1st position use time:1617 ms
- Stack : read 100000 elements by position use time:9 ms
- Vector : read 100000 elements by position use time:6 ms
- LinkedList : read 100000 elements by position use time:10809 ms
- ArrayList : read 100000 elements by position use time:5 ms
- Stack : delete 100000 elements from the 1st position use time:1916 ms
- Vector : delete 100000 elements from the 1st position use time:1910 ms
- LinkedList : delete 100000 elements from the 1st position use time:15 ms
- ArrayList : delete 100000 elements from the 1st position use time:1909 ms
从中, 我们可以发现:
插入 10 万个元素, LinkedList 所花时间最短: 29ms.
删除 10 万个元素, LinkedList 所花时间最短: 15ms.
遍历 10 万个元素, LinkedList 所花时间最长: 10809 ms; 而 ArrayList,Stack 和 Vector 则相差不多, 都只用了几秒.
考虑到 Vector 是支持同步的, 而 Stack 又是继承于 Vector 的; 因此, 得出结论:
(01) 对于需要快速插入, 删除元素, 应该使用 LinkedList.
(02) 对于需要快速随机访问元素, 应该使用 ArrayList.
(03) 对于 "单线程环境" 或者 "多线程环境, 但 List 仅仅只会被单个线程操作", 此时应该使用非同步的类.
第 3 部分 LinkedList 和 ArrayList 性能差异分析
下面我们看看为什么 LinkedList 中插入元素很快, 而 ArrayList 中插入元素很慢!
LinkedList.java 中向指定位置插入元素的代码如下:
- // 在 index 前添加节点, 且节点的值为 element
- public void add(int index, E element) {
- addBefore(element, (index==size ? header : entry(index)));
- }
- // 获取双向链表中指定位置的节点
- private Entry<E> entry(int index) {
- if (index <0 || index>= size)
- throw new IndexOutOfBoundsException("Index:"+index+
- ", Size:"+size);
- Entry<E> e = header;
- // 获取 index 处的节点.
- // 若 index <双向链表长度的 1/2, 则从前向后查找;
- // 否则, 从后向前查找.
- 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;
- }
- return e;
- }
- // 将节点 (节点数据是 e) 添加到 entry 节点之前.
- private Entry<E> addBefore(E e, Entry<E> entry) {
- // 新建节点 newEntry, 将 newEntry 插入到节点 e 之前; 并且设置 newEntry 的数据是 e
- Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
- // 插入 newEntry 到链表中
- newEntry.previous.next = newEntry;
- newEntry.next.previous = newEntry;
- size++;
- modCount++;
- return newEntry;
- }
从中, 我们可以看出: 通过 add(int index, E element)向 LinkedList 插入元素时. 先是在双向链表中找到要插入节点的位置 index; 找到之后, 再插入一个新节点.
双向链表查找 index 位置的节点时, 有一个加速动作: 若 index <双向链表长度的 1/2, 则从前向后查找; 否则, 从后向前查找.
接着, 我们看看 ArrayList.java 中向指定位置插入元素的代码. 如下:
- // 将 e 添加到 ArrayList 的指定位置
- public void add(int index, E element) {
- if (index> size || index <0)
- throw new IndexOutOfBoundsException(
- "Index:"+index+", Size:"+size);
- ensureCapacity(size+1); // Increments modCount!!
- System.arraycopy(elementData, index, elementData, index + 1,
- size - index);
- elementData[index] = element;
- size++;
- }
ensureCapacity(size+1) 的作用是 "确认 ArrayList 的容量, 若容量不够, 则增加容量."
真正耗时的操作是 System.arraycopy(elementData, index, elementData, index + 1, size - index);
Sun JDK 包的 java/lang/System.java 中的 arraycopy()声明如下:
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
arraycopy()是个 JNI 函数, 它是在 JVM 中实现的. sunJDK 中看不到源码, 不过可以在 OpenJDK 包中看到的源码. 网上有对 arraycopy()的分析说明, 请参考: System.arraycopy 源码分析
实际上, 我们只需要了解: System.arraycopy(elementData, index, elementData, index + 1, size - index); 会移动 index 之后所有元素即可. 这就意味着, ArrayList 的 add(int index, E element)函数, 会引起 index 之后所有元素的改变!
通过上面的分析, 我们就能理解为什么 LinkedList 中插入元素很快, 而 ArrayList 中插入元素很慢.
"删除元素" 与 "插入元素" 的原理类似, 这里就不再过多说明.
接下来, 我们看看 "为什么 LinkedList 中随机访问很慢, 而 ArrayList 中随机访问很快".
先看看 LinkedList 随机访问的代码
- // 返回 LinkedList 指定位置的元素
- public E get(int index) {
- return entry(index).element;
- }
- // 获取双向链表中指定位置的节点
- private Entry<E> entry(int index) {
- if (index <0 || index>= size)
- throw new IndexOutOfBoundsException("Index:"+index+
- ", Size:"+size);
- Entry<E> e = header;
- // 获取 index 处的节点.
- // 若 index <双向链表长度的 1/2, 则从前先后查找;
- // 否则, 从后向前查找.
- 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;
- }
- return e;
- }
从中, 我们可以看出: 通过 get(int index)获取 LinkedList 第 index 个元素时. 先是在双向链表中找到要 index 位置的元素; 找到之后再返回.
双向链表查找 index 位置的节点时, 有一个加速动作: 若 index <双向链表长度的 1/2, 则从前向后查找; 否则, 从后向前查找.
下面看看 ArrayList 随机访问的代码
- // 获取 index 位置的元素值
- public E get(int index) {
- RangeCheck(index);
- return (E) elementData[index];
- }
- private void RangeCheck(int index) {
- if (index>= size)
- throw new IndexOutOfBoundsException(
- "Index:"+index+", Size:"+size);
- }
从中, 我们可以看出: 通过 get(int index)获取 ArrayList 第 index 个元素时. 直接返回数组中 index 位置的元素, 而不需要像 LinkedList 一样进行查找.
第 4 部分 Vector 和 ArrayList 比较
相同之处
1 它们都是 List
它们都继承于 AbstractList, 并且实现 List 接口.
ArrayList 和 Vector 的类定义如下:
- // ArrayList 的定义
- public class ArrayList<E> extends AbstractList<E>
- implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- // Vector 的定义
- public class Vector<E> extends AbstractList<E>
- implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
- }
2 它们都实现了 RandomAccess 和 Cloneable 接口
实现 RandomAccess 接口, 意味着它们都支持快速随机访问;
实现 Cloneable 接口, 意味着它们能克隆自己.
3 它们都是通过数组实现的, 本质上都是动态数组
ArrayList.java 中定义数组 elementData 用于保存元素
- // 保存 ArrayList 中数据的数组
- private transient Object[] elementData;
Vector.java 中也定义了数组 elementData 用于保存元素
- // 保存 Vector 中数据的数组
- protected Object[] elementData;
4 它们的默认数组容量是 10
若创建 ArrayList 或 Vector 时, 没指定容量大小; 则使用默认容量大小 10.
ArrayList 的默认构造函数如下:
- // ArrayList 构造函数. 默认容量是 10.
- public ArrayList() {
- this(10);
- }
Vector 的默认构造函数如下:
- // Vector 构造函数. 默认容量是 10.
- public Vector() {
- this(10);
- }
5 它们都支持 Iterator 和 listIterator 遍历
它们都继承于 AbstractList, 而 AbstractList 中分别实现了 "iterator()接口返回 Iterator 迭代器" 和 "listIterator()返回 ListIterator 迭代器".
不同之处
1 线程安全性不一样
ArrayList 是非线程安全;
而 Vector 是线程安全的, 它的函数都是 synchronized 的, 即都是支持同步的.
ArrayList 适用于单线程, Vector 适用于多线程.
2 对序列化支持不同
ArrayList 支持序列化, 而 Vector 不支持; 即 ArrayList 有实现 java.io.Serializable 接口, 而 Vector 没有实现该接口.
3 构造函数个数不同
ArrayList 有 3 个构造函数, 而 Vector 有 4 个构造函数. Vector 除了包括和 ArrayList 类似的 3 个构造函数之外, 另外的一个构造函数可以指定容量增加系数.
ArrayList 的构造函数如下:
- // 默认构造函数
- ArrayList()
- // capacity 是 ArrayList 的默认容量大小. 当由于增加数据导致容量不足时, 容量会添加上一次容量大小的一半.
- ArrayList(int capacity)
- // 创建一个包含 collection 的 ArrayList
- ArrayList(Collection<? extends E> collection)
Vector 的构造函数如下:
- // 默认构造函数
- Vector()
- // capacity 是 Vector 的默认容量大小. 当由于增加数据导致容量增加时, 每次容量会增加一倍.
- Vector(int capacity)
- // 创建一个包含 collection 的 Vector
- Vector(Collection<? extends E> collection)
- // capacity 是 Vector 的默认容量大小, capacityIncrement 是每次 Vector 容量增加时的增量值.
- Vector(int capacity, int capacityIncrement)
4 容量增加方式不同
逐个添加元素时, 若 ArrayList 容量不足时,"新的容量"="(原始容量 x3)/2 + 1".
而 Vector 的容量增长与 "增长系数有关", 若指定了 "增长系数", 且 "增长系数有效(即, 大于 0)"; 那么, 每次容量不足时,"新的容量"="原始容量 + 增长系数". 若增长系数无效(即, 小于 / 等于 0), 则 "新的容量"="原始容量 x 2".
ArrayList 中容量增长的主要函数如下:
- public void ensureCapacity(int minCapacity) {
- // 将 "修改统计数"+1
- modCount++;
- int oldCapacity = elementData.length;
- // 若当前容量不足以容纳当前的元素个数, 设置 新的容量 ="(原始容量 x3)/2 + 1"
- if (minCapacity> oldCapacity) {
- Object oldData[] = elementData;
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity <minCapacity)
- newCapacity = minCapacity;
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
- }
Vector 中容量增长的主要函数如下:
- private void ensureCapacityHelper(int minCapacity) {
- int oldCapacity = elementData.length;
- // 当 Vector 的容量不足以容纳当前的全部元素, 增加容量大小.
- // 若 容量增量系数 > 0(即 capacityIncrement>0), 则将容量增大当 capacityIncrement
- // 否则, 将容量增大一倍.
- if (minCapacity> oldCapacity) {
- Object[] oldData = elementData;
- int newCapacity = (capacityIncrement> 0) ?
- (oldCapacity + capacityIncrement) : (oldCapacity * 2);
- if (newCapacity <minCapacity) {
- newCapacity = minCapacity;
- }
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
- }
5 对 Enumeration 的支持不同. Vector 支持通过 Enumeration 去遍历, 而 List 不支持
Vector 中实现 Enumeration 的代码如下:
- public Enumeration<E> elements() {
- // 通过匿名类实现 Enumeration
- return new Enumeration<E>() {
- int count = 0;
- // 是否存在下一个元素
- public boolean hasMoreElements() {
- return count < elementCount;
- }
- // 获取下一个元素
- public E nextElement() {
- synchronized (Vector.this) {
- if (count < elementCount) {
- return (E)elementData[count++];
- }
- }
- throw new NoSuchElementException("Vector Enumeration");
- }
- };
- }
来源: http://www.bubuko.com/infodetail-3039454.html