你的位置:首页 > Java教程

[Java教程]Java源码分析之ArrayList

ArrayList是以数组为基准的容器类,和LinkedList(链表)正好相反。因而ArrayList拥有更好的查找性能,增删操作则差一些。ArrayList封装了对于常规数组的操作,同时可以自动扩展容量。

下面对ArrayList的API进行归类:

1、构造函数:

①ArrayList()  以空数组进行构造  

②ArrayList(int) 以指定大小的容量初始化数组

③ArrayList(Collection)  以指定集合构造ArrayList的数组元素

2、增加元素:

①boolean add(E)  在数组末尾加入指定元素

②void add(int,E)  在第一个参数指定的索引处插入元素,后面所有元素后移一个位置

③boolean addAll(Collection)  在数组末尾加入集合的所有元素

④boolean addAll(int,Collection) 在指定索引处加入集合所有元素

3、删除元素:

①E remove(int)  移除索引处元素,之后的所有元素前移一位

②boolean remove(Object)  查找到指定元素,删除之,未删除成功false

③void removeRange(int,int) 删除指定区间的所有元素,删除第一个索引处,但不删除最后一个索引处

④void clear()  删除所有元素

4、更改元素:

 set(int,Object)  将指定索引处的值修改为指定的值

5、查找:

①E get(int)  返回指定索引处的元素

②boolean contains(Object)  确定是否包含该元素

③int indexOf(Object)  从前往后查找指定元素的索引,找不到返回-1

④int lastIndexOf(Object)  从后往前查找元素索引,找不到返回-1

⑤int size()  返回包含的元素个数

⑥boolean isEmpty()  确定数组是否为空

6、其他操作:

①Object[] toArray()  返回Object数组,每个Object对应ArrayList的一个元素

②T[] toArray(T[])  返回T类型数组,每个T对应ArrayList的一个实际类型的元素

③void trimToSize()  删除数组最后冗余的值为null的元素

④void ensureCapacity(int)  使数组容量扩充为指定的容量

⑤Object clone()    复制一个除了内存地址其他信息完全一样的ArrayList

 

接下来进行源码解析

一、ArrayList包含的成员变量和常量:

transient Object[] array;  //ArrayList的核心,所有操作都围绕它展开,ArrayList类似于数组的包装类int size;  //数组包含的实际元素个数,不是数组容量,为了满足添加元素时数组不必多次扩容,必须预先将容量设定为某个略大些的值。这样就不能用array.length得到元素个数了

 

二、构造函数3种

  //不给参数,用空数组初始  public ArrayList() {    array = EmptyArray.OBJECT;  }

  //用一个已有的容器对象初始化数组
  public ArrayList(Collection<? extends E> collection) { if (collection == null) { throw new NullPointerException("collection == null"); } Object[] a = collection.toArray(); if (a.getClass() != Object[].class) {//这个过程看不懂 Object[] newArray = new Object[a.length]; System.arraycopy(a, 0, newArray, 0, a.length); //数组复制操作 a = newArray; } array = a; size = a.length; }

  //用指定初始容量初始化数组,当容量可以确定的时候用这个方法可以避免多次更改数组大小,提高性能  public ArrayList(int capacity) {    if (capacity < 0) {      throw new IllegalArgumentException("capacity < 0: " + capacity);    }    array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);  }

  三、增加元素

  这应该是ArrayList中最复杂的操作了,因为涉及到容量扩充的操作,也是ArrayList和数组最大的区别——自动扩容。但是因为涉及到重新分配内存空间和数组整个复制,多次扩容会影响性能

 

  @Override   public boolean add(E object) {    Object[] a = array;    //用一个代表,减少书写量    int s = size;    if (s == a.length) {  //数组已满,必须先扩容    //注意这边的扩容策略,必须先开辟一片更大的内存空间,再执行数组复制操作    //具体新数组取多大,如果当前容量小于最小容量增长值的一半,则按这个值增长;否则即原来容量足够大,在原来容量基础上增加一半      Object[] newArray = new Object[s +          (s < (MIN_CAPACITY_INCREMENT / 2) ?           MIN_CAPACITY_INCREMENT : s >> 1)];      System.arraycopy(a, 0, newArray, 0, s); //数组复制操作      array = a = newArray;    }    a[s] = object;  //现在容量足够了,在新数组末尾直接加上这个新元素    size = s + 1;  //别忘了现在元素个数加了一个,必须保持同步    modCount++; //修改次数加1    return true;  }

 

  //对上面的扩容操作进行了抽象,可能因为上面的操作更频繁,所以直接把扩容操作写在代码里面以提高性能吧  private static int newCapacity(int currentCapacity) {    int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?        MIN_CAPACITY_INCREMENT : currentCapacity >> 1);    return currentCapacity + increment;  }    //在指定位置插入,除了数组复制操作的范围不同,其他都一样  @Override   public void add(int index, E object) {    Object[] a = array;    int s = size;    if (index > s || index < 0) {      throwIndexOutOfBoundsException(index, s);    }    if (s < a.length) {      System.arraycopy(a, index, a, index + 1, s - index);    } else {      // assert s == a.length;      Object[] newArray = new Object[newCapacity(s)];      System.arraycopy(a, 0, newArray, 0, index);      System.arraycopy(a, index, newArray, index + 1, s - index);      array = a = newArray;    }    a[index] = object;    size = s + 1;    modCount++;  }

 

四、删除元素

 

  //这里数组相比链表的劣势就很明显了,删除指定位置的值很简单,但是为了保持后面操作的稳定性,必须将之后的所有值前移一个位置,需要O(n)的时间,而链表只要O(1)。  //这里得到一个很重要的启示:如果要移除多个连续的元素,用for循环配合这个方法会非常损耗性能,应该用下面的removeRange方法  @Override   public E remove(int index) {    Object[] a = array;    int s = size;    if (index >= s) {      throwIndexOutOfBoundsException(index, s);    }    @SuppressWarnings("unchecked")    E result = (E) a[index];  //因为每个元素都是Object类型,必须强转    System.arraycopy(a, index + 1, a, index, --s - index);    a[s] = null; // 防止内存占用过多,不用的值置为null,给系统及时回收    size = s;    modCount++;    return result;  }  //移除连续区间的元素,只需执行一次arrayCopy操作  @Override protected void removeRange(int fromIndex, int toIndex) {    if (fromIndex == toIndex) {      return;    }    Object[] a = array;    int s = size;    if (fromIndex >= s) {      throw new IndexOutOfBoundsException("fromIndex " + fromIndex          + " >= size " + size);    }    if (toIndex > s) {      throw new IndexOutOfBoundsException("toIndex " + toIndex          + " > size " + size);    }    if (fromIndex > toIndex) {      throw new IndexOutOfBoundsException("fromIndex " + fromIndex          + " > toIndex " + toIndex);    }    System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);    int rangeSize = toIndex - fromIndex;    Arrays.fill(a, s - rangeSize, s, null);  //不用的索引处全部置null    size = s - rangeSize;    modCount++;  }  //需要依次对每一个元素进行比较,性能也不好  //可以看出这个方法只会删除第一个出现的元素,如果存在equals比较后相同的元素,还有遗留  @Override   public boolean remove(Object object) {    Object[] a = array;    int s = size;    if (object != null) {      for (int i = 0; i < s; i++) {        if (object.equals(a[i])) {          System.arraycopy(a, i + 1, a, i, --s - i);          a[s] = null; // Prevent memory leak          size = s;          modCount++;          return true;        }      }    } else {      for (int i = 0; i < s; i++) {        if (a[i] == null) {          System.arraycopy(a, i + 1, a, i, --s - i);          a[s] = null; // Prevent memory leak          size = s;          modCount++;          return true;        }      }    }    return false;  } 

 

  //这里可以看出是通过将每个元素依次置为null,也需要O(n)时间;并不改变数组容量  @Override   public void clear() {    if (size != 0) {      Arrays.fill(array, 0, size, null);      size = 0;      modCount++;    }  }

 五、修改元素值

  //修改元素值很简单,跟数组操作一样,只要O(1)时间就能完成,同时返回被修改的旧值  @Override   public E set(int index, E object) {    Object[] a = array;    if (index >= size) {      throwIndexOutOfBoundsException(index, size);    }    @SuppressWarnings("unchecked")     E result = (E) a[index];    a[index] = object;    return result;  }  

六、查找操作

  //查找操作是ArrayList最大的优势,因为数组在内存中占用连续的存储区域,只要O(1)时间就能找到指定索引所对应的值  @SuppressWarnings("unchecked")   @Override   public E get(int index) {    if (index >= size) {      throwIndexOutOfBoundsException(index, size);    }    return (E) array[index];  }

 

七、其他操作

  关于ArrayList向数组转换(其实是返回ArrayList的成员数组的拷贝)

 

  /*这两个方法经常会搞混,包括我初学的时候也不知道是怎么回事。第一种方法貌似很简单,但是因为返回的是Object数组,后续如果要对这个返回的数组操作一般要转换为具体的类型,就还要对该数组的每个元素都强转一次。而第二个方法传入一个给定的数组,这个数组是指定了具体的类型的,因而返回后这个数组可以直接用。通常传入一个空数组 new T[]{}即可。  */  @Override   public Object[] toArray() {    int s = size;    Object[] result = new Object[s];    System.arraycopy(array, 0, result, 0, s);    return result;  }  /*这里有一点让我不明白,为什么泛型要选择T而不是E?如果T和E不一致,arraycopy操作会成功吗?*/  @Override   public <T> T[] toArray(T[] contents) {    int s = size;    if (contents.length < s) { //如果提供的数组不够放,重新开辟内存      @SuppressWarnings("unchecked")       T[] newArray        = (T[]) Array.newInstance(contents.getClass().getComponentType(), s);      contents = newArray;    }    System.arraycopy(this.array, 0, contents, 0, s);    if (contents.length > s) {      contents[s] = null;  //这里也让我不明白,为什么只把s处置为null,s以后的不也应该置为null吗?    }    return contents;  }