ArrayList源码解析与学习

r囧r小猫 2022-06-17 14:07 245阅读 0赞

为了更深一步的学习掌握Java中的集合类，最近决定把Java中比较常用的集合类源码学习一下。

今天就把我对ArrayList源码的理解跟大家分享下，JDK版本是1.7（不同版本的源码可能略有差异，但是思想几乎不变）。

ArrayList底层是通过数组来实现的，其主要方法get、add、remove等方法都是通过围绕这个数组来进行一系列的操作，这些方法也是我们理解ArrayList的重点。

## 1、ArrayList类中的全局参数 ##

private transient Object\[\] elementData;//实现ArrayList的数组

private int size;//ArrayList的大小（即其中包含数据元素的个数）

有个关键字需要解释：transient。

Java的serialization提供了一种持久化对象实例的机制。当持久化对象时，可能有一个特殊的对象数据成员，我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字transient。

## 2、ArrayList类的构造函数 ##

### （1）参数是设置list初始大小的构造函数 ###

public ArrayList(int initialCapacity) {
    	        super();
    	        if (initialCapacity < 0)
    	            throw new IllegalArgumentException("Illegal Capacity: "+
    	                                               initialCapacity);
    	        this.elementData = new Object[initialCapacity];
    	    }

### （2）默认的构造函数（list初始大小是10） ###

public ArrayList() {
            this(10);
        }

### （3）参数是collection的构造函数 ###

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、add（）方法 ##

### （1）boolean add(E e) ###

public boolean add(E e) {
    		//数组是否扩容
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            //数组相应位置添加数据，list大小加1
            elementData[size++] = e;
            return true;
        }
    	
    	private void ensureCapacityInternal(int minCapacity) {
            modCount++;
            //如果list的大小加1大于数组的长度,那么执行数组扩容
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    	
    	private void grow(int minCapacity) {
            //扩容之前数组大小
            int oldCapacity = elementData.length;
            //扩容之后数组大小是原来的1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //如果扩容1.5倍之后的数组大小比数组的（size（）+1）更小，那么新数组size即是（size（）+1）
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            //如果扩容1.5倍之后的数组size比（0x7fffffff-1-8）还大，那么查看数组的（size（）+1）值，如果此值比（0x7fffffff-1-8）大，那么
            //数组值是(0x7fffffff-1),否则是（0x7fffffff-1-8）
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            //最后数组执行扩容操作
            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;
        }

### （2）void add(int index, E element) ###

//在指定位置添加元素
    	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++;
        }
    	
    	private void rangeCheckForAdd(int index) {
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

## 4、get（）方法（很好理解，不再赘述） ##

public E get(int index) {
            rangeCheck(index);
    
            return elementData(index);
        }
    	
    	private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    	
    	@SuppressWarnings("unchecked")
        E elementData(int index) {
            return (E) elementData[index];
        }

## 5、remove（）方法 ##

### （1）E  remove(intindex)： ###

public E remove(int index) {  
            //检查index是否在list的容量大小范围之内，否则抛出异常  
            rangeCheck(index);  
            //modCount表示list的修改次数（此处可以忽略这个参数）  
            modCount++;  
            //Arralist底层是一个数组实现，elementData表示实现list的数组  
            E oldValue = elementData(index);  
            //size表示list的容量大小，以下两行代码表示，执行删除操作时，即：删除位置之后的数据全部前移一个位置  
            int numMoved = size - index - 1;  
            if (numMoved > 0)  
                System.arraycopy(elementData, index+1, elementData, index,  
                                 numMoved);  
            //最后将带删除元素置空，等到GC清除  
            elementData[--size] = null; // Let gc do its work  
            return oldValue;  
        }  
        private void rangeCheck(int index) {  
            if (index >= size)  
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
        }

### （2）boolean  remove(Object o) ###

public boolean remove(Object o) {  
            //分成两种情况考虑：参数是null或者不是null  
            if (o == null) {  
                //循环遍历实现list的数组，查找所有值是null的数组元素，然后执行fastRemove方法。  
                for (int index = 0; index < size; index++)  
                    if (elementData[index] == null) {  
                        fastRemove(index);  
                        return true;  
                    }  
            } else {  
                //循环遍历实现list的数组，查找所有值是o的数组元素，然后执行fastRemove方法。  
                for (int index = 0; index < size; index++)  
                    if (o.equals(elementData[index])) {  
                        fastRemove(index);  
                        return true;  
                    }  
            }  
            return false;  
        }  
        //根据数组下标进行数组元素删除（类似于E remove(int index)方法，只是不加异常判断而已）  
        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  
        }

## 6、其他 ##

### （1）int indexOf(Object o) ###

//返回指定元素在list中第一次出现的位置
     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;
        }

### （2）E set(int index, E element) ###

//指定位置进行数据替换
    	public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }