ArrayList源码解析

谁践踏了优雅 2021-09-25 05:52 531阅读 0赞

### ArrayList ###

*  ArrayList
 *   *  ArrayList整体结构
     *  定义的变量
     *  构造函数
     *  常用方法
     *   *  contains、indexOf、lastIndexOf
         *  get
         *  set
         *  add、addAll (核心)
         *  remove、removeAll、retainAll(核心)
     *  内部核心方法

--------------------

# ArrayList #

## ArrayList整体结构 ##

![arrayList结构图][arrayList]

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

注意：ArrayList实现了`RandomAccess`接口，这是个**标记接口**，没有具体的实现，只是作为标记用；比如List下的ArrayList和LinkedList。其中ArrayList实现了RandomAccess。而LinkedList没有。我们可以利用instanceof来判断哪一个是实现了RandomAccess。分辨出两个集合。其中**ArrayList使用for循环遍历快，而LinkedList使用迭代器快**。

public interface RandomAccess { }

## 定义的变量 ##

private static final long serialVersionUID = 8683452581122892189L;
    
    /** * Default initial capacity. 默认的容量 */
    private static final int DEFAULT_CAPACITY = 10;
    
    /** * Shared empty array instance used for empty instances. * 空数组，当用户指定ArrayList容量为0时，返回该数组 */
    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. * 一个空数组，用于new ArrayList(); 无参构造时返回。 * --当添加元素(add)时，数组就会扩容 长度为(DEFAULT_CAPACITY)10 ==>通过ensureCapacityInternal()实现 */
    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. * 存储数组列表元素的数组缓冲区,也就是实际存储数据的数组，ArrayList的底层就是数组 * --ArrayList基于数组实现 被`transient`修饰的对象不会被序列化 */
    transient Object[] elementData; // non-private to simplify nested class access
    
    /** * The size of the ArrayList (the number of elements it contains). * 实际的大小，区别于容量（CAPACITY），容量可能为10 但实际大小为1 * @serial */
    private int size;

## 构造函数 ##

> ArrayList 拥有三个构造函数

// 无参构造，数据缓冲区为空数组
    public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /** * 带参构造 * @param initialCapacity 自定义初始化容量 * @throws IllegalArgumentException if the specified initial capacity is negative */
    public ArrayList(int initialCapacity) { 
    	// 如果自定义容量大于0 则按照自定义容量为准。
        if (initialCapacity > 0) { 
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { 
            this.elementData = EMPTY_ELEMENTDATA;
        } else { 
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        }
    }
    
    /** * 创建一个包含collection的ArrayList * @param c 要放入集合 * @throws NullPointerException if the specified collection is null */
    public ArrayList(Collection<? extends E> c) { 
        // public Object[] toArray() { return Arrays.copyOf(elementData, size); }
        // 把集合转成数组
        elementData = c.toArray();
        if ((size = elementData.length) != 0) { 
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            // 这句话意思是：c.toArray 可能不会返回 Object[]，可以查看 java 官方编号为 6260652 的 bug
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else { 
            // replace with empty array. 空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

## 常用方法 ##

// 获取size
    public int size() { 
        return size;
    }
    // 判断是否为空
    public boolean isEmpty() { 
        return size == 0;
    }
    //实现Cloneable接口，深度复制：对拷贝出来的 ArrayList 对象的操作，不会影响原来的 ArrayList
    public Object clone() { 
        try { 
            ArrayList<?> v = (ArrayList<?>) 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(e);
        }
    }
    
    // 转成数据方法 其实就是数组的拷贝
    public Object[] toArray() { 
        return Arrays.copyOf(elementData, size);
    }
    // 根据传入数组 转成相对应类型的List
    public <T> T[] toArray(T[] a) { 
        if (a.length < size)
            // 如果传入的数组a的长度小于 arraylist的size 
            // 则复制list的数据到 一个新的数组(数组长度为list的size)
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        // 若数组a的大小 >= ArrayList的元素个数,则将ArrayList的全部元素都拷贝到数组a中。
        // Object src : 原数组
       	// int srcPos : 从原数据的起始位置开始
    　　 // Object dest : 目标数组
    　　 // int destPos : 目标数组的开始起始位置
    　　 // int length : 要copy的数组的长度
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }
    // 清空元素
    public void clear() { 
        modCount++;
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

### contains、indexOf、lastIndexOf ###

> 顺序查找和逆序查找

// 是否包含某个值
    public boolean contains(Object o) { 
        return indexOf(o) >= 0;
    }
    // 获取某个值的下标，顺序查找
    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++)
                // 注意这里使用的是equals
                if (o.equals(elementData[i]))
                    return i;
        }
        return -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--)
            	// 注意这里使用的是equals
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

### get ###

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

### set ###

// 替换值
    public E set(int index, E element) { 
        // 判断下标是否越界
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        // 返回的是旧值
        return oldValue;
    }
    private void rangeCheck(int index) { 
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

### add、addAll (核心) ###

> add方法调用顺序。  
> add–>ensureCapacityInternal–>calculateCapacity–>ensureExplicitCapacity  
> (如需扩容)–>grow–>hugeCapacity

public boolean add(E e) { 
        // 扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!! 增量modCount
        // 赋值
        elementData[size++] = e;
        return true;
    }
    // 在指定位置加元素
    public void add(int index, E element) { 
        rangeCheckForAdd(index);
    	// 扩容长度+1
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // Object src : 原数组
       	// int srcPos : 从原数据的起始位置开始
    　　// Object dest : 目标数组
    　　// int destPos : 目标数组的开始起始位置
    　　// int length : 要copy的数组的长度
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    
    // 添加集合元素
    public boolean addAll(Collection<? extends E> c) { 
        Object[] a = c.toArray();
        int numNew = a.length;
        // 扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        // 末尾添加
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    
    // 指定下标，从这个下标开始插入集合c
    public boolean addAll(int index, Collection<? extends E> c) { 
        rangeCheckForAdd(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        // 扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        int numMoved = size - index;
        if (numMoved > 0)
            // 这里可以自己用比画一下逻辑
            // 他把数组从index到最后的数据 复制给原数组从 index+numNew 到最后 
            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
        // 再把index到index+numNew的数据用 c 数据覆盖
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }
    
    // private
    private void rangeCheckForAdd(int index) { 
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    private void ensureCapacityInternal(int minCapacity) { 
        // calculateCapacity 获取 默认容量和用户输入的最大值
        // ensureExplicitCapacity 确保容量 如果需要就扩容 grow()
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) { 
        // 如果elementData = {},那么默认容量为 (10(默认容量) 和 用户传入)的最大值
        // 否则返回需要扩容后的大小 (最小elementData数组大小要求)
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    private void ensureExplicitCapacity(int minCapacity) { 
        modCount++;
        // 如果传入的最小容量 > 数组现有长度 则需要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    // 扩容算法
    private void grow(int minCapacity) { 
    	// 数组现有长度
        int oldCapacity = elementData.length;
        // 系统自动计算新容量
        // >> 带符号右移 >>1 相当于除以2 
        // 例如： 5(0101) >> 1 0101 --> 0010 (2)
        // newCapacity = 1.5 * oldCapacity 
        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);
    }
    
    private static int hugeCapacity(int minCapacity) { 
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
        	MAX_ARRAY_SIZE;
    }

### remove、removeAll、retainAll(核心) ###

> removeAll一般用于取差集 retainAll一般用于取交集

// 根据下标移除元素
    public E remove(int index) { 
        rangeCheck(index);
        modCount++;
        E oldValue = elementData(index);
    	// 假设size=10 需要删除第3个 index=2 numMoved=10-2-1=7
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 复制到新数组 并截掉了下标为index的元素
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        // 设最后一个元素为null 方便GC回收
        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 rangeCheck(int index) { 
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    // 跟remove(int index) 相比少了返回值以及下标判断(rangeCheck)
    // private
    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
    }
    
    // 移除一段索引下的数据
    // protected 
    protected void removeRange(int fromIndex, int toIndex) { 
        modCount++;
        // 假设 fromIndex=2 toIndex=3 size=10
        // numMoved = 7
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);
        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) { 
            elementData[i] = null;
        }
        size = newSize;
    }
    
    public boolean removeAll(Collection<?> c) { 
    	// 确保不为空
        Objects.requireNonNull(c);
        // 核心方法
        return batchRemove(c, false);
    }
    
    public boolean retainAll(Collection<?> c) { 
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
    
    /** ***牛逼的写法*** * 可以自己带一些数据进去画个图 * 从一个list中移除另一个list包含的内容，差集 * 假设 原list数组为 [1,3,5,7,9] c为[1,4,8,9,10] * @param c * @param complement false 差集 true 交集 */ 
    private boolean batchRemove(Collection<?> c, boolean complement) { 
        // [1,3,5,7,9]
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try { 
            for (; r < size; r++)
                // 如果 不包含
                if (c.contains(elementData[r]) == complement)
                    // 先赋值 再 w++
                    elementData[w++] = elementData[r];
            // 循环结束后 w = 3
            // elementData = [3,5,7,7,9]
        } finally { 
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) { 
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) { 
                // w=3
                // 从下标3开始 也就是第4个开始 后面的置为null
                // elementData = [3,5,7,null,null]
                for (int i = w; i < size; i++)
                    elementData[i] = null; // clear to let GC do its work
                // 修改次数+ (5-3)
                modCount += size - w;
                // 修改size = 3
                size = w;
                modified = true;
            }
        }
        return modified;
    }

## 内部核心方法 ##

> 主要还是add和remove方法中的小算法

/** * 将 ArrayList 实例的容量调整为列表的当前大小。 * 应用程序可以使用此操作来最小化存储 ArrayList 实例。 * 注：这个方法并没有直接在ArrayList类中被用到，被使用在FastArrayList类中 */
    public void trimToSize() { 
        // modCount * 字面来看就是修改次数，这个跟线程安全有关；
        // Fail-Fast 机制 ：在一个迭代器初始的时候会赋予它调用这个迭代器的对象的mCount，如何在迭代器遍历的过程中，一旦发现这个对象的mcount和迭代器中存储的mcount不一样那就抛异常。
        modCount++;
        // 如果实际使用大小 小于 数组长度，且不为空数组，那么复制数组到对应长度的数组中。
        // 通过这一步，可以使得空间得到有效利用。
        if (size < elementData.length) { 
            elementData = (size == 0)
                ? EMPTY_ELEMENTDATA
                : Arrays.copyOf(elementData, size);
        }
    }
    
    /** * 增加ArrayList实例的容量，确保它至少能容纳元素的数量由最小容量参数指定。 * @param minCapacity the desired minimum capacity */
    public void ensureCapacity(int minCapacity) { 
        int minExpand = 
            // 如果数组缓冲区不为空数组 就设为0 ；如果为空数组 就为 默认值10
            (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
    	// 若用户指定的最小容量 > 最小扩充容量，则以用户指定的为准，否则还是 10
        if (minCapacity > minExpand) { 
            ensureExplicitCapacity(minCapacity);
        }
    }
    /** * 确保明确的容量 */
    private void ensureExplicitCapacity(int minCapacity) { 
        modCount++;
        // 如果用户传入的最小容量 > 数组缓冲区的实际长度 则需要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    //一些 VM 会在一个数组中存储某些数据--->为什么要减去 8 的原因
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    // 扩容
    private void grow(int minCapacity) { 
        // overflow-conscious code
        // 原数据缓冲区长度
        int oldCapacity = elementData.length;
        // 系统自动计算新容量 
        // >>:带符号右移 >>1 相当于除以2 
        // 例如： 5(0101) >> 1 0101 --> 0010 (2)
        // 新容量 = 1.5 * 旧容量
        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);
    }
    
    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方法中使用，add方法时，size会增加 * @param minCapacity 新的size */
    private void ensureCapacityInternal(int minCapacity) { 
    	/* * calculateCapacity：计算容量 * ensureExplicitCapacity：确保明确的容量 如果需要就扩容 grow() */
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) { 
    	// 如果数组缓冲区为空数组，那么返回默认容量(10)和用户输入容量中的最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 如果数组缓冲区不为空数组，最小elementData数组大小要求
        return minCapacity;
    }
    
    private void ensureExplicitCapacity(int minCapacity) { 
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
        	// 扩容
            grow(minCapacity);
    }

[arrayList]: /images/20210923/2969fc35da474521821027012eeeffbd.png