coding……
但行好事 莫问前程

Java编程拾遗『容器——ArrayList』

上篇文章简单介绍了一下Java集合框架中两个最常见的接口,表示集合的Collection和表示K-V映射的Map。本篇文章重点介绍一下Collection的一个重要实现类,动态数组容器类ArrayList。由于在上一篇文章已经介绍了Collection接口的通用方法,本篇文章会简单介绍一下ArrayList中的方法,重点介绍一下内部原理。

1. 使用规则

ArrayList是基于数组实现的一个动态数组,在使用过程中,如果容量不足,会进行动态扩容,声明如下:

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

继承AbstractList抽象类,实现泛型接口List的原因在上一篇文章已经说明——使用AbstractList抽象类更方便实现List接口(AbstractList中已经实现了很多List接口中的方法)。另外ArrayList实现了RandomAccess接口,支持快速随机访问(通过数组下标序号进行快速访问);实现了Serializable接口,支持序列化,能够通过序列化传输;实现了Cloneable接口,可以被克隆。

S.N. 方法 说明
1 public ArrayList()
public ArrayList(Collection<? extends E> c)
public ArrayList(int initialCapacity)
构造方法
2 public boolean add(E e)
public boolean addAll(Collection<? extends E> c)
在ArrayList末尾添加一个/多个元素
3 public void add(int index, E element)
public boolean addAll(int index, Collection<? extends E> c)
在ArrayList index位置起添加一个/多个元素
4 public void clear() 清空ArrayList
5 public Object clone() clone方法
6 public boolean contains(Object o) 判断ArrayList中是否包含o
7 public void ensureCapacity(int minCapacity) 将ArrayList内部Object数组容量扩展为minCapacity,
如果minCapacity > Object[].length
8 public void forEach(Consumer<? super E> action) 迭代遍历访问ArrayList
9 public E get(int index) 获取ArrayList index位置的元素
10 public int indexOf(Object o) 获取o在ArrayList中第一次出现的index,如果不存在返-1
11 public boolean isEmpty() 判断ArrayList中是否存在元素
12 public Iterator<E> iterator() 返回ArrayList的Iterator迭代器
13 public int lastIndexOf(Object o) 返回o在ArrayList中的最后一次出现的index
14 public ListIterator<E> listIterator() 返回ArrayList从index 0开始的ListIterator迭代器,与Iterator不同的是
ListIterator支持双向迭代
15 public ListIterator<E> listIterator(int index) 返回ArrayList从index位置开始的ListIterator迭代器
16 public E remove(int index) 从ArrayList中移除index位置的元素
17 public boolean remove(Object o) 从ArrayList中移除第一次出现的元素o,如果元素o不存在,返false
18 public boolean removeAll(Collection<?> c) 从ArrayList中移除包含的c中所有元素
19 public boolean removeIf(Predicate<? super E> filter) 如果集合中的元素满足Predicate,则删除元素,如果调用改变了集合返回true
20 public void replaceAll(UnaryOperator<E> operator) 将ArrayList中每一个元素,根据UnaryOperator规则,替换为另一个元素
21 public boolean retainAll(Collection<?> c) 保留ArrayList中集合C中存在的元素
22 public E set(int index, E element) 将ArrayList index位置的元素设置为element
23 public int size() 返回ArrayList中元素的个数
24 public void sort(Comparator<? super E> c) 根据Comparator排序规则,对ArrayList进行排序
25 public Spliterator<E> spliterator() 返回ArrayList的并行遍历Spliterator
26 public List<E> subList(int fromIndex, int toIndex) 返回ArrayList中从fromIndex到toIndex的子List,区间左闭右开
27 public Object[] toArray() 转Object数组
28 public <T> T[] toArray(T[] a) 转T数组(需要传入一个特性类型的数组)
29 public void trimToSize() trim ArrayList中数组的length为实际元素个数大小

2. 实现源码分析

查看ArrayList内部源码可以发现,ArrayList的实现最终要的两个成员就是用来存放元素的Object[]数组,还有一个用来表示实际元素个数的size,ArrayList内部所有的方法都试基于这两个成员实现的。如下所示:

transient Object[] elementData;
private int size;

除此之外,还有三个共享的静态常量,如下:

private static final int DEFAULT_CAPACITY = 10; //elementData数组默认容量

private static final Object[] EMPTY_ELEMENTDATA = {}; //空数组

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //默认容量空元素数组

2.1 默认构造函数

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

先讲一个结论,通过默认构造函数构造的ArrayList,默认容量是10。通过上述源码可以看到默认构造函数实际上是将内部elementData数组初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA,DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的定义是一个容量为0的空数组,但是语义上却说这是个有着默认容量10的空数组,那么这个默认容量是怎么实现的?其实是通过Add方法来实现这个默认容量设置的

2.2 add(E e)方法

add方法定义如下所示:

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

基本原理很简单,就是通过ensureCapacityInternall确保数组容量是够的,然后像内部数组中添加元素。ensureCapacityInternall源码如下:

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

ensureCapacityInternal方法内部调用了两个方法,分别是用来计算需要的最小容量的calculateCapacity方法,和用来分配容量的ensureExplicitCapacity方法,下面先来看一下calculateCapacity方法:

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

这里可以看到,假如elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA(通过默认构造函数构造的情况),方法的返回值是肯定是DEFAULT_CAPACITY(因为此时calculateCapacity方法入参minCapacity是1)。接下来将返回值作为ensureExplicitCapacity方法的实参传入分配空间,如下:

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

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

modCount表示内部的修改次数,modCount++就表示增加修改次数,关于这个modCount,接下来会解释。如果计算得到的ArrayList需要的最小容量大于现elementData数组的length,说明需要进行扩容了。这里特殊提一下ArrayList通过默认构造函数构造然后add元素的过程,上面已经讲过,这种场景下计算得到的minCapacity是10,但是此时elementData是DEFAULTCAPACITY_EMPTY_ELEMENTDATA(长度为0的空数组),所以肯定会执行grow函数进行扩容。下面看一下gorw扩容操作:

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

右移一位相当于除2,所以,ArrayList扩容的逻辑是newCapacity相当于oldCapacity的1.5倍。回到上面讲的通过默认构造函数构造的场景,可以得到newCapacity为10,也就是讲,通过ArrayList的默认构造函数,内部数组的容量默认为10。

2.3 add(int index, E element)方法

这个方法没什么好讲的,就是在ArrayLIst内部elementData数组特定的index位置插入element元素,但是这里我还是想提一下,因为这边有一个我认为比较容易出错的地方,就是插入的位置index不能大于ArrayList中元素个数size。2.2节讲的add方法,相当于一次向ArrayList数组尾部插入元素,这时候我脑洞大开,想能不能通过add(int index, E element)方法构造一个如下的数组:

List<Integer> integerList = new ArrayList<>();
integerList.add(1, 1);
integerList.add(3, 2);

好像通过上述代码就可以构造出如上的ArrayList,但是很不幸的是,报了IndexOutOfBoundsException。来看一下add(int index, E element)方法的源码:

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

首先检查了index,然后通过ensureCapacityInternal保证数组有足够的容量,然后通过System.arraycopy做移位操作,讲index位置及以后的元素往后移一个位置,最后对index位置进行赋值。而上述的IndexOutOfBoundsException就是在检查index的rangeCheckForAdd方法中报的,如下:

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

也就是讲ArrayList的add(int index, E element)操作只能在size范围内进行插入。如果要构造出上图所示的ArrayList可以通过如下方式:

integerList1.add(1);
integerList1.add(2);
integerList1.add(0, null);
integerList1.add(2, null);

2.4 迭代器iterator

上面讲过通过iterator()方法可以获取ArrayList的迭代器,可以用来遍历ArrayList。在讲ArrayList迭代器之前,先明确两个接口的概念:Iterable、Iterator。Iterable接口表示可迭代,定义为:

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接口的类都要实现iterator()方法,iterator()方法返回一个Iterator对象,Iterator接口定义如下:

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());
    }
}
  • hasNext():判断是否还有元素未访问
  • next():返回下一个元素
  • remove():删除最后返回的元素

可以通过Iterator对象对实现了Iterable接口的类进行迭代,如下:

Iterator<Integer> iterator = list.iterator();
while(iterator .hasNext()){
    System.out.println(iterator.next());
}

下面来看一下ArrayList类中,iterator()方法的实现:

public Iterator<E> iterator() {
    return new Itr();
}

可以看到方法返回的是一个Itr类的实例,Itr类是ArrayList中的一个内部类,定义如下:

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;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

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

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

实现比较简单,就是通过cursor表示当前遍历到的元素的index,默认值为0(Iterator迭代器从index 0开始遍历)。然后通过cursor访问ArrayList内部ArrayList数组,实现上述Iterator接口的next、hasNext、remove方法。对于方法的实现这里不详细讲解了,重点来看一下Itr类的成员变量expectedModCount,表示期望修改的次数,初始值为modCount。对于modCount,上面讲过,是ArrayList类中的成员变量,每次ArrayList内部elementData数组改变都会进行modCount++操作。观察Itr实现可以发现,每次调用next、remove及forEachReminding方法访问ArrayList时,都会调用checkForComodification方法,比较modCount和expectedModCount值是否相等,不相等就会抛ConcurrentModificationException异常。所以在这我们可以很明确地得到一个结论:在使用迭代器遍历过程中,改变了容器结构,那么肯定会抛ConcurrentModificationException异常。如下:

List<Integer> integerList = new ArrayList<>();
integerList.add(1);
integerList.add(2);
integerList.add(3);
integerList.add(4);

for(Integer i : integerList) {
    if (i == 2) {
        integerList.remove(i);
    }
}

这里要注意的是,使用for(:)这种形式遍历容器,其实是一种语法糖,编译器会编译成如下形式:

Iterator var2 = integerList.iterator();
while(var2.hasNext()) {
    Integer i = (Integer)var2.next();
    if (i == 2) {
        integerList.remove(i);
    }
}

执行,会抛ConcurrentModificationException异常,也很好解释,因为当i==2时,调用integerList的remove方法,modCount会加1。在下次进入循环,调用迭代器的next方法时,expectedCount和modCount不再相等,抛ConcurrentModificationException异常。但是如果代码如下时,是不会抛异常的:

for(Integer i : integerList) {
    if (i == 3) {
        integerList.remove(i);
    }
}

看着好像很奇怪,命名在使用迭代器遍历时,修改了ArrayList结构,为什么没有抛ConcurrentModificationException异常?其实原因是,当i == 3时,确实执行了integerList的remove方法,modCount也自增了,但是同时ArrayList的size也减少了1,所以下次进行hasNext判断时,cusor == 3 == size,所以hasNext结果为false,不会进入循环体执行next操作,导致没有抛ConcurrentModificationException异常。普遍情况下,我们都认为,在使用迭代器进行迭代时,是不允许通过容器的方法修改容器的。假如有这种需求,在迭代的过程中删除某些特定元素,可以通过迭代器的remove方法实现,如下:

Iterator<Integer> it = integerList.iterator();
while(it.hasNext()){
    if(it.next() == 2){
        it.remove();
    }
}

在Java 8之后,可以调用Collection接口的新方法removeIf实现相同的效果,如下:

integerList.removeIf(integer -> integer == 2);

2.5 迭代器listIterator

除了iterator(),ArrayList中还提供了两个返回ListIterator接口的方法:

public ListIterator<E> listIterator()
public ListIterator<E> listIterator(int index)

理解了上述Iterator接口之后,ListIterator就比较好理解了。ListIterator扩展了Iterator接口,支持双向遍历。增加了一些方法,向前遍历、添加元素、修改元素、返回索引位置等,如下:

public interface ListIterator<E> extends Iterator<E> {
    
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
    
}

比较好理解,这里不多解释了。listIterator()方法返回的迭代器从0开始,而listIterator(int index)方法返回的迭代器从指定位置index开始,比如,从容器末尾往前遍历可以通过如下方式实现:

ListIterator<Integer> iterator = list.listIterator(list.size());
while(iterator.hasPrevious()){
    System.out.println(iterator.previous());
}

3. ArrayList特点

通过上面介绍的ArrayList的内部实现(基于数组实现),可以总结出ArrayList有如下特点:

  • 支持随机访问,按照索引位置进行访问效率很高,时间复杂度为O(1)
  • 插入和删除元素的效率比较低,时间复杂度为O(N),因为数组内部要进行移位
  • 查找元素效率比较低,如果在未排序的前提下,时间复杂度为O(N),如果已排序,可以通过二分查找,时间复杂度为O(logN)

所以如果需求中,容器的变动比较大,有大量的插入删除操作,尽量不要使用ArrayList,可以选用下节要讲的LinkedList容器。

参考链接:

  1. 《Java编程的逻辑》
  2. 《Java核心技术 卷Ⅰ》
  3. JDK源码

赞(0) 打赏
Zhuoli's Blog » Java编程拾遗『容器——ArrayList』
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

zhuoli's blog

联系我关于我

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏