阅读 6

ArrayList源码

ArrayList简介

ArrayList底层是数组,它内部会进行动态扩容。它继承了AbstractList,实现List接口。我们知道数组的添加元素的时间复杂度是O(n),查询元素的时间复杂度是O(1)。它是非线程安全的,并发情况下可以使用Vector或者CopyOnWriteArrayList。

ArrayList核心代码

    /* 默认初始化是10 */
    private static final int DEFAULT_CAPACITY = 10;

    /* 空数组 */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /* 用于默认大小空实例的共享空数组实例 */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /* 保存ArrayList数据的数组 */
    transient Object[] elementsData;

    /* ArrayList包含元素个数 */
    private int size;

    /* 构造函数,用户自己传的参数 */
    public ArrayList(int initialCapacity){
        if(initialCapacity > 0){
            this.elementsData = new Object[initialCapacity];
        }else if(initialCapacity == 0){
            this.elementsData = EMPTY_ELEMENTDATA;
        }else{
            throw new IllegalArgumentException("非法参数");
        }
    }

    /* 默认构造函数,初始化为0,当添加第一个元素的时候,扩容为10 */
    public ArrayList(){
        this.elementsData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA ;
    }

    /* 必要的话就要扩容,确保它能容纳元素的数量 */
    public void ensureCapacity(int minCapacity) {
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;

            if (minCapacity > minExpand) {
                ensureExplicitCapacity(minCapacity);
            }
    }
    /* 判断要不要扩容 */
    private void ensureExplicitCapacity(int minCapacity) {
            modCount++;

            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                /* 这里是扩容的代码,执行到这里就表示已经开始扩容了 */
                grow(minCapacity);
    }

    /* 数组的最大容量 */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /* 这里才是扩容的代码 */
     private void grow(int minCapacity) {
        // overflow-conscious code
         
        int oldCapacity = elementData.length;
        /* 将oldCapacity右移一位,相当于oldCapacity/2,位运算性能高,新的容量等于旧容量的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:
        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;
    }

   public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    /* 首次出现的位置,-1表示没有这个元素 */
    public boolean contains(Object o) {
       return indexOf(o) >= 0;
    }

    /* 返回元素首次出现在数组的索引值 */
    public int indexOf(Object o) {
        /* 这个对象为null的情况 */
        if (o == null) {
            for (int i = 0; i < size; i++)
                /* 记得null的情况是和基本数据类型判断的一样的 */
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    /* 返回元素最后一次出现的索引,这个方法和上一个方法很像 */
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
     }


    //对数组进行浅克隆,数组的本身没有被复制
    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);
        }
    }

    //返回一个包含此列表全部元素的数组,
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

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

    //返会指定索引的元素
    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;
    }

    //在数组的末尾添加元素,这个方法的时间复杂度为O(1)
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    //在指定的位置添加元素,将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++;
    }

    // 删除指定元素的值,将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;
    }

    //删除第一次出现的指定的元素
    public boolean remove(Object o) {
        //也考虑到了null的情况
        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
    }

    //清空此列表,将所有的元素置为null,将size置为0
    public void clear() {
        dCount++;
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

复制代码