ArrayList顺序表

定义

ArrayList的本质是顺序表，内部实现是使用数组存储的，集合扩容时会创建更大的数组空间，把原来的数据复制到新数组中。ArrayList支持对元素的快速随机访问，但是插入和删除时速度会很慢，因为这个过程可能要移动其他的元素。

默认大小

/**
  * Default initial capacity.
  */
 private static final int DEFAULT_CAPACITY = 10;

初始化

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  //用于默认初始化状态的校验

public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  //指定为空，当add时才会扩容
}

 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);
       }
 }

当没有指定容量时，内部数组指定为空数组，当add的时候才会扩容。

一般明确集合数据量范围的话，我们必须初始化容量，不然遇到大数据量时，会进行多次的扩容，进行数组的复制，降低系统性能。那么，数组是如何扩容的呢？

扩容

// 当size+1大于length的时候，对容器进行1.5倍扩容
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
}

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); 
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  //增加初始化判断
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
 }
 
 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)  //当最多能放的数大于length，进行扩容
            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);
    }

当添加100个元素时，容器的扩容跟踪为：

1	（new）0——(add first)10—— (add 11)15 --（add 16）22——（add 23）33——（add 34）49......

这里如果估量一下，如果有1000个元素，会进行多少次扩容呢？

73——109——163——244——366——549——823——（add 824）1234。故需要13次扩容

Arrays.copyOf方法实现

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> 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;
    }

最大容量

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;   //去掉低三位

private static int hugeCapacity(int minCapacity) {   
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?  //返回能够扩容的最大值
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

增添

/**
    * Appends the specified element to the end of this list.
    *
    * @param e element to be appended to this list
    * @return <tt>true</tt> (as specified by {@link Collection#add})
    */
   public boolean add(E e) {				//默认加在最后面
       ensureCapacityInternal(size + 1);
       elementData[size++] = e;
       return true;
   }

/**
    * Inserts the specified element at the specified position in this
    * list. Shifts the element currently at that position (if any) and
    * any subsequent elements to the right (adds one to their indices).
    *
    * @param index index at which the specified element is to be inserted
    * @param element element to be inserted
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
   public void add(int index, E element) {
       rangeCheckForAdd(index);   //校验index是否越界

       ensureCapacityInternal(size + 1);  // Increments modCount和自动扩容
       System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
       elementData[index] = element;
       size++;
   }

/*
    * @param      src      the source array.
    * @param      srcPos   starting position in the source array.
    * @param      dest     the destination array.
    * @param      destPos  starting position in the destination data.
    * @param      length   the number of array elements to be copied.
    * @exception  IndexOutOfBoundsException  if copying would cause
    *               access of data outside array bounds.
    * @exception  ArrayStoreException  if an element in the <code>src</code>
    *               array could not be stored into the <code>dest</code> array
    *               because of a type mismatch.
    * @exception  NullPointerException if either <code>src</code> or
    *               <code>dest</code> is <code>null</code>.
    */
   public static native void arraycopy(Object src,  int  srcPos,
                                       Object dest, int destPos,
                                       int length);

System.arraycopy本地方法参数说明

src：原数组
srcPos：原数组开始复制的下标
dest：目标数组
destPos：目标数组开始下标
length：要复制的元素个数

删除

普通remove

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 *
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {    			//按下标remove
    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;
}

快速remove

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If the list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * <tt>i</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns <tt>true</tt> if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return <tt>true</tt> if this list contained the specified element
 */
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;
}

/*
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 */
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; // clear to let GC do its work
}

遍历

为什么遍历删除指定对象时，不能边遍历，边使用list.remove()和list.add()做删除和增加操作？

验证

// output:Exception in thread "main" java.util.ConcurrentModificationException
private static void testArrayList() {
    ArrayList arrayList = new ArrayList();
    arrayList.add("123");
    arrayList.add("345");
    arrayList.add("1");
    arrayList.add("23");
    for (Object ele : arrayList) {
        if ("123".equals(ele)) {
            arrayList.remove(ele);   //除非这里break;或者return；
        }
    }
    System.out.println(arrayList);
}

因为forEach遍历，编译后是使用内部迭代器Iterator的next方法遍历的，在List中维护了一个modCount字段，表示修改的次数，而Iterator内部也维护了一个字段expectedModCount，每次遍历的时候，会去比较这两个字段的值是否相等，就是checkForComodification()方法，如果不等，就会抛出ConcurrentModificationException异常

而使用fori遍历做删除，add的话，有可能会出现问题，如下例，为安全起见一般不建议这么用。

//output:[Student{name='male'}, Student{name='female'}, Student{name='female'}]
public static void main(String[] args) {

        //准备数据
        List<Student> list = new ArrayList<>();
        list.add(new Student("male"));
        list.add(new Student("male"));
        list.add(new Student("female"));
        list.add(new Student("female"));
        list.add(new Student("male"));

        //普通for循环遍历删除
        for (int i = 0; i < list.size(); i++) {
            Student student = list.get(i);
            if ("male".equals(student.getName())) {
                list.remove(i); //使用集合的删除方法删除
//                i--;          //删完之后i不减一，回到之前的值开始遍历
            }
        }
        System.out.println(list.toString());
    }

Iterator遍历

public Iterator<E> iterator() {
    return new Itr();
}

/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

  public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();			//检查modcount

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
  
  	final void checkForComodification() { 
         if (modCount != expectedModCount)  // fail-fast机制，多处会使用这个判断
             throw new ConcurrentModificationException();
    }
}

实例

Iterator iterator = branchList.iterator();
while (iterator.hasNext()) {
    Object ele = iterator.next();
    System.out.println(ele);
}

fail-fast

在ArrayList设计了一个内部List类，为什么要设计这个类?

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

private class SubList extends AbstractList<E> implements RandomAccess {
        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.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
        }

        public E set(int index, E e) {...}
        public E get(int index) {...}
        public int size() {...}
        public void add(int index, E e) {...}
        public E remove(int index) {...}
        protected void removeRange(int fromIndex, int toIndex) {...}
        public boolean addAll(Collection<? extends E> c) {...}
        public boolean addAll(int index, Collection<? extends E> c) { ...}
        public Iterator<E> iterator() {...}
        public ListIterator<E> listIterator(final int index) {...}
}

由于SubList提供了add()、remove()、addAll()方法的实现，均加了checkForComodification() 方法的校验，且对他们的操作会影响外部类，所以使用的时候特别注意。这样一种设计使用了适配器模式，当我们对子集合进行修改、插入、删除操作时，可以操控父集合的元素。但一定要注意，当我们对声明子集合后，再对父集合进行了修改，那么子集合的遍历与修改都会报fail-fast异常。

private static void testFailfast() {
       List<String> masterList = new ArrayList<>();
       masterList.add("one");
       masterList.add("two");
       masterList.add("three");
       masterList.add("four");
       masterList.add("five");


       List<String> branchList = masterList.subList(0, 2);
       //masterList.remove(0);   // 打开后对branchList做遍历、修改、删除操作会报ConcurrentModificationException

       branchList.clear();
       branchList.add("six");
       branchList.add("seven");
       System.out.println(masterList);

       branchList.remove(0);      //output:[six, seven, three, four, five]

       System.out.println(branchList);  //output:[seven]

       System.out.println(masterList);  //output:[seven, three, four, five]
   }

这个案例告诉我们

当取完子对象后，父对象与子对象有了联系，就不能随意的改变了，当父对象更改时，再对子对象操作，就会报fail-fast错误。
当建立联系后，子对象的更改会影响到父对象，彼此影响，所以使用的时候，一定不要同时对两个对象做修改操作。

asList & toArray

由于ArrayList底层是由数组实现的，那么，肯定是存在数组转集合和集合转数组的方法。我们常使用Arrays.asList(T [])将数组转换为List集合，注意使用该方法时，不能对子集合进行add、remove、clear等操作，因为，返回的ArrayList是一个内部类，没有提供以上方法的实现。

1
2
3

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

如果使用了，就会报fail-fast错误。如果一定要使用修改的话，一般我们是这么声明的。

1 2	String[] strs = new String[2]; ArrayList list=new ArrayList(Arrays.asList(strs));

ArrayList集合本身提供了一个集合转数组的方法，就是toArray方法。当我们使用这个方法的时候，一定要注意一些小坑。我们先来看一个例子，猜测一下会打印什么？

private static void testArrayList() {
        ArrayList arrayList = new ArrayList();
        arrayList.add("male");
        arrayList.add("male");
        arrayList.add("female");
        arrayList.add("female");

//        String[] objs = (String[]) arrayList.toArray();
        Object[] objs = arrayList.toArray();
        String[] strs = new String[2];
        String[] strs1 = new String[5];
        arrayList.toArray(objs);
        arrayList.toArray(strs);
        arrayList.toArray(strs1);

        System.out.println(Arrays.asList(objs));
        System.out.println(Arrays.asList(strs));
        System.out.println(Arrays.asList(strs1));
    }

最终的打印结果为：

[male, male, female, female]
[null, null]
[male, male, female, female, null]

分析一下，第一条结果很明确，能完成复制，当我使用无参的方法时，该方法返回的是Object[]，不能转化为String[]，会报ClassCastException异常。第二条当数组声明的长度比集合小的时候，返回全是空。当大于的时候，能进行复制，其余的默认为null，这是什么导致的呢，我们来看看源码。

无参方法实现

1
2
3

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

无参方法返回Object数组

有参方法实现

public <T> T[] toArray(T[] a) {
    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;
}

当小于集合大小时，我们看到这里返回了一个复制好的数组，但是入参数组a被忽略了，所以a还是空，如果声明另一个数组要接受的话，是有值的。

我们看看Arrays.copyOf()方法是如何实现的

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    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;
}

可以看到，这里copy new了一个空的数组，长度为newLength,然后调用本地方法进行了复制，返回。

当我们集合转数组的时候，要注意，将数组的长度声明为list.size()，这性能往往高于大于时候的长度。