JAVA 深入集合-- ArrayList

一、介绍

   ArrayList 简单的说就是一个存放元素的集合，也是一个数组，只是提供了大量方便我们操作的方法， 比数组的优势就是不用我们手动维护了，相信大家用得比较多了，还是看代码吧！

 

二、源码介绍

    2.1 类：

  

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

 

 

    

    可以看出，继承了AbstractList<E> 实现了 List<E> 和 RandomAccess,这里List 只一个接口，定义了该集合的一些方法，

AbstractList 是实现了List 接口的抽象类，继承他 只是为了减少我们常用的一些操作，这里和hashMap 的设计一样，具体请看hashMap 的介绍。

    RandomAccess 这东西作为一个接口定义，允许一般的算法更改其行为，- -比较抽象，暂时不管，后期再谈！

 

 

  2.2 构造
    private transient Object[] elementData;

    public ArrayList(int initialCapacity) {
	super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
	this.elementData = new Object[initialCapacity];
    }

    public ArrayList() {
	this(10);
    }
    
     // 从上面看出，当我们new一个 ArrayList 的时候，实际是创建了一个elementData 的数组，当     // 然默认长度为10，很简单对吧！
    // 这里集合扩展，就是数组复制，也没啥奇特的
    public ArrayList(Collection<? extends E> c) {
	elementData = c.toArray();
	size = elementData.length;
	if (elementData.getClass() != Object[].class)
	    elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

 

 

 

 2.3 我们切入点从常用的 add set 方法开始看：
       add:这里进行的重写

       // 属性获得获得元素的个数      
       private int size;
       public boolean add(E e) {
        // size 默认是0，其实这里仅仅是进行一个是否扩容的判断
	ensureCapacity(size + 1);  // Increments modCount!!
        // 可以看出 这就仅仅是给数组放值
	elementData[size++] = e;
	return true;
      }

	public void ensureCapacity(int minCapacity) {
        // 依然是控制集合修改次数，用于迭代的时候控制异常
	modCount++;
	// 数组长度
	int oldCapacity = elementData.length;
        // 如果当前容量大于的数组长度
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
            // 进行扩容后的长度，这里有点意思，要扩容成奇数，不知道为啥
	    int newCapacity = (oldCapacity * 3)/2 + 1;
            // 这里为了addAll的时候，可能一次性添加多了
    	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
            // 这里就是扩容啦，也看看源码吧，虽然在工具类Arrays里面的
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }
           
    // 扩容源码
       
	public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }   
	// 这里用于返回U类型的T 数组
	public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
	// 这里进行了地址判断，判断参数是否是Object类型,否则就从新 new 一个newType 类型的数        // 组
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
	// 这是JAVA数组扩容最快的方法了，参数解释 看看API 就行了
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }  
    

 

2.3.2 继续看方法：add(index, element)
        // 这里我们知道是方法是将元素element 加入到集合的指定位置index
 
	public void add(int index, E element) {
        // 先进行判断，位置是否超出了界限，当然这里判断只是判断size,而非数组界限
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
	// 这里就是刚才的了
	ensureCapacity(size+1);  // Increments modCount!!
	// 这里看出还是数组的复制，只是将当前数组elementData 的index + 1位置 向后移动了一位，就完成了插入
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);
	elementData[index] = element;
	size++;
    }

 

 2.3.3 方法addAll(Collection<? extends E> c)
	
	public boolean addAll(Collection<? extends E> c) {
	Object[] a = c.toArray();
        int numNew = a.length;
	// 数组扩容
	ensureCapacity(size + numNew);  // Increments modCount
	// 数组复制
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
	return numNew != 0;
    }

 

 2.4 get方法
	public E get(int index) {
	// 仅仅判断数组是否越界，抛出自己定义的错误信息
	RangeCheck(index);
	// 直接访问的数组下标，因此访问元素很快
	return (E) elementData[index];
    }
	private void RangeCheck(int index) {
	if (index >= size)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
    }
   

  

 2.5  方法：remove(int index) 

	public E remove(int index) {
	// 同上
	RangeCheck(index);
	// 看来在迭代的时候不允许删除的
	modCount++;
	E oldValue = (E) elementData[index];
	// 获取删除的位置
	int numMoved = size - index - 1;
	if (numMoved > 0)
	    // 当前数组在numMoved 位置，向左复制，
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	// 将数组最后一个元素设为null,我们发现虽然元素删除了，但是数组的长度并没减少，还占         // 空间
	elementData[--size] = null; // Let gc do its work

	return oldValue;
    }
	// 这里要提到另一个方法，在remove(Object o)中使用了，其实内容和上面一样，只是JDK 人        // 员忘记掉了
	// 看到这些我总会相信，大神也会失误的，也是不完美的~。~
 	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	方法：indexOf(Object o) 
	 public int indexOf(Object o) {
	if (o == null) {
	    // 这里小技巧发现，对null 的判断总是要特殊一些
	    for (int i = 0; i < size; i++)
		if (elementData[i]==null)
		    return i;
	} else {
	    // 总的来说就是便利数组啦，有就返回，没有返回-1
	    for (int i = 0; i < size; i++)
		if (o.equals(elementData[i]))
		    return i;
	}
	// 同时contains方法额也是调用的这个
	return -1;
    }

 

2.7 方法：toArray，带参数和不带参数差不多
	public <T> T[] toArray(T[] a) {
	// 带参数情况就是，如果a 数组length 比较大，那么剩余的都是null,而不带参数 仅仅是将
        // list元素放进数组返回
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
	
	System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

 

    2.8 方法：removeRange 
	 // 这个方法可以一次移除 指定两个位置的所有元素，但是不知道为什么是protected ，调用         // 不了
	 // 当然实现这个功能 我们可以用 list.sublist(int b,int e).clear() 完成此功能
	 protected void removeRange(int fromIndex, int toIndex) {
	// 内容和remove 比较类似
	modCount++;
	int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

	// Let gc do its work
	int newSize = size - (toIndex-fromIndex);
	while (size != newSize)
	    elementData[--size] = null;
    }

 

   
    2.9 方法：trimToSize 
	// 上面讲到我们删除元素的时候，数组还是占着位置，这个方法就是将那些没有元素的位置删        //  除掉
	public void trimToSize() {
	modCount++;
	int oldCapacity = elementData.length;
	if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
	}
    }

 

 

 2.9.1 方法：subList(fromIndex, toIndex)
	// 这里实际上是在AbstractList 里面了，arrayList 没进行重写
	public List<E> subList(int fromIndex, int toIndex) {
	// 这两个内部类...其实对象都访问到SubList 里面去了
        return (this instanceof RandomAccess ?
                new RandomAccessSubList<E>(this, fromIndex, toIndex) :
                new SubList<E>(this, fromIndex, toIndex));
    }  
    // 先来看看 内部类吧
         
	class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
	// 从构造看出，其实操作了 SubList<E> 的构造，super() 继续往下看
    	RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
       	 super(list, fromIndex, toIndex);
    	}

    	public List<E> subList(int fromIndex, int toIndex) {
        return new RandomAccessSubList<E>(this, fromIndex, toIndex);
    	}
   	 }
	// 这个内部类 就是我们需要返回RandomAccessSubList<E>  的父类，看看做了什么操作
	class SubList<E> extends AbstractList<E> {
   	 private AbstractList<E> l;
   	 private int offset;
    	 private int size;
    	 private int expectedModCount;
	// 构造线对位置进行了判断
    	SubList(AbstractList<E> list, int fromIndex, int toIndex) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > list.size())
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
	// 然后赋值，注意这个是强引用
        l = list;
        offset = fromIndex;
        size = toIndex - fromIndex;
        expectedModCount = l.modCount;
    }
   	// ...
    }

    // 这里可以看出其实我们调用subList 方法的同时，返回的其实是一个RandomAccessSubList 对象，

 

   // 但是该对象继承了SubList<E> ，而SubList<E>  内容是原来list 的的一个引用。

   // 既然是引用，那么为什么还要单独设计一个类呢，为什么不直接引用，操作数组呢？

  

// 这个是SubList<E> 内部的方法，看看区别
   public E set(int index, E element) {
	// 检查参数大小
        rangeCheck(index);
        checkForComodification();
        return l.set(index+offset, element);
    }

   public E get(int index) {
      	rangeCheck(index);
       	checkForComodification();
	// 这里看到 我们获得元素的位置 已经发生了变化
        return l.get(index+offset);
    }

   public int size() {
        checkForComodification();
        return size;
    }
    // 大家都调用了这个方法，也就是说当我们操作这个sublist 返回的类的时候
    // 都是不允许影响集合的操作
    // 包括原list 也不允许删除 等操作
    private void checkForComodification() {
        if (l.modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

    // 下面继续看内部类的通用方法：
    // 下面所有的方法我们都可以看出一点
    // 所有元素的位置 都跟index 和 offset 相关，也就是和我们定义的位置有关，实质内容没变
    public void add(int index, E element) {
        if (index<0 || index>size)
            throw new IndexOutOfBoundsException();
        checkForComodification();
        l.add(index+offset, element);
        expectedModCount = l.modCount;
        size++;
        modCount++;
    }

    public E remove(int index) {
        rangeCheck(index);
        checkForComodification();
        E result = l.remove(index+offset);
        expectedModCount = l.modCount;
        size--;
        modCount++;
        return result;
    }

    protected void removeRange(int fromIndex, int toIndex) {
        checkForComodification();
        l.removeRange(fromIndex+offset, toIndex+offset);
        expectedModCount = l.modCount;
        size -= (toIndex-fromIndex);
        modCount++;
    }

     // 上面的元素操作，参考前面的介绍，我们来模拟一下这个内部类干了什么。

 

    // 1.假设我们有个ArrayList m,存放了元素  1,2,3,4,5,6,7,8,9

    // 2.假设我们要得到1,2,3 的元素，从而调用sublist(0,3) 方法。

    // 3.这个时候内部类给我们定义变量 private AbstractList<E> l ,size 等属性

    // 4.为属性赋值l = list; offset = fromIndex = 0; size = toIndex - fromIndex = 3;

    // 5.我们可以看出，现在 我们操作的实际是m的引用l,但是操作的范围只能是 0,3 这个区间。

    // 6.也就是说，大家共用一块区域，但是sublist 的结果，只能从大的区域m,划分出一片小的区域

    // 7.但是如果操作任何一个变量，都会引起大家的变化，我们做个尝试

   

public static void main(String[] args) {
		ArrayList<Object> m = new ArrayList<Object>();
		System.out.println(new Test() instanceof RandomAccess);
		for(int i =1;i<10;i++){
			// 放9个元素
			m.add(i);
		}
		// 取3个元素1,2,3
		List<Object> l = m.subList(0, 3);
		// 这里已经拿到 1,2，3 了
		System.out.println(l);
		// 这里是没变化的
		System.out.println(m); 
		// 如果l 添加一个值，我们发现m 的数据已经变了，多了一个元素10
	        l.add(10);
		System.out.println(m); 
		System.out.println(l); 
		// 如果操作m,那么打印l,就会抛ConcurrentModificationException
		m.add(11);
		System.out.println(m); 
		// 因为l添加时，先检查 checkForComodification() 变量再自增，
		// 而m 元素增加了 ，modCount 数量也加1，打印不报错
		// 而m添加元素了，modCount 增加，而l 元素没有增加，期望的expectedModCount                   // 没变
		// 价差不通过 就报错了
		System.out.println(l); 
		// 所以使用的时候要小心啦，当然你可以这样 new ArrayList(l) 创建新的
		System.exit(0);
	}  

 

 

关于AbstractList 里面提供的源码，后面再介绍吧，大概的都差不多，只是iterator 迭代 那里不同

关于私有方法writeObject 和 readObject 这是为io 准备的，传输的时候会通过反射查找调用，这里暂时不讲

 

 

三、小结：

    1.ArrayList 是一个动态数组，动态通过数组的底层复制进行，和Vector差不多，它不是线程安全的

    2.为了减小计算，可以手动指定空间或者扩容ensureCapacity ，同时也可以trimToSize 去掉不必要的空间

    3.存放元素和获取元素 都是通过数组依次存放，通过下标存放，因此是很快的