ArrayList源码分析精简版

傷城~ 2021-12-12 10:31 237阅读 0赞

# 简述扩容机制 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]

# 常用属性 #

*  默认容量大小：`private static final int DEFAULT_CAPACITY = 10;`
 *  默认大小空实例的数组实例：`private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};`
 *  保存ArrayList数据的数组：`transient Object[] elementData;`
 *  空数组（用于空实例）：`private static final Object[] EMPTY_ELEMENTDATA = {};`
 *  要分配的最大数组大小：`private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//Integer.MAX_VALUE=2147483647`
 *  ArrayList 所包含的元素个数：`private int size;`

# 常用方法 #

*  带初始容量参数的构造函数。（用户自己指定容量）：`public ArrayList(int initialCapacity)`
 *  构造一个包含指定集合的元素的列表：`public ArrayList(Collection<? extends E> c)`
 *  判断是否需要扩容：`ensureCapacity`，调用`ensureExplicitCapacity`方法判断是否需要扩容。

private void ensureCapacityInternal(int minCapacity) { 
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    // 若当前为空数组，添加时取传入的值和默认的容量中较大的，如传入3，则用默认的10.
    // 当要add进第一个元素时，minCapacity为1，在Math.max()方法比较后，minCatacity为10.
    private static int calculateCapacity(Object[] elementData, int minCapacity) { 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

*  判断是否需要扩容：`ensureExplicitCapacity`

//判断是否需要扩容
    private void ensureExplicitCapacity(int minCapacity) { 
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //调用grow方法进行扩容，调用此方法代表已经开始扩容了
            grow(minCapacity);
    }

*  ArrayList扩容的核心方法：`grow`，里面调用了`hugeCapacity`方法比较`minCapacity`和`MAX_ARRAY_SIZE`。

/** * ArrayList扩容的核心方法 * @param minCapacity the desired minimum capacity */
    private void grow(int minCapacity) { 
        // oldCapacity为旧容量，newCapacity为新容量
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //再检查新容量是否超出了ArrayList所定义的最大容量，
        //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
        //如果minCapacity大于最大容量，则新容量则为ArrayList定义的最大容量，否则，新容量大小则为 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);
    }

*  列表中的元素个数：`public int size()`
 *  判断列表是否为空：`isEmpty()`
 *  是否包含指定元素：`contains(Object o)`
 *  返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1：`public int indexOf(Object o)`
 *  返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1：`public int lastIndexOf(Object o)`
 *  返回此ArrayList实例的拷贝：`public Object clone()`
 *  List转数组：`public Object[] toArray()`
 *  返回此列表中指定位置的元素：`public E get(int index)`
 *  用指定的元素替换此列表中指定位置的元素（返回的是旧元素）：`public E set(int index, E element)`
 *  将特定的元素追加到此列表的末尾：`public boolean add(E e)`

/** * 将特定的元素追加到此列表的末尾 */
    public boolean add(E e) { 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //这里看到ArrayList添加元素的实质就相当于为数组赋值
        elementData[size++] = e;
        return true;
    }

*  在此列表中的指定位置插入指定的元素：`add`

/** * 在此列表中的指定位置插入指定的元素。 * 先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大； * 再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。 */
    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++;
    }

*  删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）：`public E remove(int index)`
 *  从列表中删除指定元素的第一个出现位置的元素（如果存在）。 如果列表不包含该元素，则它不会更改：`public boolean remove(Object o)`
 *  从列表中删除所有元素：`public void clear()`
 *  按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾：`public boolean addAll(Collection<? extends E> c)`
 *  将指定集合中的所有元素插入到此列表中，从指定的位置开始：`public boolean addAll(int index, Collection<? extends E> c)`
 *  从此列表中删除所有索引为fromIndex （含）和toIndex之间的元素,后序元素前移：`protected void removeRange(int fromIndex, int toIndex)`
 *  从此列表中删除指定集合中包含的所有元素：`public boolean removeAll(Collection<?> c)`
 *  仅保留此列表中包含在指定集合中的元素：`public boolean retainAll(Collection<?> c)`
 *

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]: /images/20211211/e7be47f45ec3452aa32355ac5518babd.png