从源码看集合ArrayList

可能大家都知道，java中的ArrayList类，是一个泛型集合类，可以存储指定类型的数据集合，也知道可以使用get(index)方法通过索引来获取数据，或者使用for each 遍历输出集合中的内容，但是大家可能对其中的具体的方法是怎么实现的不大了解，本篇就将从jdk源码的角度看看什么是动态扩容数组（毕竟我们不应该停留在会用的层面上）。本篇主要从以下几个角度看看ArrayList:

add及其重载方法是如何实现的
remove及其重载方法是如何实现的
迭代器的本质及实现的基本原理

一、add方法添加元素到集合中

实际上ArrayList内部是用的 transient Object[] elementData;这么一条语句定义的一个Object类型的数组，因为我们知道数组一旦被初始化长度就不能再发生改变，那我们的ArrayList是怎么做到可以不断的添加元素到集合中的呢？其实就是通过创建新的数组，将原来的数组中的内容转移到新的数组中来，实现动态扩容。具体的我们看源码：

public static void main(String[] args){

		ArrayList<Integer> list = new ArrayList<Integer>();

		list.add(1);

	}

/*这是最简单的add方法*/

public boolean add(E e) {

        ensureCapacityInternal(size + 1);  // Increments modCount!!

        elementData[size++] = e;

        return true;

    }

当调用此add方法时，将指定了类型的数据传入（变量e接受），首先执行第一条语句：ensureCapacityInternal(size + 1);，这条语句实际上就是用来判断size+1之后是否会导致原数组长度溢出，如果会就扩充数组容量，如果没有就什么也不做。我们看看ensureCapacityInternal方法内部源码：

private void ensureCapacityInternal(int minCapacity) {

        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

        }

        ensureExplicitCapacity(minCapacity);

    }

	/*ensureExplicitCapacity*/

    private void ensureExplicitCapacity(int minCapacity) {

        modCount++;

        // overflow-conscious code

        if (minCapacity - elementData.length > 0)

            grow(minCapacity);

    }

首先判断当前数组是否为空，默认数组长度为DEFAULT_CAPACITY=10，minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);表示：如果数组还未初始化即刚刚声明并未做任何操作，就取10作为数据容量值，然后调用方法ensureExplicitCapacity(minCapacity);设置数组长度。

接受过传入的数据容量值，执行modCount++;增加修改次数（后文会说为什么有这个计数器），判断数据容量值是否比现数组长度大，如果数据容量值超过现有数组长度（需要扩容），执行：grow(minCapacity);，我们可以看看他是怎么进行扩容的。

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

    }

          这条语句 int newCapacity = oldCapacity + (oldCapacity >> 1);通过位右移将新数组容量扩充为原来的1.5倍。数组的每次扩容都是，扩充为原来的1.5倍。下面是一系列的判断，最终确定新数组的长度，调用Arrays.copyOf方法，新建数组并且转移原数组内容。再往下，就不深究了。。

          最后小结一下整个过程，调用add 方法首先调用ensureCapacityInternal方法，如果原数组是空的就将10作为数据容量值，然后判断数据容量值是否大于当前数组长度（如果当前数组是空数组的话，自然长度为0），然后进行扩充数组容量，创建新数组返回。如果原数组非空，将判断数据容量值是否大于现数组长度，否说明添加此新元素之后数据量长度仍然小于数组长度（数组长度足够），是就会调用grow方法创建新数组赋值elementData数组。

          add的另一个比较麻烦的方法是，addAll方法，其他的重载方法类似，本篇不再赘述。下面我们一起看看addAll方法原理。

public boolean addAll(Collection<? extends E> c) {

        Object[] a = c.toArray();

        int numNew = a.length;

        ensureCapacityInternal(size + numNew);  // Increments modCount

        System.arraycopy(a, 0, elementData, size, numNew);

        size += numNew;

        return numNew != 0;

    }

addAll()方法的动态扩容和添加数值都和add 类似，我们主要理解一下，他的这个参数是什么意思，也顺便复习一下泛型相关内容。

          大家知道Collection<? extends E>作为类型，有哪些类型可以作为形参传入？假如E是Number类型，Collection<Integer>，Collection<Float>，Collection<Double>，都是可以作为形参传入的。而所有继承Collection接口的类也可以作为形参传入，例如：List<Integer>，Set<Integer>，List<Double>，ArrayList<Integer>，等等，但在本方法中是需要调用toArray这个具体的方法的，所以只能使具体类作为形参传入，这样就保证，形参是可以是任意类型的集合（前提是此类型必须继承与我们指定的E）。

     二、Remove方法的实现原理

          既然集合是可以添加元素的，自然也是可以删除元素的，接下来我们一起看看ArrayList的Remove方法。

/*根据集合索引删除任意位置的元素*/

 public E remove(int index) {

        rangeCheck(index);

        modCount++;

        E oldValue = elementData(index);

        int numMoved = size - index - 1;

        if (numMoved > 0)

            System.arraycopy(elementData, index+1, elementData, index,

                             numMoved);

        elementData[--size] = null; // clear to let GC do its work

        return oldValue;

    }

          第一行代码很简单，rangeCheck(index);，检查指定索引是否越界，如果越界抛出异常。然后计算出，移除后的数据容量，因为经过判断index是<size的，也就是说numMoved >=0。判断是否大于0，如果等于0表示原来就一个数据，直接将其赋值null交给GC回收即可。如果大于0，执行System.arraycopy方法，因为此方法为native方法，我们不得而知它是如何实现的，但是我们可以大致猜出他是这样实现的：以索引位置开始，索引位置后面的数组元素向前覆盖。例如：index=3；elementData[3]=elementData[4]，elementData[4]=elementData[5]等等。最后将最后位置的元素赋值为null。

          以上便是remove方法的简单原理，至于其他重载与上述类似。接下来，我们看看重要的迭代器。

     三、迭代器

public interface Iterator<E> {

 boolean hasNext();

 E next();

 default void remove() {

        throw new UnsupportedOperationException("remove");

    }

 default void forEachRemaining(Consumer<? super E> action) {

        Objects.requireNonNull(action);

        while (hasNext())

            action.accept(next());

    }

}

我们把接口 Iterator<E>叫做迭代器接口。通过反复调用next方法可以访问到所有的元素，当访问到最后一个元素的下一的位置时，就会抛出异常，所以我们常常在调用next方法之前调用hasNext方法判断是否还有下一个元素，remove方法表示删除元素（一个要求，调用remove方法之前一定要先调用next方法，这一点下文说）

了解完 Iterator<E>，我们看看另一个和它相关的接口，Iterable<E>：

public interface Iterable<T> {

Iterator<T> iterator();

default void forEach(Consumer<? super T> action) {

        Objects.requireNonNull(action);

        for (T t : this) {

            action.accept(t);

        }

    }

 default Spliterator<T> spliterator() {

        return Spliterators.spliteratorUnknownSize(iterator(), 0);

    }

}

这个接口 Iterable<E>表示可迭代，强调了可以迭代的这种能力。声明一个方法 iterator();返回 Iterable<E> 迭代器接口，所有实现了 Iterable<E>接口的类都是可以使用for each 循环遍历集合中元素的。当我们的类实现 Iterable<E>接口时，可以使用for each 循环集合，其实内部还是，通过调用方法 iterator()实现当前集合和迭代器的一种类似于绑定的过程，最终返回迭代器接口，实际上for each 语法还是调用的是迭代器接口中声明的方法类似：

ArrayList<Integer> list = new ArrayList<Integer>();

list.add(1);

list.add(2);

list.add(3);

list.add(4);

list.add(5);

Iterator<Integer> i = list.interator();

while(i.hasNext()){

	System.out.println(i.next);

}

/*for each 语句的本质其实就是这样*/

下面要说的关于迭代器的一个重要的特性，迭代器的结构不可破坏性。就是说，在进行迭代的过程中，是不允许改变原集合的结构性的，集合的结构性就是指：对集合进行添加（add），删除（remove）。对集合的修改操作不属于破坏集合的结构性。例如：

for(Integer a : list){

	if(a == 3){

		list.remove(a);  //throw exception

	}

}

//破坏了集合的结构性，不允许的。

要想解决这个问题就要看看ArrayList中是怎么实现迭代器的。实际上是通过内部类来实现迭代器接口的。

public Iterator<E> iterator() {

        return new Itr();

    }

//内部类，我们只看其中remove方法

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;

   //remove方法

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

            }

        }

我们之所以在for each循环中不能破坏结构性，是因为for each每次调用next方法时，都会检查是否破坏了结构性，而这种检查就是依靠modCount 这个变量，通过对比前后的修改次数得出是否破坏了结构性，在我们的remove方法中，调用了外部类remove方法删除元素，并且 expectedModCount = modCount; 更新了修改次数变量，使得下次检查时，不会出现结构性破坏。

Iterator<Integer> it = list.interator();

while(it.hasNext()){

	if(it.next().equals(1)){

		it.remove();

	}

}

最后想要强调一点的是，迭代器中调用remove方法之前一定要，调用next方法，例如：

Iterator<Integer> it = list.interator();

while(it.hasNext()){

	it.remove();

}//报错

现在大家能够想明白为什么在调用remove方法之前一定要调用next方法了吧，因为next方法为lastRet和cursor重置数值，如果没有next方法，lastRet为 -1 自然是不能用作删除的。

本篇就此结束，如果文中有博主说的不清楚的地方，望大家指出！

巴特西

从源码看集合ArrayList

最新文章

热门文章