Java集合源码解析-ArrayList

从今天开始，会用一段时间对Java集合框架中的一些常用数据结构进行源码解析（部分的源码解析会以注释的方式出现）。首先入手的是ArrayList，ArrayList是一个动态数组，其容量能够自动增长。

 

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

从ArrayList类的定义中可以看出，它是支持泛型的，除了继承和实现与List相关的抽象类和接口外，还实现了RandomAccess,Cloneable, Serializable标记接口（接口中没有任何内容），表明ArrayList支持随机访问、拷贝和序列化。 首先从ArrayList的构造方法开始看起，ArrayList总共提供3种构造方法 private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; private transient Object[] elementData; //以transient修饰，说明其数组不会被序列化 private int size; //elementData数组中元素的数量 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); } 从上述的构造函数源码可以看出，初始化ArrayList其实就是在初始化其内部的一个私有Object数组elementData。也就是说ArrayList使用一个Object数组来存储其内部的元素。在这里一开始对elementData被transient修饰感到比较困惑，被transient修饰的变量的值在序列化时是不会被保存的，ArrayList又是可序行化的类，elementData是ArrayList具体存放元素的成员，岂不是反序列化后的ArrayList丢失了原先的元素？其实当看完整个源码你就明白了，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(); } } }  ArrayList在序列化的时候会调用writeObject，直接将size和element写入ObjectOutputStream；反序列化时调用readObject，从ObjectInputStream获取size和element，再恢复到elementData。不直接序列化elementData的原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。 下面再看ArrayList的常用方法： add: private static final int DEFAULT_CAPACITY = 10; ....public boolean add(E e) { ensureCapacityInternal(size + 1); //size+1代表插入元素后数组的容量 elementData[size++] = e; //在数组elementData的末尾插入当前元素，同时size自增 return true; } public void add(int index, E element) { rangeCheckForAdd(index); //检查index是否合法 ensureCapacityInternal(size + 1); System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } //以下是几个函数实现数组扩容的相关方法 //添加元素前会调用此方法 private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { //如果elementData数组为空 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 取二者最大赋给变量minCapacity } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++;//定义于ArrayList的父类AbstractList，用于存储结构修改次数 // overflow-conscious code if (minCapacity - elementData.length > 0) //如果minCapacity大于elementData数组的长度，开始扩容 grow(minCapacity); } //容量扩容的主要实现算法 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //相当于int newCapacity=oldCapacity+(oldCapacity/2),扩容50%的意思，右移比除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); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } 从上述源码可以得出，当执行add(E e)方法时，首先调用了ensureCapacity(size+1)方法，之后将元素的索引赋给elementData[size]，而后size自增。比如初次添加元素时，size=0，add方法将e赋值给elementData[0]，然后size为1。size+1为增加元素后，数组的容量。在方法ensureCapacity中，我们可以看到，size+1大于数组的当前容量，就会开始扩容。在具体的扩容算法grow中，从中可以看出，数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。当执行add(int index, E element)时，首先会检查index值的合法性，然后判断是否需要扩容，是否执行System.arraycopy(elementData, index, elementData, index + 1,size - index)方法，此方法的意思是将elementData中从Index位置开始、长度为size-index的元素， 拷贝到从下标为index+1位置开始的新的elementData数组中，即将当前位于该位置的元素以及所有后续元素右移一个位置。然后在index处插入e。 从上述可以看出，每次进行扩容时，都要将原来的数组拷贝到一个新的数组中，非常耗时。所以当我们可以预知ArrayList的容量时，就应该手动传入容量以避免扩容。也可以调用如下方法ensureCapacity，一次性增加capacity，可以减少增加重分配的次数提高性能。 public void ensureCapacity(int minCapacity) { int minExpand = (elementData != EMPTY_ELEMENTDATA) // any size if real element table ? 0 // larger than default for empty table. It's already supposed to be // at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } remove: public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work } ArrayList提供了2种移除元素的方式，remove(int index)是根据下标来移除元素，而remove(object o)则是根据指定对象来移除元素。remove(int index)的实现思路如下：首先是检查index范围，修改modCount，j把要被移除的元素进行保留，将移除位置之后的元素向前挪动一个位置，将list末尾元素置为null，返回被移除的元素。remove(object o)的实现思路则为：遍历elementData数组，找到需要删除的元素，将移除位置之后的元素向前挪动一个位置，将list末尾元素置为null（ArrayList允许元素为null,当传入的object为null需要使用==进行比较）。 get: public E get(int index) { rangeCheck(index); return elementData(index); } set: public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } 这两个方法没什么好说的，因为ArrayList是顺序存储结构（数组），可以根据下标实现随机存取。 以后会抽空了解更多的Java框架的源码并进行分享。