這三個集合類型,其底層都是數組實作的。讨論集合關注的問題:
- 底層資料結構
- 增删改查方式
- 初始容量,擴容方式,擴容時機
- 線程安全與否
- 是否允許空,是否允許重複,是否有序
ArrayList
ArrayList是實作List接口的動态數組。實作了所有可選清單操作,并允許包括 null 在内的所有元素。除了實作 List 接口外,此類還提供一些方法來操作内部用來存儲清單的數組的大小。
每個數組都有一個容量,由一個數組維護,初始的容量為10(在第一個元素添加進來時擴容),也可以在初始化new操作時給定。ArrayList繼承自AbstractList,實作了List,RandomAccess,Cloneable,.Serializable接口。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
每次添加新的元素時:先判斷合法性,會判斷數組的長度,當超過目前的容量大小時,則會擴容一個新的1.5倍的數組,使用Arrays.copyOf将對象複制到新數組中。内部數組elementData使用transient修飾,即進行序列化時,隻複制有值的内容,可以節省空間。還可以插入到制定的位置下,同樣操作,使用System.copyOf操作,Arrays.copyOf最終調用的也是該方法。删除也會拷貝,清空則是置為null。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//擴容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
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);
}
ArrayList的所有方法都沒有加鎖或同步控制,是以是非線性安全的。可以在建立時,使用Collection.synchronizedList使其對外線程同步。内置一個modCount進行控制,對内部數組進行了增删改動後,該值會++,後續使用疊代器時判斷與expectedModCount不相同則抛出異常。“Fast-Fail機制”
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
Vector
Vector是實作了List的動态可變集合。Vector同樣繼承自AbstractList,實作了List,RandomAccess,Cloneable,.Serializable接口。基本和ArrayList類似,内部也是一個對象數組elementData維護,不過沒有transient,意味着序列化全部内容。
初始化,預設直接為10,不需要第一次加載。另外,除了初始化大小外,還可以制定增長的寬度。
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);
}
/**
* Constructs an empty vector so that its internal data array
* has size {@code 10} and its standard capacity increment is
* zero.
*/
public Vector() {
this(10);
}
新增元素時,同樣會對modCount++,同時判斷目前的大小,加1時超過容量則進行擴容。如果設定了擴容增量大小則按該值,否則就擴容成原來的兩倍,同樣是使用了System.copyOf進行操作。擴容完畢後進行容量的更新。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
Vector中所有對資料進行修改的方法都加了synchronized修飾,來保證線程安全性。
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; // Let gc do its work
return oldValue;
}
Stack
Stack是一種棧結構,在Java中其隻繼承自Vector。棧很常見,就是一種先進後出,或者說後進先出的資料結構。Stack使用了Vector中的數組維護資料結構,在Vector外隻實作了pop,push,peek,empty,search5個另外的方法。
同樣地,這些方法基本都是使用synchronized修飾,是以Stack是線性安全的。
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
/* @return the object at the top of this stack (the last item
* of the <tt>Vector</tt> object).
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
小結:
總的來說,ArrayList實作了RandomAccess,是以随機通路快速;但是在進行插入或删除資料的時候,要使用System.copyOf進行大量的資料拷貝,浪費資源。且ArrayList線性不安全。
Vector同樣可以随機讀取,和ArrayList類似在增删資料時涉及大量拷貝,但是優點是線性安全的。
Stack用于一些特定的資料結構需求中。
參考文章