【集合】ArrayList源码分析

ArrayList源码分析一、结构

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable

1）支持泛型
2）继承AbstractList，可以使用该抽象类的一些方法
3）List，支持List接口中的方法
4）RandomAccess，支持随机访问
5）Cloneable 支持对象克隆
6）Serializable 支持序列化功能

二、属性

 private static final long serialVersionUID = 8683452581122892189L;

    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; // non-private to simplify nested class access
    private int size;

1）DEFAULT_CAPACITY 默认初始容量=10
2）EMPTY_ELEMENTDATA 空数组
3）DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组，插入第一个元素时会初始化长度为10
4）elementData 保存元素的缓冲数组，transient表示不会被序列化
5）size 是集合中元素的个数

三、方法 1.构造方法

1）

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

根据给定的初始容量initialCapacity构建一个ArrayList
如果initialCapacity>0则直接直接创建容量为initialCapacity的ArrayList
如果initialCapacity=0则直接使用EMPTY_ELEMENTDATA空集合
如果initialCapacity<0，则出错。
2）

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

创建容量为10的ArrayList
3）

public ArrayList(Collection c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

将集合转换为ArrayList

2.常用实例方法

1）

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

添加任一类型元素到ArrayList末尾，长度加1；
2）

public int size() {
        return size;
    }

直接返回ArrayList的长度
3）

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

rangCheck判断是否越界，返回数组下标对应的元素
4）

public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

也是先判断是否越界，获取原来数组中的值，设置新值element，将旧值返回
5）

public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

modCount，来自其父类AbstractList，记录了ArrayList结构性变化的次数。方法作用是将数组中的元素全部置为null，将数组长度置为0
6）

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

在指定位置插入元素
7）

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

删除数组指定下标的元素
8）

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

删除指定元素
9）

   public boolean isEmpty() {
        return size == 0;
    }

判断是否为空
10）

public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

获取指定元素的下标
11）

    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

判断数组中是否含有指定元素
12）

 public Iterator iterator() {
        return new Itr();
    }

返回迭代器，可利用迭代器进行遍历

四、扩容原理分析

需要扩容是在增加元素的时候

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

这里的 ensureCapacityInternal(size + 1);方法就是判断是否需要扩容

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

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

实际的扩容逻辑在grow方法中

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//新的长度是原长度的1.5倍
        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相当于在没指定initialCapacity时就是会使用延迟分配对象数组空间，当第一次插入元素时才分配10（默认）个对象空间。假如有20个数据需要添加，那么会分别在第一次的时候，将ArrayList的容量变为10 (如下图一)；之后扩容会按照1.5倍增长。也就是当添加第11个数据的时候，Arraylist继续扩容变为10*1.5=15(如下图二)；当添加第16个数据时，继续扩容变为15 * 1.5 =22个(如下图四)。：

【集合】ArrayList源码分析

Java相关栏目本月热门文章