美文网首页
ArrayList源码解析

ArrayList源码解析

作者: 囧囧有神2号 | 来源:发表于2017-08-06 15:47 被阅读0次
    这仨货
    1. elementData:就是实际存储元素的数组,被transient,表明不参与序列化,意味着elementData里的数据仅存在调用者的内存中
    2. EMPTY_ELEMENT空数组
    3. DEFAULTCAPACITY_EMPTY_ELEMENT: 不同于EMPTY_ELEMENT,这个空的Object[]有啥用?
      (为什么要两个空数组?3号空数组用法如下,那么二号呢?其实二号要解决的是当我想创建一个空集合时,即调用new ArrayList(0),在随后调用add方法时,不会被自动扩容成大小为10,这就是二者区别-defaultCapacity。)


      无参构造函数

      当调用无参构造函数时,将它赋给elementData,这样做感觉好像没多大用?其实它就像一个标记,什么时候会用到它呢?当第一个元素被添加的时候

    add()

    size: 是实际元素个数

    扩容三姐妹之二三

    ---DEFAULT_CAPACITY = 10;也就是说当你new ArrayList()调用add(E e)或是其它add方法后,会根据需要创建一个Object[minCapacity]初始数组-------(感觉写了半天细枝末节的东西)
    ---modeCount是用作Fail-Fast机制
    ---grow()执行数组扩容操作,利用Arrays.copyOf(),继续追踪发现是调用了System.arrayCopy(),创建了一个扩容后大小的新数组copy[],返回copy

    ArrayList还有一类构造函数:ArrayList(Collection<? extends E> c),它什么原理呢? Collection接口有个toArray(),举例如具体实现类ArrayList的toArray()里调用Arrays.copyOf(),如上所述它返还一个copy[],而该构造函数里就利用了这个来将c转化为数组赋给elementData。其实很多地方都用到了Arrays.copy(),比如trimToSize()..

    ADD():

    ArrayList其实是一个动态变化的数组,我们来看它在添加删除元素时的变化:
    从add入手:add(E e); add(int index; E elementi); add(Collention<? extends E> c); add(int index, Collection<? extends E> c)四种方法。

    1. add(E e):首先会调用ensureCapacityInternal(size+1),该方法又会调用ensureEcplicitCapacity(),在该方法里如果size+1>elementData.length,则调用growth()方法进行扩容,逻辑如下
    扩容

    一般情况下扩容为原来的1.5倍,这里又用到 了Arrays.copyOf()

    1. add(int index, E e)
    add

    显而易见,先判断index是否越界,在进行扩容判断,之后调用System.arraycopy()将原数组index及之后的元素后挪一位,最后添加

    1. add(Collention<? extends E> c)与add(int index, Collection<? extends E> c)核心类是toArray()与System.arraycopy(),与之前提的一样(代码不贴了--累人!)

    indexOf(Object o)与lastIndexOf(Object o)都会对o进行null判断,因为ArrayList可以添加null;clone()为浅拷贝,elementData数据不包括在内

    get,set,remove方法都没什么好说的

    removeAll(Collection<?> c), retainAll(Collection<?> c)

    这两个方法中若c==null则抛出NullPointException异常,接着调用batchRemove(Collection<?> c, boolean complement)

        private boolean batchRemove(Collection<?> c, boolean complement) {
            final Object[] elementData = this.elementData;
            int r = 0, w = 0;
            boolean modified = false;
            try {
                for (; r < size; r++)
                    if (c.contains(elementData[r]) == complement)
                        elementData[w++] = elementData[r];
            } finally {
                // Preserve behavioral compatibility with AbstractCollection,
                // even if c.contains() throws.
                if (r != size) {
                    System.arraycopy(elementData, r,
                                     elementData, w,
                                     size - r);
                    w += size - r;
                }
                //w == size则说明没有改变,返回false,removeAll与retainAll结果为false
                if (w != size) {
                    // clear to let GC do its work
                    for (int i = w; i < size; i++)
                        elementData[i] = null;
                    modCount += size - w;
                    size = w;
                    modified = true;
                }
            }
            return modified;
        }
    

    该方法在complement为true时,取elementData与c的交集,即相同部分保留;为false时,取elementData独有部分保留。所以removeAll调用batchRemove(c, false),retainAll调用batchRemove(c, true);

    迭代器

    1. Iterator
        private class Itr implements Iterator<E> {
            int cursor;       // 下一个要返回的元素的下标
            int lastRet = -1; // 被返回的元素的下标,即调用next()返回elementData[lastRet]
            int expectedModCount = modCount; //fail-fast,迭代中若数组被更改(add,remove
    添加删除操作)会造成二者不相等,抛ConcurrentModificationException
            public boolean hasNext() {
                return cursor != size;
            }
    
            @SuppressWarnings("unchecked")
            public E next() {
                checkForComodification();  //fail-fast
                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); //调用的是ArrayList的remove方法
                    cursor = lastRet; //lastRet表示被删除的位置,后被cusor前挪一位填补上,cusor变为lastRet
                    lastRet = -1;
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }
            //如果相对elementData中每个元素都执行相同操作,你可以写一类实现Consumer接口,
    复写accept(),在调用该方法
            @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();
            }
        }
    

    Consumer是个函数式接口,函数描述符为:T → void, 多用于lambda

    1. ListIterator
       //继承itr,实现ListIterator implements Iterator<E>,ListIterator拓展了Iterator
     private class ListItr extends Itr implements ListIterator<E> {
            ListItr(int index) {
                super();
                cursor = index;
            }
    //是否有前一个元素
            public boolean hasPrevious() {
                return cursor != 0;
            }
    //下一个元素位置
            public int nextIndex() {
                return cursor;
            }
    //前一个元素位置
            public int previousIndex() {
                return cursor - 1;
            }
    //返回前一个元素,即cusor-1处;cusor退一位,反复调用实现倒叙;如果之后你接着调用next(),
    previous()将返回同一个结果
            @SuppressWarnings("unchecked")
            public E previous() {
                checkForComodification();
                int i = cursor - 1;
                if (i < 0)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i;
                return (E) elementData[lastRet = i];
            }
    //下面的add()方法会重置lastRet = -1;所以add后避免调用set
            public void set(E e) {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();
    
                try {
                    ArrayList.this.set(lastRet, e);
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }
    //add会插入到原本调用next函数返回的元素之前,cusor自增1仍指向原本next函数返回的元素,
    此时可通过previous来得到新增的元素;这样设计保证了next函数不受影响
            public void add(E e) {
                checkForComodification();
    
                try {
                    int i = cursor;
                    ArrayList.this.add(i, e);
                    cursor = i + 1;
                    lastRet = -1;
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }
        }
    

    SubList extends AbstractList<E> implements RandomAccess

    内部类private class SubList,作用就是生成一个[fromeIndex,toIndex)大小的小型List,麻雀虽小五脏俱全,只能通过subList(int fromIndex, int toIndex)函数调用,功能实现依赖外部类ArrayList,实现了自己的迭代器ListIterator。

    还有一方法Arraylist.sort在这篇文章里介绍MergeSort与TimSort,ComparableTimSort

    相关文章

      网友评论

          本文标题:ArrayList源码解析

          本文链接:https://www.haomeiwen.com/subject/tqwglxtx.html