Java容器ArrayList源代码解析

蔚落 2022-06-14 23:57 240阅读 0赞

#### 写在前面 ####

本文是针对Java1.6源代码解析的，可能会与其他版本有出入。

#### 概述 ####

ArrayList是很常用的一个容器，它的底层是用动态数组实现的，可以根据数据量大小自动扩容。它支持很多操作，比如向容器中添加、删除、查找数据，返回容器的大小等等。

##### 1.全局变量 #####

ArrayList定义了两个全局变量，一个是存放数据的动态数组，一个是标志数组大小的字段size。源代码如下：

/**
         * The array buffer into which the elements of the ArrayList are stored.
         * The capacity of the ArrayList is the length of this array buffer.
         */
        private transient Object[] elementData;
    
        /**
         * The size of the ArrayList (the number of elements it contains).
         *
         * @serial
         */
        private int size;

##### 2.构造方法 #####

###### (1)带有初始容器大小initialCapacity的构造函数 ######

先判断initialCapacity的值，如果小于0，则抛出异常。否则，就生成一个initialCapacity大小的数组。源代码如下：

/**
         * Constructs an empty list with the specified initial capacity.
         *
         * @param   initialCapacity   the initial capacity of the list
         * @exception IllegalArgumentException if the specified initial capacity
         *            is negative
         */
        public ArrayList(int initialCapacity) {
            super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            this.elementData = new Object[initialCapacity];
        }

###### **(2)默认构造函数** ######

默认构造函数会生成一个大小为10的数组。源代码如下：

/**
         * Constructs an empty list with an initial capacity of ten.
         */
        public ArrayList() {
            this(10);
        }

###### (3)带参数Collection的构造函数 ######

这个构造函数是将一个collection的实现类对象转化为ArrayList，通过调用每个实现类的toArray方法，把对象转化为数组赋值给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);
    }

##### 3.方法 #####

###### (1)trimToSize方法 ######

当ArrayList中的动态数组不足以存储数据时，ArrayList就会自动扩容。但是这样的扩容，每次并不会填充满整个数组。所以数组的长度length一般都要比ArrayList的大小size要大，这也就是为什么我们用ArrayList存储数据时，经常会看到下面很多数据都是null的原因。这个方法的作用就是把数组的大小由length变为size。对ArrayList涉及改变elementData大小的操作都会有一个modCount字段来记录操作数，这个字段是在AbstractList中定义的，主要作用就是防止在多线程操作下，list发生结构性变化。源代码如下：

public void trimToSize() {
    	modCount++;
    	int oldCapacity = elementData.length;
    	if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
    	}
    }

###### (2)ensureCapacity方法 ######

这个方法就是ArrayList的扩容方法，用传进来的最小所需容量minCapacity参数与现在的elementData大小length进行比较，如果数组足够大，则不做任何操作。否则，先把数字组扩容到之前的1.5倍，如果扩容后的数组还不够大，则直接把数组扩容到minCapacity大小。源代码如下：

public void ensureCapacity(int minCapacity) {
    	modCount++;
    	int oldCapacity = elementData.length;
    	if (minCapacity > oldCapacity) {
    	    Object oldData[] = elementData;
    	    int newCapacity = (oldCapacity * 3)/2 + 1;
        	if (newCapacity < minCapacity)
    		    newCapacity = minCapacity;
                // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    	}
    }

###### (3)size方法 ######

返回ArrayList的大小，源代码如下：

public int size() {
    	        return size;
        }

###### (4)isEmpty方法 ######

判断ArrayList是否为空，直接判断size是否等于0即可。源代码如下：

public boolean isEmpty() {
    	        return size == 0;
        }

###### (5)indexOf方法 ######

查找某个数据第一次出现的索引值，如果存在，则返回索引值，不存在，返回-1。源代码如下：

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;
    }

###### (6)contains方法 ######

判断某个数据是否存在，直接调用indexOf方法，判断返回值是否大于等于0。源代码如下：

public boolean contains(Object o) {
    	        return indexOf(o) >= 0;
        }

###### (7)lastIndexOf方法 ######

查找某个数据最后一次出现的索引值，如果不存在，则返回-1。源代码如下：

public int lastIndexOf(Object o) {
    	if (o == null) {
    	    for (int i = size-1; i >= 0; i--)
    		    if (elementData[i]==null)
    		         return i;
    	} else {
    	    for (int i = size-1; i >= 0; i--)
    		    if (o.equals(elementData[i]))
    		        return i;
    	}
    	return -1;
    }

###### (8)clone方法 ######

返回此ArrayList对象的拷贝副本。源代码如下：

public Object clone() {
    	try {
    	    ArrayList<E> v = (ArrayList<E>) 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();
    	}
    }

###### (9)toArray方法 ######

将ArrayList转化为Object的数组，直接调用Arrays.copyOf()方法。源代码如下：

public Object[] toArray() {
            return Arrays.copyOf(elementData, size);
        }

###### (10)toArray(T\[\] a)方法 ######

将ArrayList里面的元素赋值给到数组a中。如果a的大小小于size，则直接调用Arrays.copyOf方法，返回一个比a要大的数组，里面存储的是ArrayList的元素；否则，调用System.arraycopy方法。源代码如下：

public <T> T[] toArray(T[] a) {
            if (a.length < size)
                // Make a new array of a's runtime type, but my contents:
                return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    	        System.arraycopy(elementData, 0, a, 0, size);
            if (a.length > size)
                a[size] = null;
            return a;
        }

###### (11)get方法 ######

获取ArrayList中某个索引的值。先调用RangeCheck方法检查给的的索引是否越界，如果越界，则直接抛出异常；否则，返回elementData对应索引处的值。源代码如下：

public E get(int index) {
    	RangeCheck(index);
    
    	return (E) elementData[index];
    }

RangeCheck源代码如下：

private void RangeCheck(int index) {
    	        if (index >= size)
    	            throw new IndexOutOfBoundsException(
    		        "Index: "+index+", Size: "+size);
        }

###### (12)set(int index, E element)方法 ######

用Element替换掉index索引处的值。此方法也是会调用RangeCheck方法检查index是否越界，如果不越界，则替换掉原先的值，并把原先的值作为结果返回。源代码如下：

public E set(int index, E element) {
    	RangeCheck(index);
    
    	E oldValue = (E) elementData[index];
    	elementData[index] = element;
    	return oldValue;
    }

###### (13)add(E e)方法 ######

在ArrayList对象的末尾追加数据，首先调用ensureCapacity方法，确保elementData足够大，然后在数组末尾追加数据，并把size加一。源代码如下：

public boolean add(E e) {
    	ensureCapacity(size + 1);  // Increments modCount!!
    	elementData[size++] = e;
    	return true;
    }

###### (14)add(int index, E element)方法 ######

在ArrayList对象的index处增加数据，先检查数据是否越界，然后调用ensureCapacity方法，确保elementData足够大，再调用System.arraycopy方法把从index开始的数据拷贝到index+1开始的地方，最后再把index处的数据置为element。源代码如下：

public void add(int index, E element) {
    	if (index > size || index < 0)
    	    throw new IndexOutOfBoundsException(
    		"Index: "+index+", Size: "+size);
    
    	ensureCapacity(size+1);  // Increments modCount!!
    	System.arraycopy(elementData, index, elementData, index + 1,
    			 size - index);
    	elementData[index] = element;
    	size++;
    }

###### (15)remove(int index)方法 ######

删除index处的值，先检查数组是否越界，然后利用System.arraycopy方法拷贝数组，再把size减一，并且把elementData\[size-1\]置为null。源代码如下：

public E remove(int index) {
    	RangeCheck(index);
    
    	modCount++;
    	E oldValue = (E) elementData[index];
    
    	int numMoved = size - index - 1;
    	if (numMoved > 0)
    	    System.arraycopy(elementData, index+1, elementData, index,
    			     numMoved);
    	elementData[--size] = null; // Let gc do its work
    
    	return oldValue;
    }

###### (16)remove(Object o)方法 ######

删除ArrayList中第一个出现的数据o，先查找到o在ArrayList中第一次出现的位置index，然后调用fastRemove(int index)方法删除。fastRemove与remove类似，不同之处在于fastRemove不会进行数组越界检查，且不会返回删除的值。这是因为如果能查找到要删除的值，则数组肯定不会越界。源代码如下：

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;
    }

fastRemove的源代码如下：

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; // Let gc do its work
        }

###### (17)clear方法 ######

清空ArrayList。把elementData所有值置为null，并把size置为0。源代码如下：

public void clear() {
    	modCount++;
    
    	// Let gc do its work
    	for (int i = 0; i < size; i++)
    	    elementData[i] = null;
    
    	size = 0;
    }

###### (18)addAll(Collection<? extends E> c)方法 ######

在list末尾追加collection对象，先把collection转化为数组，然后根据数组的大小对ArrayList进行扩容，之后把数据拷贝到elementData中，最后调整size的值。源代码如下：

public boolean addAll(Collection<? extends E> c) {
    	Object[] a = c.toArray();
        int numNew = a.length;
    	ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
    	return numNew != 0;
    }

###### (19)addAll(int index, Collection<? extends E> c)方法 ######

在index索引处插入collection对象，先判断index是否越界，然后把collection转化为数组，再根据数组的大小对ArrayList进行扩容，之后拷贝数据，最后调整size值。源代码如下：

public boolean addAll(int index, Collection<? extends E> c) {
    	if (index > size || index < 0)
    	    throw new IndexOutOfBoundsException(
    		"Index: " + index + ", Size: " + size);
    
    	Object[] a = c.toArray();
    	int numNew = a.length;
    	ensureCapacity(size + numNew);  // Increments modCount
    
    	int numMoved = size - index;
    	if (numMoved > 0)
    	    System.arraycopy(elementData, index, elementData, index + numNew,
    			     numMoved);
    
        System.arraycopy(a, 0, elementData, index, numNew);
    	size += numNew;
    	return numNew != 0;
    }

###### (20)removeRange(int fromIndex, int toIndex)方法 ######

与remove(index)方法类似，只是删除fromIndex到toIndex一系列的值。源代码如下：

protected void removeRange(int fromIndex, int toIndex) {
    	modCount++;
    	int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                             numMoved);
    
    	// Let gc do its work
    	int newSize = size - (toIndex-fromIndex);
    	while (size != newSize)
    	    elementData[--size] = null;
    }