博客

动态数组，但是不是线程安全的。

1.类的定义

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

AbstractList也实现了List接口，这样做是为了使用一些重复代码，自己又实现了List是为了实现自己特有的方法。

2.成员变量

	private static final long serialVersionUID = 8683452581122892189L;
    private static final int DEFAULT_CAPACITY = 10;//默认容量大小
    private static final Object[] EMPTY_ELEMENTDATA = {};//空实例提供的空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; // non-private to simplify nested class access//为了节省序列化大小，重写序列化writeObject
    private int size;
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

size表明ArrayList的最大Integer_MAXVALUE – 8，因为有头部信息。


3.构造函数

	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<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

4.成员方法

add方法

	public boolean add(E e) {//尾部插入数据
        modCount++;//fast-fail机制
        add(e, elementData, size);
        return true;
    }
    
    public void add(int index, E element) {//指定位置插入数据
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);//把后边数据后移一位
        elementData[index] = element;
        size = s + 1;
    }

	private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)//扩容的实际
            elementData = grow();//数组增长长度
        elementData[s] = e;
        size = s + 1;
    }
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

    private Object[] grow() {
        return grow(size + 1);
    }
    //扩容之后数组的大小的确定
	private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//1.5倍容量的增长
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE)
            ? Integer.MAX_VALUE
            : MAX_ARRAY_SIZE;
    }

扩容方法 Arrays.copyOf(T[] original, int newLength) System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

remove方法

 public E remove(int index) {
        Objects.checkIndex(index, size);
        final Object[] es = elementData;

        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);

        return oldValue;
    }
private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;//前移一位，把最后一位设置为null并且重置size大小
    }

序列化方法

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        int expectedModCount = modCount;
        s.defaultWriteObject();//默认信息序列化
        s.writeInt(size);//长度写入
        
        for (int i=0; i<size; i++) {//把真正数据写入
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
    
private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // like clone(), allocate array based upon size not capacity
            SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
            Object[] elements = new Object[size];

            // Read in all elements in the proper order.
            for (int i = 0; i < size; i++) {
                elements[i] = s.readObject();
            }

            elementData = elements;
        } else if (size == 0) {
            elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new java.io.InvalidObjectException("Invalid size: " + size);
        }
    }

5.内部类

迭代器

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;

        // prevent creating a synthetic constructor
        Itr() {}

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

        @SuppressWarnings("unchecked")
        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();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i < size) {
                final Object[] es = elementData;
                if (i >= es.length)
                    throw new ConcurrentModificationException();
                for (; i < size && modCount == expectedModCount; i++)
                    action.accept(elementAt(es, i));
                // update once at end to reduce heap write traffic
                cursor = i;
                lastRet = i - 1;
                checkForComodification();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

private class ListItr extends Itr implements ListIterator<E> 

由 iterator 或 listIterator 方法生成的 iterators遵从 fail-fast 规则：如果在创建了 iterator 之后， list 被以任何方法（除了 iterator 自身的 remove, add 方法）进行结构性修改， iterator 会抛出 ConcurrentModificationException ,因此，当存在并行修改时， iterator 会快速失败，而不是在未来位置的时间做出冒险的位置操作。

需要注意 fail-fast行为 不能保证正如设计的那样，通常来说，发生非同步并发修改时，很难做出强有力的保证 fail-fast， Fail-fast iterators 抛出 ConcurrentModificationException 是基于尽力而为的基础。因此，编程时基于这个 exception 来保证准确性是错误的做法， fail-fast 应该仅仅用来检测 bugs。

因为不是线程安全的可以使用Collections.synchronizedList()

参考链接