java开发进阶程序员JVM实践

和我一起读Java8 ArrayList源码

2017-09-09  本文已影响261人  卡巴拉的树

集合系列文章:和我一起读Java8 LinkedList源码
首先放一张Java集合接口图:

14种容器接口

Collection是一个独立元素序列,这些元素都服从一条或多条规则,List必须按照插入的顺序保存元素,而Set不能有重复元素,Queue按照排队规则来确定对象产生的顺序。
List在Collection的基础上添加了大量的方法,使得可以在List的中间插入和移除元素。
有2种类型的List:

下面正式进入ArrayList实现原理,主要参考Java8 ArrayList源码

类定义

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

ArrayList 继承了AbstractList并且实现了List,所以具有添加,修改,删除,遍历等功能
实现了RandomAccess接口,支持随机访问
实现了Cloneable接口,支持Clone
实现了Serualizable接口,可以被序列化

底层数据结构

transient Object[] elementData;  //存放元素的数组
private int size; //ArrayList实际存放的元素数量

ArrayList的底层实际是通过一个Object的数组实现,数组本身有个容量capacity,实际存储的元素个数为size,当做一些操作,例如插入操作导致数组容量不够时,ArrayList就会自动扩容,也就是调节capacity的大小。

初始化

指定容量大小初始化

/**
     * 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) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

初始化一个指定容量的空集合,若是容量为0,集合为空集合,其中
private static final Object[] EMPTY_ELEMENTDATA = {};,容量也为0。

无参数初始化

/**
 * Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

无参数初始化,其实DEFAULTCAPACITY_EMPTY_ELEMENTDATA的定义也为:
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};EMPTY_ELEMENTDATA的区别是当第一个元素被插入时,数组就会自动扩容到10,具体见下文说add方法时的解释。

集合作为初始化参数

/**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

构造一个包含指定 collection 的元素的列表,这些元素按照该collection的迭代器返回它们的顺序排列的。

size和IsEmpty

首先是两个最简单的操作:

public int size() {
        return size;
    }
public boolean isEmpty() {
        return size == 0;
    }

都是依靠size值,直接获取容器内元素的个数,判断是否为空集合。

Set 和Get操作

Set和Get操作都是直接操作集合下标

public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

在操作之前都会做RangeCheck检查,如果index超过size,则会报IndexOutOfBoundsException错误。
elementData的操作实际就是基于下标的访问,所以ArrayList 长于随机访问元素,复杂度为O(1)。

@SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

Contain

public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

contains 函数基于indexOf函数,如果第一次出现的位置大于等于0,说明ArrayList就包含该元素, IndexOf的实现如下:

public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

ArrayList是接受null值的,如果不存在该元素,则会返回-1,所以contains判断是否大于等于0来判断是否包含指定元素。

Add和Remove

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

首先确保已有的容量在已使用长度加1后还能存下下一个元素,这里正好分析下用来确保ArrayList容量ensureCapacityInternal函数:

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

这边可以返回看一开始空参数初始化,this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA, 空参数初始化的ArrayList添加第一个元素,上面的if语句就会调用,DEFAULT_CAPACITY定义为10,所以空参数初始化的ArrayList一开始添加元素,容量就变为10,在确定了minCapacity后,还要调用ensureExplicitCapacity(minCapacity)去真正的增长容量:

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

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

这里modCount默默记录ArrayList被修改的次数, 然后是判断是否需要扩充数组容量,如果当前数组所需要的最小容量大于数组现有长度,就调用自动扩容函数grow:

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); //扩充为原来的1.5倍
        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);
    }

oldCapacity记录数组原有长度,newCapacity直接将长度扩展为原来的1.5倍,如果1.5倍的长度大于需要扩充的容量(minCapacity),就只扩充到minCapacity,如果newCapacity大于数组最大长度MAX_ARRAY_SIZE,就只扩容到MAX_ARRAY_SIZE大小,关于MAX_ARRAY_SIZE为什么是private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;,我文章里就不深究了,感兴趣的可以参考stackoverflow上的有关回答:
Why the maximum array size of ArrayList is Integer.MAX_VALUE - 8?

Add还提供两个参数的形式,支持在指定位置添加元素。

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位置起的所有元素后移一位,然后在index处插入元素。

在index=2处插入5
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;
    }

Remove接口也很好理解了,存储index位置的值到oldView作为返回值,将index后面所有的元素都向前拷贝一位,不要忘记的是还要将原来最后的位置标记为null,以便让垃圾收集器自动GC这块内存。
还可以根据对象Remove:

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

找到对象所在位置,调用FastRemove函数快速删除index位置上的元素,FastRemove也就是比remove(index)少了个边界检查。

clear
/**
     * Removes all of the elements from this list.  The list will
     * be empty after this call returns.
     */
    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

由于Java有GC机制,所以不需要手动释放内存,只要将ArrayList所有元素都标记为null,垃圾收集器就会自动收集这些内存。

Add和Remove都提供了一系列的批量操作接口:

public boolean addAll(Collection<? extends E> c);
public boolean addAll(int index, Collection<? extends E> c);
protected void removeRange(int fromIndex, int toIndex) ;
public boolean removeAll(Collection<?> c) ;

相比于单文件一次只集体向前或向后移动一位,批量操作需要移动Collection 长度的距离。

Iterator与fast_fail

首先看看ArrayList里迭代器是如何实现的:

private class Itr implements Iterator<E> {
        int cursor;       // 记录下一个返回元素的index,一开始为0
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;  //这边确保产生迭代器时,就将当前modCount赋给expectedModCount

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

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor; //访问元素的index
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1; //不断加1,只要不断调用next,就可以遍历List
            return (E) elementData[lastRet = i];  //lastRet在这里会记录最近返回元素的位置
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);  //调用List本身的remove函数,删除最近返回的元素
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount; //上面的Remove函数会改变modCount,所以这边expectedModCount需要更新
            } 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();
        }
    }

ArrayList里可以通过iterator方法获取迭代器,iterator方法就是new一个上述迭代器对象:

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

那么我们看看Itr类的主要方法:

在next和remove操作之前,都会调用checkForComodification函数,如果modCount和本身记录的expectedModCount不一致,就证明集合在别处被修改过,抛出ConcurrentModificationException异常,产生fail-fast事件。

fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。
例如:当某一个线程A通过iterator去遍历某集合的过程中,若该集合的内容被其他线程所改变了;那么线程A访问集合时,就会抛出ConcurrentModificationException异常,产生fail-fast事件。
一般多线程环境下,可以考虑使用CopyOnWriteArrayList来避免fail-fast。

上一篇下一篇

猜你喜欢

热点阅读