JavaWeb tws mirror java反射机制 docker容器 xml vue安装教程 jquery通过class获取元素 matlab定义空矩阵 android调试工具 python刷题 mysql入门 表白网页源码 python如何实现多线程 python中import java学习平台 java抛出自定义异常 linux基础教程 离散数学及其应用 linux操作系统原理 找茬辅助 workflow中文 java游戏编程 js获取数组长度 送货单管理系统 sdm439 c程序 上单艾克出装 mac修改器 键盘打字手指口诀 g4560配什么显卡 加字幕软件 mysql退出命令 layout软件 mysql定时备份 网红男头像 下载文件管理 obs怎么设置 python编码 js删除元素 x重启
当前位置: 首页 > 学习教程  > 编程语言

【JDK源码】ArrayList源码分析

2020/12/28 18:36:58 文章标签:

目录 1、构造方法 2、扩容机制 3、遍历删除时的陷阱 4、关于ArrayList集合增/删操作慢&#xff0c;查询/修改操作快的分析 5、并发安全问题 6、其他方法 1、构造方法 源码分析如下&#xff1a; public class ArrayList<E> extends AbstractList<E>implemen…

目录

1、构造方法

2、扩容机制

3、遍历删除时的陷阱

4、关于ArrayList集合增/删操作慢,查询/修改操作快的分析

5、并发安全问题

6、其他方法


1、构造方法

源码分析如下:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     * 对象数组
    **/ 
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; 
    /**
     *  集合中包含的元素数量
    **/ 
    private int size;

    /**
     * 无参,默认空数组
    **/
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
    }
    /**
     * 传入指定容量大小
    **/
    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);
        }
    }
    /**
     * 传入指定集合
    **/
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray(); // 注意传入的集合不能为空,否则转数组时会发生NPE
        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;
        }
    } 
}

小结一下:

  • 从ArrayList集合继承和实现的关系来看:ArrayList是List集合的一个实现类。它实现了RandomAccess接口(随机访问),说明ArrayList的查询速度比增删操作快。它实现了Cloneable接口、Serializable接口,说明ArrayList类的实例可克隆,可序列化。
  • ArrayList集合在底层是通过维护一个对象数组Object[]来实现存储元素的,且元素是有序、可重复的存储;
  • ArrayList集合的构造器有三种传参形式:无参(对象数组为空)、指定容量(指定对象数组大小)、指定集合(集合转成对象数组)。

2、扩容机制

ArrayList集合通过add()方法添加元素,会触发自动扩容操作,当集合的容量不足时会进行自动扩容,源码分析如下:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     * 默认初始容量为10
    **/
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 数组最大容量
    **/
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     *  以add(E e)方法为例,扩容的关键步骤如下:
    **/
    public boolean add(E e) {
        // 1、元素添加到数组前先进行是否扩容判断("确保内部容量")
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 7、将该元素存放在数组上,size自加1标识ArrayList集合中元素添加了1个
        elementData[size++] = e;
        return true;
    }

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

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 2、若对象数组为空,返回默认初始容量和minCapacity中最大的一个;
        //      若不为空,返回minCapacity。而minCapacity = size+1
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++; //修改计数器
        // 3、当minCapacity超过对象数组的大小时,需要进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // 4、扩容后的对象数组大小为原大小的1.5倍
        int oldCapacity = elementData.length; 
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 5、扩容后对象数组大小出现以下两种情况,则重新赋值扩容后对象数组大小
        if (newCapacity - minCapacity < 0) 
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 6、将原对象数组按新容量大小拷贝成新的对象数组,实现扩容功能    
        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 :
            MAX_ARRAY_SIZE;
    }

    /**
     *  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++; //size自增1标识集合添加了一个新元素
    }
    
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     *  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;
    }
}

小结一下:

  • 向ArrayList集合添加新元素之前都要进行判断是否需要扩容,保证有足够的容量存储元素。初始容量默认为10,后续的每次扩容都是按1.5倍进行的(如第2次是15,第三次是22等.....),需要注意ArrayList是不可能无限扩容,新数组容量最大不能超过Integer.MAX_VALUE;
  • 若在ArrayList集合指定位置插入新元素,会发生数组的移动操作,当数组容量很大时,插入操作会是一个耗时且效率低的过程!!

3、遍历删除时的陷阱

ArrayList集合有两种删除方法:按索引位置删除的remove(int index)、按对象删除的remove(Object o),源码分析如下:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     *  remove(int index):根据索引位置删除元素,并返回删除的元素
    **/
    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;
    }
    
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     *  remove(int index):删除指定对象
    **/
    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;
    }
    
    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
    }  
}

小结一下:

  • 使用按索引位置删除元素的remove(int index)方法中,要特别注意数组越界检查,每移除一个元素时size会自减1,而index可能不会变,因此在fori遍历中要时刻保证index不能超过size;
  • 使用foreach遍历删除时会使用直接删除对象的remove(Object o)方法,foreach遍历是一颗语法糖 —— 本质上是通过迭代器Iterator实现遍历的,而在Iterator源码中的next()方法中存在 checkForComodification()方法,它会检查预期修改次数expectedModCount 和实际修改次数modCount 是否一致,不一致会报并发修改异常。再反观上面的remove(Object o)方法,每执行异常modCount 会自加1,因此进行下一次遍历时,modCount 肯定不等于expectedModCount了,导致异常发生!!因此不建议使用foreach遍历的方式删除ArrayList集合元素,但可以使用迭代器Iterator及其内部的remove()方法实现遍历删除ArrayList集合元素。

ArrayList集合的迭代器Iterator源码如下:

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(); //检查modCount是否符合expectedModCount
        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(); //检查modCount是否符合expectedModCount
    
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount; //重置expectedModCount 
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    
    final void checkForComodification() { // 检查并发修改异常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

在ArrayList集合中容易引发ConcurrentModificationException异常的方法有:(modCount变量存在的地方都有可能引发并发修改异常!!)

  • trimToSize()、clear()、add()、addAll()、remove()等方法用在遍历时;
  • Java8新增的方法:forEach()、removeIf()、sort()、replaceAll()等等。
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     *  修剪集合,去除预留元素的位置,当内存容量吃紧时会使用到它
    **/
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

    /**
     *  清空集合元素
    **/
    public void clear() {
        modCount++; //注意:避免引起ConcurrentModificationException
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

    /**
     *  遍历集合中的所有元素;
    **/
    @Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    /**
     *  删除所有符合条件的元素
    **/
    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);

        int removeCount = 0;
        final BitSet removeSet = new BitSet(size);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            @SuppressWarnings("unchecked")
            final E element = (E) elementData[i];
            if (filter.test(element)) {
                removeSet.set(i);
                removeCount++;
            }
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }

        ...;
        return anyToRemove;
    }

    /**
     *  按照指定转换规则替换集合中所有的元素
    **/
    @Override
    @SuppressWarnings("unchecked")
    public void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            elementData[i] = operator.apply((E) elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    /**
     *  集合元素按Comparator比较器规则进行排序
    **/
    @Override
    @SuppressWarnings("unchecked")
    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }
}

4、关于ArrayList集合增/删操作慢,查询/修改操作快的分析

元素在ArrayList集合中是按顺序进行存储的,若要在指定位置上插入元素(数组上最后一个元素除外),则会发生数组的移动操作;若删除元素(数组上最后一个元素除外)也会发生数组的移动操作,且最坏的情况是删除第一个元素导致数组所有的元素都要发生移动,因此插入和删除元素都是个耗时且效率低的过程,从上面的源码分析也可看到!!以remove()删除方法为例,用图示说明源码中的因删除导致的数组上其他的元素移动的操作:

 

而为什么查询和修改操作则快呢?还是看get()方法、set()方法的源码:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     * 获取指定位置元素
    **/
    public E get(int index) {
        rangeCheck(index); // 数组越界检查
        return elementData(index);
    }

    /**
     * 修改指定位置元素
    **/
    public E set(int index, E element) {
        rangeCheck(index); // 数组越界检查

        E oldValue = elementData(index);
        // 指定位置更新元素
        elementData[index] = element;
        return oldValue;
    }

    E elementData(int index) {
        return (E) elementData[index];
    }
}

从源码中可知:get()方法、set()方法的核心都是 —— elementData[index],也就是说基于数组下标去查询元素,加上实现RandomAccess接口,这种方式在数组上很快就能定位到元素,因此查询和修改的操作效率快于增删操作!!!!

5、并发安全问题

众所周知,ArrayList集合是一个非安全操作的集合类,但可以使用java.util下的Vector集合 或J.U.T包下的 CopyOnWriteArrayList集合来替换ArrayList集合,确保List集合在并发环境中能进行安全操作。然而,Java8开始,ArrayList类中新增了一个分割器Spliterator,它能将ArrayList集合按分割规则,分为多段,且多个线程可以并发的执行该集合。

分割器Spliterator接口的API说明:

  • boolean tryAdvance(Consumer<? super T> action); 

解释:对当前分割器Spliterator的单个元素执行给定的动作,同时返回 true,否则返回 false;若分割器Spliterator 具有 ORDER特性,则动作会以指定顺序执行。

  • default void forEachRemaining(Consumer<? super T> action) {do { } while (tryAdvance(action));} 

解释:线程中对当前分割器Spliterator的每个元素执行给定操作,或者动作抛出异常;若分割器Spliterator 具有 ORDER 特性,则动作会以指定顺序执行。默认的实现会重复调用 tryAdvance() ,直到返回 false。

  • Spliterator<T> trySplit();  

解释:如果这个分割器Spliterator可以被分割,返回一个新的分割器Spliterator,如果不能分割,则返回null;在理想情况下(没有遍历)会将元素平均分成两半,允许平衡并行计算,被分割的迭代器只有原来的一半,新的迭代器为另一半;很多背离了此理想状态的情况仍然能够保持高效率,而平衡型较差的分割将会导致并行效率的急剧下降。

  • long estimateSize();

解释:返回会被 forEachRemaining 操作的元素数量的估算值;如果一个分割器Spliterator 具有 SIZED 特性、并且未被遍历或分割,或者此分割器Spliterator 具有 SUBSIZED 特性、并且未被分割遍历,那么返回的一定是在一次完整遍历中遇到的所有元素数量的精确的值,否则,此估算值则会是不精确的,但是一定会随着 trySplit()的调用而越来越小。

  • int characteristics();

解释:返回该分割器Spliterator及其元素的一组特征值,如ORDERED、SIZED、SUBSIZED等。

  • default Comparator<? super T> getComparator() {throw new IllegalStateException();}

解释:如果分割器Spliterator的list是通过Comparator排序的,则返回Comparator;如果是自然排序的 ,则返回null。

  • public static final int ORDERED = 0x00000010;  public static final int SORTED = 0x00000004;  public static final int SIZED  = 0x00000040; public static final int SUBSIZED = 0x00004000;

解释:定义分割器Spliterator的一系列特征值,便于控制和优化分割器Spliterator的使用,如ORDERED表示元素是原始顺序排序的,SORTED表示元素按照某种规则排序的,SIZED表示遍历或分割之前estimesize()返回的一个有限的大小的值,SUBSIZED表示分割之后的调整的大小。

ArrayList集合的spliterator()方法的源码分析如下:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     * 在ArrayList中的元素上创建一个后期绑定和fail-fast的分割器Spliterator。
    **/
    @Override
    public Spliterator<E> spliterator() {
        return new ArrayListSpliterator<>(this, 0, -1, 0);
    }
    /**
     *  内部类ArrayListSpliterator:基于索引的二分分割,延迟初始化Spliterator
     **/
    static final class ArrayListSpliterator<E> implements Spliterator<E> {
        private final ArrayList<E> list;
        private int index; // current index, modified on advance/split
        private int fence; // -1 until used; then one past last index
        private int expectedModCount; // initialized when fence set

        /** Create new spliterator covering the given  range */
        ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
                             int expectedModCount) {
            // 底层对ArrayList进行拷贝后,操作拷贝的ArrayList,保证并发操作安全
            this.list = list; // OK if null unless traversed
            this.index = origin;
            this.fence = fence;
            this.expectedModCount = expectedModCount;
        }

        /** 首次使用时初始化栅栏大小 */
        private int getFence() {  
            int hi; // (a specialized variant appears in method forEach)
            ArrayList<E> lst;
            if ((hi = fence) < 0) {
                if ((lst = list) == null)
                    hi = fence = 0;
                else {
                    expectedModCount = lst.modCount;
                    hi = fence = lst.size;
                }
            }
            return hi;
        }

        /** 基于index的二分分割方法 */
        public ArrayListSpliterator<E> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid) ? null : // divide range in half unless too small
                new ArrayListSpliterator<E>(list, lo, index = mid,
                                            expectedModCount);
        }

        /** 单独循环方法:遍历当前分割器Spliterator的下一个元素 */
        public boolean tryAdvance(Consumer<? super E> action) {
            if (action == null)
                throw new NullPointerException();
            int hi = getFence(), i = index;
            if (i < hi) {
                index = i + 1;
                @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
                action.accept(e);
                if (list.modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                return true;
            }
            return false;
        }

        /** 批量循环方法:遍历当前分割器Spliterator的所有元素,支持并行执行,比forEach()的性能更好 */
        public void forEachRemaining(Consumer<? super E> action) {
            int i, hi, mc; // hoist accesses and checks from loop
            ArrayList<E> lst; Object[] a;
            if (action == null)
                throw new NullPointerException();
            if ((lst = list) != null && (a = lst.elementData) != null) {
                if ((hi = fence) < 0) {
                    mc = lst.modCount;
                    hi = lst.size;
                }
                else
                    mc = expectedModCount;
                if ((i = index) >= 0 && (index = hi) <= a.length) {
                    //相当于重复执行 tryAdvance()
                    for (; i < hi; ++i) {
                        @SuppressWarnings("unchecked") E e = (E) a[i];
                        action.accept(e);
                    }
                    if (lst.modCount == mc)
                        return;
                }
            }
            throw new ConcurrentModificationException();
        }

        /** 预估当前分割器Spliterator可使用的元素数量 */
        public long estimateSize() {
            return (long) (getFence() - index);
        }

        /** 当前分割器Spliterator的特征值 */
        public int characteristics() {
            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
        }
    }
}

小结一下:

ArrayList的spliterator()方法是支持并行和顺序处理元素的。多线程环境中,trySplit()方法能将原分割器Spliterator的元素接近半数的进行切割,即原Spliterator一半,新的Spliterator一半,以此类推还可以继续分割原Spliterator和新的Spliterator成另外新的分割器Spliterator;tryAdvance()和forEachRemaining()均能在各自的线程中遍历对应Spliterator里的元素;借助estimateSize() 和 characteristics() 可以更好的控制和优化当前Spliterator里的元素操作。

6、其他方法

ArrayList集合的其他方法:(有些方法这里不作详细分析了!)

  • public int size() {return size;}  // ArrayList集合大小
  • public boolean isEmpty() {return size == 0;}   // 集合判空
  • public boolean contains(Object o) {return indexOf(o) >= 0;}  // 集合中是否含有查找元素
  • public int indexOf(Object o) {...; return -1}  // 查找元素在集合中的位置(顺序查找)
  • public int lastIndexOf(Object o) {...; return -1}  //  查找元素在集合中的位置(倒序查找)
  • public Object clone() {...}  //  是一种浅克隆,不会将原集合的元素拷贝到新的集合
  • public Object[] toArray() {return Arrays.copyOf(elementData, size);} // ArrayList集合 转 对象数组
  • public T[] toArray(T[] a) { ...; System.arraycopy(elementData, 0, a, 0, size); ...; return a; }  // ArrayList集合 转 泛型数组,由运行时确定数组类型

重点分析下subList(int fromIndex, int toIndex)方法,它表达的含义是:从指定范围,截取生成新的子集合,有点像String中的substring(from, to)。

源码分析如下:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     * subList():原ArrayList集合截取生成新的List集合
    **/
    public List<E> subList(int fromIndex, int toIndex) {
        // 越界和逻辑检查
        subListRangeCheck(fromIndex, toIndex, size);
        // 调用内部类SubList
        return new SubList(this, 0, fromIndex, toIndex);
    }

    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > size)
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
    }

    /**
     * 内部类SubList,内部实现了自己的add/remove/get/set.../listIterator/spliterator等
    **/
    private class SubList extends AbstractList<E> implements RandomAccess {
        private final AbstractList<E> parent;
        private final int parentOffset; // fromIndex
        private final int offset; // offset + fromIndex
        int size; //截取后集合大小
        
        /**
         * SubList构造器,初始化成员属性
        **/
        SubList(AbstractList<E> parent,
                int offset, int fromIndex, int toIndex) {
            this.parent = parent;
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
        }

        public E get(int index) {
            rangeCheck(index);
            checkForComodification();
            return ArrayList.this.elementData(offset + index);
        }

        public void add(int index, E e) {
            rangeCheckForAdd(index);
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
        }

        ......;
        private void checkForComodification() {
            if (ArrayList.this.modCount != this.modCount)
                throw new ConcurrentModificationException();
        }
    }
}

生成新的子集合subList,可以通过内部类的get/set/add/remove...等方法操作子集合,注意 —— 子集合的相关操作是非线程安全的。

小结

至此,与ArrayList集合特点相关的源码基本都涉及到了,其中最重要的是自动扩容机制,遍历的陷阱,ArrayList集合增删慢/查询快原因,Java8新增的API,ArrayList集合安全操作问题等。不积硅步无以至千里,点滴付出终将有所收获,共同进步 ~


本文链接: http://www.dtmao.cc/news_show_550047.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?