阅读 634

源码系列(一)ArrayList 源码解析

1、ArrayList定义

ArrayList 是一个数组队列,相当于 动态数组。与Java中的数组相比,它的容量能动态增长。它继承于AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

ArrayList 继承了AbstractList,实现了List。它是一个数组队列,提供了相关的添加、删除、修改、遍历等功能。 ArrayList 实现了RandmoAccess接口,即提供了随机访问功能。RandmoAccess是java中用来被List实现,为List提供快速访问功能的。在ArrayList中,我们即可以通过元素的序号快速获取元素对象;这就是快速随机访问。稍后,我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率。

ArrayList 实现了Cloneable接口,即覆盖了函数clone(),能被克隆。

ArrayList 实现java.io.Serializable接口,这意味着ArrayList支持序列化,能通过序列化去传输。

和Vector不同,ArrayList中的操作不是线程安全的!所以,建议在单线程中才使用ArrayList,而在多线程中可以选择Vector或者CopyOnWriteArrayList。

2、ArrayList源码分析

ArrayList 有以下三种初始化的方法,此为1.8.0的源码,和之前的源码有所区别,在之前的源码中,默认情况下,初始容量为10,而在1.8的源码中,默认情况下则为

    /**
     * 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 = {};
复制代码
/**
     * 指定一个初始容量的构造方法
     *
     * @param  ArrayList的初始容量
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        //如果初始容量>0 ,则以指定的值为初始容量
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
      //如果指定的值为0,则直接赋值为空数组
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     *在此方法中则默认赋值一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空数组,此数组和EMPTY_ELEMENTDATA 区分开来,用来在添加第一个元素的时候,确定要扩容多少
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     *构造一个包含指定元素的list,这些元素的是按照Collection的迭代器返回的顺序排列的
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            //如果是非空的集合,则直接拷贝进入当前数组
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 如果传入的数据为空,则使用默认的空数组代替
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
复制代码

##3、增删改查

add方法

 /**
     * 直接在集合的末尾添加一个元素
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
复制代码

add方法分成了两步进行,

判断并扩充容量( ensureCapacityInternal(size + 1))+赋值( elementData[size++] = e)

从代码中可以看出,进行添加数据操作的时候,会先判断当前底层的数组是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA ,这个数组在构造方法 ArrayList() 中被赋值,用来区别于EMPTY_ELEMENTDATA ,在第一次进行数组操作的时候进行判断,从源码可以看出,会和默认的容量10进行比较,取较大的值,相对于之前直接 赋值为 10 的容量,个人觉得有两点优势:1、初始化的时候不会直接开辟空间 2、减少了一次扩容操作;效率上有一定的提升,设计还是比较巧妙的

private void ensureCapacityInternal(int minCapacity) {
       //如果调用的是 参数为空的构造方法,第一次操作的时候,就判断一下,
       //如果此时请求的容量大于默认初始容量10,取请求的容量,否则为默认容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //明确容量
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 如果请求的最小容量大于数组长度,则进行一次扩容,以储存所有数据
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

//增加容量,以确保能容纳mincapacity指定的元素
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //扩容,新的容量为原来的 1.5倍
        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:
        //将老数据copy到新的数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
复制代码

####add 的其他方法 从源码可以很明确的看出来,和add(E e)非常接近,仅在copy数据的时候有所差别

 public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //和add(E e)方法的区别仅这一行代码,扩容之后,将老数据在从指定位置(index)开始
      //之后的数据都向后移动一位,然后将index位置的赋值为 e
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

//和add 方法类似,区别在于将传入的集合转化成数组,然后整体位移copy
 public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        //扩容判断
        ensureCapacityInternal(size + numNew);  // Increments modCount
      //将传入的数据copy进入数组
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

复制代码

删除 remove方法

移出数据有 remove(int index) remove(Object o) ,两个方法本质都是根据index,直接利用数组的下标删除指定数据,同时会将数据进行位移,填补空缺

 public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) 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;
    }

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

复制代码

查找 get(int index)

ArrayList底层是数组,因此查找就非常简单,直接根据数组下标找到数据

public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }
复制代码

更改 set(int index, E element)

更改也是非常简单,直接根据数组下标更改数据

   public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }
复制代码

增删改查小结

从上面的源码可以很明显的看出,ArrayList的增删改查操作实质上就是对底层数组的操作,新增的时候,都需要对数组进行扩容+copy操作,删除也需要对数组进行copy,所以ArrayList的增加和删除效率会非常低,但是相对的,得利于底层的数组结果,在进行查找和更改操作的时候,可以根据下标直接进行操作,只有O(1)的复杂度,因此在查找需求比较频繁的操作中,可以使用ArrayList,极大的增加操作效率,但是在增删比较频繁的时候,就需要考虑其他的数据结构了; 同时,合理的使用ArrayList的构造方法,例如在初始化的时候,如果已经知道当前数据的大小,可以直接使用ArrayList(int initialCapacity) 构造方法指定初始容量,这样可以避免在添加数据的时候频繁扩容降低性能,同时也可以避免1.5倍扩容机制造成的空间浪费