初始化

  • 默认容量大小为10;
  • 存储是Object[]数组;
 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;
    }

扩容

  • 调用grow()函数,新数组容量扩大了是1.5倍;
  • 通过System.arraycopy()函数复制数组;
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);
    }

remove()带来的问题

remove移除元素的时候会调用fastRemove()方法
private void fastRemove(int index){
        modCount++;
        intnumMoved=size-index-1;
        if(numMoved>0)             
          System.arraycopy(elementData,index+1,elementData,index,numMoved);
        elementData[--size]=null;// Let gc do its work
}

理解

  • 通过System.arraycopy()方法,导致删除元素时涉及到数组元素的移动;
  • 所以for-each + remove()的写法,会导致遇到第一满足删除条件,把该元素从数组中删除;
  • 并且后一个元素会移动到当前位置,导致下一次遍历的时候后一个元素没有遍历到,导致无法删除满足条件的第二个元素;

解决办法:

倒序遍历删除的方式
for(int i = list.size(); i >= 0; i--){
    String s = list.get(i);
    if(s.equals("hshuo")){
        list.remove(s);
    }
}
或者使用迭代器
public static void remove(ArrayList<String> list) 
    {
        Iterator<String> it = list.iterator();
        while (it.hasNext()) 
        {
            String s = it.next();
            if (s.equals("b")) 
            {
                it.remove();
            }
        }
}

参考:


补充

  • list 列表的结尾会预留一定的容量空间。
  • 向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法,以减少增量重新分配的次数。
ensureCapacity()
    /**
    如有必要,增加此 ArrayList 实例的容量,以确保它至少可以容纳由minimum capacity参数指定的元素数。
     *
     * @param   minCapacity   所需的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
ensureExplicitCapacity()调用grow()进行扩容
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

例如:

多添加了list.ensureCapacity(N);
public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        list = new ArrayList<Object>();
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(N);
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法后:"+(endTime1 - startTime1));
    }
}