一、数组是否可以变长?

我们都知道,数组时定长的,初始化时一定要给定长度,由于这个长度的问题,我们在实际的开发中,会更倾向于使用容器,如ArrayList等,使用容器类时,无需考虑长度问题,因为容器已经帮我们处理了,那么数组就没有办法变长了吗?当然不是,ArrayList就是基于数组实现的,我们可以看看ArrayList是如何处理的

二、ArrayList的实现原理

ArrayList用一个Object数组作为其内部操作,并有一个成员变量size代表容器的长度

    private transient Object[] elementData; private int size;

添加数据时,调用add()方法:

public boolean add(E e) { 
      ensureCapacityInternal(size + 1);  // Increments modCount!! 
      elementData[size++] = e; 
      return true; 
 }

    private void ensureCapacityInternal(int minCapacity) { 
        modCount++; // 如果添加了新元素后的长度超出了原来的长度,则需要扩容 if (minCapacity - elementData.length > 0) 
            grow(minCapacity); 
    }

可以看到扩容的核心代码在grow方法中:

    private void grow(int minCapacity) { int oldCapacity = elementData.length; //扩容,生成新容量,为原来的2倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) 
            newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) 
            newCapacity = hugeCapacity(minCapacity); // 把数组扩大到新长度 
        elementData = Arrays.copyOf(elementData, newCapacity); 
    }

elementData = Arrays.copyOf(elementData, newCapacity)

API文档的解释是:复制指定的数组,截取或用 null 或 0 填充(如有必要),以使副本具有指定的长度

也就是说,通过Arrays.copyOf,将数组elementData的长度扩大到newCapacity,扩大的部分填充由数组类型决定

例如:

        int[] a = new int[]{1,2}; 
        System.out.println("扩容前长度:" + a.length); 
        a = Arrays.copyOf(a, 3); 
        System.out.println("扩容后长度:" + a.length); 
        System.out.println("填充的数据:" + a[2]);

输出:
扩容前长度:2
扩容后长度:3
填充的数据:0

  我们来查看一下Arrays.copyOf源代码,看看它做了什么:

    public static int[] copyOf(int[] original, int newLength) { int[] copy = new int[newLength]; 
        System.arraycopy(original, 0, copy, 0, 
                         Math.min(original.length, newLength)); return copy; 
    }

  Arrays.copyOf方法中,重新创建了一个新长度的数组,并且通过System.arraycopy方法把原来的数组复制到新数组中,最后返回。System.arraycopy是一个本地的系统方法,采用的是直接对内存中的数据块进行复制,是一块一块复制的(操作系统中有讲到),所以比我们平时for循环一个一个复制要快得多。

三、效率

  值得注意这些问题,什么时候会扩容?扩容会影响效率吗?如果影响要怎么避免?
  当增加元素后的size 大于 原来的size时,就需要扩容,而扩容需要复制数组,小数据量还好,而大数据量的时候肯定很影响效率!注意到,ArrayList中有两个和size相关构造函数:

    public ArrayList() { this(10); 
    } 
 public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ 
                                               initialCapacity); this.elementData = new Object[initialCapacity]; 
    }

  第一个构