Java常用集合ArrayList分析

Arraylist底层是由数组实现的，因此ArrayList拥有很好的随机访问能力（时间复杂度为O(1)），但是删除和添加操作性能比较差时间复杂度为O(n).因为ArrayList底层是数组实现的所以删除和添加操作会造成数据扩容或者收缩；ArrayList允许null元素；

问题一：ArrayList怎么初始化？

1.无参的构造方法,不初始化任何容器，给一个空的数组
 public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
2.带参数的构造方法，如果入参是一个空集合和无参构造一样；
    public ArrayList(Collection<? extends E> 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;
        }
    }
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);
        }
    }

问题二：ArrayList如何扩容？

1.计算最小的容器大小minCapacity，现在最小为10；
2.新大小newCapacity是oldCapacity的1.5倍（扩容逻辑和ArrayMap类似都是1.5倍）；
3.新容量newCapacity不超过Int最大值；
4.拷贝原始数据到新数组中；
  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);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

问题三：通过迭代器遍历ArrayList时做了什么？
程序员在通过迭代器遍历ArrayList的时候，主要使用了Iterator的next()和hasNext()方法,现在我们来看下这两个方法；

   1.cursor记录了该迭代器访问游标的位置，每调用一次next方法，cursor的值都会+1；
   2.limit是返回迭代器中，对当前ArrayList中数组数据量的一个快照；
   3.如果cursor<limit说明迭代器中还有可以访问的数据
   public boolean hasNext() {
            return cursor < limit;
   }
=====================================================
 1.next方法里面实现了fail-fast机制,expectedModCount是迭代器返回时记录的容器修改次数。如果ArrayList被多线程修改了modCount的值就不会等于之前的expectedModCount，这就说明了其他线程修改了这个容器。
 public E next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            int i = cursor;
            if (i >= limit)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }