导航：首页 > 互联网科技 >

如何用源码分析ArrayList

发表于：2024-10-21 作者：千家信息网编辑

千家信息网最后更新 2024年10月21日，今天就跟大家聊聊有关如何用源码分析ArrayList，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。成员变量/** ArrayList的初始化容

千家信息网最后更新 2024年10月21日如何用源码分析ArrayList

今天就跟大家聊聊有关如何用源码分析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 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 c)
boolean addAll(int index, Collection c)

add(E e)

/** 添加元素 **/@Overridepublic 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)

/** 在指定位置添加元素 **/@Overridepublic 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 c)

/** 往当前集合中添加集合c **/public boolean addAll(Collection 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 c)

/** 在当前集合中的index位置添加集合c **/public boolean addAll(int index, Collection 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 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元素 **/@Overridepublic 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 **/@Overridepublic 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)

/** 查询元素 **/@Overridepublic 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)

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