Vector分析:
主要特性:有序,可随机访问,可变长,可重复,线程安全等。
其结构图:
其基本属性有:
//存放元素的数组
protected Object[] elementData;
//元素个数
protected int elementCount;
//容量扩容指标,默认以2倍增长
protected int capacityIncrement;
从其构造函数中可以看出,Vector默认容量为10,capacityIncrement默认设为0(<=0时就以2倍扩容):
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector() {
this(10);
}
看几个比较重要的方法,add(), remove():
add方法:
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1); //扩容检测
elementData[elementCount++] = e; //添加,改变引用
return true;
}
private void ensureCapacityHelper(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//默认2*oldCapacity,
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);//拷贝新数组
}
remove方法,可见删除操作要做复制操作:
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1; //被删除元素后面元素个数
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved); //将被删除元素后面的元素往前挪
elementData[--elementCount] = null; //这点很重要,让gc能够回收无引用对象,防止"内存泄漏"
return oldValue;
}
Vector实现是比较简单明了的,其大部分方法都synchronized同步了,因此线程安全。
ArrayList分析:
其主要特性:有序,可随机访问,可变长,可重复,非线程安全等。
其结构图:
其主要属性:
//默认容量
private static final int DEFAULT_CAPACITY = 10;
//空标志
private static final Object[] EMPTY_ELEMENTDATA = {};
//存放元素的数组
private transient Object[] elementData;
//元素个数
private int size;
其构造方法有(不能设置ArrayList的扩容机制):
public ArrayList(int initialCapacity) { //可指定初始容量
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA; //空数组
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
看看其主要方法add, remove:
public boolean add(E e) {
ensureCapacityInternal(size + 1); //扩容
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //扩容为原来的3/2倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
remove方法, 基本同上面Vector。
LinkedList分析:
其主要特性:可变长,可重复,不可随机访问,非线程安全等。
LinkedList不同于Vector,ArrayList(由数组实现),基于双链表实现:
其结构图:
其主要特性:可重复,不可随机访问,非线程安全。
其主要属性:
//长度
transient int size = 0;
//头
transient Node<E> first;
//尾
transient Node<E> last;
其将我们的元素抽象为Node类:
private static class Node<E> {
E item; //元素对象
Node<E> next; //后节点引用
Node<E> prev; //前节点引用
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
还是看看其主要方法, add,remove:
add方法:
public boolean add(E e) {
linkLast(e); //接到尾上
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) //空链表
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
remove方法, 主要由unlink方法实现:
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) { //头节点
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) { //尾节点
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
上面就讲了有关List集合的3个实现类,对于这三个类我们该如何选取,就的根据具体情况:
对于Vector和ArrayList, 需要同步时,则可用Vector, 或Collections.synchronizedList(),不需同步则用ArrayList, 对于这三种做了些性能测试:
- Vector与SynchronizedList并发插入性能:5个线程,每个线程插入100w元素,Vector要更快。
- ArrayList与LinkedList插入性能: 当数据量比较小时,LinkedList更快(前者由于复制操作耗时),当数据量比较大时(如>=50W), ArrayList更快(后者由于遍历操作耗时)。
不吝指正。