首页 > 代码库 > Java集合-ArrayList

Java集合-ArrayList

一、ArrayList是什么?

  ArrayList是实现List接口的动态数组,所谓动态是指它的大小是可变的。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。

  既然是数组,肯定就有容量。每个ArrayList对象都有一个容量,该容量是用来表示可以存放多少个数据在里面,即是数组的大小(默认是10)。当然,动态的肯定就会自动增加,每次我们往里面添加数据的时候,它都会进行扩容检查,检查完扩容会扩大为原来的1.5倍,扩容操作带来数据向新数组的重新拷贝,影响性能,所以如果我们知道具体业务数据量,在构造ArrayList时可以给ArrayList指定一个初始容量,这样就会减少扩容时数据的拷贝问题。当然在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量。

  ArrayList的底层实现是不同步,多线程操作会出现问题,这一点大家要注意。可以插入重复数据,可以插入Null。

二、ArrayList源码分析

  2.1、ArrayList定义

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

    ArrayList的定义,继承AbstractList,实现List<E>, RandomAccess, Cloneable, java.io.Serializable,其中AbstractList实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换。RandomAccess代表该类是否支持 随机访问,Cloneable类支持克隆,Serializable支持序列化。

  2.2、底层使用数组

    private static final long serialVersionUID = 8683452581122892189L;//serialVersionUID作用是序列化时保持版本的兼容性,即在版本升级时反序列化仍保持对象的唯一性。

    private transient Object[] elementData;//Object数组,transient关键字不知道的同学自己查资料去,带transient关键字的变量不会序列化。ArrayList容器,基本操作都是基于该数组进行操作的。

    private int size;//数组的大小。

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//要分配的数组的最大大小。

  2.3、构造函数   

    ArrayList有三个构造函数:

    ArrayList():默认构造函数,提供初始容量为10的空列表。

    ArrayList(int initialCapacity):构造一个具有指定初始容量的空列表。

    ArrayList(Collection<? extends E> c):构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

技术分享

  /**
     * 构造具有指定初始容量的空列表。.
     *
     * @param  初始容量列表的初始容量
     * @throws IllegalArgumentException 如果指定的初始容量为负会抛出非法异常。     */
    public ArrayList(int initialCapacity) {        super();        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);        this.elementData = new Object[initialCapacity];
    }    /**
     * 构建一个初始容量为十的空列表.     */
    public ArrayList() {        this(10);
    }    /**
     * 构造包含指定元素的列表。
     * 集合,按集合返回的顺序
     * 迭代器
     *
     * @param c的集合,其元素将放在这个列表中。
     * @throws NullPointerException 如果指定的集合为null为抛出这个空指针异常。     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();//如果为空,这里会抛异常
        size = elementData.length;        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

技术分享

  2.4、add方法  

    ArrayList提供了add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)、set(int index, E element)这个五个方法来实现ArrayList增加。

我就拿一个来讲了,懂的一个,其他应该都懂了。  

技术分享

  public boolean add(E e) {
        ensureCapacityInternal(size + 1);  //增加操作次数
        elementData[size++] = e;//把值放到最后一位
        return true;
  }
  private void ensureCapacityInternal(int minCapacity) {
        modCount++;        // overflow-conscious code
        if (minCapacity - elementData.length > 0)//如果数组真实存储大于数组容量就增加            grow(minCapacity);
  }
  private void grow(int minCapacity) {        // overflow-conscious code
        int oldCapacity = elementData.length;//原来的容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);//新的容量为旧的1.5倍
        if (newCapacity - minCapacity < 0)//增加了还小就按真实的来
            newCapacity = 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);//复制数组
 } private static int hugeCapacity(int minCapacity) {//注意是个静态方法
        if (minCapacity < 0) // overflow   小于0,抛异常
            throw new OutOfMemoryError();        return (minCapacity > MAX_ARRAY_SIZE) ?//大于MAX_ARRAY_SIZE就设置为MAX_VALUE,否则就MAX_ARRAY_SIZE            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

技术分享

  2.5、remove方法

    ArrayList提供了remove(int index)、remove(Object o)、removeRange(int fromIndex, int toIndex)、removeAll()四个方法进行元素的删除。

    remove(int index):移除此列表中指定位置上的元素。

技术分享

  public E remove(int 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; // 让GC工作
        return oldValue;//返回旧值  }
  private void rangeCheck(int index) {//检查越界
        if (index >= size)            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }
  private String outOfBoundsMsg(int index) {//是不是感觉经常空间这个,哈哈
        return "Index: "+index+", Size: "+size;
  }
  @SuppressWarnings("unchecked")
  E elementData(int index) {        return (E) elementData[index];
  }

技术分享

    remove(Object o):如果存在移除此列表中首次出现的指定元素。

技术分享

  public boolean remove(Object o) {        if (o == null) {//如果为null
            for (int index = 0; index < size; index++)                if (elementData[index] == null) {//==来比较                    fastRemove(index);                    return true;//存在并删除返回true                }
        } else {//如果不为null
            for (int index = 0; index < size; index++)                if (o.equals(elementData[index])) {//equals来比较
                    fastRemove(index);//存在并删除返回true
                    return true;
                }
        }        return false;//不存在返回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; // Let gc do its work  }

技术分享

  2.6、get方法

   public E get(int index) {
        rangeCheck(index);//检查是否越界
        return elementData(index);//取值  }

  2.7、注意subList方法

技术分享

  public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<Integer>();
        list1.add(1);
        list1.add(2);        // 通过构造函数新建一个包含list1的列表 list2
        List<Integer> list2 = new ArrayList<Integer>(list1);        // 通过subList生成一个与list1一样的列表 list3
        List<Integer> list3 = list1.subList(0, list1.size());        // 修改list3
        list3.add(3);
        System.out.println(list1.size());
        System.out.println("list1 == list2:" + list1.equals(list2));
        System.out.println("list1 == list3:" + list1.equals(list3));

  }

技术分享

    上面一段代码我感觉大部人都会认为结果是2个false,list2是新构造的肯定与list1不一样,list3是截取的肯定也不一样。所以会认为都是false,我们深入subList去看看。

技术分享

public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);//检查下标和大小
        return new SubList(this, 0, fromIndex, toIndex);//新创建一个SubList对象,注意传入的是this,代表了要截取的对象}private class SubList extends AbstractList<E> implements RandomAccess {//我擦,跟list差不多的感觉private final AbstractList<E> parent;private final int parentOffset;private final int offset;int size;//我擦,熟悉的感觉SubList(AbstractList<E> parent,int offset, int fromIndex, int toIndex) {//刚刚的构造
            this.parent = parent;//this.parent = parent;而parent就是在前面传递过来的list,也就是说this.parent就是原始list的引用。
            this.parentOffset = fromIndex;            this.offset = offset + fromIndex;            this.size = toIndex - fromIndex;            this.modCount = ArrayList.this.modCount;//操作数也是跟原来的一样
}

技术分享

  原来sublist里面操作的是原来的list,并没有生成新的list,导致2个其实是一样的。

  所以上面正确的结果是:

  list1 == list2:false
  list1 == list3:true

三、ArrayList总结

  因为它是基于数组实现的,主要有如下特点:

  1、插入、删除比较慢,因为插入、删除需要移动数据位置。

  2、可以重复插入数据、可以插入null。

  3、查找比较快,可以直接使用下标。


Java集合-ArrayList