ArrayList源码学习

路行的亚洲

发布于 2020-07-17 16:17:49

4070

发布于 2020-07-17 16:17:49

ArrayList是一种以数组实现的列表，而数组的优势在于有角标，因此查询的速度较快，是一种可以动态扩容的数组。我们着重了解添加、获取、替换、删除操作。

1.相关变量信息

//默认初始化容量为10
private static final int DEFAULT_CAPACITY = 10;

//为空数组实例准备一个空数组{}
private static final Object[] EMPTY_ELEMENTDATA = {};

//默认容量空元素数据，添加数组是会重新分配容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//元素数据，存放元素的数组，重要，操作数据用的都是它
transient Object[] elementData; // non-private to simplify nested class access
 
 //ArrayList大小
 private int size;

2.构造函数

//构造一个空的带特定初始化容量的list
public ArrayList(int initialCapacity) {
    //如果初始化容量>0，创建一个带特定容量的数组
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    //如果初始化容量为0，空元素数组
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //否者抛异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

//构造一个空列表同时带有初始化容量0，默认初始化容量
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//将传入集合的元素初始化到ArrayList中
public ArrayList(Collection<? extends E> c) {
    //集合转数组
    elementData = c.toArray();
    //如果长度不为0
    if ((size = elementData.length) != 0) {
        /**
         * 如果c.toArray()不是数组的话，
         * 采用arrays中的方法copyOf(U[] original, int newLength, Class<? extends T[]> newType)
         * 将其转成数组
         **/
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //否者size=0,将c.toArray()替换成空数组
        this.elementData = EMPTY_ELEMENTDATA;
     }
  }

3.方法

(1)元素添加操作

添加元素：我们可以思考，如果让你添加元素，你会考虑什么？第一考虑容量是否充足，第二是进行元素的添加。

public boolean add(E e) {
    //确保容量够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //进行元素添加
    elementData[size++] = e;
    return true;
}

 //进行容量确保是否够，不够则进行扩容
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

 //计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果数组为空，则直接返回默认容量
    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.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果新容量比需要的容量小，则将新容量变为需要容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果新容量比最大容量，则使用最大容量
    // MAX_VALUE=>@Native public static final int   MAX_VALUE = 0x7fffffff;  //2^31-1
    //private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; =>2^31-9
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //将数据转移到新的数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

添加元素到指定位置

//添加元素到指定位置
public void add(int index, E element) {
    //检查index索引是否越界
    rangeCheckForAdd(index);

    //看容量是否够，确保容量够用
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    /**
     * public static native void arraycopy(
     *          Object src,  int  srcPos,Object dest, int destPos,int length);
     * 进行数据拷贝，这样做的目的是为了将index的位置空出来，添加元素
     */
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //在index位置添加元素
    elementData[index] = element;
    //list长度+1
    size++;
}

进行addAll操作：

//将集合c中所有元素添加到当前ArrayList中
public boolean addAll(Collection<? extends E> c) {
    //将传入的集合转换为数组
    Object[] a = c.toArray();
    //获取集合转成数组之后的长度
    int numNew = a.length;
    //看容量是否够
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //将c中元素拷贝到arraylist中
    System.arraycopy(a, 0, elementData, size, numNew);
    //长度+添加元素长度
    size += numNew;
    return numNew != 0;
}

进行addAll操作添加元素到指定位置：

//将集合c中所有元素添加到当前ArrayList中
public boolean addAll(Collection<? extends E> c) {
    //将传入的集合转换为数组
    Object[] a = c.toArray();
    //获取集合转成数组之后的长度
    int numNew = a.length;
    //看容量是否够
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //将c中元素拷贝到arraylist中
    System.arraycopy(a, 0, elementData, size, numNew);
    //长度+添加元素长度
    size += numNew;
    return numNew != 0;
}

进行addAll操作添加元素到指定位置：

//将集合c中所有元素添加到当前ArrayList中
public boolean addAll(int index, Collection<? extends E> c) {
    //检查是否越界
    rangeCheckForAdd(index);
    //将传入的集合c转成数组
    Object[] a = c.toArray();
    //获取长度
    int numNew = a.length;
    //进行容量检查，如果容量不够，则进行扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //需要移动的元素个数
    int numMoved = size - index;
    //如果需要移动的个数大于0，则需要移动元素，并进行添加操作，size加上移动的数量
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    //将元素拷贝到index位置
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

默认的初始容量为10。是否需要扩容，会先计算容量。如果数组为空，则直接返回默认容量10。如果需要容量>数组长度，则进行扩容。如果需要容量比老容量要大，则需要进行扩容1.5倍，采用位运算实现，也就是15。如果新容量比最大容量大，则采用默认的最大容量,为2^31-9。最后将数据转移到新的数组中。而添加元素到指定位置，会先检查是否越界，接着会看容量是否够，不够，则进行扩容，接着进行数据拷贝，空出index位置，将元素放入到指定的index位置，同时size+1。

(2)get操作

获取指定位置的元素

public E get(int index) {
    //检查是否越界
    rangeCheck(index);
    //返回指定位置元素
    return elementData(index);
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    //获取元素
    return (E) elementData[index];
}

(3)替换操作

//在特定位置替换你想要替换的元素
public E set(int index, E element) {
    //检查越界
    rangeCheck(index);
    //获取老的元素
    E oldValue = elementData(index);
    //将其替换成新的元素
    elementData[index] = element;
    //返回老的值
    return oldValue;
}

(4)删除操作

删除特定元素操作

//删除特定的元素
public E remove(int index) {
    //检查index是否越界
    rangeCheck(index);

    modCount++;
    //获取要删除的值
    E oldValue = elementData(index);
    //需要进行移动数据的个数
    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
    //返回要删除的值
    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 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
    }

删除包含和特定元素相同的所有元素，类似求差集

//删除包含c集合的元素
public boolean removeAll(Collection<?> c) {
    //进行非空校验
    Objects.requireNonNull(c);
    //不为空，执行批量删除操作
    return batchRemove(c, false);
}

//进行批量删除操作
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    //采用双指针 r是读指针，w是写指针
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            //如果集合c中包含元素，如果是true，则true==true则进行写入
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        //保留与AbstractCollection的行为兼容性，
        // 即使c.contains（）抛出异常也是如此。
        if (r != size) {
            //如果c.contains()抛出了异常，则把未读的元素都拷贝到写指针之后
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            //将写指针之后的元素置置空，方便GC操作
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

删除包含c集合的元素：首先这里采用了双指针的方法。类似元素匹配。删除不包含c集合的所有元素，类似求交集

//移除不包含特定元素的所有的元素
public boolean retainAll(Collection<?> c) {
    //非空校验
    Objects.requireNonNull(c);
    //进行批量删除操作
    return batchRemove(c, true);
}

因此我们可以得到以下信息：

从操作上看，我们可以知道其实际上是在操作数组，而操作完之后将其采用arrayCopy的方式放入到arrayList中。同时我们可以知道其默认容量是10，如果不够的时候，会进行扩容，每次都是扩容成原来的1.5倍，采用位运算（右移动一位）进行扩容。

其进行添加元素的时候，会首先进行越界校验，如果没有越界才继续进行操作。接着查看容量是否够，不够的话，进行扩容操作，而扩容操作是在grow()方法中进行的。同时如果容量大于规定的最大容量2^31-9时，会默认为最大容量。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-02-27，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自后端技术学习微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度