• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

集合框架源码学习之ArrayList

技术杂谈 勤劳的小蚂蚁 3个月前 (01-27) 51次浏览 已收录 0个评论 扫描二维码

目录:

0-0-1. 前言
0-0-2. 集合框架知识回顾
0-0-3. ArrayList简介
0-0-4. ArrayList核心源码
0-0-5. ArrayList源码剖析
0-0-6. ArrayList经典Demo

ArrayList简介:

  ArrayList 的底层是数组队列,相当于动态数组。与Java中的数组相比,它的容量能动态增长。在添加大量元素前,应用程序可以使用ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。它继承于AbstractList,实现了ListRandomAccessCloneablejava.io.Serializable这些接口。   在我们学数据结构的时候就知道了线性表的顺序存储,插入删除元素的时间复杂度为O(n),求表长以及增加元素,取第 i 元素的时间复杂度为O(1)   ArrayList 继承了AbstractList,实现了List。它是一个数组队列,提供了相关的添加、删除、修改、遍历等功能。   ArrayList 实现了RandmoAccess接口,即提供了随机访问功能。RandmoAccess是java中用来被List实现,为List提供快速访问功能的。在ArrayList中,我们即可以通过元素的序号快速获取元素对象,这就是快速随机访问。   ArrayList 实现了Cloneable接口,即覆盖了函数clone(),能被克隆。   ArrayList 实现java.io.Serializable接口,这意味着ArrayList支持序列化能通过序列化去传输。   和Vector不同,ArrayList中的操作不是线程安全的!所以,建议在单线程中才使用ArrayList,而在多线程中可以选择Vector或者CopyOnWriteArrayList。

ArrayList核心源码:

  1. package java.util;
  2. import java.util.function.Consumer;
  3. import java.util.function.Predicate;
  4. import java.util.function.UnaryOperator;
  5. publicclassArrayList<E>extendsAbstractList<E>
  6.        implementsList<E>,RandomAccess,Cloneable, java.io.Serializable
  7. {
  8.    privatestaticfinallong serialVersionUID =8683452581122892189L;
  9.    /**
  10.     * 默认初始容量大小
  11.     */
  12.    privatestaticfinalint DEFAULT_CAPACITY =10;
  13.    /**
  14.     * 空数组(用于空实例)。
  15.     */
  16.    privatestaticfinalObject[] EMPTY_ELEMENTDATA ={};
  17.     //用于默认大小空实例的共享空数组实例。
  18.      //我们把它从EMPTY_ELEMENTDATA数组中区分出来,以知道在添加第一个元素时容量需要增加多少。
  19.    privatestaticfinalObject[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA ={};
  20.    /**
  21.     * 保存ArrayList数据的数组
  22.     */
  23.    transientObject[] elementData;// non-private to simplify nested class access
  24.    /**
  25.     * ArrayList 所包含的元素个数
  26.     */
  27.    privateint size;
  28.    /**
  29.     * 带初始容量参数的构造函数。(用户自己指定容量)
  30.     */
  31.    publicArrayList(int initialCapacity){
  32.        if(initialCapacity >0){
  33.            //创建initialCapacity大小的数组
  34.            this.elementData =newObject[initialCapacity];
  35.        }elseif(initialCapacity ==0){
  36.            //创建空数组
  37.            this.elementData = EMPTY_ELEMENTDATA;
  38.        }else{
  39.            thrownewIllegalArgumentException("Illegal Capacity: "+
  40.                                               initialCapacity);
  41.        }
  42.    }
  43.    /**
  44.     *默认构造函数,其默认初始容量为10
  45.     */
  46.    publicArrayList(){
  47.        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  48.    }
  49.    /**
  50.     * 构造一个包含指定集合的元素的列表,按照它们由集合的迭代器返回的顺序。
  51.     */
  52.    publicArrayList(Collection<?extends E> c){
  53.        //
  54.        elementData = c.toArray();
  55.        //如果指定集合元素个数不为0
  56.        if((size = elementData.length)!=0){
  57.            // c.toArray 可能返回的不是Object类型的数组所以加上下面的语句用于判断,
  58.            //这里用到了反射里面的getClass()方法
  59.            if(elementData.getClass()!=Object[].class)
  60.                elementData =Arrays.copyOf(elementData, size,Object[].class);
  61.        }else{
  62.            // 用空数组代替
  63.            this.elementData = EMPTY_ELEMENTDATA;
  64.        }
  65.    }
  66.    /**
  67.     * 修改这个ArrayList实例的容量是列表的当前大小。 应用程序可以使用此操作来最小化ArrayList实例的存储。
  68.     */
  69.    publicvoid trimToSize(){
  70.        modCount++;
  71.        if(size < elementData.length){
  72.            elementData =(size ==0)
  73.              ? EMPTY_ELEMENTDATA
  74.              :Arrays.copyOf(elementData, size);
  75.        }
  76.    }
  77. //下面是ArrayList的扩容机制
  78. //ArrayList的扩容机制提高了性能,如果每次只扩充一个,
  79. //那么频繁的插入会导致频繁的拷贝,降低性能,而ArrayList的扩容机制避免了这种情况。
  80.    /**
  81.     * 如有必要,增加此ArrayList实例的容量,以确保它至少能容纳元素的数量
  82.     * @param   minCapacity   所需的最小容量
  83.     */
  84.    publicvoid ensureCapacity(int minCapacity){
  85.        int minExpand =(elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
  86.            // any size if not default element table
  87.            ?0
  88.            // larger than default for default empty table. It's already
  89.            // supposed to be at default size.
  90.            : DEFAULT_CAPACITY;
  91.        if(minCapacity > minExpand){
  92.            ensureExplicitCapacity(minCapacity);
  93.        }
  94.    }
  95.   //得到最小扩容量
  96.    privatevoid ensureCapacityInternal(int minCapacity){
  97.        if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
  98.              // 获取默认的容量和传入参数的较大值
  99.            minCapacity =Math.max(DEFAULT_CAPACITY, minCapacity);
  100.        }
  101.        ensureExplicitCapacity(minCapacity);
  102.    }
  103.  //判断是否需要扩容
  104.    privatevoid ensureExplicitCapacity(int minCapacity){
  105.        modCount++;
  106.        // overflow-conscious code
  107.        if(minCapacity - elementData.length >0)
  108.            //调用grow方法进行扩容,调用此方法代表已经开始扩容了
  109.            grow(minCapacity);
  110.    }
  111.    /**
  112.     * 要分配的最大数组大小
  113.     */
  114.    privatestaticfinalint MAX_ARRAY_SIZE =Integer.MAX_VALUE -8;
  115.    /**
  116.     * ArrayList扩容的核心方法。
  117.     */
  118.    privatevoid grow(int minCapacity){
  119.        // oldCapacity为旧容量,newCapacity为新容量
  120.        int oldCapacity = elementData.length;
  121.        //将oldCapacity 右移一位,其效果相当于oldCapacity /2,
  122.        //我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍,
  123.        int newCapacity = oldCapacity +(oldCapacity >>1);
  124.        //然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当作数组的新容量,
  125.        if(newCapacity - minCapacity <0)
  126.            newCapacity = minCapacity;
  127.        //再检查新容量是否超出了ArrayList所定义的最大容量,
  128.        //若超出了,则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE,
  129.        //如果minCapacity大于最大容量,则新容量则为ArrayList定义的最大容量,否则,新容量大小则为 minCapacity。
  130.        if(newCapacity - MAX_ARRAY_SIZE >0)
  131.            newCapacity = hugeCapacity(minCapacity);
  132.        // minCapacity is usually close to size, so this is a win:
  133.        elementData =Arrays.copyOf(elementData, newCapacity);
  134.    }
  135.    //比较minCapacity和 MAX_ARRAY_SIZE
  136.    privatestaticint hugeCapacity(int minCapacity){
  137.        if(minCapacity <0)// overflow
  138.            thrownewOutOfMemoryError();
  139.        return(minCapacity > MAX_ARRAY_SIZE)?
  140.            Integer.MAX_VALUE :
  141.            MAX_ARRAY_SIZE;
  142.    }
  143.    /**
  144.     *返回此列表中的元素数。
  145.     */
  146.    publicint size(){
  147.        return size;
  148.    }
  149.    /**
  150.     * 如果此列表不包含元素,则返回 true 。
  151.     */
  152.    publicboolean isEmpty(){
  153.        //注意=和==的区别
  154.        return size ==0;
  155.    }
  156.    /**
  157.     * 如果此列表包含指定的元素,则返回true 。
  158.     */
  159.    publicboolean contains(Object o){
  160.        //indexOf()方法:返回此列表中指定元素的首次出现的索引,如果此列表不包含此元素,则为-1
  161.        return indexOf(o)>=0;
  162.    }
  163.    /**
  164.     *返回此列表中指定元素的首次出现的索引,如果此列表不包含此元素,则为-1
  165.     */
  166.    publicint indexOf(Object o){
  167.        if(o ==null){
  168.            for(int i =0; i < size; i++)
  169.                if(elementData[i]==null)
  170.                    return i;
  171.        }else{
  172.            for(int i =0; i < size; i++)
  173.                //equals()方法比较
  174.                if(o.equals(elementData[i]))
  175.                    return i;
  176.        }
  177.        return-1;
  178.    }
  179.    /**
  180.     * 返回此列表中指定元素的最后一次出现的索引,如果此列表不包含元素,则返回-1。.
  181.     */
  182.    publicint lastIndexOf(Object o){
  183.        if(o ==null){
  184.            for(int i = size-1; i >=0; i--)
  185.                if(elementData[i]==null)
  186.                    return i;
  187.        }else{
  188.            for(int i = size-1; i >=0; i--)
  189.                if(o.equals(elementData[i]))
  190.                    return i;
  191.        }
  192.        return-1;
  193.    }
  194.    /**
  195.     * 返回此ArrayList实例的浅拷贝。 (元素本身不被复制。)
  196.     */
  197.    publicObject clone(){
  198.        try{
  199.            ArrayList<?> v =(ArrayList<?>)super.clone();
  200.            //Arrays.copyOf功能是实现数组的复制,返回复制后的数组。参数是被复制的数组和复制的长度
  201.            v.elementData =Arrays.copyOf(elementData, size);
  202.            v.modCount =0;
  203.            return v;
  204.        }catch(CloneNotSupportedException e){
  205.            // 这不应该发生,因为我们是可以克隆的
  206.            thrownewInternalError(e);
  207.        }
  208.    }
  209.    /**
  210.     *以正确的顺序(从第一个到最后一个元素)返回一个包含此列表中所有元素的数组。
  211.     *返回的数组将是“安全的”,因为该列表不保留对它的引用。 (换句话说,这个方法必须分配一个新的数组)。
  212.     *因此,调用者可以自由地修改返回的数组。 此方法充当基于阵列和基于集合的API之间的桥梁。
  213.     */
  214.    publicObject[] toArray(){
  215.        returnArrays.copyOf(elementData, size);
  216.    }
  217.    /**
  218.     * 以正确的顺序返回一个包含此列表中所有元素的数组(从第一个到最后一个元素);
  219.     *返回的数组的运行时类型是指定数组的运行时类型。 如果列表适合指定的数组,则返回其中。
  220.     *否则,将为指定数组的运行时类型和此列表的大小分配一个新数组。
  221.     *如果列表适用于指定的数组,其余空间(即数组的列表数量多于此元素),则紧跟在集合结束后的数组中的元素设置为null 。
  222.     *(这仅在调用者知道列表不包含任何空元素的情况下才能确定列表的长度。)
  223.     */
  224.    @SuppressWarnings("unchecked")
  225.    public<T> T[] toArray(T[] a){
  226.        if(a.length < size)
  227.            // 新建一个运行时类型的数组,但是ArrayList数组的内容
  228.            return(T[])Arrays.copyOf(elementData, size, a.getClass());
  229.            //调用System提供的arraycopy()方法实现数组之间的复制
  230.        System.arraycopy(elementData,0, a,0, size);
  231.        if(a.length > size)
  232.            a[size]=null;
  233.        return a;
  234.    }
  235.    // Positional Access Operations
  236.    @SuppressWarnings("unchecked")
  237.    E elementData(int index){
  238.        return(E) elementData[index];
  239.    }
  240.    /**
  241.     * 返回此列表中指定位置的元素。
  242.     */
  243.    public E get(int index){
  244.        rangeCheck(index);
  245.        return elementData(index);
  246.    }
  247.    /**
  248.     * 用指定的元素替换此列表中指定位置的元素。
  249.     */
  250.    public E set(int index, E element){
  251.        //对index进行界限检查
  252.        rangeCheck(index);
  253.        E oldValue = elementData(index);
  254.        elementData[index]= element;
  255.        //返回原来在这个位置的元素
  256.        return oldValue;
  257.    }
  258.    /**
  259.     * 将指定的元素追加到此列表的末尾。
  260.     */
  261.    publicboolean add(E e){
  262.        ensureCapacityInternal(size +1);  // Increments modCount!!
  263.        //这里看到ArrayList添加元素的实质就相当于为数组赋值
  264.        elementData[size++]= e;
  265.        returntrue;
  266.    }
  267.    /**
  268.     * 在此列表中的指定位置插入指定的元素。
  269.     *先调用 rangeCheckForAdd 对index进行界限检查;然后调用 ensureCapacityInternal 方法保证capacity足够大;
  270.     *再将从index开始之后的所有成员后移一个位置;将element插入index位置;最后size加1。
  271.     */
  272.    publicvoid add(int index, E element){
  273.        rangeCheckForAdd(index);
  274.        ensureCapacityInternal(size +1);  // Increments modCount!!
  275.        //arraycopy()这个实现数组之间复制的方法一定要看一下,下面就用到了arraycopy()方法实现数组自己复制自己
  276.        System.arraycopy(elementData, index, elementData, index +1,
  277.                         size - index);
  278.        elementData[index]= element;
  279.        size++;
  280.    }
  281.    /**
  282.     * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧(从其索引中减去一个元素)。
  283.     */
  284.    public E remove(int index){
  285.        rangeCheck(index);
  286.        modCount++;
  287.        E oldValue = elementData(index);
  288.        int numMoved = size - index -1;
  289.        if(numMoved >0)
  290.            System.arraycopy(elementData, index+1, elementData, index,
  291.                             numMoved);
  292.        elementData[--size]=null;// clear to let GC do its work
  293.      //从列表中删除的元素
  294.        return oldValue;
  295.    }
  296.    /**
  297.     * 从列表中删除指定元素的第一个出现(如果存在)。 如果列表不包含该元素,则它不会更改。
  298.     *返回true,如果此列表包含指定的元素
  299.     */
  300.    publicboolean remove(Object o){
  301.        if(o ==null){
  302.            for(int index =0; index < size; index++)
  303.                if(elementData[index]==null){
  304.                    fastRemove(index);
  305.                    returntrue;
  306.                }
  307.        }else{
  308.            for(int index =0; index < size; index++)
  309.                if(o.equals(elementData[index])){
  310.                    fastRemove(index);
  311.                    returntrue;
  312.                }
  313.        }
  314.        returnfalse;
  315.    }
  316.    /*
  317.     * Private remove method that skips bounds checking and does not
  318.     * return the value removed.
  319.     */
  320.    privatevoid fastRemove(int index){
  321.        modCount++;
  322.        int numMoved = size - index -1;
  323.        if(numMoved >0)
  324.            System.arraycopy(elementData, index+1, elementData, index,
  325.                             numMoved);
  326.        elementData[--size]=null;// clear to let GC do its work
  327.    }
  328.    /**
  329.     * 从列表中删除所有元素。
  330.     */
  331.    publicvoid clear(){
  332.        modCount++;
  333.        // 把数组中所有的元素的值设为null
  334.        for(int i =0; i < size; i++)
  335.            elementData[i]=null;
  336.        size =0;
  337.    }
  338.    /**
  339.     * 按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
  340.     */
  341.    publicboolean addAll(Collection<?extends E> c){
  342.        Object[] a = c.toArray();
  343.        int numNew = a.length;
  344.        ensureCapacityInternal(size + numNew);  // Increments modCount
  345.        System.arraycopy(a,0, elementData, size, numNew);
  346.        size += numNew;
  347.        return numNew !=0;
  348.    }
  349.    /**
  350.     * 将指定集合中的所有元素插入到此列表中,从指定的位置开始。
  351.     */
  352.    publicboolean addAll(int index,Collection<?extends E> c){
  353.        rangeCheckForAdd(index);
  354.        Object[] a = c.toArray();
  355.        int numNew = a.length;
  356.        ensureCapacityInternal(size + numNew);  // Increments modCount
  357.        int numMoved = size - index;
  358.        if(numMoved >0)
  359.            System.arraycopy(elementData, index, elementData, index + numNew,
  360.                             numMoved);
  361.        System.arraycopy(a,0, elementData, index, numNew);
  362.        size += numNew;
  363.        return numNew !=0;
  364.    }
  365.    /**
  366.     * 从此列表中删除所有索引为fromIndex (含)和toIndex之间的元素。
  367.     *将任何后续元素移动到左侧(减少其索引)。
  368.     */
  369.    protectedvoid removeRange(int fromIndex,int toIndex){
  370.        modCount++;
  371.        int numMoved = size - toIndex;
  372.        System.arraycopy(elementData, toIndex, elementData, fromIndex,
  373.                         numMoved);
  374.        // clear to let GC do its work
  375.        int newSize = size -(toIndex-fromIndex);
  376.        for(int i = newSize; i < size; i++){
  377.            elementData[i]=null;
  378.        }
  379.        size = newSize;
  380.    }
  381.    /**
  382.     * 检查给定的索引是否在范围内。
  383.     */
  384.    privatevoid rangeCheck(int index){
  385.        if(index >= size)
  386.            thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));
  387.    }
  388.    /**
  389.     * add和addAll使用的rangeCheck的一个版本
  390.     */
  391.    privatevoid rangeCheckForAdd(int index){
  392.        if(index > size || index <0)
  393.            thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));
  394.    }
  395.    /**
  396.     * 返回IndexOutOfBoundsException细节信息
  397.     */
  398.    privateString outOfBoundsMsg(int index){
  399.        return"Index: "+index+", Size: "+size;
  400.    }
  401.    /**
  402.     * 从此列表中删除指定集合中包含的所有元素。
  403.     */
  404.    publicboolean removeAll(Collection<?> c){
  405.        Objects.requireNonNull(c);
  406.        //如果此列表被修改则返回true
  407.        return batchRemove(c,false);
  408.    }
  409.    /**
  410.     * 仅保留此列表中包含在指定集合中的元素。
  411.     *换句话说,从此列表中删除其中不包含在指定集合中的所有元素。
  412.     */
  413.    publicboolean retainAll(Collection<?> c){
  414.        Objects.requireNonNull(c);
  415.        return batchRemove(c,true);
  416.    }
  417.    /**
  418.     * 从列表中的指定位置开始,返回列表中的元素(按正确顺序)的列表迭代器。
  419.     *指定的索引表示初始调用将返回的第一个元素为next 。 初始调用previous将返回指定索引减1的元素。
  420.     *返回的列表迭代器是fail-fast 。
  421.     */
  422.    publicListIterator<E> listIterator(int index){
  423.        if(index <0|| index > size)
  424.            thrownewIndexOutOfBoundsException("Index: "+index);
  425.        returnnewListItr(index);
  426.    }
  427.    /**
  428.     *返回列表中的列表迭代器(按适当的顺序)。
  429.     *返回的列表迭代器是fail-fast 。
  430.     */
  431.    publicListIterator<E> listIterator(){
  432.        returnnewListItr(0);
  433.    }
  434.    /**
  435.     *以正确的顺序返回该列表中的元素的迭代器。
  436.     *返回的迭代器是fail-fast 。
  437.     */
  438.    publicIterator<E> iterator(){
  439.        returnnewItr();
  440.    }

ArrayList源码分析:

System.arraycopy()和Arrays.copyOf()方法
  通过上面源码我们发现这两个实现数组复制的方法被广泛使用而且很多地方都特别巧妙。比如下面add(int index, E element)方法就很巧妙的用到了arraycopy()方法让数组自己复制自己实现让index开始之后的所有成员后移一个位置:
  1.    /**
  2.     * 在此列表中的指定位置插入指定的元素。
  3.     *先调用 rangeCheckForAdd 对index进行界限检查;然后调用 ensureCapacityInternal 方法保证capacity足够大;
  4.     *再将从index开始之后的所有成员后移一个位置;将element插入index位置;最后size加1。
  5.     */
  6.    publicvoid add(int index, E element){
  7.        rangeCheckForAdd(index);
  8.        ensureCapacityInternal(size +1);  // Increments modCount!!
  9.        //arraycopy()方法实现数组自己复制自己
  10.        //elementData:源数组;index:源数组中的起始位置;elementData:目标数组;index + 1:目标数组中的起始位置; size - index:要复制的数组元素的数量;
  11.        System.arraycopy(elementData, index, elementData, index +1, size - index);
  12.        elementData[index]= element;
  13.        size++;
  14.    }
又如toArray()方法中用到了copyOf()方法
  1.    /**
  2.     *以正确的顺序(从第一个到最后一个元素)返回一个包含此列表中所有元素的数组。
  3.     *返回的数组将是“安全的”,因为该列表不保留对它的引用。 (换句话说,这个方法必须分配一个新的数组)。
  4.     *因此,调用者可以自由地修改返回的数组。 此方法充当基于阵列和基于集合的API之间的桥梁。
  5.     */
  6.    publicObject[] toArray(){
  7.    //elementData:要复制的数组;size:要复制的长度
  8.        returnArrays.copyOf(elementData, size);
  9.    }
两者联系与区别:
联系: 看两者源代码可以发现copyOf()内部调用了System.arraycopy()方法 区别: 1,arraycopy()需要目标数组,将原数组拷贝到你自己定义的数组里,而且可以选择拷贝的起点和长度以及放入新数组中的位置 2,copyOf()是系统自动在内部新建一个数组,并返回该数组。

ArrayList核心扩容技术

  1. /**
  2.     * ArrayList扩容的核心方法。
  3.     */
  4.    privatevoid grow(int minCapacity){
  5.        // oldCapacity为旧容量,newCapacity为新容量
  6.        int oldCapacity = elementData.length;
  7.        //将oldCapacity 右移一位,其效果相当于oldCapacity /2,
  8.        //我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍,
  9.        int newCapacity = oldCapacity +(oldCapacity >>1);
  10.        //然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当作数组的新容量,