List浅析

java.util.List是java集合框架的基础接口之一，使用频率非常高，如下主要从数据结构和应用场景做简单分析，仅供交流和参考。

 

1.Vector

Jdk遗留类，现在使用很少，但了解下最初jdk集合类的实现方法也是不错的。添加、删除方法如下所示，都是通过synchronized关键字保证线程安全性。

public synchronized void addElement(E obj) {
	modCount++;
	ensureCapacityHelper(elementCount + 1);
	elementData[elementCount++] = obj;
}

public synchronized boolean removeElement(Object obj) {
	modCount++;
	int i = indexOf(obj);
	if (i >= 0) {
	    removeElementAt(i);
	    return true;
	}
	return false;
}

 

2.ArrayList数据结构是数组，非线程安全。

/**
* The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer.
 */
 private transient Object[] elementData;

 

3.LinkedList数据结构是双向循环链表，非线程安全。

实现了双端队列方法，添加元素时，可以添加到list的头部或尾部。

public void addFirst(E e) {
        addBefore(e, header.next);
}
public void addLast(E e) {
	addBefore(e, header);
}

addBefore(E e, Entry<E> entry)实现了将e添加到entry元素之前，addFirst(e)将元素添加到header之后，也就是list的头部。addLast(e)将e添加到header之前，因为LinkedList是循环链表，header之前就是List尾部。

 

4.CopyOnWriteArrayList

CopyOnWriteArrayList是java.util.ArrayList的一个线程安全的变体。适用于读远远大于写的场景。

 

1)CopyOnWriteArrayList实现了List接口。

 

2)CopyOnWriteArrayList包含了成员变量lock。通过lock，实现了对CopyOnWriteArrayList的互斥访问。

/** The lock protecting all mutators */
transientfinal ReentrantLock lock = new ReentrantLock();

 

 3)CopyOnWriteArrayList包含了成员array数组，这说明CopyOnWriteArrayList本质上通过数组实现的。 

CopyOnWrite的缺点

CopyOnWrite容器有很多优点，但是同时也存在两个问题，即内存占用问题和数据一致性问题。所以在开发的时候需要注意一下。内存占用可以从使用场景来规避，读多写少的场景比较适合选择CopyOnWriteArrayList。数据一致性问题是网上看到的一种错误分析，后面做了浅析。

 

内存占用

因为CopyOnWrite的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象（有两份对象内存，新数组生成后就使用新数组了，java代码中没有删除旧数组的操作，可能是依靠jvm GC来回收）。如果这些对象占用的内存比较大，比如说200M左右，那么再写入100M数据进去，内存就会占用300M，那么这个时候很有可能造成频繁的Yong GC和Full GC。

 

数据一致性 

从代码来看，通过ReentrantLock保证了线程的安全性，显示锁在内存可见性上和Synchronized是一致的，所以，不存在数据一致性的问题。

 

JDK 注释：

 

A thread-safe variant of java.util.ArrayList in which all mutativeoperations (add， set， and so on) are implemented bymaking a fresh copy of the underlying array.

This is ordinarily too costly， but may be more efficientthan alternatives when traversal operations vastly outnumbermutations， and is useful when you cannot or don't want tosynchronize traversals， yet need to preclude interference amongconcurrent threads.  The "snapshot" style iterator method uses areference to the state of the array at the point that the iteratorwas created. This array never changes during the lifetime of the iterator， so interference is impossible and the iterator isguaranteed not to throw ConcurrentModificationException.

The iterator will not reflect additions， removals， or changes tothe list since the iterator was created.  Element-changingoperations on iterators themselves (remove， set， and add) are not supported. These methods throw UnsupportedOperationException.

All elements are permitted， including null.