首先,类名
public class ArrayList<E>
明显看到有泛型,然后看看属性:
/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */ transient Object[] elementData; // non-private to simplify nested class access /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size;
经常看到说ArrayList的底层实现是数组,看来就是这里了吧,使用一个object数组来存放数据。
下面再看看ArrayList的构造函数:
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }
有空构造,有可指定长度的构造函数,有入参为该泛型的子类的集合的构造函数。
前两个都好理解,第三个构造函数举个例子来说明下:
ArrayList<Exception> elist = new ArrayList<Exception>(); list.add(new Exception("11")); list.add(new Exception("22")); ArrayList<Throwable> tlist = new ArrayList<>(elist);
那我们平时经常使用的
ArrayList< User> list = new ArrayList< User>(); 这个是用的空构造函数,尖括号中填的是泛型类型 • 1
接下来说说ArrayList的扩容,每当向list中插入一条数据的时候,都要去检出是否超出了当前集合的长度如果超过了,就会调用ensureCapacityInternal方法得到所需新增元素后所需长度:
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
而ensureCapacityInternal方法中调用了calculateCapacity和ensureExplicitCapacity,见方法中注释:
private static final int DEFAULT_CAPACITY = 10; private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //如果list是空集合的话,返回默认的初始容量10作为所需长度 return Math.max(DEFAULT_CAPACITY, minCapacity); } //否则,返回长度加一作为所需长度 return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // 当所需的长度大于当前数组的长度,那么执行grow方法进行扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); }
当所需长度大于当前长度的时候,执行grow方法进行扩容:
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 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) //如果扩容后的长度大于数组的最大长度,返回一个 //Integer.MAX_VALUE 或 Integer.MAX_VALUE-8长度作为扩容后长度 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; }
有一个地方注意一下:
newCapacity = oldCapacity + (oldCapacity >> 1)
这里>>1 右位移一位,相当于除以二,加上原来的,相当于扩容后的长度是原长度的1.5倍!
最后使用Arrays.copyOf方法,将原来的数据复制到扩容后长度的数组中,扩容的操作完成!