基础篇--ArrayList扩容，基础篇--arraylist

基础篇--ArrayList扩容，基础篇--arraylist

首先，我们来看ArrayList的继承关系如下，从表面上我们可以看到它支持抽象对象的方法

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

我们来看看都继承了哪些方法

   AbstractList 一个抽象类，里面会有一些常用方法的实现

   List接口必须实现方法

  randomAccess是一个空接口，起到一个标识的作用，在AbstractList会有用到，这里暂不讨论

  Colneable 与randomAccess类似也是一个空接口，提供了Object.colne()方法

  Serializable 接口以启用其序列化功能

ArrayList用到了两个全局变量，对于多线程稍微了解一点，也应该能够知道，从这里就可以看出ArrayList也出现并发问题，非线程安全类

 

Object[] elementData 数组类型

/**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer.
     */
    private transient Object[] elementData;

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

List list = new ArrayList();//这是我们常用的创建方式，我们来看看内部会发生什么？

  默认对象属性为10，为数组形式

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];// <span >数组类型</span>
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this(10); // <span >默认10个元素</span>
    }

接下来进入主题，来看看它的添加方法

<span >/**
     * 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);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }</span>

重点来了，我们知道初始元素个数为10，那么如果满了会发生什么呢

<span >private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }</span>

<span >  </span><pre name="code" class="java"><span >   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;</span>

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

从这里我们可以看到，每次的扩容增量为  （1 + 0.5） * oldCapacity,最大为

<pre name="code" class="java"><span >Integer.MAX_VALUE</span>

并且每次的扩容会重新创建一个对象

<span >    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;
    }</span>

设想一下，如果每次添加一个元素，一直添加10万百万个元素，会创建多少个对象

最简单的优化方法，在创建list的时候，我们是否可以预估一下预计的个数呢？每次添加元素之前  我们是否可以预估一下要扩容元素的个数呢？

<span >ArrayList list = new ArrayList(100);// 更改默认值100
        list.ensureCapacity(1000); // 预估扩容1000</span>

如果有其他的好的扩容方法，欢迎讨论

测试如下

public static void main(String[] args) throws IOException {
        Runtime run = Runtime.getRuntime();
        run.gc();
        System.out.println("time: " + (new Date()));
        // 获取开始时内存使用量
        long startMem = run.totalMemory() - run.freeMemory();
        System.out.println("memory> total:" + run.totalMemory() + " free:" + run.freeMemory() + " used:" + startMem);


        ArrayList list = new ArrayList();
        int size = 10000000;
//        list.ensureCapacity(size);  // 是否扩容
        int i = 0;
        try {
            for (; i < size; i++) {
                list.add(i);
            }
        } catch (Throwable e) {
            e.printStackTrace();
            System.out.println("i= " + i);
        }


        System.out.println("time: " + (new Date()));
        long endMem = run.totalMemory() - run.freeMemory();
        System.out.println("memory> total:" + run.totalMemory() + " free:" + run.freeMemory() + " used:" + endMem);
        System.out.println("memory difference:" + (endMem - startMem));
    }

输出内存差异结果结果：

a.不扩容

time: Tue Aug 23 16:38:49 CST 2016
memory> total:18350080 free:16858832 used:1491248
time: Tue Aug 23 16:38:53 CST 2016
memory> total:291962880 free:14030184 used:277932696
memory difference:276441448

b.扩容

time: Tue Aug 23 16:41:47 CST 2016
memory> total:18612224 free:17107928 used:1504296
time: Tue Aug 23 16:41:50 CST 2016
memory> total:296026112 free:94840808 used:201185304
memory difference:199681008