共同点:都是线性集合
ArrayList
ArrayList 底层是基于数组实现的,并且实现了动态扩容(当需要添加新元素时,如果 elementData 数组已满,则会自动扩容,新的容量将是原来的 1.5 倍),来看一下 ArrayList 的部分源码(PS:以下代码均来自Java8,不同版本可能存在细微差距)。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10; // 默认容量
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // 存储元素的数组,数组类型:Object
private int size; // 列表的大小,即列表中元素的个数
ArrayList 还实现了 RandomAccess 接口,这是一个标记接口:
public interface RandomAccess {
}
内部是空的,标记“实现了这个接口的类支持快速(通常是固定时间)随机访问”。快速随机访问是什么意思呢?就是说不需要遍历,就可以通过下标(索引)直接访问到内存地址。而 LinkedList 没有实现该接口,表示它不支持高效的随机访问,需要通过遍历来访问元素。
ArrayList 还实现了 Cloneable 接口,并且重写了 Object 类的 clone() 方法,但只是浅拷贝,还是要根据需求使用。
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
ArrayList 还实现了 Serializable 接口,支持序列化:
但是关键字段 elementData 使用了 transient 关键字修饰,这个关键字的作用是,让它修饰的字段不被序列化。
看到这里是不是心里出现了很多问好?
我们这样来看:elementData 是一个数组,数组是定长的,如果一个新创建的ArrayList,并且我们只往里添加了2个元素,如果我们默认序列化就会多序列化8个空的内存空间,我们再反序列化出来的时候需要更大的空间去接收这个数组。如下例子中可以更好的反应该问题,可能出现很大的bug:
public class Main {
public static void main(String[] args) throws Exception {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
list.add(i);
}
System.out.println(list.size());
list.clear();
Class<? extends List> listClass = list.getClass();
Field field = listClass.getDeclaredField("elementData");
field.setAccessible(true);
Object[] o = (Object[]) field.get(list);
System.out.println(o.length);
}
}
输出如下:
100000
106710
于是,ArrayList 做了一个愉快而又聪明的决定,内部提供了两个私有方法 writeObject 和 readObject 来完成序列化和反序列化。
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
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, 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();
}
}
}
从源码中可以看出序列化和反序列化时,只保存了list的大小和所有元素。
还需要注意 ArrayList 在序列化时,不允许有并发的修改操作。
Vector/Stack
Vector 也是基于数组实现的,但是是线程安全的,其他和 ArrayList 基本没有区别,源码注释中有句话也可以看出
{@code Vector} is synchronized. If a thread-safe
implementation is not needed, it is recommended to use {@link
ArrayList} in place of {@code Vector}.
// Vector的序列化和反序列化的方法与ArrayList略有差异
private void readObject(ObjectInputStream in)
throws IOException, ClassNotFoundException {
ObjectInputStream.GetField gfields = in.readFields();
int count = gfields.get("elementCount", 0);
Object[] data = (Object[])gfields.get("elementData", null);
if (count < 0 || data == null || count > data.length) {
throw new StreamCorruptedException("Inconsistent vector internals");
}
elementCount = count;
elementData = data.clone();
}
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
final java.io.ObjectOutputStream.PutField fields = s.putFields();
final Object[] data;
synchronized (this) {
fields.put("capacityIncrement", capacityIncrement);
fields.put("elementCount", elementCount);
data = elementData.clone();
}
fields.put("elementData", data);
s.writeFields();
}
Stack 继承了 Vector,同时Stack添加了 push/pop/peek 等方法,实现了后进先出(LIFO)。
LinkedList
LinkedList 是一个继承自 AbstractSequentialList 的双向链表,同时实现了 Deque 双向队列接口,因此它也可以被当作堆栈、队列或双向队列进行操作。
部分源码
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0; // 表示链表中的节点个数
transient LinkedList.Node<E> first; // 链表中的第一个节点
transient LinkedList.Node<E> last; // 链表中的最后一个节点
可以看到 LinkedList 同样实现了 Serializable 接口,支持序列化。但是上面源码中 LinkedList 的所有属性都是 transient 修饰的,这又让我们想到了 ArrayList 的序列化实现,果然找到了writeObject和readObject方法的实现:
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (LinkedList.Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}
仔细琢磨,发现不仅尽可能少的占用存储空间,反序列化时还巧妙的恢复了原来的顺序。