在平时的开发中,用到最多的集合应该就是ArrayList了,本篇文章将结合源代码来学习ArrayList。
这些大家应该都很清楚,下面根据源代码来深入分析一下ArrayList。
源代码如下所示:
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 = {}; /** * 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 private int size;
初步思考:
继续分析:
源代码如下所示:
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; } }
初步思考:
继续分析:
无参构造:
指定容量构造:
传入Collection子类对象构造:
public ArrayList(Collection<? extends E> c) { /** *将传入的集合转换为一个Object类型的数组,并将此数组的引用赋给elementData */ elementData = c.toArray(); if ((size = elementData.length) != 0) {// 转换后的数组不为空时 /** * 判断转换后的数组是不是Object[]数组 * 如果不是的话,就把它复制为一个Object[]数组,进行赋值 */ if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 转换后的数组为空,用成员变量EMPTY_ELEMENTDATA来辅助 this.elementData = EMPTY_ELEMENTDATA; } }
toArray()方法源代码如下:
public Object[] toArray() { return Arrays.copyOf(elementData, size); }
Arrays类的copyOf()方法源代码如下:
@SuppressWarnings("unchecked") public static <T> T[] copyOf(T[] original, int newLength) { // 此处的copyOf()调用了本类的重载方法 return (T[]) copyOf(original, newLength, original.getClass()); }
重载方法源代码如下所示:
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { @SuppressWarnings("unchecked") T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }
代码分析:
调用链最后调用到了native方法上:
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos, int length); /** * 参数说明: * src:源对象 * srcPos:源数组中的起始位置 * dest:目标数组对象 * destPos:目标数据中的起始位置 * length:要拷贝的数组元素的数量 */
源代码中最后都调用到了native方法,只能看到方法名和参数,看不到具体的实现,对native方法做个简单的介绍吧。
native声明的接口方法: Java代码和本地C代码进行互操作的API,称为Java Native Interface (Java本地接口)。也就是说,带有native标记的方法,都是使用C语言来实现的,读者了解到这里即可,感兴趣的可以去查阅下相关资料,这里就不多阐述了。
源代码如下所示:
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
初步分析:
继续跟踪ensureCapacityInternal()方法,该方法相关源代码如下所示:
private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }
分析:
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
该方法源代码如下所示:
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
初步分析:
继续分析:
接下来,看下grow()方法的源代码,马上就要揭开ArrayList能够动态扩容的根本原因了,想想还有些激动,哈哈~
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); }
分析:
此处需要注意一个地方,如果oldCapacity + (oldCapacity >> 1)执行的结果超过了int的最大值,即2的31次方减1,那么新数组的长度将变为负数
代码如下:
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
传入的容量超过了MAX_ARRAY_SIZE大小,则将Integer.MAX_VALUE的值进行返回,否则返回MAX_ARRAY_SIZE
源代码如下所示:
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++; }
基于add()方法的分析,分析如下:
rangeCheckForAdd()方法源代码如下所示:
private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
分析如下:
注意: 由于此处判断范围上限取的实际元素的个数,那么就会造成一个情况,我们使用指定容量的构造方法,创建了一个ArrayList对象,然后使用add(int index, E element)方法时,当添加的index不是0时,就会报错
举例如下:
public static void main(String[] args) { List<String> a = new ArrayList<>(12);// 初始化指定了数组的容量为12 a.add(5, "element"); } //结果如下: // Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 5, Size: 0 // at java.util.ArrayList.rangeCheckForAdd(ArrayList.java:661) // at java.util.ArrayList.add(ArrayList.java:473) // at test.TestAddArrayList.main(TestAddArrayList.java:11)
源代码如下所示:
public E get(int index) { rangeCheck(index); return elementData(index); } private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } E elementData(int index) { return (E) elementData[index]; }
简要分析:
源代码如下所示:
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 int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }
indexOf方法是返回某元素在ArrayList对象里的下标(索引)。
分析:
非null元素时,使用equals()方法来判断(ps:由此处调用的equals()方法,可以看出为什么不支持基本类型的元素)
ArrayList中还有很多方法,篇幅有限,在此不再赘述。