阅读 274

Java集合框架分析(二)ArrayList分析

相关文章 Java集合框架分析(一)综合概述

本篇文章主要分析一下 Java 集合框架中的 List 部分,ArrayList,该源码分析基于JDK1.8,分析工具,AndroidStudio,文章分析不足之处,还请指正!

ArrayList简介

ArrayList 底层维护的是一个动态数组,每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素,其容量也自动增长。ArrayList 不是同步的(也就是说不是线程安全的,同 HashMap、LinkedHashMap 一样),如果多个线程同时访问一个 ArrayList 实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步,在多线程环境下,可以使用 Collections.synchronizedList 方法声明一个线程安全的 ArrayList,例如:

List arraylist = Collections.synchronizedList(new ArrayList());
复制代码

源码分析

类结构定义

首先我们来看一下关于ArrayList的类结构,

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

上面是是 ArrayList 类的定义,它继承了抽象类 AbstractList,但是真正继承的方法只有 equals 和 hashCode,别的方法在 ArrayList 中都有自己的重新实现;List 接口在 AbstractList 中已经实现,这里是为了表明一下,没有太大含义;RandomAccess 没有方法,表明 ArrayList 支持快速随机访问;实 现了 Cloneable 接口,以指示 Object.clone() 方法可以合法地对该类实例进行按字段复制,如果在没有实现 Cloneable 接口的实例上调用 Object 的 clone 方法,则会导致抛出 CloneNotSupportedException 异常;类通过实现 java.io.Serializable 接口以启用其序列化功能,未实现此接口的类将无法使其任何状态序列化或反序列化

变量定义

接着我们分析一下 ArrayList 定义的变量。

//序列化ID
private static final long serialVersionUID = 8683452581122892189L;
//数组初始容量大小
private static final int DEFAULT_CAPACITY = 10;
//
private static final Object[] EMPTY_ELEMENTDATA = {};
//elementData存储ArrayList内的元素
transient Object[] elementData;
//存储在ArrayList内的元素的数量
private int size;
复制代码

构造函数

//设定初始容量大小的构造函数
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    //数组初始化
    this.elementData = new Object[initialCapacity];
}
//无参数构造函数
public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}
//将提供的集合转成数组返回给elementData(返回若不是Object[]将调用Arrays.copyOf方法将其转为Object[])
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}
复制代码

构造函数还是比较简单的,我们来看看 ArrayList 的最常用的方法 add,

Add(E e)添加数据

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
复制代码

发现 ArrayList 的 add 方法,只有简单的两行代码,粗略的看一下是在数组 elementData 的尾部添加一个元素 E,那么到底是怎么样操作的呢?我们详细查看一下源码,首先进入 ensureCapacityInternal 方法中一探究竟。看这个方法的名字就大概知道这是确保数组容量的,怎么个确保法呢?

private void ensureCapacityInternal(int minCapacity) {
    //当我们调用ArrayList的无参构造函数时调用此代码
    if (elementData == EMPTY_ELEMENTDATA) {
        //设置数组容量为10,默认的大小
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //
    ensureExplicitCapacity(minCapacity);
}
//确保容量大小,modCount自增,并判断数组大小是否足够,不够的话将增大数组
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //如果最小需要空间比elementData的内存空间要大,则需要扩容  
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
复制代码

到了这里还是有点模糊到底怎么数组扩容的?我们接着看 grow 的方法

//扩容并重新copy一份数组
private void grow(int minCapacity) {

        // oldCapacity为当前数组大小  
        int oldCapacity = elementData.length;
        // newCapacity为新容量的大小等于旧容量的1.5倍大小
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩充后的容量还是比最少需要的容量还要小的话,就设置扩充容量为最小需要的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //判断最新的容量是否已经超出最大数组范围,溢出判断
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
            
        // 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间  
    // 并将elementData的数据复制到新的内存空间  
        elementData = Arrays.copyOf(elementData, newCapacity);
}
复制代码

我们总结一下 add 操作的过程,首先我们先要判断是否需要扩容,在扩容判断里面,我们主要进行一些判断,如果当前所需要的容量和当前数组的容量进行比较,如果不够的话则进行扩容,在扩容的同时则需要判断是否溢出了,然后将旧的数据数组进行 copy 到新的容量大小的数组中,最后再将需要添加的数据添加到数组的最后一位。

我们接着分析 add 的另一个方法,重载 add(int index, E element) 方法,

//在指定的位置上面插入一个数据
 public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //判断是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //需要将指定位置及其后面数据向后移动一位,然后在位置上面插入数据
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //插入数据
        elementData[index] = element;
        //大小改变
        size++;
    }
复制代码

中心思想就是,首先判断指定位置 index 是否超出 elementData 的界限,之后调用 ensureCapacity 调整容量(若容量足够则不会拓展),调用 System.arraycopy 将 elementData 从 index 开始的 size-index 个元素复制到 index+1 至 size+1 的位置(即 index 开始的元素都向后移动一个位置),然后将 index 位置的值指向 element,同时改变数组的大小。

addAll 方法

接着我们分析一下 addAll 方法。

public boolean addAll(Collection<? extends E> c) {
       Object[] a = c.toArray();
       int numNew = a.length;
       ensureCapacityInternal(size + numNew);  // Increments modCount
       //将a的第0位开始拷贝至elementData的size位开始,拷贝长度为numNew 
       System.arraycopy(a, 0, elementData, size, numNew);
       size += numNew;
       return numNew != 0;
   }
复制代码

其实这个方法很好理解,首先将批量添加的数据转为数组,然后获取它的容量大小,判断一下,如果我们要在数组中插入这一批数据的话,是否需要扩容,经过这个扩容判断操作,我们的数组容量是足够了,然后我们开始批量导入数据,其中 System.arraycopy(a, 0, elementData, size, numNew) ;意思就是,将需要导入的批数据从 0 开始,导入到数组从 size 位置开始,导入的大小数量就是需要导入的数量。这个时候,总的数组容量就变成了原先的容量加上导入的容量了。

addAll 还有一个重载方法,我们也来看看:

public boolean addAll(int index, Collection<? extends E> c) {
        //判断插入的位置是否越界
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }
复制代码

这个方法其实在 add 的方法基础上面修改而来,复制数组的时候主要进行两步复制,第一步,现将原数组在指定的位置上面向后移动需要的位数,然后第二步再将需要导进去的数据从 index 位置复制进去。

get方法

分析完了 add 方法,我们来分析分析 get 方法内容,get 方法也是比较简单的

public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        return (E) elementData[index];
    }
复制代码

首先判断需要返回的位置是否越界了,其次直接返回数组对应索引里面的值。非常简单,我们再看看其他方法。

其余方法

remove(int index)

我们来看看 remove 方法

public E remove(int index) {
      if (index >= size)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
      modCount++;
      //保存一下需要删除的数据
      E oldValue = (E) 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;
  }
复制代码

同理,因为涉及到数组的问题,所以首先需要判断一下是否出现越界的问题,然后就开始将指定删除位置后面的数据都向前移动一位,然后将最后的一位设置为 null,最后返回删除的数据。

删除一个数据,remove 也有重载方法

remove(Object o)

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;
    }
复制代码

删除一个数据,主要是遍历数组,看看数组中是否存在这个数据,如果存在的话则进行fastRemove,我们进入 fastRemove 中看看

fastRemove(int index)

//删除指定位置上面的数据
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
}
复制代码

将指定位置 index 后面的数据全部向前移动一位,最后将最后一位回收掉。

另外我们看下全部删除数组中的数据方法 clear

clear

public void clear() {
        modCount++;
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }
复制代码

将数组中所有的数据都重置为 null,等带回收。

removeRange(int fromIndex, int toIndex)

protected void removeRange(int fromIndex, int toIndex) {

    if (toIndex < fromIndex) {
        throw new IndexOutOfBoundsException("toIndex < fromIndex");
    }
    modCount++;
    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;
}
复制代码

执行过程是将 elementData 从 toIndex 位置开始的元素向前移动到 fromIndex,然后将 toIndex 位置之后的元素全部置空顺便修改 size。

set(int index, E element)

public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }
复制代码

这个方法很简单,就是修改数组 index 里面的数据,并返回旧的数据。

indexOf(Object o)

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++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
复制代码

返回在数组中第一次出现的值。如果找到这个值的话就返回 index,找不到就返回-1。

trimToSize()

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = Arrays.copyOf(elementData, size);
    }
}
复制代码

由于 elementData 的长度会被拓展,size 标记的是其中包含的元素的个数。所以会出现 size 很小但 elementData.length 很大的情况,将出现空间的浪费。trimToSize 将返回一个新的数组给elementData,元素内容保持不变,length 跟 size 相同,节省空间。

总结

以上便是 ArrayList 的源码内容,总的来说不是很难,接下来我们来总结一下关于 ArrayList 的方方面面。

ArrayList 底层是基于数组来实现的,可以通过下标准确的找到目标元素,因此查找的效率高;但是添加或删除元素会涉及到大量元素的位置移动,效率低。

ArrayList 提供了三种不同的构造方法,无参数的构造方法默认在底层生成一个长度为 10 的 Object 类型的数组,当集合中添加的元素个数大于 10,数组会自动进行扩容,即生成一个新的数组,并将原数组的元素放到新数组中。

ensureCapacity 方法对数组进行扩容,它会生成一个新数组,长度是原数组的 1.5 倍 +1,随着向 ArrayList 中不断添加元素,当数组长度无法满足需要时,重复该过程。

ArrayList 不是同步的(也就是说不是线程安全的,同 HashMap、LinkedHashMap 一样),如果多个线程同时访问一个 ArrayList 实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步,在多线程环境下,可以使用 Collections.synchronizedList 方法声明一个线程安全的 ArrayList,例如:List arraylist = Collections.synchronizedList(new ArrayList());

关于作者

专注于 Android 开发多年,喜欢写 blog 记录总结学习经验,blog 同步更新于本人的公众号,欢迎大家关注,一起交流学习~

在这里插入图片描述

关注下面的标签,发现更多相似文章
评论