浅谈ArrayList源码实现

本文记录笔者对JDK1.8下ArrayList源码的解读

ArrayList中属性解读

  • transient Object[] elementData; //顾名思义,属性为数据空间,有容量大小限制,其中存放add进的数据
  • private static final Object[] EMPTY_ELEMENTDATA = {};//如果在调用构造方法传入初始容量为0时候,会创建一个空elementData
  • private int size;//该属性为List中拥有的元素个数

add:添加元素

boolean add(E e)

此方法为单独插入元素到List中

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 确保新元素可添加的条件为容量大于等于size+1
        elementData[size++] = e;//在数组尾部添加元素,顺便size+1
        return true;
    }

void add(int index, E element)

此方法为在index处插入元素element

public void add(int index, E element) {
        rangeCheckForAdd(index);//数组越界Check,条件:index > size || index < 0

        ensureCapacityInternal(size + 1);  //这句为了确保要插入数据容量至少大于size+1,内部实现中如果minCapacity - elementData.length > 0会调用grow方法扩容。
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//arraycopy是一个native方法,作用是将要插入位置后的所有元素后移一位,在index处预留出空间以供新元素插入
        elementData[index] = element;//把预插入元素放置到index位置
        size++;//list大小增加
}

grow:扩容

此方法在add前会进行容量检测,可能调用扩容方法

    private void grow(int minCapacity) {//传参为最小需要扩容的大小
        // overflow-conscious code
        int oldCapacity = elementData.length;//原有容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量为原容量的1.5倍
        if (newCapacity - minCapacity < 0)//如果新容量(1.5倍)小于最小需要容量(原因:int取值范围越界)
            newCapacity = minCapacity;//赋值为最小所需容量
        if (newCapacity - MAX_ARRAY_SIZE > 0)//如果新容量大于int最大值-8
            newCapacity = hugeCapacity(minCapacity);//则利用hugeCapacity进行计算复制大小(后面有写)
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//分配好新空间,可以对旧数组进行扩容
    }


    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow 溢出
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE ://最小分配大小大于Integer_Max-8则复制为int最大值
            MAX_ARRAY_SIZE;
    }

//此外,如ensureCapacity等方法,内部都是调用grow来进行扩容,没什么其他内容,这里就不谈了

remove:移除元素

public E remove(int index):按index移除

    public E remove(int index) {
        rangeCheck(index);//检查index越界

        modCount++;//标记修改次数,类似版本号
        E oldValue = elementData(index);//取出index位置的元素

        int numMoved = size - index - 1;//需要移动元素的个数,也就是如果从index位置删除元素,那么后续所有其他元素需要前移一位来补空缺
        if (numMoved > 0)//如果移动的元素不是最后一个元素,则都需要前移后面所有元素,由此可见,如果移除index=0的元素的效率最差,需要数组整体前移
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);//移动操作
        elementData[--size] = null; // clear to let GC do its work,将最后一个元素位置置为null,原注释解释方便GC回收垃圾

        return oldValue;//返回删除的元素
    }

public boolean remove(Object o):按元素移除

public boolean remove(Object o) {
        if (o == null) {//如果要移除元素为null
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {遍历查找数值=null的元素
                    fastRemove(index);//实际就是封装了之前移除过程
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {//使用equals来进行比较,如果相等,则移除
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

//此方法基本上就是对于之前移除过程进行封装,可参考public E remove(int index)中的移除注释
private void fastRemove(int index) {
        modCount++;
        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
    }

Iterator:内部实现迭代器

public Iterator<E> iterator() {//默认调用此方法
            return listIterator();//其中会调用listIterator(0),也就是从0位置开始迭代
}        

public ListIterator<E> listIterator(final int index) {
            checkForComodification();//检测修改版本号,for concurrent
            rangeCheckForAdd(index);//检测越界
            final int offset = this.offset;

            return new ListIterator<E>() {
                int cursor = index;//内部维护索引,默认为0开始
                int lastRet = -1;//记录上一次返回的索引,初始化为-1
                int expectedModCount = ArrayList.this.modCount;

                public boolean hasNext() {//是否有下一个元素
//这里使用sublist,实际上内部有属性指向parent(当前list),可理解为就是当前list
                    return cursor != SubList.this.size;//判断游标是否到达list的size

                }

                @SuppressWarnings("unchecked")
                public E next() {
                    checkForComodification();//检查修改次数版本号
                    int i = cursor;
                    if (i >= SubList.this.size)//如果越界,抛出无元素异常
                        throw new NoSuchElementException();
                    Object[] elementData = ArrayList.this.elementData;//创建对list的引用
                    if (offset + i >= elementData.length)//越界
                        throw new ConcurrentModificationException();
                    cursor = i + 1;//此时游标自动后移,为了迭代继续进行
                    return (E) elementData[offset + (lastRet = i)];//返回通过游标取出的元素,更新lastRet为当前返回的索引
                }

                public boolean hasPrevious() {//如果游标不等于0,则有前置元素
                    return cursor != 0;
                }

                @SuppressWarnings("unchecked")
                public E previous() {//返回前置元素,与next方法大同小异
                    checkForComodification();
                    int i = cursor - 1;
                    if (i < 0)
                        throw new NoSuchElementException();
                    Object[] elementData = ArrayList.this.elementData;
                    if (offset + i >= elementData.length)
                        throw new ConcurrentModificationException();
                    cursor = i;
                    return (E) elementData[offset + (lastRet = i)];
                }

                @SuppressWarnings("unchecked")//支持lambda表达式特性的方法
                public void forEachRemaining(Consumer<? super E> consumer) {
                    Objects.requireNonNull(consumer);
                    final int size = SubList.this.size;
                    int i = cursor;
                    if (i >= size) {
                        return;
                    }
                    final Object[] elementData = ArrayList.this.elementData;
                    if (offset + i >= elementData.length) {
                        throw new ConcurrentModificationException();
                    }
                    while (i != size && modCount == expectedModCount) {
                        consumer.accept((E) elementData[offset + (i++)]);
                    }
                    // update once at end of iteration to reduce heap write traffic
                    lastRet = cursor = i;
                    checkForComodification();
                }

                public int nextIndex() {//返回游标下一次访问的元素位置
                    return cursor;
                }

                public int previousIndex() {//返回上一个访问的位置
                    return cursor - 1;
                }

                public void remove() {//移除元素
                    if (lastRet < 0)
                        throw new IllegalStateException();
                    checkForComodification();//同上

                    try {
                        SubList.this.remove(lastRet);//内部调用此list的remove方法去移除刚访问过的元素
                        cursor = lastRet;//移除后,内部游标则跳到上一次访问元素位置
                        lastRet = -1;//上一次访问元素因为被删除,所以lastret又置为-1
                        expectedModCount = ArrayList.this.modCount;
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                public void set(E e) {
                    if (lastRet < 0)
                        throw new IllegalStateException();
                    checkForComodification();//修改版本检测

                    try {
                        ArrayList.this.set(offset + lastRet, e);//调用set方法设置当前元素为新值
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                public void add(E e) {
                    checkForComodification();

                    try {
                        int i = cursor;
                        SubList.this.add(i, e);//在当前游标位置添加元素
                        cursor = i + 1;//游标后移一位
                        lastRet = -1;
                        expectedModCount = ArrayList.this.modCount;//设置期望的修改版本号,此处运用了类似CAS的控制机制,在许多方法调用前会有checkForComodification()方法来进行修改版本号检测
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }


                final void checkForComodification() {//修改版本号检测
                    if (expectedModCount != ArrayList.this.modCount)
//这里使用了期望修改版本号与当前修改版本号对比,来判断是否期间有其他线程修改了这个值,利用CAS机制,以支持并发操作;如果不一致抛出并发修改异常
                        throw new ConcurrentModificationException();
                }
            };
        }

get and set:简单的获取元素和设置元素

     public E get(int index) {
        rangeCheck(index);//检查越界

        return elementData(index);//直接返回元素
    }


    public E set(int index, E element) {
        rangeCheck(index);//检查越界

        E oldValue = elementData(index);//记录index位置的旧元素
        elementData[index] = element;//将index位置设置为新元素
        return oldValue;//返回旧元素
    }

思考:

1、由上面源代码,可以总结,许多地方都用到了ensureCapacity与modcount版本号检测方法,如果我们学过设计模式后,考虑是否可以使用一个代理类,来完成一些鲁棒性等内容的前置代理?

2、对于remove的两个方法,可以明显发现,数组前移一个是写在方法内,另一个则是调用封装方法,所以这一点可以统一使用封装方法,重用代码。

3、本文未讲解到支持lambda部分的源码,之后笔者会补充。

其他文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注