JavaSE7 ArrayList源码 上

这是jre7版本的

public class ArrayList<E>
  extends AbstractList<E>//这个  extends AbstractCollection<E> implements List<E>
  implements List<E>, RandomAccess, Cloneable, Serializable
{
  private static final long serialVersionUID = 8683452581122892189L;
  /**
   * 看下面这两个私有属性，就知道ArrayList实际上就是一个数组
   * 其（数组、ArrayList）数据结构就是一个简单的线性序列
   */
  //数组elementData 存储ArrayList的所有数据
  private transient Object[] elementData;
  //size<=elementData.length,两者没什么特别关系
  //size是数组elementData中元素（E） 的个数
  private int size;
  private static final int MAX_ARRAY_SIZE = 2147483639;
  
  /**
   * 构造方法1
   * 可以初始化数组大小
   * 例：ArrayList<E> array = new ArrayList<E>(10000); 
   * 这时候size=0,但是数组的容量是10000
   */
  public ArrayList(int paramInt)
  {
    if (paramInt < 0) {
      throw new IllegalArgumentException("Illegal Capacity: " + paramInt);
    }
    this.elementData = new Object[paramInt];
  }
  /**
   * 构造方法2
   * 默认构造方法，初始化数组大小是10,感觉好小啊
   */
  public ArrayList()
  {
   //表示调用构造方法1
    this(10);
  }
  
  /**
   * 构造方法3 
   * 可以放一个实现Collection接口的集合进去
   */
  public ArrayList(Collection<? extends E> paramCollection)
  {
	//  1.将集合转换成数组，elementData指向这个数组
    this.elementData = paramCollection.toArray();
    //  2.设置size值  
    this.size = this.elementData.length;
    //  3.判断ele..是不是Object数组,不是的话创建一个，将内容（基本类型的值，对象的引用）copy进新数组中，返回
    if (this.elementData.getClass() != [Ljava.lang.Object.class) {
      this.elementData = Arrays.copyOf(this.elementData, this.size, [Ljava.lang.Object.class);
    }
  }

???

?

?下面看一下，构造方法3中的第一步（假设传进来的是一个ArrayList）和第三步。

/**
	 * ArrayList实现的 Collection接口中toArray()方法
	 */
	  public Object[] toArray()
	  {
	    return Arrays.copyOf(this.elementData, this.size);
	  }
	  /**
	   * 在Arrays类中找到的copyOf的方法
	   */
	  public static <T> T[] copyOf(T[] paramArrayOfT, int paramInt)
	  {
	    return (Object[])copyOf(paramArrayOfT, paramInt, paramArrayOfT.getClass());
	  }
	  /**
	   * 直接看这个吧，上面构造方法3的第三步调用的也是这个方法
	   */
	  public static <T, U> T[] copyOf(U[] paramArrayOfU, int paramInt, Class<? extends T[]> paramClass)
	  {
		 //根据给定的paramClass数组类型，生成一个大小paramInt的新数组
	    Object[] arrayOfObject = 
	    		        //三目运算
	    		        paramClass == [Ljava.lang.Object.class ? 
	    				//构造方法3的第三步走的这里
	    				(Object[])new Object[paramInt] :
	    				//Array.newInstance 是native的，看不到了 
	    				(Object[])Array.newInstance(paramClass.getComponentType(), paramInt);
	    //这个也是	native方法，x = Math.min(paramArrayOfU.length, paramInt)
      //复制paramArrayOfU[0~x]内容到arrayOfObjec[0~x]中，用这个操作数组还是很爽的				
	    System.arraycopy(paramArrayOfU, 0, arrayOfObject, 0, Math.min(paramArrayOfU.length, paramInt));
	    return arrayOfObject;
	  }

?

?

??其实一般的构造方法3，第三步都会走。

ArrayList<String> array = new ArrayList<String>(Arrays.asList("a","b"));
		//对应构造方法3的第一步
		Object[] elementData = Arrays.asList("a","b").toArray();
		System.err.println(elementData.getClass());//输出class [Ljava.lang.String;

??

?

下面继续源码:对数组进行扩容

  /**
   * 给数组瘦身，释放资源，确定数组大小不会改变时用这个
   * 生成一个新数组大小与元素个数一样
   */
  public void trimToSize()
  {
	//记录对arrayList的操作次数？不知道有什么用处
    this.modCount += 1;
    int i = this.elementData.length;
    if (this.size < i) {
       //上面介绍过了
      this.elementData = Arrays.copyOf(this.elementData, this.size);
    }
  }
  /**
   * 手动给数组扩容，生成一个容量不小于paramInt数组，然后将内容copy进去
   */
  public void ensureCapacity(int paramInt)
  {
    if (paramInt > 0) {
      ensureCapacityInternal(paramInt);
    }
  }
  /**
   * 给定数值不能比当前数组容量小。
   */
  private void ensureCapacityInternal(int paramInt)
  {
    this.modCount += 1;
    if (paramInt - this.elementData.length > 0) {
      grow(paramInt);
    }
  }
  /**
   * 执行扩容
   */
  private void grow(int paramInt)
  {
    int i = this.elementData.length;
    //自己会根据当前容量算出一个扩容值，跟给定值比较选择最大的
    //移位操作符>> 参考：http://flyouwith.iteye.com/blog/2163032
    int j = i + (i >> 1);
    if (j - paramInt < 0) {
      j = paramInt;
    }
    if (j - 2147483639 > 0) {
      //限定数组最大的容量不能超过多少
      j = hugeCapacity(paramInt);
    }
    //继续copy
    this.elementData = Arrays.copyOf(this.elementData, j);
  }
  /**
   * 最大数值能不能超过Integer.MAX_VALUE
   * 2147483647
   */
  private static int hugeCapacity(int paramInt)
  {
    if (paramInt < 0) {
      throw new OutOfMemoryError();
    }

    return paramInt > 2147483639 ? Integer.MAX_VALUE : 2147483639;
  }

?下面内容是一些基本方法

  /**
   * 返回数组中元素个数
   */
  public int size()
  {
    return this.size;
  }
  /**
   * 是否只有一副皮囊
   */
  public boolean isEmpty()
  {
    return this.size == 0;
  }
  /**
   * 是否包含制定paramObject
   */
  public boolean contains(Object paramObject)
  {
    return indexOf(paramObject) >= 0;
  }
  /**
   * paramObject 在数组中的一次出现的位置
   * 通过对象的equals比较
   */
  public int indexOf(Object paramObject)
  {
    int i;
    if (paramObject == null) {
      for (i = 0; i < this.size; i++) {
        if (this.elementData[i] == null) {
          return i;
        }
      }
    } else {
      for (i = 0; i < this.size; i++) {
        if (paramObject.equals(this.elementData[i])) {
          return i;
        }
      }
    }
    return -1;
  }
  /**
   * paramObject 在数组中最后一次出现的位置
   * 从后面开始循环
   * 通过对象的equals比较
   */
  public int lastIndexOf(Object paramObject)
  {
    int i;
    if (paramObject == null) {
      for (i = this.size - 1; i >= 0; i--) {
        if (this.elementData[i] == null) {
          return i;
        }
      }
    } else {
      for (i = this.size - 1; i >= 0; i--) {
        if (paramObject.equals(this.elementData[i])) {
          return i;
        }
      }
    }
    return -1;
  }
  /**
   * 复制
   * 数组存基本类型的值，对象的引用。
   * 所以copy的不过是引用，都指向一个对象
   */
  public Object clone()
  {
    try
    {
      ArrayList localArrayList = (ArrayList)super.clone();
      localArrayList.elementData = Arrays.copyOf(this.elementData, this.size);
      localArrayList.modCount = 0;
      return localArrayList;
    }
    catch (CloneNotSupportedException localCloneNotSupportedException)
    {
      throw new InternalError();
    }
  }
  /**
   * 转换成数组，对象存引用
   */
  public Object[] toArray()
  {
    return Arrays.copyOf(this.elementData, this.size);
  }
  
  /**
   * 新建一个数组，放到这里拷贝ArrayList中内容
   */
  public <T> T[] toArray(T[] paramArrayOfT)
  {
	  //如果给定数组容量小于size ，则生成一个大小是size的数组，然后把内容copy进去
    if (paramArrayOfT.length < this.size) {
      return (Object[])Arrays.copyOf(this.elementData, this.size, paramArrayOfT.getClass());
    }
    //否则直接copy，上面有介绍这个方法的含义
    System.arraycopy(this.elementData, 0, paramArrayOfT, 0, this.size);
    if (paramArrayOfT.length > this.size) {
      paramArrayOfT[this.size] = null;
    }
    return paramArrayOfT;
  }
  /**
   * 返回数组指定位置的元素
   */
  E elementData(int paramInt)
  {
    return this.elementData[paramInt];
  }
  /**
   * 返回指定位置的元素
   */
  public E get(int paramInt)
  {
    rangeCheck(paramInt);//检核是否越界
    return elementData(paramInt);
  }
  /**
   * 替换指定位置的元素，返回被替换元素
   */
  public E set(int paramInt, E paramE)
  {
    rangeCheck(paramInt);//检核是否越界
    Object localObject = elementData(paramInt);
    this.elementData[paramInt] = paramE;
    return localObject;
  }
  /**
   * 在末尾添加元素。
   * 第一步上面有介绍这个方法。扩容
   * 注意：size加1
   */
  public boolean add(E paramE)
  {
    ensureCapacityInternal(this.size + 1);
    this.elementData[(this.size++)] = paramE;
    return true;
  }
  /**
   * 指定位置添加元素，从指定位置开始后面元素统一后移一位
   * 这里不是用的for循环来移位，而是copy，即使这样也比LinkedList慢好多
   * 这个如果用for循环的话时间复杂度是O(this.size - paramInt) copy应该是比这小的
   * 但是肯定比LinkedList 的O(1) 要大的多
   * 注意：size加1
   */
  public void add(int paramInt, E paramE)
  {
    rangeCheckForAdd(paramInt);//检核是否越界
    ensureCapacityInternal(this.size + 1);
    System.arraycopy(this.elementData, paramInt, this.elementData, paramInt + 1, this.size - paramInt);
    this.elementData[paramInt] = paramE;
    this.size += 1;
  }
  /**
   * 跟上面性质是一样的。把删除位置后面的元素统一向前移动一位   
   * 比LinkedList慢
   * 注意：size减1
   */
  public E remove(int paramInt)
  {
    rangeCheck(paramInt);//检核是否越界
    this.modCount += 1;
    Object localObject = elementData(paramInt);
    int i = this.size - paramInt - 1;
    if (i > 0) {
      System.arraycopy(this.elementData, paramInt + 1, this.elementData, paramInt, i);
    }
    this.elementData[(--this.size)] = null;
    return localObject;
  }
  /**
   * 删除对象，现查到对象在集合中的位置
   * 比LinkedList慢
   */
  public boolean remove(Object paramObject)
  {
    int i;
    if (paramObject == null) {
      for (i = 0; i < this.size; i++) {
        if (this.elementData[i] == null)
        {
          fastRemove(i);
          return true;
        }
      }
    } else {
      for (i = 0; i < this.size; i++) {
        if (paramObject.equals(this.elementData[i]))
        {
          fastRemove(i);
          return true;
        }
      }
    }
    return false;
  }
  /**
   * 因为是在集合众找到的位置。所以不需要检核，直接删除
   */
  private void fastRemove(int paramInt)
  {
    this.modCount += 1;
    int i = this.size - paramInt - 1;
    if (i > 0) {
      System.arraycopy(this.elementData, paramInt + 1, this.elementData, paramInt, i);
    }
    this.elementData[(--this.size)] = null;
  }
  /**
   * 清空，通过for循环
   */
  public void clear()
  {
    this.modCount += 1;
    for (int i = 0; i < this.size; i++) {
      this.elementData[i] = null;
    }
    this.size = 0;
  }
  /**
   * 添加一个集合到当前集合后面
   * 先把要添加的集合转变成数组，然后对this数组扩容，copy到this数组中
   * 比LinkedList慢
   */
  public boolean addAll(Collection<? extends E> paramCollection)
  {
    Object[] arrayOfObject = paramCollection.toArray();
    int i = arrayOfObject.length;
    ensureCapacityInternal(this.size + i);
    System.arraycopy(arrayOfObject, 0, this.elementData, this.size, i);
    this.size += i;
    return i != 0;
  }
  /**
   * 在指定位置插入集合，
   * 先将扩容，然后移位，之后把内容copy进来
   * 比LinkedList慢
   */
  public boolean addAll(int paramInt, Collection<? extends E> paramCollection)
  {
    rangeCheckForAdd(paramInt);//检核是否越界
    Object[] arrayOfObject = paramCollection.toArray();
    int i = arrayOfObject.length;
    ensureCapacityInternal(this.size + i);
    int j = this.size - paramInt;
    if (j > 0) {
      System.arraycopy(this.elementData, paramInt, this.elementData, paramInt + i, j);
    }
    System.arraycopy(arrayOfObject, 0, this.elementData, paramInt, i);
    this.size += i;
    return i != 0;
  }
  
  /**
   * 这是protected的不能用。。
   * remove区间的内容
   * 先把paramInt2后的内容copy到paramInt1后面
   * 然后把后面paramInt2-paramInt1位置的元素清空
   */
  protected void removeRange(int paramInt1, int paramInt2)
  {
    this.modCount += 1;
    int i = this.size - paramInt2;
    System.arraycopy(this.elementData, paramInt2, this.elementData, paramInt1, i);
    int j = this.size - (paramInt2 - paramInt1);
    while (this.size != j) {
      this.elementData[(--this.size)] = null;
    }
  }
  /**
   * 检核越界
   */
  private void rangeCheck(int paramInt)
  {
    if (paramInt >= this.size) {
      throw new IndexOutOfBoundsException(outOfBoundsMsg(paramInt));
    }
  }
  /**
   * 检核越界
   */
  private void rangeCheckForAdd(int paramInt)
  {
    if ((paramInt > this.size) || (paramInt < 0)) {
      throw new IndexOutOfBoundsException(outOfBoundsMsg(paramInt));
    }
  }
  /**
   * 异常信息
   */
  private String outOfBoundsMsg(int paramInt)
  {
    return "Index: " + paramInt + ", Size: " + this.size;
  }
 

??

?

JavaSE7 ArrayList源码 上

原文：http://flyouwith.iteye.com/blog/2166890