ArrayList 和 Vector 底层分析

ArrayList

ArrayList 实现于 ListRandomAccess 接口。可以插入空数据,也支持随机访问。

ArrayList相当于动态数组,最重要的两个属性分别是: elementData[] 数组,和 size 大小。

在调用 add() 方法时:


public boolean add(E e) {

ensureCapacityInternal(size + 1); // 校验扩容

elementData[size++] = e; // 插值放尾部, size+1

return true;

}

如果是调用 add(index,e) 在指定位置添加的话:


public void add(int index, E element) {

rangeCheckForAdd(index);



ensureCapacityInternal(size + 1); // 校验扩容

// 数组内容向后移动

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); // 容量在原来的基础上再增加1/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);

}

序列化

由于 ArrayList 是基于动态数组实现的,所以并不是所有的空间都被使用。因此使用了 transient 修饰,可以防止被自动序列化。


transient Object[] elementData;

因此 ArrayList 自定义了序列化与反序列化:


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();

}

}



private void readObject(java.io.ObjectInputStream s)

throws java.io.IOException, ClassNotFoundException {

elementData = EMPTY_ELEMENTDATA;



// Read in size, and any hidden stuff

s.defaultReadObject();



// Read in capacity

s.readInt(); // ignored



if (size > 0) {

// be like clone(), allocate array based upon size not capacity

ensureCapacityInternal(size);



Object[] a = elementData;

// Read in all elements in the proper order.

for (int i=0; i<size; i++) {

a[i] = s.readObject();

}

}

}

当对象中自定义了 writeObject 和 readObject 方法时,JVM 会调用这两个自定义方法来实现序列化与反序列化。

Vector

Vector 也是实现于 List 接口,底层数据结构和 ArrayList 类似,也是一个动态数组存放数据。不过是在 add() 方法的时候使用 synchronized 进行同步写数据,但是开销较大,所以 Vector 是一个同步容器并不是一个并发容器。


public synchronized boolean add(E e) {

modCount++;

ensureCapacityHelper(elementCount + 1);

elementData[elementCount++] = e;

return true;

}





public void add(int index, E element) {

insertElementAt(element, index);

}



public synchronized void insertElementAt(E obj, int index) {

modCount++;

if (index > elementCount) {

throw new ArrayIndexOutOfBoundsException(index

+ " > " + elementCount);

}

ensureCapacityHelper(elementCount + 1);

System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);

elementData[index] = obj;

elementCount++;

}