重新认识java-ArrayList
源码解读
ArrayList
的声明:
public class ArrayListextends AbstractList implements List , RandomAccess, Cloneable, java.io.Serializable
通过继承和实现关系,可以看出ArrayList
继承自抽象类AbstractList
,实现了接口List
, RandomAccess
, Cloneable
, java.io.Serializable
.
RandomAccess接口
从RandomAccess
的声明中可以看到,这只是一个类声明,没有函数和成员变量,那ArrayList
的声明中为什么要添加这个接口? 原来,List 实现所使用的标记接口,用来表明其支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。
接口
Clonable
,java.io.Serializable
也是同样的道理。通过重写 Object.clone() 方法来定制对其进行复制的细节,如果在没有实现 Cloneable 接口的实例上调用 Object 的 clone 方法,则会导致抛出CloneNotSupportedException
异常。java.io.Serializable
ArrayList的实现
常量
//list初始容量private static final int DEFAULT_CAPACITY = 10;
变量
/*** ArrayList中元素存储的地方,数组的长度就是它的容量* 不是私有的,方便嵌套类访问。后面提供了迭代类,需要访问*/transient Object[] elementData;/** *ArrayList所包含的元素的大小 */private int size;
构造方法
/** * 使用初始大小创建一个空的list * * @param initialCapacity list初始容量 * @throws IllegalArgumentException if the specified initial capacity * is negative */public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}public ArrayList(Collection c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}
第一种方法需要一个默认的容量大小; 第二个是默认的构造方法,会默认创建一个容量为10的 ArrayList ; 第三个则传给一个 Collection ,注意,不管 Collection 里面是什么类型,最后放进 ArrayList 都会上转为 Object
此处的bug问题,见下节。
核心方法
add
public boolean add(E e) { ensureCapacityInternal(size + 1); // 保证当元素的数量超过内部数组elementData的大小后,自动扩容。防止越界 elementData[size++] = e; return true;}
add 方法中使用了 ensureCapacityInternal 来控制容量:
private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity);//根据实际容量判断是不是要增加elementData容量}private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity);}
modCount
是用来记录 list被结构修改的次数,所谓结构上的修改是指任何添加或删除一个或多个元素的操作,或者显式调整底层数组的大小 ;仅仅设置元素的值不是结构上的修改;在上面的方法中,如果 minCapacity 大于现有数组长度,则执行 grow 方法:
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);//当增长到`newCapacity > MAX_ARRAY_SIZE`时,只能创建Integer.MAX_VALUE大小的数组,不能超过这个值 // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity);}
第二个add方法:
public void add(int index, E element) { rangeCheckForAdd(index); //确保插入的位置是在elementData大小范围内,不会越界。 ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++;}
主要使用了 System.arraycopy()
方法将 index 之后的元素向后移动一个位置,将 index 位空出来放入新元素
函数原型:
System.arraycopy(Object[] src, int srcPos, Object[] dest, int destPos, int length)
src: the source array. srcPos: starting position in the source array. dest: the destination array. destPos: starting position in the destination data. length: the number of array elements to be copied.
Clear
public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0;}
clear方法比较简单,但是也会使modCount+1。
只要添加或删除元素或者显示调用底层数组,都会修改modCount
clone
public Object clone() { try { ArrayList v = (ArrayList ) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); }}
clone 方法只能进行浅复制,并不复制元素本身,实际在内部调用的是Object的clone()。
remove
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; // clear to let GC do its work return oldValue;}
删除指定下标的元素的时候,只是将待删除后面的元素全部前移,而该元素在内存中的占用由JVM gc自动处理。
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; }
删除指定对象实例的时候,如果要移除的元素为 null ,则删除数组中第一个为 null 的元素。如果数组中有超过一个匹配的元素,仅移除第一个。
fastRemove(int index)
比remove(int index)
块在没做index关于elementData的边界检查。其余都是一样的。
toArray
public Object[] toArray() { return Arrays.copyOf(elementData, size);}
这个方法被很多方法使用,它调用了 Arrays 工具类中的方法 copyOf
:
public staticT[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass());}public static T[] copyOf(U[] original, int newLength, Class newType) { T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy;}
trimToSize 将此 ArrayList 实例的容量调整为列表的当前大小。应用程序可以使用此操作来最小化 ArrayList 实例的存储量。
public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}
在 ArrayList 容量确定下来以后,可以调用这个方法最小化存储空间
Fast-Fail快速失败机制 此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的:在创建迭代器之后,除了通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改,否则在任何时间以任何方式对列表进行修改,迭代器都会抛出 ConcurrentModificationException 。因此,面对并发的修改,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
注意,迭代器的快速失败行为无法得到保证,快速失败迭代器会尽最大努力抛出 ConcurrentModificationException 。迭代器的快速失败行为应该仅用于检测 bug。
ArrayList 中定义了一个 modCount 来记录对容器进行结构修改的次数,在 add 、 addAll 、 remove 、 clear 、 clone 方法中都会引起 modCount 变化,而在创建迭代器时,会使用局部变量保存当前的 modCount 值:
private class Itr implements Iterator{ int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; ...
在进行迭代的过程中,会先检查 modCount 有没有发生变化,以此来判定是否有外部操作改变了容器:
final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }
因为 ArrayList 是非同步的,因此,在多线程环境下,如果有对容器进行结构修改的操作,则必须使用外部同步。
关于remove的坑
remove方法有两种实现:remove(int index),remove(Object obj)。但假设一个ArrayList为[5,4,3,2,1],先要删除2这个元素(不是第二号元素!),那么必须使用remove(new Integer(2))
或remove(Integer.valueOf(2))
,将2转为一个对象实例(不是基础类型),然后调用remove(Object)方法。
remove(数字)默认调用的是remove(index)。
bug理解
参照下面例子理解bug6260652
package com.hgf.collection.List;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import org.junit.Test;/** * @see 参考:http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652 * @author hgfdo hgf的博客 * */public class Bug6260652Test { class BaseClass{ } class SubClass extends BaseClass{ } @Test public void test1(){ //subArray 是[Lcom.hgf.collection.List.Bug6260652Test$SubClass;类型 SubClass[] subArray = new SubClass[3]; System.out.println(subArray.getClass()); //因为java向上转型,所以baseArray 也是[Lcom.hgf.collection.List.Bug6260652Test$SubClass;类型 BaseClass[] baseArray =subArray; System.out.println(baseArray.getClass()); //异常:java.lang.ArrayStoreException: com.hgf.collection.List.Bug6260652Test$BaseClass //因为baseArray下标0指向的内存区域是SubClass实例,现在要新 //建一个BaseClass的实例,肯定就会出错。 baseArray[0] = new BaseClass(); /* * 总结:有一个Object[]类型的数组,并不到别我们能将所有的类型的 * 数据存到数组中,还取决于初始化时的数组元素的实际类型。 */ } @Test public void test2(){ // 返回的是java.util.Arrays$ArrayList(java.util.Array的内部类),不是java.util.ArrayList Listlist = Arrays.asList("abc","def"); System.out.println(list.getClass()); //[Ljava.lang.String; Object[] array = list.toArray(); System.out.println(array.getClass()); //与test1有相同的问题,数组在内存中是有具体的数据类型的, //不能将Object类型的数据随便的赋值给object数组。 array[0] = new Object(); } @Test public void test3(){ //因为java.util.ArrayList是利用Object[]实现 //的,list所指向的内存中的数据也是Object类型的,所以 //使用list.toArray()方法得到的Object[]数组的内 //存类型就是Object类型,最后可以修改数组里面的对象实例。 List list = new ArrayList (); list.add("aaa"); list.add("bbb"); //[Ljava.lang.Object; Object[] object = list.toArray(); System.out.println(object.getClass()); //不会出错,因为object数组里面的数据类型就是Object类型的。 object[0] = new Object(); }}/** * 总结: * 为了考虑这种情况,所以源码中进行了if判断,来防止错误的数组对象导致异常。 * Arrays.copyOf(elementData, size, Object[].class);这个方法就是 * 用来创建1个Object类型,大小为size的数组,这样数组中就可以存放任意对象 * 了,也将某些在内存中实际不是Object类型的转为Object类型,达到与普通情 * 况中ArrayList利用的数组类型一致。 */
小结
-
ArrayList通过使用私有的Object数组来保存数据,存储的数据若为基础数据,会默认将基础数据自动装箱。
-
使用
Arrays.copyOf()
和List.toArray
等方法转变集合类型时,一定要明确内存中元素真正的类型是什么,最好使用的时候做类型检查。 -
使用Array.asList获取的List对象不是
java.util.ArrayList
而是java.util.Arrays$ArrayList
,java.util.Arrays$ArrayList
没有java.util.ArrayList
完美。 -
调用
java.util.ArrayList
对象的remove方法时,如果参数是int类型而且ArrayList中的元素也是int型,默认执行的是删除ArrayList的元素,但是就想删除第i号元素,而不是ArrayList中存储的i,必须使用
Thanks for reading!