ArrayList源码解析(jdk1.8)——思路篇(如何看源码)

时间:2020-6-27 作者:admin

前言:关于ArrayList相信大家都不陌生。而且大多数人应该都点开过它的源码浏览过。不过看到了什么,记住了什么,这是个值得深思的问题。博主今天写这篇文章的重点也不是解析其源码。更多的是想和大家分享一下看源码的一种方法以及一种思路。

源码解析第一步:简单了解其特性

ArrayList特点:

  1. ArrayList是有序的(放入顺序)
  2. ArrayList元素是不唯一的(可存放重复元素)

ArrayList简介:

  1. ArrayList底层是由数组实现的
  2. 他的容量是动态增长的
  3. 操作元素时查询效率高,增删效率低

源码解析第二步:提出自己的疑问,带着问题去读源码

  1. ArrayList是如何实现有序的
  2. ArrayList是如何扩容的
  3. ArrayList为何查询效率高,增删效率低
  4. ArrayList如何转换为数组

源码解析第三步:解读其继承与实现

现在让我们打开其源码,简单的读了读类注释,大体意思就是:它是一个集合框架,它是由数组实现的,它的容量可以自动扩充,它是线程不安全的以及迭代相关的一些说明;还有建议我们去看的一些类@see

/**
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see     Collection
 * @see     List
 * @see     LinkedList
 * @see     Vector
 * @since   1.2
 */
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

我们可以看到他继承了AbstractList抽象类,实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。

  • 继承了AbstractList,实现了ListAbstractList是个抽象类,抽象类一般用来提取一些共有的属性。简单看下他有add(),get(),set(),remove()等方法。
  • 实现了RandomAccess接口:点进去看了眼啥也没有!查了下RandomAccess 是一个标志接口,表明实现这个接口的 List 集合是支持快速随机访问的。
  • 实现了Cloneable 接口:点进去看了眼还是啥也没有!查了下实现这个接口需要覆盖clone()函数,表示能被克隆。源码如下:
public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }
  •  实现java.io.Serializable 接口:ArrayList支持序列化,能通过序列化去传输。

源码解析第四步:了解其成员变量

 private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;
  • DEFAULT_CAPACITY:默认初始容量,容量大小为10。
  • EMPTY_ELEMENTDATA:用于空实例的共享空数组实例(来源有道翻译)。
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA:用于默认大小的空实例的共享空数组实例。我们将其与EMPTY_ELEMENTDATA区分开来,以知道在添加第一个元素时容量需要增加多少。
  • elementData:保存数据的数组。
  • size:ArrayList 所包含的元素个数

源码解析第五步:阅读源码,寻找答案

  1. ArrayList是如何实现有序的
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

    解答:由add()方法可以看出新加元素时是将新元素追加到数组末尾,实际是对数组的赋值。

  2. ArrayList是如何扩容的

    private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            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);
        }

    解答:这段代码是ArrayList的核心扩容方法。由第二行可以看出(扩容后=扩容前+(扩容前>>1)),扩容1.5倍(位移一位除以2)。因为位运算的运行速度是极快的,我们可以得出结论之所以扩容1.5倍是为了快。

  3. ArrayList为何查询效率高,增删效率低

        public E get(int index) {
            rangeCheck(index);
    
            return elementData(index);
        }
    
        private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

    解答:上面是查询方法,不从算法的角度看应该也能看出它快吧。下面看看其增删的方法:

        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++;
        }
    
        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;
        }

    解答:以上是增加和删除的方法,都调用了System.arraycopy()方法。这个方法是实现数组自己复制自己的。

       
        
     //src:原数组;srcPos:元数组起始位置;
     //dest:目标数组;destPos:目标数组的起始位置;length:要复制的元素数量
     public static native void arraycopy(Object src,  int  srcPos,
                                            Object dest, int destPos,
                                            int length);

    简单点说就是把一节数组拷贝到目标数组;而这里的目标数组也是其自身;我们来模拟一下添加操作,看一下效果;

     public static void main(String[] args) {
            //初始数组
            Integer[] elementData = new Integer[]{1,3,5,7,9,11,13,15,17,19};
            //在下标为1的位置
            int index = 1;
            //添加元素2
            int element = 2;
            int size = elementData.length;
            System.out.println("初始容量:"+size);
            //模拟扩容1.5倍
            elementData = new Integer[]{1,3,5,7,9,11,13,15,17,19,null,null,null,null,null};
            System.arraycopy(elementData, index, elementData, index + 1,
                    size - index);
            elementData[index] = element;
            size++;
            System.out.println("添加完后的数组:"+Arrays.toString(elementData));
            System.out.println("添加完后容量:"+size);
        }
    
    输出结果:
    初始容量:10
    添加完后的数组:[1, 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, null, null, null, null]
    添加完后容量:11

    综上:添加移除时都需对数组进行复制,因此得出结论增删效率低(有兴趣的可以结合算法算一下)。

  4. ArrayList如何转换为数组

        public Object[] toArray() {
            return Arrays.copyOf(elementData, size);
        }

    这个无参的转换是使用了Arrays里的一个方法,具体实现如下:

        public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
            @SuppressWarnings("unchecked")
            T[] copy = ((Object)newType == (Object)Object[].class)
                ? (T[]) new Object[newLength]
                : (T[]) Array.newInstance(newType.getComponentType(), newLength);
            System.arraycopy(original, 0, copy, 0,
                             Math.min(original.length, newLength));
            return copy;
        }

    可以看出也是调用了System.arraycopy()方法,这里所用的目标数组copy就是一个新数组。

 源码解析第六步:总结与思考

  1. ArrayList创建时实际是一个容量为10的数组;
  2. 容量不够时扩容1.5倍,1.5倍扩充速度最快;
  3. 添加元素时都是追加在数组末尾,所以实现了有序,可以重复;
  4. 访问时直接通过下标,效率较高;
  5. 增删时需要将数组复制到新数组(尽管是自己复制自己);
  6. 转数组时其实是将现数组复制到新数组返回;

思考一:另外俩个没提到的成员变量参与了什么;

思考二:关于克隆的思考;

思考三:扩容的具体实现ensureCapacityInternal();

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:87074139@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。