如何用源码分析ArrayList

发布时间：2021-10-20 17:37:10 作者：柒染
来源：亿速云阅读：166

今天就跟大家聊聊有关如何用源码分析ArrayList，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

成员变量

/** ArrayList的初始化容量 **/
public static final int DEFAULT_CAPACITY = 10;

/** 数组能存储的最大元素容量 **/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/** 空数组，当调用无参数构造函数的时候默认给个空数组 **/
public static final Object[] EMPTY_ELEMENTDATA = {};

/** 真正保存数据的数组 **/
transient Object[] elementData;

/** 实际ArrayList的元素个数 **/
private int size;

ArrayList的初始化容量为10，真正的数据是存在elementData中，实际存储的元素个数用size表示。

构造方法

/** 无参构造函数 **/
public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

/** 初始化容量构造函数 **/
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0) {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
    this.elementData = new Object[initialCapacity];
}

/** 已有集合构造函数 **/
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    if (elementData.getClass() != Object[].class) {
        elementData = Arrays.copyOf(elementData, size, Object[].class);
    }
}

如果构造函数不传入List容量则初始化elementData为空数组。
如果构造函数传入List容量则初始化elementData为传入容量的Object数组
如果构造函数传入了集合则将集合转换为数组赋值给elementData，同时设置size值为数组的长度。

元素的插入

元素插入主要有以下四个方法：

boolean add(E e)
void add(int index, E e)
boolean addAll(Collection<? extends E> c)
boolean addAll(int index, Collection<? extends E> c)

add(E e)

/** 添加元素 **/
@Override
public boolean add(E e) {
    //确保数组容量
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

在添加元素时，先通过ensureCapacityInternal方法保证elementData数组拥有足够的容量。
然后直接插入尾部位置的元素并改变元素的实际总数量。

ensureCapacityInternal

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //如果元素数量将超过数组长度  则需动态扩容
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

/** 数组扩容机制 **/
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity < minCapacity) {
        newCapacity = minCapacity;
    }
    if (newCapacity > MAX_ARRAY_SIZE) {
        newCapacity = minCapacity > MAX_ARRAY_SIZE ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }
    elementData = Arrays.copyOf(elementData, newCapacity);
}

先判断需要保证的元素数量是否大于elementData数组的长度，如果大于，则需要将elementData数组进行扩容。
在扩容时，先设置数组长度newCapacity为原数组长度的1.5倍，然后判断需要保证的元素数量是否大于newCapacity新数组的长度，若仍然不够，则直接设置newCapacity为需要保证的元素数量。
然后将新数组长度newCapacity与常量最大数组长度对比，最后通过Arrays.copyOf方法进行扩容。

add(int index, E e)

/** 在指定位置添加元素 **/
@Override
public void add(int index, E e) {
    rangeCheckForAdd(index);
    //确保数组容量
    ensureCapacityInternal(size + 1);
    //将插入位置后的所有元素往后移
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = e;
    size ++;
}

先判断index是否越界，然后通过ensureCapacityInternal方法保证elementData数组拥有足够的容量。
然后将index之后的所有元素往后移动。
最后插入index位置的值，并改变元素的实际总数量。

addAll(Collection<? extends E> c)

/** 往当前集合中添加集合c **/
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);
    //将数组a中所有元素copy到elementData中
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

先将集合c转换为Object数组a，并取出a的长度。
然后通过ensureCapacityInternal方法保证elementData数组拥有足够的容量。
将数组a复制到elementData数组的后面并改变元素的实际总数量。

addAll(int index, Collection<? extends E> c)

/** 在当前集合中的index位置添加集合c **/
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);
    //将index后面所有元素往后移动
    System.arraycopy(elementData, index, elementData, index + numNew, size - index);
    //将数组a中元素插入到elementData的index位置
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

相比addAll(Collection<? extends E> c)方法仅多一步，将index后面所有元素往后移动

元素的移除

元素移除主要有以下五个方法

void clear()
E remove(int index)
boolean remove(Object o)
boolean removeAll(Collection<?> c)
boolean retainAll(Collection<?> c)

clear()

/** 清空当前集合中所有元素 **/
public void clear() {
    modCount ++;
    //将所有元素设置为null让GC回收掉
    for (int i = 0; i < size; i++) {
        elementData[i] = null;
    }
    size = 0;
}

将所有元素设置为null并设置size为0。

remove(int index)

/** 移除指定位置index元素 **/
@Override
public E remove(int index) {
    rangeCheck(index);
    //获取到旧的元素
    E oldValue = (E) elementData[index];
    //计算需要移动的元素
    int needMoveNum = size - index - 1;
    if (needMoveNum > 0) {
        //将移除位置后的所有元素往前移
        System.arraycopy(elementData, index + 1, elementData, index, needMoveNum);
    }
    //将数组最后一个元素置为null
    elementData[--size] = null;
    return oldValue;
}
/** 检测数组是否越界 **/
private void rangeCheck(int index) {
    if (index >= size || index < 0) {
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
    }
}

先检测元素是否越界，然后根据索引获取到原有元素oldValue。
数组移除时，需要将index后面的元素往前移动一位，所以先根据移除元素的位置计算出需要移动元素的个数needMoveNum，如果大于0就通过System.arraycopy方法移动。
然后将最后一个元素设置为null，返回原有元素oldValue。

remove(Object o)

/** 移除指定元素o **/
@Override
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;
}
/** 相比remove(int index)方法，不需要检测数组越界和返回旧元素 **/
private void fastRemove(int index) {
    modCount++;
    //计算需要移动的元素
    int needMoveNum = size - index - 1;
    if (needMoveNum > 0) {
        //将移除位置后的所有元素往前移
        System.arraycopy(elementData, index + 1, elementData, index, needMoveNum);
    }
    //将数组最后一个元素置为null
    elementData[--size] = null;
}

如果指定的元素o是null,则循环找到一个为null的元素并移除。
否则循环数组元素，通过equals方法找到元素并移除。

removeAll(Collection<?> c)

/** 从当前集合中移除集合c中所有的元素 **/
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

retainAll(Collection<?> c)

/** 只保留当前集合与指定集合c中都存在的元素 **/
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }

batchRemove(Collection<?> c, boolean complement)

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++) {
            //判断是保留相同的还是保留不同的
            if (c.contains(elementData[r]) == complement) {
                elementData[w++] = elementData[r];
            }
        }
    } finally {
        //正常情况下 r和size是相等的  如果抛出异常 则将剩余未比较的复制到elementData中
        if (r != size) {
            System.arraycopy(elementData, r, elementData, w, size - r);
            w += size - r;
        }
        //如果有移除的数据，w和size是不相等的  此时将W之后的数据置空 让GC回收掉
        if (w != size) {
            for (int i = w; i < size; i++) {
                elementData[i] = null;
            }
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return  modified;
}

元素的查询

get(int index)

/** 查询元素 **/
@Override
public E get(int index) {
    //检查索引是否越界
    rangeCheck(index);
    //返回数组指定位置的元素
    return elementData(index);
}

判断数组是否越界
返回指定位置的数组元素即可。

elementData(int index)

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

元素的修改

set(int index, E e)

/** 更改元素 **/
@Override
public E set(int index, E e) {
    rangeCheck(index);
    //查询原有元素
    E oldValue = (E) elementData[index];
    //设置为最新元素
    elementData[index] = e;
    return oldValue;
}

先判断数组是否越界
获取到旧的元素
将当前位置设置为新的元素
返回旧元素。

总结

ArrayList底层主要通过Object数组elementData实现
ArrayList初始化容量为10，扩容时每次增加至原来的1.5倍
查询更新操作时最简单，通过数组下标可快速定位元素位置进行操作
添加删除时由于需要移动后面的元素位置，所以会更加耗时；移动元素位置时主要通过System.arraycopy方法实现

看完上述内容，你们对如何用源码分析ArrayList有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注亿速云行业资讯频道，感谢大家的支持。